A faster algorithm for betweenness centrality*
2001/06/01 by Ulrik Brandes · 181 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
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 Passifloraceae 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
- A Tractable Complex Network Model based on the Stochastic Mean-field Model of Distance
- 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 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
- Uncovering nodes that spread information between communities in social networks
- Capsule Neural Networks for Graph Classification using Explicit Tensorial Graph Representations
- Shattering and Compressing Networks for Centrality Analysis
- Betweenness Centrality : Algorithms and Lower Bounds
- The Ubiquitous Sparse Matrix-Matrix Products
- An Evolution Process for Effective Network Topological Compression
- Foureye: Defensive Deception based on Hypergame Theory Against Advanced Persistent Threats
- Intra-City Urban Network and Traffic Flow Analysis from GPS Mobility 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: The Good, the Bad, and the Ugly
- Patterns of Primes and Composites from Divisibility Network of Natural Numbers
- Abstract Graph Machine
- Maximizing Coverage Centrality via Network Design: Extended Version
- An Experimental Study of Permanently Stored Learned Clauses
- Sparse Tensor Algebra as a Parallel Programming Model
- Computational Human Dynamics
- Role of Toll-Like Receptors in the interplay between pathogen and damage associated molecular patterns
- DANCE: A Framework for the Distributed Assessment of Network Centralities
- Finding the most degree-central walks and paths in a graph: Exact and heuristic approaches
- Lessons from Three Views of the Internet Topology
- On the random access performance of Cell Broadband Engine with graph analysis application
- Graph Analytics for anomaly detection in homogeneous wireless networks - A Simulation Approach
- Scalable Betweenness Centrality Maximization via Sampling
- Limiting the Neighborhood: De-Small-World Network for Outbreak Prevention
- Elastic Resource Allocation for Distributed Graph Processing Platforms
- Indicators of the Interdisciplinarity of Journals: Diversity, Centrality, and Citations
- Subnetwork hierarchies of biochemical pathways
- The role of network embeddedness in film success
- Connectivity-based approach to guide conservation and restoration of seagrass Posidonia oceanica in the NW Mediterranean
- Scalable distributed service migration via Complex Networks Analysis
- Graph Centrality Measures for Boosting Popularity-Based Entity Linking
- Trip-Based Public Transit Routing Using Condensed Search Trees
- Force-Directed Graph Drawing Using Social Gravity and Scaling
- System-Wide Termination in Distributed Betweenness Centrality Computation
- Toward a Local Perspective on Online Collaboration
- Network modeling methods for precision medicine
- On Demand Memory Specialization for Distributed Graph Databases
- A Comprehensive Machine Learning Framework for Micromobility Demand Prediction
- Ranking the Importance Level of Intermediaries to a Criminal using a Reliance Measure
- Gunrock: GPU Graph Analytics
- A Heuristic Algorithm for Shortest Path Search
- FlashGraph: Processing Billion-Node Graphs on an Array of Commodity SSDs
- PiNet: A Permutation Invariant Graph Neural Network for Graph Classification
- Overlaying Quantitative Measurement on Networks: An Evaluation of Three Positioning and Nine Visual Marker Techniques
- Fast Geometric Embedding for Node Influence Maximization
- CLGNN: A Contrastive Learning-based GNN Model for Betweenness Centrality Prediction on Temporal Graphs
- Effective Stimulus Propagation in Neural Circuits: Driver Node Selection
- Community Detection for Power Systems Network Aggregation Considering Renewable Variability
- A measure of betweenness centrality based on random walks
- Keyword and Keyphrase Extraction Using Centrality Measures on Collocation Networks
- Decremental All-Pairs ALL Shortest Paths and Betweenness Centrality
- Visualizing criminal networks reconstructed from mobile phone records
- Disentangling Complex Systems: IdopNetwork Meets GLMY Homology Theory
- How to Compare the Scientific Contributions between Research Groups
- Evaluating Presidential Support in the Brazilian House of Representatives Through a Network-Based Approach
- On Local and Global Centrality in Large Scale Networks
- Toeplitz Inverse Covariance-Based Clustering of Multivariate Time Series Data
- Overlapping Communities in Social Networks
- A heuristic optimization method for mitigating the impact of a virus attack
- Tracking Large-Scale Video Remix in Real-World Events
- Biological and Shortest-Path Routing Procedures for Transportation Network Design
- DX100: A Programmable Data Access Accelerator for Indirection
- A Comprehensive Survey of Ontology Summarization: Measures and Methods
- Green-Marl
- FI-GRL: Fast Inductive Graph Representation Learning via Projection-Cost Preservation
- Quantum Walk Inspired Neural Networks for Graph-Structured Data
- Why Are There Six Degrees of Separation in a Social Network?
- Modeling Social Dynamics with an LLM-Enabled Agent Based Network-Dynamic (LAND) Model
- Simple and Fast Distributed Computation of Betweenness Centrality
- Letting losses be lessons: Human-machine cooperation in maritime transport
- GraphMaps: Browsing Large Graphs as Interactive Maps
- Measuring Social Influence with Networked Synthetic Control
- Surgical immunization strategies against lateral movement in Active Directory environments
- A Graph-Theoretic Approach to Efficient Voice-Leading
- Liquidity-Saving through Obligation-Clearing and Mutual Credit: An Effective Monetary Innovation for SMEs in Times of Crisis
- Fine-Grained Complexity and Conditional Hardness for Sparse Graphs
- Understanding Information Spreading in Social Media during Hurricane Sandy: User Activity and Network Properties
- Improving Power Systems Controllability via Edge Centrality Measures
- Predicting species emergence in simulated complex pre-biotic networks
- Minor intron–containing genes as an ancient backbone for viral infection?
- Forecasting financial markets with semantic network analysis in the COVID‐19 crisis
- Connecting brain and heart: artificial intelligence for sustainable development
- The identity of social impact venture capitalists: exploring social linguistic positioning and linguistic distinctiveness through text mining
- A Fine-Grained Hybrid CPU-GPU Algorithm for Betweenness Centrality Computations
- Community detection in graphs
- A Graph-Based Machine Learning Approach for Bot Detection
- Global Rank Estimation
- Social Network Analysis, Large-Scale
- Central loops in random planar graphs
- Measures of Tipping Points, Robustness, and Path Dependence
- Comparing community structure identification
- An Evidential Reasoning Based Approach to Building Node Selection Criterion for Network Reduction
- Global disease spread: Statistics and estimation of arrival times
- A new method for quantifying network cyclic structure to improve community detection
- DomainNet: Homograph Detection for Data Lake Disambiguation
- Exploring cities of Central and Eastern Europe within transnational company networks: the core-periphery effect
- Optimal transport on wireless networks
- Pruned Landmark Labeling Meets Vertex Centric Computation: A Surprisingly Happy Marriage!
- Vertex overload breakdown in evolving networks
- Machine learning meets complex networks via coalescent embedding in the hyperbolic space
- Crisis Communications in the Age of Social Media
- The architecture of complex weighted networks
- A Graph Isomorphism-based Decentralized Algorithm for Modular Robot Configuration Formation
- Quantifying the interdisciplinarity of scientific journals and fields
- Foundation Species Abundance Influences Food Web Topology on Glass Sponge Reefs
- Social connectedness and movements among communities of giraffes vary by sex and age class
- Code evolution for link prediction in complex networks
- How do scholars and non-scholars participate in dataset dissemination on Twitter
- Permaculture for agroecology: design, movement, practice, and worldview. A review
- Scientific collaboration networks. II. Shortest paths, weighted networks, and centrality
- Dynamical properties of interaction data
- Deciphering the generating rules and functionalities of complex networks
- Graph partitioning for scalable distributed graph computations
- Resilience of public transport networks against attacks
- Centrality properties of directed module members in social networks
- Prediction of lethal and synthetically lethal knock-outs in regulatory networks
- Scalable Online Betweenness Centrality in Evolving Graphs
- Robust manifold learning with CycleCut
- On the role of words in the network structure of texts: Application to authorship attribution
- An Approach for the Identification of Targets Specific to Bone Metastasis Using Cancer Genes Interactome and Gene Ontology Analysis
- Integrating fluctuations into distribution of resources in transportation networks
- ONBRA: Rigorous Estimation of the Temporal Betweenness Centrality in Temporal Networks
- The network structure of mathematical knowledge according to the Wikipedia, MathWorld, and DLMF online libraries
- Shortest Paths with Pairwise-Distinct Edge Labels: Finding Biochemical Pathways in Metabolic Networks
- Immunization strategies in networks with missing data
- Absorbing random walks interpolating between centrality measures on complex networks
- A method for reducing the severity of epidemics by allocating vaccines according to centrality
- Betweenness centrality in large complex networks
- Effect of edge removal on topological and functional robustness of complex networks
- Detection of core–periphery structure in networks using spectral methods and geodesic paths
- Mapping wind-power controversies on social media: Facebook as a powerful mobilizer of local resistance
- Ranking Vertices or Edges of a Network by Loops: A New Approach
- Systematic evaluation of a new combinatorial curvature for complex networks
- Centrality with Diversity
- Large-scale structures in the ΛCDM Universe: network analysis and machine learning
- Power Grid Network Evolutions for Local Energy Trading
- Network Backbone Discovery Using Edge Clustering
- NodeRAG: Structuring Graph-based RAG with Heterogeneous Nodes
- Disconnecting bones within the jaw‐otic network modules underlies mammalian middle ear evolution
- Network-based ranking in social systems: three challenges
- Utility-aware Social Network Anonymization using Genetic Algorithms
Related