To calculate the `between centrality` [wiki def](http://en.wikipedia.org/wiki/Betweenness_centrality):
$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?



Methods to approximate the betweenness centrality on large networks
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)](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.68.9850)


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](http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=06406259)


