Defined in File DynBetweennessOneNode.hpp
public NetworKit::Algorithm (Class Algorithm)
public NetworKit::DynAlgorithm (Class DynAlgorithm)
This algorithm computes the betweenness centrality for a specified focus node x. It works for dynamic graphs that can be undirected/directed and unweighted/weighted without negative cycles. The Algorithm proceeds as described in [1]. The run() method computes the betweenness centrality by computing SSSP (similar to Dijkstra) for each node. The update() method only works with edge insertions and edge weight decrements and has a WC runtime complexity of O(n²) which outperforms the DynamicBetweenness algorithm for all nodes (instead of one focus node) that takes O(nm).
[1] Bergamini et al. : Improving the Betweenness Centrality of a Node by Adding Links https://dl.acm.org/doi/abs/10.1145/3166071
Public Functions
Creates the object for G.
G – The graph. @paarm x The node for which we want to compute betweenness.
initialize distances and Pred by repeatedly running the Dijkstra2 algorithm
Updates the betweenness centrality of x after an edge insertions on the graph. Notice: it works only with edge insertions.
e – The edge insertions.
Updates the betweenness centrality of x after a batch of edge insertions on the graph. Notice: it works only with edge insertions.
batch – The batch of edge insertions.
Returns the new betweenness score of node x after the insertion of an edge. Distances and scores of the other nodes are not changed by this function.