The Physics of Communicability in Complex Networks

Ernesto Estrada; Naomichi Hatano; Michele Benzi

Source-linked AI summary

The Physics of Communicability in Complex Networks

Ernesto Estrada, Naomichi Hatano, Michele Benzi

arXiv:1109.2950v1Sep 13, 2011physics.soc-phcond-mat.stat-mechcs.SImath-ph

TL;DR

The paper addresses how to quantify correlation and information flow in complex networks when communication can use many routes rather than only shortest paths. It reviews communicability functions based on matrix functions and physical oscillator models, then surveys applications, locality, and sparse computation. The review shows that these measures support analyses of diverse network structures and processes while motivating efficient computation for large networks.

Problem
Quantitative measures are needed to characterize correlation and information flow between different parts of complex networks.
Method
The paper reviews communicability measures based on adjacency or Laplacian matrix functions, physical oscillator models, applications, locality, and computational methods.
Results
Communicability measures are used to analyze community structure, bipartivity, spreading, bottlenecks, social conflict, and network centrality.
Takeaways & Limitations
Accounting for all routes, with smaller weights for longer ones, provides a basis for studying correlation across biological, physical, and social networks.

Abstract

from arXiv · show

A fundamental problem in the study of complex networks is to provide quantitative measures of correlation and information flow between different parts of a system. To this end, several notions of communicability have been introduced and applied to a wide variety of real-world networks in recent years. Several such communicability functions are reviewed in this paper. It is emphasized that communication and correlation in networks can take place through many more routes than the shortest paths, a fact that may not have been sufficiently appreciated in previously proposed correlation measures. In contrast to these, the communicability measures reviewed in this paper are defined by taking into account all possible routes between two nodes, assigning smaller weights to longer ones. This point of view naturally leads to the definition of communicability in terms of matrix functions, such as the exponential, resolvent, and hyperbolic functions, in which the matrix argument is either the adjacency matrix or the graph Laplacian associated with the network. Considerable insight on communicability can be gained by modeling a network as a system of oscillators and deriving physical interpretations, both classical and quantum-mechanical, of various communicability functions. Applications of communicability measures to the analysis of complex systems are illustrated on a variety of biological, physical and social networks. The last part of the paper is devoted to a review of the notion of locality in complex networks and to computational aspects that by exploiting sparsity can greatly reduce the computational efforts for the calculation of communicability functions for large networks.

30322, USA

Complex networks support correlation effects that extend beyond immediate neighbors, motivating communicability as a network-based measure of how perturbations are felt across nodes.

Motivation: Complex network topology allows global correlation effects to extend beyond nearest neighbors.The paper contrasts one-dimensional chains with structures offering many alternative paths for correlation growth.
Applications: Examples across ecological, biological, infrastructural, and economic systems show local perturbations producing wider cascades of effects.Examples include species extinction, protein perturbation, power-grid failures, and economic crises.
Research problem: Understanding which topologies promote or disrupt correlation is presented as essential for analyzing complex systems in nature and society.The paper frames communicability as a tool for studying the structure and functioning of such systems.
Motivation: Social interactions are often described as correlated behavior among agents sharing groups or institutional environments.Examples include neighborhood effects, conformity, imitation, contagion, epidemics, and herd behavior.
Communicability: Communicability denotes situations in which a perturbation on one node is felt by the rest of the network with different intensities.Unlike shortest-path measures, it considers all possible routes, assigning greater weight to shorter ones.
Applications: Communicability measures support analyses including community detection, bipartivity, spreading processes, bottlenecks, social conflict, and subgraph centrality.The review also notes applications to complex-network structure at multiple analytical levels.

B. Correlation function

The paper connects network communicability with physical correlation functions and develops several matrix-based formulations, alongside applications and computational considerations.

