The Physics of Communicability in Complex Networks
arXiv:1109.2950 · doi:10.1016/j.physrep.2012.01.006
Abstract
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.
Review Article. 90 pages, 14 figures. Contents: Introduction; Communicability in Networks; Physical Analogies; Comparing Communicability Functions; Communicability and the Analysis of Networks; Communicability and Localization in Complex Networks; Computability of Communicability Functions; Conclusions and Prespectives
References in corpus (15)
- Modularity and community structure in networks
- Finding community structure in networks using the eigenvectors of matrices
- Cooperative Game Theory Approaches for Network Partitioning
- Statistical physics of social dynamics
- Resolution limit in community detection
- Communicability in complex networks
- Statistical-mechanical approach to subgraph centrality in complex networks
- Communicability Betweenness in Complex Networks
- Communicability Graph and Community Structures in Complex Networks
- Disassortative mixing in online social networks
- Fast matrix computations for pair-wise and column-wise commute times and Katz scores
- Communicability and multipartite structures in complex networks at negative absolute temperatures
- Netons: Vibrations of Complex Networks
- What do we learn from correlations of local and global network properties?
- Return probability and k-step measures
Cited by in corpus (59)
- The structure and dynamics of multilayer networks
- Diffusion dynamics on multiplex networks
- Random walks and diffusion on networks
- Optimally controlling the human connectome: the role of network topology
- Fundamentals of spreading processes in single and multilayer complex networks
- Network Geometry
- Network Analysis of Particles and Grains
- Spectral entropies as information-theoretic tools for complex network comparison
- On the limiting behavior of parameter-dependent network centrality measures
- Functional complexity emerging from anatomical constraints in the brain: the significance of network modularity and rich-clubs
- Communicability reveals a transition to coordinated behavior in multiplex networks
- Models of communication and control for brain networks: distinctions, convergence, and future outlook
- Division of labor, skill complementarity, and heterophily in socioeconomic networks
- How structure sculpts function: unveiling the contribution of anatomical connectivity to the brain's spontaneous correlation structure
- Beware of the Small-World neuroscientist!
- Laplacian paths in complex networks: information core emerges from entropic transitions
- A general centrality framework based on node navigability
- Ranking influential nodes in networks from partial information
- Green's function approach for quantum graphs: an overview
- A literature survey of matrix methods for data science
- Polarization and multiscale structural balance in signed networks
- Walk modularity and community structure in networks
- Multiple abrupt phase transitions in urban transport congestion
- Quantum-like states on complex synchronized networks
- The multilayer architecture of the global input-output network and its properties
- A novel framework to analyze complex network dynamics
- Communicability Angles Reveal Critical Edges for Network Consensus Dynamics
- An integrative dynamical perspective for graph theory and the study of complex networks
- Smart random walkers: the cost of knowing the path
- Analytic relationship of relative synchronizability to network structure and motifs
- Thermodynamics of network model fitting with spectral entropies
- Exploring the "Middle Earth" of Network Spectra via a Gaussian Matrix Function
- Communication cliques in mobile phone calling networks
- Null-eigenvalue localization of quantum walks on real-world complex networks
- Discriminating Power of Centrality Measures
- Real-Space Visualization of Quantum Phase Transition by Network Topology
- Towards a class of complex networks models for conflict dynamics
- Gendered Networks and Communicability in Medieval Historical Narratives
- A Fast Monte Carlo algorithm for evaluating matrix functions with application in complex networks
- Characterising heavy-tailed networks using q-generalised entropy and q-adjacency kernels
- Potential gain as a centrality measure
- Interdependent evolution of robustness, force transmission and damage in a heterogeneous quasi-brittle granular material: from suppressed to cascading failure
- Machine Learning Analysis of Complex Networks in Hyperspherical Space
- Exact rank-reduction of network models
- Vertex distinction with subgraph centrality: a proof of Estrada's conjecture and some generalizations
- Approximation of functions of large matrices with Kronecker structure
- Node seniority ranking
- Functional brain networks: great expectations, hard times, and the big leap forward
- Decision-Making Frameworks for Network Resilience -- Managing and Mitigating Systemic (Cyber) Risk
- Finding community structure using the ordered random graph model
- Communicability Angle and the Spatial Efficiency of Networks
- Hybrid evolving clique-networks and their communicability
- New results and open problems on subgraph centrality
- Network topology transition at criticality
- Thermodynamic stability and structural transitions in virus-host networks
- Low, high and very-high density forms of liquid water revealed by a medium-range order descriptor
- Accounting for the Role of Long Walks on Networks via a New Matrix Function
- Correlation-Weighted Communicability Curvature as a Structural Driver of Dengue Spread: A Bayesian Spatial Analysis of Recife (2015-2024)
- Maximum walk entropy implies walk regularity