Class KadabraBetweenness¶

Inheritance Relationships¶

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¶