Source-linked AI summary
Communicability in complex networks
Ernesto Estrada, Naomichi Hatano
TL;DR
Shortest-path assumptions miss network transport that can follow longer routes, so the paper proposes a communicability measure that incorporates such paths. It finds distinct structure–dynamics classes, including networks where hubs communicate poorly, and uses communicability to identify communities.
Problem
Shortest-path analyses do not capture network transport that follows non-shortest routes, limiting descriptions of global communicability.
Method
The paper measures communicability from walk counts encoded by adjacency-matrix powers and defines communities through stronger within-group communicability.
Results
The analysis identifies three universality classes of complex networks, including networks whose hubs communicate poorly with one another.
Takeaways & Limitations
Communicability provides a network-wide basis for distinguishing structure–dynamics classes and identifying communities.
Takeaways & Limitations
The analysis ignores the diagonal elements of matrix L.
Abstract
from arXiv · showhide
Many topological and dynamical properties of complex networks are defined by assuming that most of the transport on the network flows along the shortest paths. However, there are different scenarios in which non-shortest paths are used to reach the network destination. Thus the consideration of the shortest paths only does not account for the global communicability of a complex network. Here we propose a new measure of the communicability of a complex network, which is a broad generalization of the concept of the shortest path. According to the new measure, most of real-world networks display the largest communicability between the most connected (popular) nodes of the network (assortative communicability). There are also several networks with the disassortative communicability, where the most "popular" nodes communicate very poorly to each other. Using this information we classify a diverse set of real-world complex systems into a small number of universality classes based on their structure-dynamic correlation. In addition, the new communicability measure is able to distinguish finer structures of networks, such as communities into which a network is divided. A community is unambiguously defined here as a set of nodes displaying larger communicability among them than to the rest of nodes in the network.
Communicability in complex networks
The paper generalizes network communicability beyond shortest paths by incorporating all walks between nodes, with longer walks contributing less. This measure is designed to capture non-shortest routes and structural bottlenecks more sensitively.
- Spectral formulation: The measure is derived from adjacency-matrix powers, which count walks between node pairs, and can be rewritten using the graph spectrum.The resulting quantity is called the communicability between nodes p and q.
- Generalized communicability: The proposed communicability accounts for all walks connecting nodes, rather than only the shortest path between them.Walks may revisit nodes and links, and the approach considers every route from the starting node to the target.
- Motivation: Non-shortest routes can carry communication, while shortest paths are relatively insensitive to structural bottlenecks.The number of walks changes significantly when such structural changes appear in a network.
- Walk weighting: Longer walks receive lower contributions than shorter walks in the communicability function.This decreasing weighting limits the influence of potentially very long detours.
Communicability as the Green’s function of networks
The paper interprets communicability as the network’s Green’s function through a spring-network model. This function describes how impacts, oscillations, or diffusing particles propagate between nodes.
- Spring-network formulation: A spring-network model connects the adjacency matrix A to node oscillations and the network’s Green’s function.Each link is represented by a spring, and node motion is analyzed through the resulting energy and Laplacian formulation.
- Physical interpretation: The correlation function describes how much the qth node oscillates when the pth node is shaken.This provides a physical interpretation of communicability as a response transmitted through the network.
- Green’s function: The resulting expression is the network’s Green’s function because it describes how an impact propagates from one place to another.The same function also characterizes particle diffusion across the network.
- Diffusion interpretation: For diffusion, the Green’s function describes how many particles reach node q when particles are placed at node p.This links communicability to transport between specific source and destination nodes.
- Implementation assumptions: The treatment subsequently ignores diagonal elements of the Laplacian and uses the adjacency matrix A for the total energy.This corresponds to adding springs between each node and the plane to cancel diagonal inhomogeneity, while restricting the analysis to = 1.
Degree-communicability correlations
Degree–communicability patterns classify networks into three structural-dynamic classes based on whether high-degree nodes communicate preferentially with one another or with low-degree nodes. Among 50 real-world networks, 38% were homogeneous assortative, 50% non-homogeneous assortative, and 12% non-homogeneous disassortative.
- Classification: Networks fall into three classes: homogeneous assortative, non-homogeneous assortative, or non-homogeneous disassortative communicability.The classification is based on degree–communicability patterns.
- Definitions: Assortative communicability means hubs communicate most strongly with other hubs, whereas disassortative communicability maximizes communication between hubs and low-degree nodes.In disassortative networks, communication among hubs and among low-degree nodes is poor.
- Real-world networks: 38%, 50% and 12% of 50 real-world networks belonged respectively to the three classes.The classes correspond to the categories represented in Fig. 1.
- Examples: The USA airport network exemplifies homogeneous assortative communicability because its lack of topological bottlenecks supports high inter-hub communicability.Its structural homogeneity produces the Class (a) pattern.
- Examples: Roget’s thesaurus exemplifies non-homogeneous assortative communicability: despite structural bottlenecks between clusters, hubs preferentially connect to other hubs.This corresponds to Class (b).
- Examples: Food webs and the final three social or biological examples display disassortative patterns when indirect routes or separated clusters reduce inter-hub communicability.In Class (c), the largest communicability occurs between a hub and a low-degree node; clustering alone does not explain the pattern.
Method of identifying network communities
The method identifies communities from communicability, or the thermal Green’s function, using spectral sign patterns to distinguish intra- from inter-community relations. It represents these relations as a signed complete graph and detects communities as maximal positive cliques, while also revealing overlaps and cohesiveness.
- Spectral basis: Communities are identified using communicability, or the Green’s function, through a spectral decomposition of the thermal Green’s function.Eigenvectors represent network-wide oscillation modes, and their sign patterns partition nodes into groups.
- Spectral basis: The sign of the product of eigenvector components indicates whether two nodes belong to the same cluster or different clusters.Positive contributions represent intra-cluster communicability, whereas negative contributions represent inter-cluster communicability after removing the largest-eigenvalue background mode.
- Signed-graph construction: By focusing on the sign of ΔG_pq, pairs with positive values are assigned to the same community and pairs with negative values to different communities.This pairwise classification represents the network as a signed complete graph.
- Clique-based detection: A community is defined as the largest possible positive clique in the signed complete graph, so detection reduces to finding maximal positive cliques.After rearranging the signed matrix, each community appears as a square positive sub-matrix.
- Overlaps and cohesiveness: The approach identifies overlapping communities, and the magnitude of ΔG_pq measures their cohesiveness.Larger ΔG_pq values indicate tighter relations between the corresponding community members.