Class DynApproxBetweenness¶

Inheritance Relationships¶

Class Documentation¶

class DynApproxBetweenness : public NetworKit::Centrality, public NetworKit::DynAlgorithm¶

Interface for dynamic approximated betweenness centrality algorithm.

Public Functions

DynApproxBetweenness(const Graph &G, double epsilon = 0.01, double delta = 0.1, bool storePredecessors = true, double universalConstant = 0.5)¶

Implementation from the algorithm from “Approximating Betweenness Centrality in Fully-dynamic

Networks” from Internet Mathematics vol. 5 by Elisabetta Bergamini and Henning Meyerhenke 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.

Parameters:

• G – the graph

• storePredecessors – keep track of the lists of predecessors?

• 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 0.5 by default.

virtual void run() override¶

Runs the static approximated betweenness centrality algorithm on the initial graph.

virtual void update(GraphEvent e) override¶

Updates the betweenness centralities after an edge insertions on the graph.

Parameters:

e – The edge insertion or deletion.

virtual void updateBatch(const std::vector<GraphEvent> &batch) override¶

Updates the betweenness centralities after a batch of edge insertions on the graph.

Parameters:

batch – The batch of edge insertions and/or deletions.

count getNumberOfSamples() const noexcept¶

Get number of path samples used for last calculation