A faster algorithm for betweenness centrality

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.

• Publication year

  2001

• Venue

  The Journal of Mathematical Sociology

• Publication date

  2001-06-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1080/0022250X.2001.9990249
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Pajek - Program for Large Network Analysis

  1999cited by this paper
• The Web as a Graph: Measurements, Models, and Methods

  1999influential reference
• Authoritative sources in a hyperlinked environment

  1999cited by this paper
• Integration and radiality: Measuring the extent of an individual's connectedness and reachability in a network

  1998cited by this paper
• Improved algorithms for topic distillation in a hyperlinked environment

  1998cited by this paper
• What can you do with a Web in your Pocket?

  1998cited by this paper
• Satellite exchange in the Baltimore Needle Exchange Program.

  1998cited by this paper
• LEDA: a platform for combinatorial and geometric computing

  1997cited by this paper
• Introduction to algorithms

  1996cited by this paper
• Eccentricity and centrality in networks

  1995cited by this paper
• Semirings for social networks analysis

  1994cited by this paper
• Social Network Analysis: Methods and Applications

  1994cited by this paper
• Theoretical Foundations for Centrality Measures

  1991cited by this paper
• Social Network Analysis

  1988cited by this paper
• Fibonacci heaps and their uses in improved network optimization algorithms

  1984cited by this paper
• Data Structures and Algorithms

  1983cited by this paper
• The gatekeeper, pair-dependency and structural centrality

  1980cited by this paper
• Centrality in social networks conceptual clarification

  1978cited by this paper
• A set of measures of centrality based upon betweenness

  1977cited by this paper
• The rush in a directed graph

  1971cited by this paper
• Structural Models: An Introduction to the Theory of Directed Graphs.

  1966cited by this paper
• The centrality index of a graph

  1966cited by this paper
• Structural Models: An Introduction to the Theory of Directed Graphs

  1966cited by this paper
• Structural parameters of communication networks

  1953cited by this paper
• A Mathematical Model for Group Structures

  1948cited by this paper

• Three-Waters Synthesis Evolution with Sustainable Development Goals in Yellow River Basin from 2015-2022

  2026cites this paper
• Overcoming sociotechnical challenges: How to model the probability of investing in climate-friendly energy technologies

  2026cites this paper
• Unveiling the specific microbiome of bivalves: insights into host microbial dynamics and pathogen interactions in a shared environment

  2026cites this paper
• Interior-Boundary Assortativity Profiles on Networks and Applications to SIS Epidemic Dynamics

  2026cites this paper
• A Framework for Improving Social Inclusion Using Network Analysis and IoT-Based Contact Tracing

  2026cites this paper
• PROTAC-Splitter: a machine learning framework for automated identification of PROTAC substructures

  2026cites this paper
• Exploring institutional academic genealogy in computer science through PQDT: enhancing the scientometric potential of dissertations

  2026cites this paper
• Friedkin-Johnsen Social Influence Dynamics on Networks: A Boundary-Value Formulation and Influenceability Measures

  2026cites this paper
• Spatial Modeling of the virus transmission network in Cape Gooseberry (Physalis peruviana L.) fields in Antioquia, Colombia

  2026cites this paper
• Mapping Tourism Stakeholders and Governance Networks to Advance Sustainable Tourism Development: A Case Study in the Lake Tana Region, Northwest Ethiopia

  2026cites this paper
• Passenger-centric resilience assessment of the Aegean ferry network under extreme weather events

  2026cites this paper
• Interpretable deep reinforcement learning optimizes emergency response for China’s freezing rain-impacted roads

  2026cites this paper
• Prioritizing post-earthquake recovery of transportation networks under uncertainty: A deep reinforcement learning approach

  2026cites this paper
• Sustainable Development of Safety Professionals’ Competencies: Insights from Safety Engineering Education in Chinese Universities

  2026cites this paper
• Intelligent routing optimization with deep reinforcement learning and Betweenness Centrality Theory in software-defined networks

  2026cites this paper
• Revealing Structural Brain-Cognition Relationships in Children: A Comparison of Morphometric Similarity and INverse Divergence Networks

  2026cites this paper
• Spatiotemporal assessment of multi hazard risk using graph based analysis for case studies in India

  2026cites this paper
• Competition between homogeneous and plasma chemistry in methane conversion at high temperatures: A global kinetic and graph theory analysis

  2026cites this paper
• Machine Learning and Deep Learning for Cultural Heritage Conservation: A Bibliometric and Task-Oriented Review

  2026cites this paper
