Class ApproxBetweenness

Inheritance Relationships

Base Type

Class Documentation

class ApproxBetweenness : public NetworKit::Centrality

Approximation of betweenness centrality according to algorithm described in Matteo Riondato and Evgenios M. Kornaropoulos: Fast Approximation of Betweenness Centrality through Sampling

Public Functions

ApproxBetweenness(const Graph &G, double epsilon = 0.01, double delta = 0.1, double universalConstant = 1.0)

The algorithm approximates the betweenness of all vertices so that the scores are within an additive error epsilon with probability at least (1- delta). The values are normalized by default. The run() method takes O(m) time per sample, where m is the number of edges of the graph. The number of samples is proportional to universalConstant/epsilon^2. Although this algorithm has a theoretical guarantee, the algorithm implemented in Estimate Betweenness usually performs better in practice Therefore, we recommend to use EstimateBetweenness if no theoretical guarantee is needed.

  • G – the graph

  • epsilon – maximum additive error

  • delta – probability that the values are within the error guarantee

  • universalConstant – the universal constant to be used in computing the sample size. It is 1 by default. Some references suggest using 0.5, but there is no guarantee in this case.

virtual void run() override

Computes betweenness approximation on the graph passed in constructor.

count numberOfSamples() const

number of samples taken in last run