Large graphs of interest, such as the Web and social networks,
evolve continuously. Thus, in addition to the identification of important
nodes in a static network, an issue of great interest is the evolution of centrality
values in dynamically changing networks.
So far, there are no approximation
algorithms that efficiently update BC scores rather than recomputing them from scratch.
A few methods have been proposed to update the BC values after a graph modification, which for some of the
algorithms can only be one edge insertion and for others can also be
one edge deletion. However, all of these approaches are exact and have
a worst-case time complexity which is the same as Brandes's algorithm (BA)
[1]} and a memory footprint of at least \(O(n^2)\) .