B. Correlation function: Correlation functions quantify how a small disturbance propagates from one point of a system to another.The review discusses propagators and Green’s functions in classical and quantum settings.
B. Correlation function: Quantum evolution uses a Hamiltonian-based time propagator, while thermal correlation uses a Gibbs density operator at inverse temperature β.The thermal Green’s function describes disturbance propagation through a system in a thermal bath.
Physical interpretations: Classical and quantum oscillator models combined with adjacency- and Laplacian-based formulations produce four communicability versions.The paper compares these versions and applies them across microscopic, mesoscopic, macroscopic, and multiscale network analyses.
Computational aspects: Computing communicability for large networks is costly, but exploiting adjacency-matrix sparsity can improve computational efficiency.The paper reviews computational approaches and emphasizes algorithmic efficiency for large networks.
B. Correlation function: Network communicability is defined as a weighted sum of all walks between two nodes, with shorter walks receiving greater weight.The adjacency matrix powers count walks of each length, and factorial penalization yields the exponential matrix function.
B. Correlation function: The shortest paths contribute most strongly, but the communicability function still accounts for every communication channel between two nodes.This combines path-length weighting with the multiplicity of longer walks.

B. Some combinatorial formulae

Combinatorial formulae connect communicability with graph structure, showing how it behaves on paths, complete graphs, random graphs, and regular graphs.

Paths: For the endpoints of a linear path, communicability tends to zero as the path length tends to infinity.This matches the intuition that increasingly distant endpoints communicate less strongly in a linear chain.
Complete graphs: For complete graphs, communicability between node pairs diverges as the number of nodes grows.The corresponding Estrada index has an analytic expression involving the graph size.
Random graphs: For Erdős-Rényi random graphs, the Estrada index has an asymptotic expression that holds almost surely as network size increases.The expression depends on the number of nodes and the link probability.
Regular graphs: Mean-variance plots for regular graphs form thread-like clusters whose members share triangle counts.Triangle counts strictly increase across clusters from left to right, starting at zero.
Regular graphs: The mean-variance plot can characterize the structure of regular graphs, and a similar pattern appears for a resolvent-like Estrada index.The latter version is derived from the paper’s resolvent formulation.

III. PHYSICAL ANALOGIES

The paper models complex networks as oscillator systems to give communicability a physical interpretation. Quantum thermal Green’s functions reproduce adjacency- and Laplacian-based communicability under stated oscillator and low-excitation assumptions.

Classical and quantum analogy: Each node is modeled as a mass and each link as a spring, with thermal disturbances propagating through the network.The model assumes no damping or external forces and includes springs to the ground in the adjacency-based Hamiltonian.
Classical and quantum analogy: The Laplacian Hamiltonian omits ground springs, so the network can undesirably move as a whole.The Laplacian is L = D − A, with node degrees on the diagonal of D.
Quantum oscillators: In the quantum treatment, orthogonal diagonalization transforms the oscillator Hamiltonian into decoupled normal modes.The analysis restricts each mode to the ground and first excited states when the mode spacing exceeds thermal, disturbance, and network-spring energy scales.
Quantum oscillators: Quantum thermal Green’s functions yield adjacency-based communicability through G^EA_pq = e^βG^A_pq.The identification uses βω² = Ω²; as β approaches zero, communicability vanishes, whereas as β approaches infinity it diverges.
Quantum oscillators: Both adjacency- and Laplacian-based quantum communicability functions correspond to thermal Green’s functions of quantum harmonic oscillators.The same physical correspondence is established for the classical functions in the classical oscillator treatment.

D. Network of Classical Oscillators

The classical oscillator formulation derives partition functions, centrality, and communicability from thermal correlations of node displacements. The resulting measures use adjacency- or Laplacian-based matrix expressions, with the Laplacian case requiring removal of its zero mode.

Classical formulation: Classical statistical mechanics treats momenta and coordinates as independent variables and evaluates the oscillator partition function by diagonalizing the adjacency matrix.A sufficiently large constant K makes the eigenvalues of K I − A positive, enabling the transformed integrations.
Classical formulation: The classical centrality index and communicability are obtained from thermal averages of node displacements.The communicability represents correlation between displacements caused by small thermal oscillations.
Laplacian formulation: The Laplacian-based classical expression uses the Moore–Penrose generalized inverse L+ because a connected Laplacian has a zero eigenvalue.The zero-eigenvalue mode is removed before obtaining the stated expression.
Classical formulation: Adjacency- and Laplacian-based classical communicability functions correspond to thermal Green’s functions of classical harmonic oscillators.This establishes the classical counterpart to the quantum oscillator interpretation.

IV. COMPARING COMMUNICABILITY FUNCTIONS

