Class EstimateBetweenness

Inheritance Relationships

Base Type

Class Documentation

class EstimateBetweenness : public NetworKit::Centrality

Estimation of betweenness centrality according to algorithm described in Sanders, Geisberger, Schultes: Better Approximation of Betweenness Centrality. There is no proven theoretical guarantee on the quality of the approximation. However, the algorithm was shown to perform well in practice. If a guarantee is required, use ApproxBetweenness.

Public Functions

EstimateBetweenness(const Graph &G, count nSamples, bool normalized = false, bool parallel_flag = false)

The algorithm estimates the betweenness of all nodes, using weighting of the contributions to avoid biased estimation. The run() method takes O(m) time per sample, where m is the number of edges of the graph.

  • graph – input graph

  • nSamples – user defined number of samples

  • normalized – normalize centrality values in interval [0,1] ?

  • parallel_flag – if true, run in parallel with additional memory cost z + 3z * t

virtual void run() override

Computes betweenness estimation on the graph passed in constructor.