Skip to main content
17 votes

social network graph problem

This is known as majority dynamics. Usually the assumption is that all nodes adopt the majority opinion simultaneously, and this is known as the synchronous model. For an arbitrary tie-breaking rule, ...
Yuval Filmus's user avatar
6 votes

social network graph problem

This is not generally achievable. Consider a blue and a red triangle connected with a single edge. Whatever node you select will keep its previous colour. In general, if you have large monochromatic ...
filipos's user avatar
  • 261
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
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
  • 39k
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
3 votes
Accepted

Densely connected non overlapping subgraph

If you want to find cliques, or quasi-cliques, don't expect non-overlapping communities, as their definitions imply that there might be overlap between clusters. When it comes to community detection ...
orezvani's user avatar
  • 1,944
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
  • 161k
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

Sampling in large graph using simple random walk

While the algorithm doesn't know the graph, when you are analyzing the performance of the algorithm on a graph, you do know the graph. For a similar example, take the egg dropping puzzle. In this ...
Yuval Filmus's user avatar
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
1 vote

Mutual Friends in a Network?

This is a possible way you can describe it: Define $P$ to be the set of all possible people. Then, define the relation $F\subseteq P\times P$ such that $xFy$ (or equivalently, $(x,y)\in F$) only if $x$...
nir shahar's user avatar
  • 11.6k
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

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

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