Dynamic algorithms update the betweenness values of all nodes
in response to a modification on the graph, which might be an edge
insertion, an edge deletion or a change in an edge's weight.
The first published approach
is QUBE by Lee et al.  [1]}, which relies on the decomposition
of the graph into connected components. When an edge update occurs,
QUBE re-computes the centrality values using BA only
within the affected component. In case the update modifies the
decomposition, this must be recomputed, and new centralities must
be calculated for all affected components. The approach proposed
by Green et al.  [2]} for unweighted graphs
maintains a structure with the previously calculated BC values and
additional information, like the distance
of each node \(v\)  from every source \(s\in V\)  and the list of predecessors, i.e. the nodes
immediately preceding \(v\)  in all shortest paths from \(s\)  to \(v\) . Using this information,
the algorithm tries to limit the recomputations to the nodes whose
betweenness has actually been affected. Kourtellis
et al.  [3]} modify the
approach by Green et al.  [2]} in
order to reduce the memory requirements. Instead of
storing the predecessors of each node \(v\)  from each possible
source, they recompute them every time the information is required.
Kas et al.  [5]} extend an existing algorithm for
the dynamic APSP problem by Ramalingam and Reps [6]}
to also update BC scores.
The recent work by Nasre
et al.  [7]} contains the first dynamic
algorithm for BC (NPR) which is asymptotically faster than recomputing
from scratch on certain inputs. In particular, when only edge insertions are allowed and
the considered graph is sparse and weighted, their algorithm
takes \(O(n^2)\)  operations, whereas BA requires
\(O(n^2\log n)\)  on sparse weighted graphs. Among other things, our
paper contains the first experimental results obtained by an implementation of this algorithm.