• Food addiction in behavioral addictions: a network approach

  2026cites this paper
• Node-Based Blockchain Decentralization Measurement Model

  2026cites this paper
• Dynamic dependency-aware vulnerability and patch management for critical interconnected systems

  2026cites this paper
• Research hotspots and trends of amblyopia treatment from 2015 to 2025: a bibliometric analysis

  2026cites this paper
• FARGO: Feature-Augmented Representation Learning Combined With Enhanced GraphSAGE for Community Detection

  2026cites this paper
• High-Order Knowledge Based Network Controllability Robustness Prediction: A Hypergraph Neural Network Approach

  2026cites this paper
• Community-Imbalanced Graph Sampling

  2026influential citation
• Nutrition Patterns, Metabolic and Psychological State Among High-Weight Young Adults: A Network Approach

  2026cites this paper
• Designing network based intervention strategies for epidemics of infectious diseases from edge based infection probability

  2026cites this paper
• The Formation of Collaborative Learning Teams in Schools Through Mathematical Optimization for Improving the Classroom Climate

  2026cites this paper
• Two-mode network autoregressive model for network analysis with core nodes

  2026cites this paper
• Cracking the Capsid Code: A Computationally-Feasible Approach for Investigating Virus-Excipient Interactions in Biologics Design

  2026cites this paper
• Resilience-oriented decision making on the pre-shock intervention to road networks

  2026cites this paper
• Real-time resilience assessment of urban road network under rainfall based on adaptive multi-expert spatio-temporal learning

  2026cites this paper
• A novel Amycolatopsis sulphurea L-alanine dehydrogenase with enhanced bidirectional catalysis: Rational design, expression, and biochemical characterization.

  2026cites this paper
• Vulnerability assessment of electric vehicles and their charging station network during evacuations

  2026cites this paper
• Three Waters Synthesis and Evolution with Sustainable Development Goals in the Yellow River Basin from 2015–2022

  2026cites this paper
• Fused Unbalanced Gromov–Wasserstein-Based Network Distributional Resilience Analysis for Critical Infrastructure Assessment

  2026cites this paper
• Complex Network Approaches for Vulnerability Assessment and Resilience Enhancement in Power Systems

  2026cites this paper
• Network‐based allosteric analysis of galectin‐7: Key residues dictate functional communication and stability

  2026cites this paper
• Integrating centrality measures and multi-criteria decision-making for enhanced food safety risk assessment: a RASFF-based approach

  2026cites this paper
• Deciphering Carcinogenic Regulatory Signatures Through Network Motif–Driven Pathway Analysis for Computational Prioritization of Candidate Regulatory Proteins

  2026cites this paper
• Dynamic analysis of transportation systems under small perturbations

  2026cites this paper
• Morphological resilience evaluation research on the conservation and renewal of historic districts: A case study on Xijie Historic District, Quanzhou

  2025cites this paper
• Effective Stimulus Propagation in Neural Circuits: Driver Node Selection

  2025influential citation
• Research status, hotspots and perspectives of artificial intelligence applied to pain management: a bibliometric and visual analysis.

  2025cites this paper
• Exploring patient-patient interactions graphs by network analysis

  2025influential citation
• Recent Advances in Efficient Dynamic Graph Processing

  2025cites this paper
• Resilience assessment of city-level virtual water flow network in the Yellow River Basin, China

  2025cites this paper
• Towards community-driven rural development: Path of women group in empowering rural Women’s capacities and role in rural development

  2025cites this paper
• A Review on the Role of Crosslinked Polymers in Renewable Energy: Complex Network Analysis of Innovations in Sustainability

  2025cites this paper
• Parasites alter interaction patterns in fish social networks

  2025cites this paper
• Electoral propaganda in digital space: profiling Facebook use in the Italian general election of 2018

  2025cites this paper
• Benchmarking methods for classifying space functions and access elements in multi-unit apartment buildings

  2025cites this paper
• Analysis of the Propane Price Oriented Weighted Network Based on the Symbolic Pattern Representation of Time Series

  2025cites this paper
• Exploring the network structure of virtual water trade among China's cities.

  2025cites this paper
• Independent transitions to fully planktonic life cycles shaped the global distribution of medusozoans in the epipelagic zone

  2025cites this paper
• DX100: Programmable Data Access Accelerator for Indirection

  2025cites this paper
• The Transdiagnostic Connectome Project: an open dataset for studying brain-behavior relationships in psychiatry

  2025cites this paper
• Fast Geometric Embedding for Node Influence Maximization

  2025cites this paper
