Skip to main content
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 ...
Yuval Filmus's user avatar
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$ ...
j_random_hacker's user avatar
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, ...
Matthieu Latapy's user avatar
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 ...
Matthieu Latapy's user avatar
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 ...
John L.'s user avatar
  • 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 ...
Iago Carvalho's user avatar
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.'s user avatar
  • 162k
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....
Matthieu Latapy's user avatar
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.'s user avatar
  • 162k
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 ...
j_random_hacker's user avatar
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 ...
maxdan94's user avatar
  • 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 ...
Jörg W Mittag's user avatar
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 ...
codeR's user avatar
  • 1,455
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 ...
Effie's user avatar
  • 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 ...
Demotte's user avatar
  • 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 ...
sligocki's user avatar
  • 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 ...
George Vidalakis's user avatar
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 ...
Vincenzo's user avatar
  • 3,317
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 ...
Yuval Filmus's user avatar
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 ...
Matthieu Latapy's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible