Communicability betweenness in complex networks

Betweenness measures provide quantitative tools to pick out fine details from the massive amount of interaction data that is available from large complex networks. They allow us to study the extent to which a node takes part when information is passed around the network. Nodes with high betweenness may be regarded as key players that have a highly active role. At one extreme, betweenness has been defined by considering information passing only through the shortest paths between pairs of nodes. At the other extreme, an alternative type of betweenness has been defined by considering all possible walks of any length. In this work, we propose a betweenness measure that lies between these two opposing viewpoints. We allow information to pass through all possible routes, but introduce a scaling so that longer walks carry less importance. This new definition shares a similar philosophy to that of communicability for pairs of nodes in a network, which was introduced by Estrada and Hatano [E. Estrada, N. Hatano, Phys. Rev. E 77 (2008) 036111]. Having defined this new communicability betweenness measure, we show that it can be characterized neatly in terms of the exponential of the adjacency matrix. We also show that this measure is closely related to a Frechet derivative of the matrix exponential. This allows us to conclude that it also describes network sensitivity when the edges of a given node are subject to infinitesimally small perturbations. Using illustrative synthetic and real life networks, we show that the new betweenness measure behaves differently to existing versions, and in particular we show that it recovers meaningful biological information from a protein–protein interaction network.

• Publication year

  2009

• Venue

  Physica A-statistical Mechanics and Its Applications

• Publication date

  2009-03-01

• Fields of study

  Mathematics, Physics, Computer Science

• Identifiers
  DOI 10.1016/j.physa.2008.11.011arXiv 0905.4102
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Proteomics

  2011cited by this paper
• Which Sectors of a Modern Economy are Most Central?

  2010cited by this paper
• What is social network analysis

  2010cited by this paper
• What Is There Between Any Two Nodes in a Complex Network

  2008cited by this paper
• The Importance of Bottlenecks in Protein Networks: Correlation with Gene Essentiality and Expression Dynamics

  2007cited by this paper
• Communicability in complex networks.

  2007cited by this paper
• Characterization of topological keystone species: Local, global and “meso-scale” centralities in food webs

  2007cited by this paper
• Bridge and brick motifs in complex networks

  2007cited by this paper
• Betweenness centrality of fractal and nonfractal scale-free model networks and tests on real networks.

  2007cited by this paper
• Quantifying positional importance in food webs: A comparison of centrality indices

  2007cited by this paper
• Functions of Matrices: from Cayley and Sylvester to Matlab

  2007cited by this paper
• Fingerprinting networks: Correlations of local and global network properties

  2006cited by this paper
• Network robustness to targeted attacks. The interplay of expansibility and degree distribution

  2006cited by this paper
• A Graph-theoretic perspective on centrality

  2006cited by this paper
• Interaction network containing conserved and essential protein complexes in Escherichia coli

  2005cited by this paper
• Characterization of complex networks: A survey of measurements

  2005cited by this paper
• Comparative genomics of centrality and essentiality in three eukaryotic protein-interaction networks.

  2005cited by this paper
• Virtual identification of essential proteins within the protein interaction network of yeast

  2005cited by this paper
• Centrality and network flow

  2005cited by this paper
• Subgraph centrality and clustering in complex hyper-networks

  2005cited by this paper
• Reliability of measures of centrality and prominence

  2005cited by this paper
• Subgraph centrality in complex networks.

  2005cited by this paper
• Inhomogeneous evolution of subgraphs and cycles in complex networks.

  2005cited by this paper
• The Structure and Function of Complex Networks

  2003cited by this paper
• A measure of betweenness centrality based on random walks

  2003cited by this paper
• Statistical mechanics of complex networks

  2001cited by this paper
• Error and attack tolerance of complex networks

  2000cited by this paper
• General Formulation of Quantum Analysis

  1998cited by this paper
• Derivatives of the Matrix Exponential and Their Computation

  1995cited by this paper
• Robust Action and the Rise of the Medici, 1400-1434

  1993cited by this paper
• Centrality in valued graphs: A measure of betweenness based on network flow

  1991cited by this paper
• Rethinking centrality: Methods and examples☆

  1989cited by this paper
• Power and Centrality: A Family of Measures

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

  1978cited by this paper
• Factoring and weighting approaches to status scores and clique identification

  1972cited by this paper

• Leader-driven social network reconstruction.

  2026cites this paper
• The many faces of multivariate information

  2026cites this paper
• Causal Effects of Enhanced Parenting on Resting-State Graph Properties of Adolescents at Risk for Maltreatment

  2025cites this paper
• The Generalized Friendship Paradox for Spectral Centralities

  2025cites this paper
• Examining the Barriers to the Adoption of IoT-Based Technologies in Green Buildings

  2025cites this paper
• Explainable AI for analyzing the decision of GNNs at predicting dynamic stability of complex oscillator networks.

  2025cites this paper
• Large-scale brain mediation network based on resting-state functional MRI

  2025cites this paper
• Topology and Network Dynamics of the Lightning Network: A Comprehensive Analysis

  2025cites this paper
• Leak detection and localization in water distribution systems via multilayer networks

  2024cites this paper
• Discovering the important proteins through persistent homology in aging protein-protein interaction networks

  2024cites this paper
• The interplay of structural features and observed dissimilarities among centrality indices

  2024cites this paper
• Enhancing Exchange-Traded Fund Price Predictions: Insights from Information-Theoretic Networks and Node Embeddings

  2024cites this paper
• Constructing and Visualizing Cyber Asset Graphs of Cybercrime Gangs

  2024cites this paper
• A scalable synergy-first backbone decomposition of higher-order structures in complex systems

  2024cites this paper
• Vital node identification in complex networks based on autoencoder and graph neural network

  2024cites this paper
• A Temporal Information Transfer Network Approach Considering Federal Funds Rate for an Interpretable Asset Fluctuation Prediction Framework

  2024cites this paper
• NSDLib: A comprehensive python library for network source detection and evaluation

  2024cites this paper
• ERIUE: Evidential reasoning-based influential users evaluation in social networks

  2023cites this paper
• Neural Network Connectivity Following Opioid Dependence is Altered by a Common Genetic Variant in the µ-Opioid Receptor, OPRM1 A118G

  2023cites this paper
• Ecological network analysis reveals complex responses of tree species life stage interactions to stand variables

  2023cites this paper
• Community-Consideration Centrality, a Case Study of Lung Cancer Proteins

  2023cites this paper
• A Network Science Perspective of Graph Convolutional Networks: A Survey

  2023cites this paper
• The concentration of edge betweenness in the evolution of planar graphs and street networks

  2023cites this paper
• From the Dialectical Perspective: Modeling and Exploiting of Hybrid Worm Propagation

  2023cites this paper
• TriBeC: identifying influential users on social networks with upstream and downstream network centrality

  2023cites this paper
• Resistance-distance betweenness: Definition, properties, and application in complex linguistic networks

  2022cites this paper
• A Flow Attack Strategy based on Critical Links for Cyber-attack

  2022cites this paper
• Modeling the Interaction Networks about the Climate Change on Twitter: A Characterization of its Network Structure

  2022cites this paper
• Variable Centrality: A scenario based centrality calculation method

  2022cites this paper
• A perturbative approach to study information communication in brain networks

  2022cites this paper
• A spatial interaction incorporated betweenness centrality measure

  2022cites this paper
• Ranking Edges by their Impact on the Spectral Complexity of Information Diffusion over Networks

  2022cites this paper
• Communication in Complex Networks

  2021cites this paper
• Analysing the Vulnerability of Public Transport Networks

  2021cites this paper
• Sociohydrology, ecohydrology, and the space-time dynamics of human-altered catchments

  2021cites this paper
• A model for tonal progressions of seventh chords

  2021influential citation
• A Hybrid Communication Pattern in Human Brain Structural Network Revealed by Evolutionary Computation

  2021cites this paper
• A scale-invariant perturbative approach to study information communication in dynamic brain networks

  2021cites this paper
• Random walks on weighted networks: a survey of local and non-local dynamics

  2021cites this paper
• Modeling the Public Transport Networks: A Study of Their Efficiency

  2021cites this paper
• Adjustable reach in a network centrality based on current flows.

  2020influential citation
• A Social Network Analysis of the Oceanographic Community: A Fragmented Digital Community of Practice

  2020cites this paper
• Discovering the genes mediating the interactions between chronic respiratory diseases in the human interactome

  2020cites this paper
• A Current-Flow Centrality With Adjustable Reach

  2020cites this paper
• Computing low‐rank approximations of the Fréchet derivative of a matrix function using Krylov subspace methods

  2020cites this paper
• Variability in Regional Ecological Vulnerability: A Case Study of Sichuan Province, China

  2020cites this paper
• A methodology and theoretical taxonomy for centrality measures: What are the best centrality indicators for student networks?

  2020cites this paper
• Characterising heavy-tailed networks using q-generalised entropy and q-adjacency kernels

  2020influential citation
• Finding Key Nodes in Complex Networks: An Edge and Local Partition Approach

  2020cites this paper
• Absorbing random walks interpolating between centrality measures on complex networks.

  2019influential citation
• Characterization and comprehensive analysis of the ecological interaction networks of bacterial communities in Paullinia cupana var. sorbilis by 16S rRNA gene metabarcoding

  2019cites this paper
• Distributed SDN Deployment in Backbone Networks for Low-Delay and High-Reliability Applications

  2019cites this paper
• The epidemiology of lateral movement: exposures and countermeasures with network contagion models

  2019cites this paper
• The language networks

  2018cites this paper
• Network research : exploration of centrality measures and network flows using simulation studies

  2018influential citation
• Evolving Robust Networks Using Evolutionary Algorithms

  2018cites this paper
• Utility-Driven Graph Summarization

  2018cites this paper
• Understanding Information Centrality Metric: A Simulation Approach

  2018cites this paper
• Evolving Graphs and Similarity-based Graphs with Applications

  2018cites this paper
• Consistency and differences between centrality measures across distinct classes of networks

  2018cites this paper
• Consistency and differences between centrality metrics across distinct classes of networks

  2018cites this paper
• Centrality without indices: Partial rankings and rank probabilities in networks

  2018cites this paper
• Modelling students’ knowledge organisation: Genealogical conceptual networks

  2018cites this paper
• A memetic algorithm for determining the nodal attacks with minimum cost on complex networks

  2018cites this paper
• Intrinsic overlapping modular organization of human brain functional networks revealed by a multiobjective evolutionary algorithm

  2018cites this paper
• Cycle Based Network Centrality

  2018cites this paper
• Communicability geometry captures traffic flows in cities

  2018cites this paper
• Machine Learning in Network Centrality Measures

  2018cites this paper
• Estrada, Ernesto (2010) Structural patterns in complex networks through spectral analysis. In: Structural, Syntactic, and Statistical Pattern

  2018cites this paper
• An efficient probability routing algorithm for scale-free networks

  2017cites this paper
• A Block Krylov Method to Compute the Action of the Fréchet Derivative of a Matrix Function on a Vector with Applications to Condition Number Estimation

  2017cites this paper
• Comparing Network Centrality Measures as Tools for Identifying Key Concepts in Complex Networks: A Case of Wikipedia

  2017cites this paper
• A bag-of-paths node criticality measure

  2017cites this paper
• A comparative study of robustness measures for cancer signaling networks

  2017cites this paper
• A comparative study of network robustness measures

  2017cites this paper
• A Two-Phase Multiobjective Evolutionary Algorithm for Enhancing the Robustness of Scale-Free Networks Against Multiple Malicious Attacks

  2017cites this paper
• Diffusion of treatment in social networks and mass drug administration

  2017cites this paper
• Correlations among centrality indices and a class of uniquely ranked graphs

  2017cites this paper
• Comparative Study of Centrality Measures on Social Networks

  2017cites this paper
• Analyzing Community Structure Based on Topology Potential over Complex Network System

  2017cites this paper
• The effect of link-based topological changes and recoveries on the robustness of cooperation on scale-free networks

  2016cites this paper
• Exploring the "Middle Earth" of Network Spectra via a Gaussian Matrix Function

  2016cites this paper
• Algorithms and Models for Network Data and Link Analysis

  2016cites this paper
• A Graph-Theoretic Approach to Efficient Voice-Leading

  2016cites this paper
• Hierarchical dynamic walks

  2016cites this paper
• Vital nodes identification in complex networks

  2016cites this paper
• Robustness of single and interdependent scale-free interaction networks with various parameters

  2016cites this paper
• Applications of low-rank approximation: complex networks and inverse problems

  2015cites this paper
• Betweenness in time dependent networks

  2015cites this paper
• A Positional Approach for Network Centrality

  2015cites this paper
• Two betweenness centrality measures based on Randomized Shortest Paths

  2015cites this paper
• , 1979-G 585 q GomQuerying and managing complex networks /

  2015cites this paper
• Graph mining algorithms for the analysis of patent citation networks

  2015cites this paper
• Generalized averaged Gauss quadrature rules for the approximation of matrix functionals

  2015cites this paper
• Unravelling the complexity of metabolic networks

  2015cites this paper
• Potential field based receding horizon motion planning for centrality-aware multiple UAV cooperative surveillance

  2015cites this paper
• MINA: A Multinetwork INformation Architecture in Cyber Physical Systems/Internet of Things Environments

  2015cites this paper
• Betweenness Centrality in Some Classes of Graphs

  2014cites this paper
• Estimating the Condition Number of the Fréchet Derivative of a Matrix Function

  2014cites this paper
• Validation of Network Communicability Metrics for the Analysis of Brain Structural Networks

  2014influential citation