# Class KadabraBetweenness¶

## Class Documentation¶

class KadabraBetweenness : public NetworKit::Algorithm

Public Functions

KadabraBetweenness(const Graph &G, double err = 0.01, double delta = 0.1, bool deterministic = false, count k = 0, count unionSample = 0, count startFactor = 100)

Approximation of the betweenness centrality and computation of the top-k nodes with highest betweenness centrality according to the algorithm described in Borassi M., and Natale E. (2016): KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation. Parallel implementation by Van der Grinten A., Angriman E., and Meyerhenke H.: Parallel Adaptive Sampling with almost no Synchronization, Euro-Par 2019. https://link.springer.com/chapter/10.1007/978-3-030-29400-7_31 ArXiv pre-print: https://arxiv.org/abs/1903.09422.

If k = 0 the algorithm approximates the betweenness centrality of all vertices of the graph so that the scores are within an additive error err with probability at least (1 - delta). Otherwise, the algorithm computes the exact ranking of the top-k nodes with highest betweenness centrality. The algorithm relies on an adaptive random sampling technique of shortest paths and the number of samples in the worst case is w = ((log(D - 2) + log(2/delta))/err^2 samples, where D is the diameter of the graph. Thus, the worst-case performance is O(w * (|E| + |V|)), but performs better in practice.

Parameters:
• G – The graph

• err – Maximum additive error guaranteed when approximating the betweenness centrality of all nodes.

• delta – probability that the values of the betweenness centrality are within the error guarantee.

• deterministic – If true, the algorithm guarantees that the results of two different executions is the same for a fixed random seed, regardless of the number of threads. Note that this guarantee leads to increased computational and memory complexity. Default: false.

• k – the number of top-k nodes to be computed. Set it to zero to approximate the betweenness centrality of all the nodes.

• unionSample – algorithm parameter that is automatically chosen.

• startFactor – algorithm parameter that is automatically chosen.

virtual void run() override

Executes the Kadabra algorithm.

inline std::vector<std::pair<node, double>> ranking() const
Returns:

The ranking of the nodes according to their approximated betweenness centrality.

inline std::vector<node> topkNodesList() const
Returns:

Nodes of the graph sorted by their approximated betweenness centrality.

inline std::vector<double> topkScoresList() const
Returns:

Sorted list of approximated betweenness centrality scores.

inline std::vector<double> scores() const
Returns:

Approximated betweenness centrality score of all the nodes of the graph.

inline count getNumberOfIterations() const
Returns:

Total number of samples.

inline double getOmega() const
Returns:

Upper bound to the number of samples.

inline count maxAllocatedFrames() const

Public Members

unsigned int baseItersPerStep = 1000
double itersPerStepExp = 1.33

Protected Functions

void init()
void computeDeltaGuess()
void computeBetErr(Status *status, std::vector<double> &bet, std::vector<double> &errL, std::vector<double> &errU) const
bool computeFinished(Status *status) const
void getStatus(Status *status, bool parallel = false) const
void computeApproxParallel(const std::vector<StateFrame> &firstFrames)
double computeF(double btilde, count iterNum, double deltaL) const
double computeG(double btilde, count iterNum, double deltaU) const
void fillResult()
void checkConvergence(Status &status)
inline void fillPQ()

Protected Attributes

const Graph &G
const double delta
const double err
const bool deterministic
const count k
const count startFactor
count unionSample
count nPairs
const bool absolute
double deltaLMinGuess
double deltaUMinGuess
double omega
std::atomic<int32_t> epochToRead
int32_t epochRead
count seed0
count seed1
std::vector<count> maxFrames
std::vector<node> topkNodes
std::vector<double> topkScores
std::vector<std::pair<node, double>> rankingVector
std::vector<std::atomic<StateFrame*>> epochFinished
std::vector<SpSampler> samplerVec
std::unique_ptr<Aux::SortedList> top
std::unique_ptr<ConnectedComponents> cc
std::vector<double> approxSum
std::vector<double> deltaLGuess
std::vector<double> deltaUGuess
std::atomic<bool> stop