Source-linked AI summary
Communicability Betweenness in Complex Networks
Ernesto Estrada, Desmond J. Higham, Naomichi Hatano
TL;DR
Betweenness approaches typically focus either on shortest paths or on all walks, leaving a middle ground for routes of differing lengths. The paper proposes communicability betweenness, a weighted all-walks measure, and reports that it recovers meaningful biological information from a protein-protein interaction network.
Problem
Betweenness ranges from shortest-path-only assumptions to considering all possible walks, motivating a measure between these viewpoints.
Source: Introduction · pp. 3, 5Method
The paper proposes communicability betweenness, weighting all walks through a node so longer routes carry less importance.
Source: Introduction · p. 5, Preliminaries · p. 6Results
The measure recovers meaningful biological information from a protein-protein interaction network.
Source: Conclusion · p. 17Takeaways & Limitations
The measure also describes network sensitivity when the edges of a given node undergo infinitesimally small perturbations.
Source: Conclusion · p. 17The conventional shortest-path betweenness premise restricts information flow to geodesic paths, while the analysis notes dependence on network sparsity structure.
Source: Introduction · p. 3, Communicability betweenness · p. 9
Abstract
from arXiv · showhide
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.
Introduction
Centrality measures identify nodes’ roles in network communication, but betweenness approaches range from shortest-path-only to random-walk assumptions. The paper proposes a weighted all-walks measure between these extremes and characterizes it through the adjacency-matrix exponential.
Introduction
- Centrality measures help identify important network actors, including essential proteins, keystone species, informational hubs, and vulnerable infrastructure.The paper situates this use in the study of local network properties and large-scale interaction data.Source: Introduction · p. 3
- Shortest-path betweenness assumes information follows only geodesics, while random-walk betweenness assumes it follows links at random.The paper frames these as opposite ends of the betweenness spectrum, each suited to processes that can occur in networks.Source: Introduction · pp. 3–4
- The proposed betweenness counts all walks through a node, giving longer, non-shortest routes less significance than shortest paths.It extends the weighted-sum idea used for pairwise communicability to walks passing through a third node.Source: Introduction · pp. 4–5
- The proposed measure is characterized and computed using the exponential of the adjacency matrix.The paper also presents synthetic and real-world examples of its application.Source: Introduction · p. 5
Preliminaries
The paper builds communicability betweenness from weighted walks connecting node pairs and passing through a third node. This extends pairwise communicability to a node-level score that can be characterized using the matrix exponential.
Preliminaries
- The paper’s objective is a betweenness measure based on all walks connecting a node pair and passing through a third node.The measure uses the communicability function to account for the walks through that node.Source: Preliminaries · pp. 5–6
- Pairwise communicability weights walks of different lengths, with the weighting used here linked to the adjacency-matrix exponential.The paper describes this communicability as having a physical interpretation involving a continuous-time quantum walk.Source: Preliminaries · pp. 5–6
- Communicability betweenness (CBC) measures the weighted sum of walks between node pairs that involve the node being scored.The paper introduces CBC as a node-level extension of communicability between pairs.Source: Preliminaries · pp. 6–7
- The paper states that CBC can be characterized neatly in terms of the matrix exponential.Its normalization factor is described as making the score range from zero to one.Source: Preliminaries · p. 7
Communicability betweenness
Communicability betweenness (CBC) assesses a node through the communicabilities between node pairs when that node’s incident edges are removed. The measure is bounded between zero and one and reaches its upper bound at the central hub of a star.
Communicability betweenness
- CBC compares pairwise communicabilities after removing a node’s incident edges with the original communicabilities, aggregating the changes over node pairs.The paper considers connected graphs and gives a matrix-exponential characterization.Source: Communicability betweenness · p. 7
- CBC lies between 0 and 1, and its upper bound occurs at a star’s central hub, the desired behavior for a betweenness measure.The normalization gives the star’s central node a value of 1.Source: Communicability betweenness · pp. 7–8
- CBC increases in any graph when a node is given an extra edge.Source: Communicability betweenness · p. 8
- The matrix exponential can be approximated with a terminating high-accuracy algorithm, while sparse-network efficiency depends on the sparsity structure.The stated operation count for computing CBC for all nodes scales like 4 n.Source: Communicability betweenness · pp. 8–9
Communicability betweenness and the Fréchet derivative
The paper relates CBC to the Fréchet derivative of the matrix exponential under a specific perturbation direction. This relation also connects CBC to weighted walks through a node.
Communicability betweenness and the Fréchet derivative
- The Fréchet-derivative entry, scaled by the paper’s factor, is at least twice the weighted number of walks between two nodes that involve the selected node.Length-two and length-three terms correspond to walks involving that node; for longer walks, the relation is less simple.Source: Communicability betweenness and the… · p. 10
- The derivative can exceed that weighted-walk quantity because walks that revisit the selected node contribute extra terms, generally with small weights when they are long.Source: Communicability betweenness and the… · p. 10
- In the illustrative eight-node graph, the ratio of the derivative entry to the corresponding communicability quantity ranges from 2.08 to 2.96.Source: Communicability betweenness and the… · p. 10
- CBC is closely related to the limiting sensitivity of the matrix exponential when the adjacency matrix is perturbed in the direction that removes a node’s incident edges.The relationship hinges on that particular perturbation direction.Source: Communicability betweenness and the… · pp. 9–10
Analysis of the communicability betweenness
Across the tested networks, CBC differs from other betweenness measures in ways that can change individual node rankings. Its correlations with other measures do not reliably predict CBC values, supporting its characterization as an independent measure of node betweenness.
Analysis of the communicability betweenness
- In network 1, CBC ranks X above C; in network 2, it ranks C only slightly below A, reflecting their different roles in shorter and within-clique walks.Source: Analysis of the communicability… · p. 11
- In network 3, both CBC and random-walk betweenness rank A highest, but CBC ranks D second and assigns little significance to C, unlike random-walk betweenness.The authors explain that C occurs in relatively long walks, which CBC down-weights.Source: Analysis of the communicability… · p. 11
- In the early-15th-century Florence marriage network, all four betweenness measures identify Medici as most central; communicability betweenness correlates more strongly with random-walk (r^2 = 0.964) than shortest-path betweenness (r^2 = 0.935).Source: Analysis of the communicability… · pp. 11–12
- In Florence, random-walk betweenness ranks Strozzi fourth while CBC ranks it sixth; CBC also distinguishes four less-central families in the order Acciaiuoli, Lamberteschi, Ginor, Pazzi.The other betweenness measures and degree centrality do not differentiate those four families.Source: Analysis of the communicability… · p. 12
- For the E. coli transcription network, CBC’s correlation with degree is 0.864 but its relative prediction error is 95.8%, as one extreme node pulls the fitted line.Source: Analysis of the communicability… · p. 13
- CBC’s average correlations with other betweenness measures range from 0.44 for flow betweenness to 0.78 for random-walk betweenness, while relative prediction errors exceed 60% in all cases, reaching 102.8 for FBC.Source: Analysis of the communicability… · p. 14
Betweenness in a protein interaction network
In the E. coli protein-interaction network, communicability betweenness identifies conserved proteins effectively, especially among the most central proteins and across broader ranking cuts. Its results differ by comparison and ranking range, alongside distinct correlations with protein conservation.
Betweenness in a protein interaction network
- The E. coli network contains 695 validated interactions among 230 proteins, and conservation comparisons draw on searches across 148 genomes.The passage reports that Butland et al. used BLAST to search for homologues across those genomes.Source: Betweenness in a protein interaction… · p. 14
- Communicability betweenness identifies more than 5 conserved proteins per non-conserved one in the top third, versus flow betweenness’s 2, and ranks second best in the bottom third.Source: Betweenness in a protein interaction… · p. 15
- Communicability betweenness has the same 0.24 Pearson correlation with conserved-genome count as degree, compared with 0.22 for random-walk, 0.15 for shortest-path, and 0.11 for flow betweenness.The paper relates this analysis to Butland et al.’s observation of a positive association between protein degree and the number of genomes in which a homolog appears.Source: Betweenness in a protein interaction… · p. 15
- Communicability-betweenness rankings have the largest average number of genomes among the top 20 proteins, with the same pattern reported for top-30 and top-40 rankings.The authors conclude that this measure performs best at identifying proteins conserved in the largest number of genomes.Source: Betweenness in a protein interaction… · p. 15
- With highly conserved defined as appearing in at least 95 of 148 genomes, random-walk and communicability betweenness each identify 54 of 76 in the top third; communicability identifies 95 of 152.Source: Betweenness in a protein interaction… · p. 16
Conclusion
The conclusion presents communicability betweenness as both a measure related to changes in the adjacency-matrix exponential and a measure of node relevance in real-world networks. It argues that centrality measures capture different topological aspects rather than establishing one universally best measure.
Conclusion
- The conclusion cautions that no centrality measure is universally best or worst because measures capture different aspects of a node’s topological relevance.A measure may summarize one network feature well and another poorly.Source: Conclusion · p. 16
- Communicability betweenness measures changes in the adjacency-matrix exponential under a perturbation and is closely related to its instantaneous rate of change.The conclusion also connects the measure to a node’s communicability sensitivity when its edges undergo infinitesimal changes, including in weighted-edge graphs.Source: Conclusion · pp. 16–17
- The authors report that communicability betweenness accounts for important topological characteristics of nodes in real-world complex networks and argue that the concept has value for centrality studies.They state that the measure is amenable to theoretical analysis and testing on real complex networks.Source: Conclusion · pp. 16–17
Appendix
The appendix explains how the walk expansion counts visits to a specified node and notes that repeated visits affect only longer walks. Its factorial scaling downweights the resulting multiplicities.
Appendix
- For walks of length k involving node r, the appendix states that each walk is counted twice, while a walk involving r d times is counted d times in the underlying count.The appendix illustrates repeated visits with a walk that passes through r twice.Source: Appendix · p. 18
- The multiplicity effect arises only for walks of length four or greater; walks of length two or three cannot involve r more than once.This is why the appendix characterizes the effect as relatively minor.Source: Appendix · p. 18
- The k! scaling in the expansion downweights multiplicities for walks that revisit r.The appendix describes this scaling as reducing the contribution of those repeated-node counts.Source: Appendix · p. 18