5
votes
Is there a name for the problem of turning a bipartite graph into two graphs?
You're (basically) computing the square of the graph, in which two vertices are adjacent if there is a path of length 2 (or at most 2, depending on the definition) connecting them. The square will ...
- 278k
4
votes
Accepted
Removing edges from a fully connected weighted graph
This is NP-hard by reduction from Set Cover. The problem remains NP-hard even if edge weights are restricted to $\{1, 3\}$.
In the Set Cover problem, we are given a ground set $U$ containing $m$ ...
- 5,489
4
votes
Partitioning a graph into subgraphs with overlapping nodes
I never heard of any algorithm with the constraint of having an overlap between communities larger than a given threshold (4 here).
But I suggest the following: turn your graph into its line graph, ...
- 653
3
votes
Accepted
Efficient Network Clustering Algorithm for Million Node Networks
The Louvain algorithm does just this, and it easily handles graphs of this size. It is implemented in most, if not all, graph libraries. In particular, Networkit provides a fast parallel ...
- 653
3
votes
Accepted
Correctness of the Betweenness centrality formula
Suppose we want to quantify the extent to which $v$ is between $s$ and $t$. There could be a few ways.
One way to describe that extent is the probability of passing through $v$ if we want to reach ...
- 39.1k
3
votes
Correctness of the Betweenness centrality formula
However it doesn't seem to me that the formula calculates what is defined.
The formula is right. The betweenness centrality is a value in an interval $[0, \ldots, 1]$. Thus, if the betweenness ...
- 239
2
votes
Representing a network with two types of connections: A fishing application
Sure, of course. You can define a matrix to contain whatever numbers you want it to contain. There's nothing that prevents you. The real question is whether the result has the properties you want ...
D.W.♦
- 164k
2
votes
Accepted
(Formal) Proofs of Node Centrality Properties
There are many papers dealing with the algorithmic aspects of these measures, with formal proofs, complexity analysis, and so on. However, I understand that this is not really what you are looking for....
- 653
2
votes
Accepted
How to find the shortest route between (0,0) and (4,4) in a 5x5 matrix, given one horizontal or vertical translation per step
You're asking how to compute the shortest path between two vertices in a graph. Solution: use an algorithm for computing shortest paths. In your case, BFS would be a good choice. There's no need ...
D.W.♦
- 164k
2
votes
Algorithm for finding "mean center" of unweighted graph
Another heuristic idea: Find a long shortest path, and pick the vertex halfway along it.
Pick a vertex and run BFS from it. For some small $k$, take the $k$ furthest vertices from the original vertex ...
- 5,489
2
votes
Partitioning a graph into subgraphs with overlapping nodes
Depends what you want to do with the "partition with overlapping nodes".
There is this survey about overlapping community detection: https://dl.acm.org/doi/10.1145/2501654.2501657
The ...
- 133
2
votes
Accepted
What's wrong in this network topology?
On a quick overview, I can find the following problems:
The IP address 192.168.10.32 for interface eth1 of the router is the ...
- 6,270
1
vote
BFS on directed graph with disjointed edges?
Assuming you want the following:
Given a graph $G=(V,E)$ and a set of nodes $N \subseteq V$, find a tree $T$ that spans over all nodes in $N$. Here, $T$ is a spanning tree of the induced subgraph of a ...
- 1,934
1
vote
Path Through Graph That Minimizes Node Attributes
Produce graph H by replacing each node $v_i$ with two nodes $I_i$ and $O_i$ and an arc $(I_i,O_i)$ between them, where input arcs to original node $v_i$ be as input arcs to new node $I_i$ and output ...
1
vote
Accepted
Go back n on server side
assuming that the client only sends and the server only receives and acks:
(1) the server may or may not contain a buffer. Go-Back-N will function perfectly, if there is a buffer for only one packet ...
- 199
1
vote
Accepted
Source and Destination IP of TCP connection
If you consider the format of the TCP-IP datagram.
Source Address: The 32-bit IP address of the originator of the datagram. Note that even though intermediate devices such as routers may handle the ...
- 126
1
vote
Algorithm for finding "mean center" of unweighted graph
After a bit of reading through literature I've come upon "closeness centrality" which is the reciprocal of what I'm calculating (mean distance, which they call "farness" in the article). But I still ...
- 213
1
vote
Accepted
PERT Chart exercise - is there enough information to solve?
I don't know if there is a standard method to identify which activity matches which arrow, but I was able to complete your PERT chart by examining a few possible cases, while filling the chart from ...
- 371
1
vote
Analyzing the railways network
Certainly it is possible. For example, in the following study the Indian railway network was analyzed.
Small-world properties of the Indian railway network.
Parongama Sen, Subinay Dasgupta, Arnab ...
- 3,424
1
vote
Representing a network with two types of connections: A fishing application
Assuming for the moment that the two types of person are distinct, your graph is (directed) bipartite, so it makes more sense to store it as a matrix whose rows correspond to people with fishing ...
- 278k
1
vote
Sample a scale free subnet from random network
In order to do this, you need high degree nodes in your initial network: since you do not add anything, degree may only decrease, and you want high degree nodes in the end.
Now, assume your initial ...
- 653
Only top scored, non community-wiki answers of a minimum length are eligible