2026-07-22T01:28:55Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7609 2024-03-06T10:39:50Z ddc:004 open_access

Faster Betweenness Centrality Updates in Evolving Networks Bergamini, Elisabetta Meyerhenke, Henning Ortmann, Mark Slobbe, Arie Graph algorithms shortest paths distances dynamic algorithms Finding central nodes is a fundamental problem in network analysis. Betweenness centrality is a well-known measure which quantifies the importance of a node based on the fraction of shortest paths going though it. Due to the dynamic nature of many today’s networks, algorithms that quickly update centrality scores have become a necessity. For betweenness, several dynamic algorithms have been proposed over the years, targeting different update types (incremental- and decremental-only, fully-dynamic). In this paper we introduce a new dynamic algorithm for updating betweenness centrality after an edge insertion or an edge weight decrease. Our method is a combination of two independent contributions: a faster algorithm for updating pairwise distances as well as number of shortest paths, and a faster algorithm for updating dependencies. Whereas the worst-case running time of our algorithm is the same as recomputation, our techniques considerably reduce the number of operations performed by existing dynamic betweenness algorithms. Our experimental evaluation on a variety of real-world networks reveals that our approach is significantly faster than the current state-of-the-art dynamic algorithms, approximately by one order of magnitude on average. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Elisabetta Bergamini and Henning Meyerhenke and Mark Ortmann and Arie Slobbe 2017 Is Part Of LIPIcs, Volume 75, 16th International Symposium on Experimental Algorithms (SEA 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SEA.2017.23 urn:nbn:de:0030-drops-76093 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017.23 eng https://creativecommons.org/licenses/by/3.0/legalcode