To calculate the `between centrality` [wiki def][1]:
$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?


  [1]: http://en.wikipedia.org/wiki/Betweenness_centrality