Approximating betweenness centrality in large evolving networks

DOI10.1137/1.9781611973754.12MaRDI QIDQ5232530zbMATH OpenOpenAlexFDO

Authors Elisabetta Bergamini, Henning Meyerhenke, Christian L. Staudt

Publication date 12 September 2019

Published in 2015 Proceedings of the Seventeenth Workshop on Algorithm Engineering and Experiments (ALENEX) (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1409.6241

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Approximation algorithms (68W25) Distance in graphs (05C12)

Abstract: 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 $10^4$ 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.

Recommendations

• Approximating Betweenness Centrality in Fully Dynamic Networks
• Fully-dynamic approximation of betweenness centrality
• scientific article; zbMATH DE number 6917138
• Approximating Betweenness Centrality
• Better approximation of betweenness centrality

Cited in

(17)

• Betweenness centrality -- incremental and faster
• Topology manipulations for speeding betweenness centrality computation
• Exact and approximate algorithms for computing betweenness centrality in directed graphs
• Fast approximation of betweenness centrality through sampling
• Scalable Katz ranking computation in large static and dynamic graphs
• Fully-dynamic approximation of betweenness centrality
• Approximating Betweenness Centrality
• Network Analysis
• On the maximum betweenness improvement problem
• KADABRA is an adaptive algorithm for betweenness via random approximation
• Improving the betweenness centrality of a node by adding links
• KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation
• Better approximation of betweenness centrality
• An Adaptive Version of Brandes' Algorithm for Betweenness Centrality
• Approximating Betweenness Centrality in Fully Dynamic Networks
• Computing Betweenness Centrality in Link Streams
• scientific article; zbMATH DE number 6917138 (Why is no real title available?)

This page was built for publication: Approximating betweenness centrality in large evolving networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5232530)