Communicability Betweenness in Complex Networks

Abstract

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 (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.

32 pages, 7 figures, 3 tables

References in corpus (13)

• Statistical mechanics of complex networks
• The structure and function of complex networks
• Error and attack tolerance of complex networks
• Characterization of complex networks: A survey of measurements
• Subgraph Centrality in Complex Networks
• Communicability in complex networks
• Complex Networks as Hypergraphs
• Virtual Identification of Essential Proteins Within the Protein Interaction Network of Yeast
• Betweenness Centrality of Fractal and Non-Fractal Scale-Free Model Networks and Tests on Real Networks
• The inhomogeneous evolution of subgraphs and cycles in complex networks
• General Formulation of Quantum Analysis
• What Is There Between Any Two Nodes in a Complex Network?
• What do we learn from correlations of local and global network properties?

Cited by in corpus (14)

• Vital nodes identification in complex networks
• The Physics of Communicability in Complex Networks
• Community landscapes: an integrative approach to determine overlapping network module hierarchy, identify key nodes and predict network dynamics
• Consistency and differences between centrality measures across distinct classes of networks
• Two betweenness centrality measures based on Randomized Shortest Paths
• Machine Learning in Network Centrality Measures: Tutorial and Outlook
• A measure of centrality based on the spectrum of the Laplacian
• A Network Science perspective of Graph Convolutional Networks: A survey
• Absorbing Random Walks Interpolating Between Centrality Measures on Complex Networks
• The epidemiology of lateral movement: exposures and countermeasures with network contagion models
• Exploring the "Middle Earth" of Network Spectra via a Gaussian Matrix Function
• Characterising heavy-tailed networks using q-generalised entropy and q-adjacency kernels
• Adjustable reach in a network centrality based on current flows
• Topological and Temporal Stability Analysis of the Lightning Network