# Approximating Betweenness Centrality in Large Evolving Networks

arXiv: https://arxiv.org/abs/1409.6241 · HTML: https://mlsanity.com/paper/1409.6241/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Sep 2014.

## Built on by (most cited first, 2 of 2)

- [Using Time-Aware Graph Neural Networks to Predict Temporal Centralities in Dynamic Graphs](https://mlsanity.com/paper/2310.15865/) (2023)
- [Node Centrality Approximation For Large Networks Based On Inductive Graph Neural Networks](https://mlsanity.com/paper/2403.04977/) (2024)

## Abstract (arXiv)

Betweenness centrality ranks the importance of nodes by their participation in all shortest paths of the network. Therefore computing exact betweenness values is impractical in large networks. For static networks, approximation based on randomly sampled paths has been shown to be significantly faster in practice. However, for dynamic networks, no approximation algorithm for betweenness centrality is known that improves on static recomputation. We address this deficit by proposing two incremental approximation algorithms (for weighted and unweighted connected graphs) which provide a provable guarantee on the absolute approximation error. Processing batches of edge insertions, our algorithms yield significant speedups up to a factor of 104 compared to restarting the approximation. This is enabled by investing memory to store and efficiently update shortest paths. As a building block, we also propose an asymptotically faster algorithm for updating the SSSP problem in unweighted graphs. Our experimental study shows that our algorithms are the first to make in-memory computation of a betweenness ranking practical for million-edge semi-dynamic networks. Moreover, our results show that the accuracy is even better than the theoretical guarantees in terms of absolutes errors and the rank of nodes is well preserved, in particular for those with high betweenness.