The paper compares four communicability functions on a 15-member office network and shows that their rankings can differ. The measures capture distinct aspects of coalition structure, vulnerability, and coordinated displacement responses.

Comparing measures: Four communicability functions are compared: two quantum measures and two classical measures, with no systematic rule for selecting one.The appropriate function depends on the particular problem under study.
Office network: The quantum and classical communicabilities are generally linearly related; Pearson correlation between E^A_pG and R^A_pG is 0.97.The office example uses normalized average communicability values for each individual.
Office network: E^A_pG is the only measure that ranks all six coalition members as having the largest average communicability.The highest communicability occurs between Pete–Lisa, Pete–Ann, and Ann–Lisa.
Office network: Emma’s relatively large communicability helped her resist coalition attacks, while Minna’s low communicability made her a vulnerable target.The analysis links these rankings to their observed positions during the office conflict.
Displacement correlations: Coalition members show small self-displacements and positive displacement correlations, whereas Emma is anticorrelated with the coalition and Minna with other office members.Emma is positively correlated with the president and some weaker members.
Temperature effects: Increasing temperature reduces Emma’s communicability gap with the coalition; at β = 0.1, she is surpassed only by Pete and Ann.The authors relate this change quantitatively to Emma consolidating her position during the crisis.

B. Study of biomolecular networks

The review applies communicability functions to protein networks to estimate atomic displacements and compare them with experimental B-factors across temperatures. Classical and quantum oscillator-based measures identify flexibility patterns, with temperature-dependent quantum communicability achieving stronger correlation within a reported range.

Protein-network construction: The lipase B network represents amino acids as nodes connected when their Cβ-atom distance is at most 7.0 Å.Glycine is represented using Cα instead of Cβ.
Atomic-displacement comparison: Classical atomic displacement correlates better with experimental B-factors than the quantum measure, although both overestimate flexibility near residues 250, 70, and 124.Experimental B-factors instead identify the region around residue 220 as having the largest atomic displacements.
Temperature dependence: The correlation between experimental B-factors and quantum communicability increases from 0.66 for β=1 to 0.75 for β=8, exceeding the classical value of 0.71.For β>8, the relationship between experimental and calculated B-factors becomes nonlinear.
Choice of communicability: Quantum communicability varies non-trivially with temperature, whereas the classical approach requires an empirical parameter and can be preferable for time-evolving networks.For evolving networks, classical communicability provides the appropriate penalization of walks across a sequence of times.

V. COMMUNICABILITY AND THE ANALYSIS OF NETWORKS

The review examines communicability and self-communicability across microscopic, mesoscopic, and macroscopic network scales. At the microscopic scale, subgraph-based measures identify essential proteins, with weighted variants and complex-aware extensions improving performance in yeast PPI networks.

Network scales: Microscopic analysis examines local topology around individual nodes and links, while mesoscopic and macroscopic analyses address clusters and whole-network properties.The review presents examples across all three scales.
Weighted PPI analysis: Weighted subgraph centrality produced the best performance across the analyzed PPI networks for identifying essential proteins.The weighted measure incorporates confidence scores based on experimental evidence and gene-ontology functional similarity.
Weighted PPI analysis: In the total PPI network, weighted subgraph centrality identified 53% of essential proteins among the top 10%, versus 44% for its unweighted version.In the high-reliability core, the corresponding values were 55% and 52%.
Complex-aware analysis: Harmonic centrality reached 70% classification performance for the top 200 ranked proteins in two yeast PPI networks.The networks contained experimentally identified or algorithmically identified protein complexes.

B. Mesoscopic analysis of networks

At the mesoscopic scale, communicability separates coordinated from discoordinated vibrations to define communities and supports overlapping or hierarchical community detection. Applications include karate-club and yeast PPI networks, but parameter selection and overlap control remain challenges.

