Betweenness centrality -- incremental and faster

DOI10.1007/978-3-662-44465-8_49MaRDI QIDQ2922644zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Meghana Nasre, Matteo Pontecorvi, Vijaya Ramachandran

Publication date 14 October 2014

Published in Mathematical Foundations of Computer Science 2014 (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05) Analysis of algorithms (68W40)

Abstract: We consider the incremental computation of the betweenness centrality of all vertices in a large complex network modeled as a graph G = (V, E), directed or undirected, with positive real edge-weights. The current widely used algorithm to compute the betweenness centrality of all vertices in G is the Brandes algorithm that runs in O(mn + n^2 log n) time, where n = |V| and m = |E|. We present an incremental algorithm that updates the betweenness centrality score of all vertices in G when a new edge is added to G, or the weight of an existing edge is reduced. Our incremental algorithm runs in O(m' n + n^2) time, where m' is the size of a certain subset of E*, the set of edges in G that lie on a shortest path. We achieve the same bound for the more general incremental update of a vertex v, where the edge update can be performed on any subset of edges incident to v. Our incremental algorithm is the first algorithm that is asymptotically faster on sparse graphs than recomputing with the Brandes algorithm. Our algorithm is also likely to be much faster than the Brandes algorithm on dense graphs since m*, the size of E*, is often close to linear in n. Our incremental algorithm is very simple and the only data structures it uses are arrays, lists, and stack. We give an efficient cache-oblivious implementation that incurs O(scan(n^2) + n sort(m')) cache misses, where scan and sort are well-known measures for efficient caching. We also give a static algorithm for computing betweenness centrality of all vertices that runs in time O(m* n + n^2 log n), which is faster than the Brandes algorithm on any graph with n log n = o(m) and m* = o(m).

Recommendations

• scientific article; zbMATH DE number 6917138
• Fully dynamic betweenness centrality
• Approximating betweenness centrality in large evolving networks
• A faster algorithm to update betweenness centrality after node alteration
• Efficient algorithms for updating betweenness centrality in fully dynamic graphs

Cited in

(15)

• A Faster Algorithm to Update Betweenness Centrality after Node Alteration
• Decremental All-Pairs ALL Shortest Paths and Betweenness Centrality
• Fully-dynamic approximation of betweenness centrality
• Fully dynamic betweenness centrality
• Improving the betweenness centrality of a node by adding links
• Dynamic merging of frontiers for accelerating the evaluation of betweenness centrality
• scientific article; zbMATH DE number 6917138 (Why is no real title available?)
• Faster computation of successive bounds on the group betweenness centrality
• Topology manipulations for speeding betweenness centrality computation
• A faster algorithm to update betweenness centrality after node alteration
• Algebraic algorithms for betweenness and percolation centrality
• An Adaptive Version of Brandes' Algorithm for Betweenness Centrality
• An Adaptive Version of Brandes' Algorithm for Betweenness Centrality
• Approximating Betweenness Centrality in Fully Dynamic Networks
• Computing Betweenness Centrality in Link Streams

This page was built for publication: Betweenness centrality -- incremental and faster

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