Communicability betweenness in complex networks

Ernesto Estrada, Desmond J. Higham, Naomichi Hatano

Research output: Contribution to journalArticle

63 Citations (Scopus)

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 [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 Fréchet 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 proteinprotein interaction network.
LanguageEnglish
Pages764-774
Number of pages10
JournalPhysica A: Statistical Mechanics and its Applications
Volume388
Issue number5
DOIs
Publication statusPublished - 1 Mar 2009

Fingerprint

Betweenness
Complex Networks
Vertex of a graph
Walk
Extremes
Fréchet Derivative
Matrix Exponential
matrices
Protein-protein Interaction
Adjacency Matrix
Small Perturbations
Shortest path
routes
interactions
scaling
perturbation
Scaling
sensitivity
Alternatives
Interaction

Keywords

  • centrality measures
  • proteinprotein interactions
  • communicability
  • spectral graph theory
  • conserved proteins
  • linear response
  • fréchet derivative

Cite this

Estrada, Ernesto ; Higham, Desmond J. ; Hatano, Naomichi. / Communicability betweenness in complex networks. In: Physica A: Statistical Mechanics and its Applications. 2009 ; Vol. 388, No. 5. pp. 764-774.
@article{0209207efba74fad89a4d7ea73720aed,
title = "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 [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 Fr{\'e}chet 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 proteinprotein interaction network.",
keywords = "centrality measures, proteinprotein interactions, communicability, spectral graph theory, conserved proteins, linear response, fr{\'e}chet derivative",
author = "Ernesto Estrada and Higham, {Desmond J.} and Naomichi Hatano",
year = "2009",
month = "3",
day = "1",
doi = "10.1016/j.physa.2008.11.011",
language = "English",
volume = "388",
pages = "764--774",
journal = "Physica A: Statistical Mechanics and its Applications",
issn = "0378-4371",
number = "5",

}

Communicability betweenness in complex networks. / Estrada, Ernesto; Higham, Desmond J.; Hatano, Naomichi.

In: Physica A: Statistical Mechanics and its Applications, Vol. 388, No. 5, 01.03.2009, p. 764-774.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Communicability betweenness in complex networks

AU - Estrada, Ernesto

AU - Higham, Desmond J.

AU - Hatano, Naomichi

PY - 2009/3/1

Y1 - 2009/3/1

N2 - 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 Fréchet 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 proteinprotein interaction network.

AB - 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 Fréchet 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 proteinprotein interaction network.

KW - centrality measures

KW - proteinprotein interactions

KW - communicability

KW - spectral graph theory

KW - conserved proteins

KW - linear response

KW - fréchet derivative

UR - http://arxiv.org/ftp/arxiv/papers/0905/0905.4102.pdf

U2 - 10.1016/j.physa.2008.11.011

DO - 10.1016/j.physa.2008.11.011

M3 - Article

VL - 388

SP - 764

EP - 774

JO - Physica A: Statistical Mechanics and its Applications

T2 - Physica A: Statistical Mechanics and its Applications

JF - Physica A: Statistical Mechanics and its Applications

SN - 0378-4371

IS - 5

ER -