A faster algorithm for betweenness centrality*

2001/06/01 by Ulrik Brandes · 48 citations
Computer Science · Physics and Astronomy · #Advanced Graph Neural Networks #Complex Network Analysis Techniques #Opinion Dynamics and Social Influence

paper · doi:10.1080/0022250x.2001.9990249

crossref issued 2001/06/01 · crossref published 2001/06/01 · crossref published-print 2001/06/01 · openalex publication_date 2001/06/01 · crossref created 2010/08/26 · crossref deposited 2025/02/25 · openalex created_date 2025/10/10 · crossref indexed 2026/07/30 · openalex updated_date 2026/07/30

Abstract

Motivated by the fast‐growing need to compute centrality indices on large, yet very sparse, networks, new algorithms for betweenness are introduced in this paper. They require O(n + m) space and run in O(nm) and O(nm + n2 log n) time on unweighted and weighted networks, respectively, where m is the number of links. Experimental evidence is provided that this substantially increases the range of networks for which centrality analysis is feasible. The betweenness centrality index is essential in the analysis of social networks, but costly to compute. Currently, the fastest known algorithms require ?(n 3) time and ?(n 2) space, where n is the number of actors in the network.

Citations

• The Centrality Index of a Graph
• Authoritative sources in a hyperlinked environment

Cited by

• Graph Processing on FPGAs: Taxonomy, Survey, Challenges
• Flow descriptors of human mobility networks
• Tracking Climate and Environmental Attention: A News‐Based Composite Index
• Science Mapping to study academic knowledge circulation
• Parallel Betweenness Computation in Graph Database for Contingency Selection
• Quantify resilience enhancement of UTS through exploiting connect community and internet of everything emerging technologies
• Guidelines for Experimental Algorithmics in Network Analysis
• Improving the betweenness centrality of a node by adding links
• Efficient Representations of Signals in Nonlinear Signal Processing with Applications to Inverse Problems
• UniqueRank: Identifying Important and Difficult-to-Replace Nodes in Attributed Graphs
• Spreaders in the Network SIR Model: An Empirical Study
• Terrorizer: a novel algorithm for patent assignee name disambiguation
• Journal Publications in Medicine: Ranking vs. Interdisciplinarity
• Independent transitions to fully planktonic life cycles shaped the global distribution of medusozoans in the epipelagic zone
• The Transdiagnostic Connectome Project: an open dataset for studying brain-behavior relationships in psychiatry
• Evolution of Linguistic Markers of Agency, Centrality and Content During Metacognitive Therapy for Psychosis: A Pilot Exploratory Study
• Networks of Exchange Poetry in Late Medieval China: Notes toward a Dynamic History of Tang Literature
• ‘Entanglement’ – A new dynamic metric to measure team flow
• An Integrated Analysis of the <i>Passifloraceae</i> Virome Using Public Domain Data
• Topology of gut Microbiota Network and Guild-Based Analysis in Chinese Adults
• Email as Spectroscopy: Automated Discovery of Community Structure within\n Organizations
• Stability and Continuity of Centrality Measures in Weighted Graphs
• MPC meets SNA: A Privacy Preserving Analysis of Distributed Sensitive Social Networks
• Multi-view Graph Embedding with Hub Detection for Brain Network Analysis
• Characterizing cycle structure in complex networks
• Efficient vaccination strategies for epidemic control using network information
• An Exhaustive DPLL Approach to Model Counting over Integer Linear Constraints with Simplification Techniques
• A Graph Machine Learning Approach for Detecting Topological Patterns in Transactional Graphs
• Fast Percolation Centrality Approximation with Importance Sampling
• Stability Optimization and Analysis of Energy Flow Networks versus Different Centrality Measurement
• Launchers and Targets in Social Networks
• Node-Constrained Traffic Engineering: Theory and Applications
• Complex Networks
• Weighted H-index for identifying influential spreaders
• Generalized Centrality Aggregation and Exclusive Centrality
• Local Virtual Nodes for Alleviating Over-Squashing in Graph Neural Networks
• Betweenness and Diversity in Journal Citation Networks as Measures of\n Interdisciplinarity -- A Tribute to Eugene Garfield --
• A New Frontier for Pull-Based Graph Processing
• Betweenness computation in the single graph representation of hypergraphs
• DEFENDCLI: Command-Line Driven Attack Provenance Examination
• Capsule Neural Networks for Graph Classification using Explicit Tensorial Graph Representations
• Betweenness Centrality : Algorithms and Lower Bounds
• The Ubiquitous Sparse Matrix-Matrix Products
• An Evolution Process for Effective Network Topological Compression
• Intra-City Urban Network and Traffic Flow Analysis from GPS Mobility\n Trace
• Characterizing the Diversity of Dynamics in Complex Networks Without Border Effects
• The role of media memorability in facilitating startups' access to venture capital funding
• Vertex-Centric Graph Processing: Good, Bad, and the Ugly

Related

• Betweenness Centrality : Algorithms and Lower Bounds
• A Lookahead algorithm to compute Betweenness Centrality
• A Faster Algorithm for Betweenness Centrality Based on Adjacency Matrices
• Scalable Betweenness Centrality Maximization via Sampling
• Shattering and Compressing Networks for Centrality Analysis