# Guidelines for Experimental Algorithmics:
## 3 Use Case
### Overview of the KADABRA Algorithm  
The KADABRA algorithm approximates the betweenness centrality of (un)directed graphs within a given absolute error of at most \(\epsilon\) with probability \((1-\delta)\)[16]. The main rationale of the algorithm is to iteratively select two nodes \(s\), \(t\) uniformly at random and then sample a shortest path \(\pi\) from \(s\) to \(t\) (again uniformly at random). This leads to a sequence of randomly selected shortest paths \(\pi_{1},\pi_{2},\ldots,\pi_{\tau}\). The betweenness centrality of each node \(v\in V\) is then estimated as:  
\[\widetilde{\mathbf{b}}(v)=\frac{1}{\tau}\sum_{i=1}^{\tau}\widetilde{\mathbf{x}}_{i}(v), \tag{2}\]  
where \(\widetilde{\mathbf{x}}_{i}\) is \(1\) iff \(v\) occurs in \(\pi_{i}\) and \(0\) otherwise.  
Compared to earlier approximation algorithms that employ similar sampling techniques (e.g., [23]), the novelty of KADABRA relies on the clever stopping condition, used to determine the number of rounds \(\tau\). Clearly, there is a number \(\omega\), depending on the input size but not the graph itself, such that if \(\tau\geq\omega\), the algorithm achieves the desired solution quality with probability \((1-\delta)\) (for example, if \(\omega\) is chosen so that almost all vertex pairs are sampled. In reality, \(\omega\) can be chosen to be much smaller). KADABRA, however, avoids to run a fixed number of \(\omega\) rounds by using _adaptive sampling_. At each round of the algorithm, it is guaranteed that  
\[P\left(\mathbf{b}(v)\leq\widetilde{\mathbf{b}}(v)-f\right)\leq\delta_{L}(v)\quad\text {and}\quad P\left(\mathbf{b}(v)\geq\widetilde{\mathbf{b}}(v)+g\right)\leq\delta_{U}( v), \tag{3}\]  
where \(P\left(\cdot\right)\) denotes the probability and \(f=f(\widetilde{\mathbf{b}}(v),\delta_{L}(v),\omega,\tau)\) and \(g=g(\widetilde{\mathbf{b}}(v),\delta_{U}(v),\omega,\tau)\) are (rather lengthy) expressions depending on \(\widetilde{\mathbf{b}}(v)\), per-vertex probabilities \(\delta_{L}(v)\) and \(\delta_{U}(v)\), the current number of rounds \(\tau\) and the static round count \(\omega\). \(\delta_{L}(v)\) and \(\delta_{U}(v)\) are chosen such that \(\sum_{v\in V}\delta_{L}(v)+\delta_{U}(v)\leq\frac{\delta}{2}\). Once \(f,g<\epsilon\) during some round, the algorithm terminates. Note also that for each round, the algorithm draws a number of samples and performs occurrence updates without checking the stopping condition. This number is determined by parameter \(c\). In the original implementation of KADABRA (but not reported in the paper), \(c\) is fixed to \(10\) (without further explanation).) Algorithm 1 displays the corresponding pseudocode with some expository comments. Besides adaptive sampling, KADABRA relies on a _balanced bidirectional BFS_ to sample shortest paths. For details we refer the interested reader to the original paper.  
```
1:procedureKADABRA(\(G=(V,E)\), \(\epsilon\), \(\delta\))
2:\(\omega\leftarrow\) non-adaptive number of iterations
3: compute \(\delta_{L}\), \(\delta_{U}\) from \(\delta\)\(\triangleright\) Requires upper bound of the diameter.
4:\(\tau\gets 0\)\(\triangleright\) Number of sampled paths.
5:for all\(v\in V\)do
6:\(\widetilde{\mathbf{x}}(v)\gets 0\)\(\triangleright\) Occurrences of \(v\) in sampled paths.
7:endfor
8:while\(\tau<\omega\)do
9:if\(f(\widetilde{\mathbf{x}}(v)/\tau,\,\delta_{L}(v),\,\omega,\,\tau)<\epsilon\)and\(g(\widetilde{\mathbf{x}}(v)/\tau,\,\delta_{U}(v),\,\omega,\,\tau)<\epsilon\)then
10:break
11:endif
12:for\(i\in\{1,\ldots,c\}\)do
13:\(s,t\leftarrow\) samplePair(\(G\))\(\triangleright\) Draw \(c\) samples per round.
14:\(\tau\leftarrow\) sampleShortestPath(\(G,s,t\))\(\triangleright\) Uniformly at random.
15:for all\(v\in\tau\)do
16:\(\widetilde{\mathbf{x}}(v)\leftarrow\widetilde{\mathbf{x}}(v)+1\)
17:endfor
18:\(\tau\leftarrow\tau+1\)
19:endfor
20:endwhile
21:return\(\widetilde{\mathbf{x}}/\tau\)\(\triangleright\) Betweenness centrality is estimated as: \(\widetilde{\mathbf{b}}=\widetilde{\mathbf{x}}/\tau\).
22:endprocedure
```  
**Algorithm 1**KADABRA algorithm (absolute error variant)