5
$\begingroup$

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?

Improve this question
$\endgroup$
8
  • 2
    $\begingroup$ 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? $\endgroup$
    – fedja
    Commented Sep 1, 2013 at 12:27
  • $\begingroup$ @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? $\endgroup$
    – Vass
    Commented Sep 1, 2013 at 20:12
  • $\begingroup$ Do the graphs have any special structure (low vertex degree, small diameter, whatever) that can be relied upon? $\endgroup$
    – fedja
    Commented Sep 1, 2013 at 20:25
  • $\begingroup$ @fedja, they arise from twitter, so large hubs. They vary. Usually a very steep degree distribution decay $\endgroup$
    – Vass
    Commented Sep 1, 2013 at 20:28
  • $\begingroup$ have you tried stats.stackexchange.com ? $\endgroup$
    – john mangual
    Commented Sep 2, 2013 at 0:33

2 Answers 2

Reset to default
5
$\begingroup$

Stochastic approximation methods for betweenness centrality have been studied by many people. A good reference is "Centrality estimation in large networks" by Brandes and Pich (2007)

For large sparse networks, exact and approximation algorithms can benefit significantly from the exploitation of structural features of the network. Decomposition into bi-connected components, for example, or the collapsing of groups of structurally equivalent vertices, parallel edges, etc. These techniques don't change the overall complexity of the problem, can speed the calculations dramatically. Details can be found in this paper

Improve this answer
$\endgroup$
3
$\begingroup$

Assuming low degree (which arises much of the time), you can just pick a node at random, do a breadth first search to get a collection of shortest paths starting at that node and compute the centralities for those paths. Repeat this k times and take the average to get an O(kE) algorithm with an O(k^{-1/2}) error (although the constant here could be problematic in extreme cases, but I think that's unlikely and perhaps not possible).

If you did this for every node O(n^2) then the answer is exact, while the sampling has a k^{-1/2} error, so a fixed k should be fine.

Improve this answer
$\endgroup$
1
  • $\begingroup$ How do you show that the error is O(k^(-1/2))? Also, what happens if the degrees obey a power law, i.e., a few nodes have very high degree, but most nodes have low degree? $\endgroup$
    – Mathias Rav
    Commented Aug 1, 2016 at 13:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .