Class ApproxBetweenness¶

Inheritance Relationships¶

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.

Parameters:

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

Returns:

number of samples taken in last run