Class DynApproxBetweenness

Inheritance Relationships

Base Types

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.

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


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.


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

count getNumberOfSamples() const noexcept

Get number of path samples used for last calculation