  Betweenness is a well-known centrality measure that ranks the nodes of a
network according to their participation in shortest paths. Since an exact
computation is prohibitive in large networks, several approximation algorithms
have been proposed. Besides that, recent years have seen the publication of
dynamic algorithms for efficient recomputation of betweenness in networks that
change over time. In this paper we propose the first betweenness centrality
approximation algorithms with a provable guarantee on the maximum approximation
error for dynamic networks. Several new intermediate algorithmic results
contribute to the respective approximation algorithms: (i) new upper bounds on
the vertex diameter, (ii) the first fully-dynamic algorithm for updating an
approximation of the vertex diameter in undirected graphs, and (iii) an
algorithm with lower time complexity for updating single-source shortest paths
in unweighted graphs after a batch of edge actions. Using approximation, our
algorithms are the first to make in-memory computation of betweenness in
dynamic networks with millions of edges feasible. Our experiments show that our
algorithms can achieve substantial speedups compared to recomputation, up to
several orders of magnitude. Moreover, the approximation accuracy is usually
significantly better than the theoretical guarantee in terms of absolute error.
More importantly, for reasonably small approximation error thresholds, the rank
of nodes is well preserved, in particular for nodes with high betweenness.

Data Structures and Algorithms