• Key Nodes Identification Method in Scale-Free Network Based on Structural Holes

  2025cites this paper
• CLGNN: A Contrastive Learning-based GNN Model for Betweenness Centrality Prediction on Temporal Graphs

  2025cites this paper
• Lookahead strategies for planning of post-disaster emergency restoration of road networks

  2025cites this paper
• Measuring Social Influence with Networked Synthetic Control

  2025cites this paper
• An Adaptive Sampling Algorithm for the Top-$K$ Group Betweenness Centrality

  2025cites this paper
• Urban Street Network Configuration and Property Crime: An Empirical Multivariate Case Study

  2025cites this paper
• Integrating socio-demographic factors for equitable resilience in networked-urban infrastructure systems

  2025cites this paper
• Improving Power Systems Controllability via Edge Centrality Measures

  2025cites this paper
• Disentangling complex systems: IdopNetwork meets GLMY homology theory

  2025cites this paper
• Relax and don't Stop: Graph-aware Asynchronous SSSP

  2025cites this paper
• Water beetle networks differences and migration between natural lakes and post-exploitation water bodies

  2025influential citation
• Ecological Security Pattern Construction for Carbon Sink Capacity Enhancement: The Case of Chengdu Metropolitan Area

  2025cites this paper
• Making Sense of Learning Analytics Use Cases in Higher Education: Development of Scientific Communities and Topics

  2025cites this paper
• Mapping the emotion-scape in Chinese-language pop song lyrics, 1967–2023: combining LLM with lexicon-based sentiment analysis

  2025cites this paper
• SimEdge: A Scalable Transitivity-Aware Graph-Theoretic Similarity Model for Capturing Edge-to-Edge Relationships

  2025cites this paper
• Modelling the future of aquatic products’ trade under marine pollution by Japan’s nuclear wastewater

  2025cites this paper
• Household finance research: A systematic bibliometric analysis of evolution, trends, and emerging research directions

  2025cites this paper
• Leveraging hierarchical temporal importance sampling and adaptive noise modulation to enhance resilience in multi-agent task execution systems

  2025cites this paper
• A Greedy Constructive Heuristic for Solving the Team Orienteering Problem with Variable Time Windows

  2025cites this paper
• Quantifying the weakness of ties with hierarchy-based link centrality

  2025cites this paper
• CycRank: a universal optimization framework for vital nodes identification in complex networks

  2025cites this paper
• On Reducing Stretch in Spanning Trees

  2025cites this paper
• Role of spatial embedding and planarity in shaping the topology of the Street Networks

  2025cites this paper
• A Scientometric Analysis of User Experience: Exploring Evolution, Emerging Themes, and Impacts

  2025cites this paper
• Network Analysis of Uniswap: Centralization and Fragility in the Decentralized Exchange Market

  2025cites this paper
• Sustainable Dependent Sub-Tasks Orchestration at Extreme Edge Computing: A Partitioning-based Deep Reinforcement Learning Approach

  2025cites this paper
• Resilient Placement of Network Functions in a WMN-Based NFV Infrastructure

  2025influential citation
• Ip-GCN: a hybrid deep learning approach to predict influence in complex networks

  2025cites this paper
• Analysis of D-Wave Topologies with k-Hop-Based Graph Metrics

  2025cites this paper
• Graph Theory: Modelling and Analyzing Complex System

  2025cites this paper
• A Heuristic Mutation Particle Swarm Optimization Algorithm for Budgeted Influence Maximization with Emotional Competition

  2025cites this paper
• Utility-aware Social Network Anonymization using Genetic Algorithms

  2025cites this paper
• Sex differences in problematic pornography use among adolescents: a network analysis

  2025cites this paper
• NodeRAG: Structuring Graph-based RAG with Heterogeneous Nodes

  2025cites this paper
• Holistic approach to analysing debates on ecological sustainability over time on X

  2025cites this paper
• CAA: Centrality Adapter Attack for Evaluating Smart City Resilience Against Targeted Attacks

  2025cites this paper
• Community reciprocity promotes cooperation in a network evolutionary prisoner's dilemma game

  2025cites this paper
• Organic molecular network analysis reveals transformation signatures of dissolved organic matter during anaerobic digestion process.

  2025cites this paper
• Security-centric node identification in complex networks

  2025cites this paper
• Analyzing X mentions to uncover micro-clusters interfering in political campaigns: a case study during the Spanish elections

  2025cites this paper
• Prestigious but less interdisciplinary: a network analysis on top-rated journals in medicine

  2025cites this paper