Community definition: The communicability function decomposes into translational, coordinated, and discoordinated vibration contributions, with the latter subtracted.The coordinated and discoordinated terms define intra-cluster and inter-cluster communicability, respectively.
Community definition: Communities are subsets whose intra-cluster communicability exceeds inter-cluster communicability for most constituent nodes.The distinction corresponds to more coordinated than discoordinated vibrations within a community.
Overlapping communities: A communicability graph connects node pairs with positive communicability difference, after which overlapping communities are identified as cliques.Applied to the karate-club network, this method detected five communities, three highly overlapped.
Community-detection trade-offs: Hierarchical methods can address the large number of highly overlapped communities but lose the feature of community overlap.The review describes this as a trade-off between hierarchical organization and overlapping membership.
Algorithmic performance: The communicability-based approach achieved the best performance among compared non-traditional spectral clustering methods but was the slowest.Its parameters include inverse temperature, a short-cycle length bound, and a cycle-density threshold.
Biological application: Applied to yeast PPI data, the communicability algorithm identified modules containing proteins sharing one, two, or three functional categories.Examples include transport, transcription and protein binding, and metabolism, DNA processing, and cell rescue.

C. Macroscopic analysis of networks

Macroscopic communicability measures characterize global network robustness, structural change, granular-material deformation, brain-network alterations, and good-expansion properties. These applications connect spectral quantities to thermodynamic, mechanical, and neurological network behavior.

Robustness: Natural connectivity measures network robustness through the logarithm of average Estrada index and represents the free-energy change associated with removing all links.It is interpreted as the free energy gained from the network’s actual connectivity pattern.
Thermodynamic quantities: Entropy, total energy, and Helmholtz free energy are expressed using vibrational-state probabilities and energies derived from the network spectrum.The vibrational probability is p_j=e^-βE_j/EE, with E_j determined from adjacency eigenvalues.
Granular materials: Average subgraph centrality and network bipartivity reflect topology changes in granular materials under external strain.A weighted subgraph centrality based on normal contact-force magnitudes follows shear stress, while its drops coincide with increased dissipation energy.
Granular materials: Weighted subgraph centrality correlates strongly with nonaffine deformation and dissipation across spatial and temporal scales.The cited analysis covers both mesoscopic and macroscopic levels.
Brain networks: Communicability differentiated chronic stroke patients from controls using information from the contralesional hemisphere despite no gross structural pathology there.Reduced communicability occurred around lesions and in remote interconnected homologous regions.
Good expansion: The spectral scaling method classifies good-expansion networks by testing deviations from a line fit with slope η=0.5 and intercept log A.Networks lacking good-expansion properties show large deviations from the fit.

E. Communicability at negative absolute temperature

At negative absolute temperature, communicability emphasizes network structure associated with odd and even walks, enabling detection of quasi-bipartite clusters. In bipartite graphs, cross-partition pairs have negative communicability while same-partition pairs have positive communicability.

Negative inverse temperature makes eigenvectors associated with negative eigenvalues dominate communicability and identify quasi-bipartite clusters.The paper contrasts these contributions with positive-eigenvalue contributions associated with communities or quasi-cliques.
Negative-temperature communicability can be expressed using hyperbolic cosine and sine terms that separate even- and odd-length walks.The cosine term represents weighted even-length walks, while the sine term represents weighted odd-length walks.
For bipartite graphs, cross-partition node pairs have G^EA_pq(β<0)<0 because no even-length walks connect them.The absence of even-length walks between partitions makes the hyperbolic-sine contribution negative.
For bipartite graphs, same-partition node pairs have G^EA_pq(β<0)>0 because odd-length walks cannot connect them.Bipartite graphs contain no odd cycles, preventing odd-length connections within a partition.
The resulting methods adapt community-detection algorithms to identify network bipartitions, including in undirected real-world networks.The paper illustrates this approach on the protein–protein interaction network of A. fulgidus.

VI. COMMUNICABILITY AND LOCALIZATION IN COMPLEX NETWORKS

The paper interprets communicability decay as a form of locality in complex networks: fast decay indicates localization, whereas slow or absent decay indicates strong long-range connectivity. Network structure determines whether this interpretation and its computational benefits apply.

