# Methods to approximate the betweenness centrality on large networks

To calculate the between centrality wiki def: $g(v) = \sum_{s\neq v \neq t} \frac{\sigma_{st}(v)}{\sigma_{st}}$ of a node in a graph/network;$\sigma_{st}$ is the total number of shortest paths from node to node and the $\sigma_{st}(v)$ are the paths including the node of concern. that is very computationally intensive due to the large number of shortest paths that must be calculated. Is there a stochastic method to approximate it? Can non-reversing truncated random walkers traverse the graph (before being ergodic) to sample the hit count for when the node $v$ is encountered? In a way it is a monte carlo approach where the paths are sampled from random walk paths taken.

are there any references for this as well?

• The little problem is that adding a single edge may change the quantity quite drastically: imagine two copies of a complete graph $K_n$ joined by an edge. If $v$ is on that edge, $g(v)\approx 2n^2$. However, adding one more edge of the same type brings it down to about $n^2$. The random walks (backtracking or not) have very little chance to notice that extra edge: about $L/n^2$ where $L$ is the walk length, so you cannot do it in time much less than $n^2$. However in this time you can do a lot in a deterministic way too. What running time (in terms of graph complexity) are you aiming at? Sep 1 '13 at 12:27
• @fedja, I was hoping for something linear in complexity. I agree with your arguments that in general there are no guarantees with a stochastic approach. But that is the same issue with all sampling approaches. What if I check for consistency of the results with individual runs? Like perform convergence diagnostics on the centrality computed?
– Vass
Sep 1 '13 at 20:12
• Do the graphs have any special structure (low vertex degree, small diameter, whatever) that can be relied upon? Sep 1 '13 at 20:25
• @fedja, they arise from twitter, so large hubs. They vary. Usually a very steep degree distribution decay
– Vass
Sep 1 '13 at 20:28
• have you tried stats.stackexchange.com ? Sep 2 '13 at 0:33