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?
 A: 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
A: 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.