Fast off-diagonal decay in e^βH is interpreted as localization and weak long-range correlations, while slow decay indicates a strongly connected network.H may be either the adjacency matrix or the graph Laplacian.
Locality can reduce computational effort for matrix-function network properties, but decay is present only in some network classes.Regular lattices and highway networks are expected to show strong locality, whereas small-world networks generally are not.
In the 3015-node, 5156-link Internet AS network, the average normalized communicability is 4.07 × 10^-4, with 16.7% of pairs below 10^-13.Normalization makes the minimum communicability negligibly close to zero.
Communicability locality varies across networks: below 10^-6 for almost 30% of Colorado Springs IDU pairs versus 0.4% of corporate-director pairs.These differences are presented as information about the structural organization of the networks.
The Colorado Springs IDU network contains a central core dominating most communicability, identifying individuals who may be important campaign targets.The paper links this communicability concentration to central communication with the rest of the network.

B. Exponential decay in communicability

The paper derives exponential distance-decay bounds for adjacency- and Laplacian-based communicability and reviews sparse, quadrature-based computation. These bounds and algorithms depend on graph structure, temperature, and network size.

Off-diagonal communicability entries are bounded by C e^-τd_pq, where d_pq is shortest-path distance and C, τ depend on network properties.For adjacency-based bounds, increasing maximum degree increases C and slows decay.
For Laplacian-based communicability, the bound deteriorates as T→0 and off-diagonal decay disappears, while at T→∞ the entries vanish.The bounds therefore capture the limiting behavior at both zero and infinite temperature.
The adjacency-based bound increases with maximum degree and inverse temperature, while communicability tends to zero as temperature approaches infinity.Increasing inverse temperature corresponds to decreasing temperature.
The paper critically reviews computational approaches because eigendecomposition and common matrix-exponential implementations use O(n^2) storage and O(n^3) arithmetic without exploiting adjacency sparsity.The review aims to clarify appropriate and inappropriate methods for large complex networks.
Quadrature rules provide lower and upper bounds that tighten toward the true quantities as quadrature nodes are added.This supports estimating selected matrix-function entries without computing the full matrix exponential.

B. Numerical experiments

Numerical experiments compare matrix-exponential and eigendecomposition methods with quadrature-based estimates on increasing small-world networks. The quadrature approach becomes faster for sufficiently large graphs, with asymptotic behavior depending on size.

The experiments use small-world networks built from a four-neighbor ring with randomly added shortcuts and sizes from 1000 to 4000 nodes.Subgraph centralities are computed for all nodes and summed to obtain the Estrada index.
For networks larger than approximately 2000 nodes, the quadrature rule-based approach is systematically faster than the compared methods.The comparison uses eigendecomposition and Matlab's expm function as reference approaches.
For the tested relatively small sparse problems, quadrature computation time appears roughly linear in n because indexing and memory operations dominate.The expected quadratic growth becomes visible for sufficiently large graphs.
The inset experiments at n=1000, 5000, and 10000 indicate quadratic growth in computation time for sufficiently large graphs.The figure compares timings for expm, eigendecomposition, and five-iteration Lanczos trace estimates per node.

VIII. CONCLUSIONS AND PERSPECTIVES

The review presents communicability as a matrix-function framework grounded in all network walks, with physical interpretations and applications across complex systems. It highlights computational tools for sparse networks, locality analysis, and open questions for future research.

VIII. CONCLUSIONS AND PERSPECTIVES: Communicability between nodes or node sets supports community detection, bipartivity quantification, rumor-spread analysis, bottleneck identification, and social-conflict dynamics.The review also discusses centrality measures based on self-communicability for analyzing complex-network structure.
VIII. CONCLUSIONS AND PERSPECTIVES: Oscillator-network models, including classical and quantum-mechanical formulations, provide physical interpretations and insights into communicability.Negative absolute temperatures are presented as one example admitting an elegant interpretation for complex-network analysis.
VIII. CONCLUSIONS AND PERSPECTIVES: Communicability measures count walks between nodes, penalizing longer walks, and lead naturally to analytic functions of adjacency or Laplacian matrices.The reviewed measures are expressed through matrix power series and related matrix functions.
VIII. CONCLUSIONS AND PERSPECTIVES: Matrix-function knowledge and sparsity can reduce the effort required to compute communicability functions for large sparse networks.Bounds on matrix-function entries can also be used to investigate locality or its absence in network communicability.
VIII. CONCLUSIONS AND PERSPECTIVES: Communicability research has expanded rapidly and retains several open questions, with further issues expected to emerge across application fields.The review anticipates continued research and describes communicability as likely to become important in theoretical and practical network analysis.