The fastest existing method for the exact BC computation, BA,
requires \(\Theta (nm)\)  operations for unweighted graphs
and \(\Theta (nm+n^{2}\log n)\)  for graphs with positive edge weights [1]}.
The algorithm computes for every node \(s\in V\) 
a slightly-modified version of a single-source shortest-path tree
(SSSP tree), producing for each \(s\)  the directed acyclic
graph (DAG) of all shortest paths starting at \(s\) . Exploiting
the information contained in the DAGs, the algorithm computes the dependency
\(\delta _{s}(v)\)  for each node \(v\) , that is
the sum over all nodes \(t\)  of the fraction of shortest paths between
\(s\)  and \(t\)  that \(v\)  is internal to. The betweenness
of each node \(v\)  is simply the sum over all sources \(s\in V\) 
of the dependencies \(\delta _{s}(v)\) . Therefore, we can
see the dependency \(\delta _{s}(v)\)  as a contribution
that \(s\)  gives to the computation of \(c_{B}(v)\) .
Based on this concept, some algorithms for an
approximation of BC have been developed.
Brandes and Pich [2]} propose to
approximate \(c_{B}(v)\)  by extrapolating it from the contributions
of a subset of source nodes, also
called pivots. Selecting the pivots uniformly at random, the
approximation can be proven to be an unbiased
estimator for \(c_{B}(v)\)  (i.e.  its expectation is equal to \(c_{B}(v)\) ).
In a subsequent work, Geisberger et al.  [3]}
notice that this can produce an overestimation of BC scores
of nodes that happen to be close to the sampled pivots. To limit
this bias, they introduce
a scaling function which gives less importance to
contributions from pivots that are close to the node.
Bader et al.  [4]} approximate
the BC of a specific node only, based on
an adaptive sampling technique that reduces the number of pivots for nodes with high centrality.
Different from the previous approaches is the approximation algorithm
of Riondato and Kornaropoulos [5]},
which samples a single random shortest path at each iteration.
This approach allows theoretical guarantees on the quality of their approximation:
For any two constants \(\epsilon ,\delta \in (0,1)\) , a number of samples
can be defined such that the error on the approximated values is at
most \(\epsilon \)  with probability at least \(1-\delta \) .
Because of this guarantee, we use this algorithm as a
building block of our new approach and refer to it as RK.
