Class KadabraBetweenness

Inheritance Relationships

Base Type

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. ArXiv pre-print:

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.

  • 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

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

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

Nodes of the graph sorted by their approximated betweenness centrality.

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

Sorted list of approximated betweenness centrality scores.

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

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

inline count getNumberOfIterations() const

Total number of samples.

inline double getOmega() const

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