Approximating Betweenness Centrality in Fully Dynamic Networks

Abstract

Betweenness is a well-known centrality measure that ranks the nodes of a network according to their participation in shortest paths. Because exact computations are 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 article, 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.

Acknowledgments

We thank Moritz von Looz for providing the synthetic dynamic networks and the numerous contributors to the NetworKit project. We also thank Matteo Riondato for his constructive comments on earlier versions of the material presented in this article.

Funding

This work is partially supported by DFG grant ME-3619/3-1 (FINCA) within the SPP 1736 Algorithms for Big Data and by DFG grant ME-3619/2-1 (TEAM).

Notes

¹http://www.cc.gatech.edu/dimacs10/downloads.shtml [2].

²http://snap.stanford.edu

³Taken from http://konect.uni-koblenz.de/.

⁴http://networkit.iti.kit.edu