Defined in File ApproxBetweenness.hpp
public NetworKit::Centrality
(Class 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
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.
Computes betweenness approximation on the graph passed in constructor.