Source-linked AI summary
Total communicability as a centrality measure
Michele Benzi, Christine Klymko
TL;DR
The paper asks whether row sums of the adjacency-matrix exponential provide a useful and scalable alternative for ranking important network nodes. It develops total communicability, compares it with subgraph centrality and related measures, and extends the idea to network-level connectivity. The results show that the rankings can differ substantially, while total communicability remains computationally attractive for very large networks.
Problem
Identifying important network nodes requires measures beyond local degree, while computing matrix-function entries for large networks can be expensive.
Method
The paper uses row sums of eA to define total communicability, interprets them through weighted walks, and evaluates them with synthetic and real-world networks.
Results
The two centrality measures can produce significantly different rankings, even among the top 1% of nodes and within the same network family.
Takeaways & Limitations
Total communicability captures information flow from a node to every node, can be estimated extremely quickly with Krylov methods, and its network sum measures connectivity.
Takeaways & Limitations
Agreement between exponential-based rankings is not generally predictable from spectral gap alone, and realistic complex networks can show weakly correlated rankings.
Abstract
from arXiv · showhide
We examine a node centrality measure based on the notion of total communicability, defined in terms of the row sums of the exponential of the adjacency matrix of the network. We argue that this is a natural metric for ranking nodes in a network, and we point out that it can be computed very rapidly even in the case of large networks. Furthermore, we propose the total sum of node communicabilities as a useful measure of network connectivity. Extensive numerical studies are conducted in order to compare this centrality measure with the closely related ones of subgraph centrality [E. Estrada and J. A. Rodriguez-Velazquez, Phys. Rev. E, 71 (2005), 056103] and Katz centrality [L. Katz, Psychometrica, 18 (1953), pp. 39-43]. Both synthetic and real-world networks are used in the computations.
1. Introduction.
The paper addresses how to rank important network nodes beyond local degree and computationally costly matrix-function entries. It studies row sums of eA as total communicability and compares this measure with related centralities.
- Node centrality seeks to identify the most important elements in a network, but degree centrality is limited because it is too local.More sophisticated measures incorporate global connectivity properties.
- Subgraph centrality uses diagonal entries of eA, but estimating these entries can be expensive for large adjacency matrices.Computing individual matrix-function entries remains costly even with advanced algorithms.
- Krylov-based matrix-function algorithms efficiently compute f(A)v for large sparse matrices using sparse matrix-vector products and O(n) storage.The exponential is a particularly important matrix function in this computational framework.
- For v = 1, the entries of f(A)1 are row sums of f(A), providing a node-wise quantity interpretable through subgraph centrality and communicability.The vector can instead be an external importance vector to incorporate intrinsic node contributions.
- The paper studies row sums of eA as node centrality, compares them with subgraph centrality, and introduces total network communicability as a connectivity measure.The analysis focuses on undirected networks and includes algorithmic and experimental comparisons.
2. Background and definitions.
The paper represents networks as graphs and adjacency matrices, with simple undirected graphs as its default setting. These definitions establish the matrix and connectivity concepts used in the centrality analysis.
- A graph consists of vertices V and edges E; edges are unordered in undirected graphs and ordered in directed graphs.The graph contains n = |V| vertices.
- A simple graph has no loops, no multiple edges, and unweighted edges; the paper generally studies simple undirected graphs.In directed graphs, nodes have distinct in-degree and out-degree.
- A walk is a sequence of adjacent vertices, while paths do not repeat vertices and closed walks start and end at the same vertex.A graph is connected when every vertex is reachable from every other vertex.
- The adjacency matrix records 1 when an edge exists and 0 otherwise.For undirected networks, the adjacency matrix is symmetric with zeros on its diagonal.
- For an undirected network, adjacency-matrix eigenvalues are real and are ordered λ1 ≥ λ2 ≥ . . . ≥ λn.For a connected graph, the largest eigenvalue is strictly greater than the second eigenvalue.
3. Diagonal entries vs. row sums.
Subgraph centrality counts weighted closed walks at a node, whereas total communicability sums weighted walks from that node to every node. The resulting rankings can differ, although spectral structure and graph type sometimes make them agree.
- Subgraph centrality of node i is [eA]ii, while [eA]ij measures subgraph communicability between nodes i and j.Larger subgraph centrality indicates a higher node ranking, and larger pairwise communicability indicates easier information flow.
- The exponential expansion weights walks of length k by 1/k!, and [Ak]ij counts walks of that length between nodes i and j.Subgraph centrality therefore counts weighted closed walks centered at node i.
- Total communicability is the ith row sum of eA, counting weighted walks from node i to every node, including itself.A node with high communicability to many nodes is treated as more important than one with low total communicability.
- The two centrality rankings generally differ because total communicability includes all walks from a node, whereas subgraph centrality includes only closed walks.Their relationship depends on the spectrum of A and the entries of its eigenvectors.
- Complete graphs, cycles, paths, and star graphs can yield identical rankings under the two measures.For large spectral gaps, both measures can be dominated by the leading eigenvector and produce similar rankings, especially for top nodes.
- The spectral-gap threshold for identical or approximately identical rankings is difficult to quantify, and substantial differences can occur even with relatively large gaps.This limits simple a priori predictions of ranking agreement.
4. Total network communicability.
The section defines total network communicability as the sum of node communicabilities, using C(A)=1T eA1 to measure ease of information exchange across a network. It discusses spectral bounds, parameterized extensions, and normalization choices for comparing networks.
- Definition and computation: The total communicability of each node measures how well it communicates with the other nodes, while their sum assesses communication effectiveness across the whole network.
- Definition and computation: Total network communicability C(A) is the sum of all entries of eA and measures the ease of sending information across a network.It can be computed without evaluating individual entries of eA, using efficient quadratic-form methods.
- Bounds: For undirected networks, C(A) admits bounds involving the Estrada index and spectral quantities, with equality cases including empty and complete graphs.The lower bound is attained by the empty graph, and the upper bound by the complete graph.
- Bounds: The same bounds apply to eβA for β > 0, and become tighter as β approaches 0+ for connected graphs.Here β is interpreted as an inverse temperature reflecting external disturbances on the network.
- Normalization: Normalized C(A) can compare the ease of information exchange across networks, but a complete-graph-based normalization may underflow on most sparse graphs.The experiments therefore normalize by n, the number of nodes; normalization by m produced the same rankings for the tested network.
5. Computational studies.
Computational studies compare rankings from subgraph centrality and total communicability across synthetic and real-world networks. Agreement varies substantially with network structure, while total network communicability distinguishes connectivity levels.
- Synthetic networks: Dense networks produce nearly identical subgraph-centrality and total-communicability rankings, with correlations near 1 and intersection distances near 0.This convergence occurs as connectivity increases in the tested synthetic networks.
- Synthetic networks: Sparse small-world networks show much weaker similarity between the two rankings than preferential-attachment networks.Their intersection distances are relatively large until increasing density strengthens agreement.
- Synthetic networks: 3.69e04 is the total communicability C(A) of a 5000-node ring lattice, while normalized C(A) rises from 7.4 to 9.7 when shortcut probability reaches p = 0.1.The values were averaged over 20 small-world networks for p = 0.1.
- Synthetic networks: In small-world graphs, low score ranges make shortcut-induced perturbations strongly affect rankings; larger d reduces these perturbations, unlike scale-free graphs with broadly spread scores.Regular rings provide no strict node ranking, whereas shortcut nodes become slightly more important after perturbation.
- Real-world networks: Real-world ranking correlations range from 0.007 for SNAP/ca-HepTh to 0.904 for SNAP/as-735, and five networks have identical top-1% rankings.The five exact matches are Zachary Karate Club, Drug User, Yeast PPI, Pajek/Erdos971, and SNAP/as-735.
- Real-world networks: Normalized total communicability varies widely: ca-HepTh and ca-GrQc reach 8.80e17 and 1.06e11, while Minnesota reaches only 14.13.These values indicate markedly different levels of information-sharing connectivity across the networks.
- Real-world networks: The two rankings can differ even among related networks, ranging from 0.122 for Erdos972 to 0.583 for Erdos971.The reported variation persists within subsets of the same Erdős collaboration network.
- Real-world networks: SNAP/as-735 has a large spectral gap and strongly correlated rankings, whereas Gleich/Minnesota has a tiny gap and very weakly correlated rankings.Intermediate networks can vary substantially, and spectral gap alone does not distinguish ranking behavior reliably.
6. Computational aspects.
Total communicability rankings require only the row sums of eA, enabling efficient matrix-function computations that avoid forming the full matrix exponential. Across tested networks, the Krylov implementation was fastest and scaled to a 4,189,503-node Wikipedia graph, although its rankings can differ substantially from subgraph centrality.
- Computational requirements: Only the row sums of eA are needed for total communicability rankings, whereas subgraph centrality requires diagonal entries of eA.The total-communicability computation applies eA to the all-ones vector rather than estimating individual matrix-exponential entries.
- Computational requirements: For many practical networks, a restarted Krylov method computes eA1 and C(A) = 1T eA1 with typical cost O(n).The method uses matrix-vector products with A and was implemented in the funm_kryl toolbox.
- Timing comparisons: Direct expm timings increase with network size but are also strongly affected by structural properties such as network diameter.For similarly sized yeast PPI and Minnesota road networks, computing the matrix exponential took almost 25 times longer for yeast, whose smaller diameter causes powers of A to fill in faster.
- Timing comparisons: For most tested networks, mmq estimated subgraph centrality faster than expm, while exceptions included small or high-diameter networks.The exceptions were Zachary Karate Club, Drug User, Erdos971, and Minnesota.
- Timing comparisons: The funm_kryl method was by far the fastest for all tested networks except the tiny Zachary Karate Club network.The comparison included direct expm computation, subgraph-centrality estimation with mmq, and total-communicability estimation with funm_kryl.
- Interpretation of rankings: Despite its computational advantage, total communicability cannot simply replace subgraph centrality because the two methods often produce different rankings.The paper therefore treats computational cost as an advantage without claiming equivalence of the resulting node rankings.
- Large-network computation: On a 4,189,503-node Wikipedia graph, funm_kryl obtained hub rankings in 216.7 seconds on 24 CPUs, demonstrating feasibility at large scale.The computation estimated the row-sum vector eA1 because the graph was too large for centrality measures based on estimating individual entries.
7. Resolvent-based centrality measures.
The resolvent replaces exponential walk weighting with geometric weighting controlled by α, but its centrality rankings and network-connectivity measure can differ substantially from exponential-based versions. Experiments show these differences depend on network type, graph parameters, and ranking depth.
- Resolvent formulation: The matrix resolvent (I −αA)−1 expands as I + αA + α^2A^2 + ···, weighting walks of length k by α^k.Its inverse exists and the series converges when α is appropriately bounded by the spectral radius.
- Resolvent formulation: Resolvent subgraph centrality counts closed walks, while resolvent total communicability counts all walks from a node to every network node.The resolvent therefore provides two related rankings based on diagonal entries and row sums of the same matrix function.
- Parameter choice: The resolvent requires choosing α, and different α values can produce different centrality rankings.The experiments use α = 0.85 scaled relative to λmax(A).
- Synthetic-network comparisons: For preferential-attachment networks, exponential rankings had correlation above 0.9 for every d ≥4 and exactly 1 for every d ≥8, whereas resolvent correlations increased more slowly.Resolvent intersection distances were also larger for all tested d, and no identical rankings occurred.
- Synthetic-network comparisons: For small-world networks, resolvent correlations were weaker than exponential correlations: at d = 1, correlation was 0.065 versus 0.177, and the highest tested resolvent correlation was 0.354 at d = 190.As d increased, exponential intersection distances eventually decreased, while resolvent distances did not show the same decline.
- Interpretation and limitations: Resolvent scores can compress when λmax(A) is large, making nodes difficult to distinguish and perturbations more consequential.This effect is less pronounced for networks with small maximum eigenvalues, such as Minnesota.
- Interpretation and limitations: For the top 1% of nodes, exponential subgraph-centrality and total-communicability rankings were much closer than their resolvent counterparts.The tested networks therefore showed greater agreement among top-ranked nodes under the exponential than under the resolvent.
- Interpretation and limitations: Resolvent total network communicability cannot reliably distinguish highly connected from poorly connected networks, unlike the exponential-based measure.The paper therefore recommends exponential total network communicability when comparing networks by ease of communication.
8. Conclusions.
The paper finds that total communicability and subgraph centrality often produce similar but not identical rankings, with the pattern depending on network and ranking level. Total communicability additionally offers a rapidly computable global connectivity measure for very large networks.
- Experimental conclusions: Preferential-attachment networks showed good agreement between total-communicability and subgraph-centrality rankings.The experiments also covered small-world networks and real-world social, citation, protein-interaction, and transportation networks.
- Experimental conclusions: For real-world networks, complete rankings were generally closer under the resolvent, but the top 1% matched more closely under the exponential.This pattern suggests stronger resolvent agreement among low-ranked nodes and stronger exponential agreement among highly ranked nodes.
- Interpretation: Total communicability incorporates all walks starting at a node, whereas subgraph centrality counts only closed walks, so the rankings can differ despite often remaining similar.Neither ranking scheme is universally better, and total communicability can provide complementary information.
- Computational significance: Krylov subspace methods can estimate total-communicability rankings extremely quickly, making row sums computationally feasible for very large networks where subgraph centrality is prohibitively expensive.The paper identifies this computational advantage as the main practical benefit of total communicability.
- Network-level measure: Total network communicability is introduced as a global measure of network connectivity and ease of information flow that can be computed quickly even for very large networks.The authors suggest it may be useful in communication-network design.