# Tag Info

### 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, ...
• 278k

### 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 ...
• 261

### 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
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 ...
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 ...
• 39k

### 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 ...
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 ...
• 1,944

### 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 ...
• 161k
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....
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 ...
• 278k

### 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,479
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$...
• 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 ...
• 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 ...
• 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 ...
• 278k

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