In this section we briefly describe the algorithm by Riondato and Kornaropoulos (RK) [1]},
the foundation for our incremental approach. The idea of RK is to sample a set \(S =\lbrace p_{(1)},...,p_{(r)}\rbrace \)  of \(r\)  shortest paths between randomly sampled source-target pairs \((s, t)\) .
Then, RK computes the approximated
betweenness centrality \(\tilde{c}_B(v)\)  of a node \(v\)  as the
fraction of sampled paths \(p_{(k)}\in S\)  that \(v\)  is internal
to, by adding \(\frac{1}{r}\)  to the node's score for each of these paths.
Figure REF  illustrates an example where the sampling of two shortest paths leads to \(\frac{2}{r}\)  and \(\frac{1}{r}\)  being added to the score of \(u\)  and \(v\) , respectively.
Each possible shortest path \(p_{st}\)  has the following probability of being sampled in each of the \(r\)  iterations:
\(\pi _{G}(p_{st})=\frac{1}{n(n-1)}\cdot \frac{1}{\sigma _{st}}\) 
