Class EstimateBetweenness¶

Inheritance Relationships¶

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.

Parameters:

• 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.