The distance backbone of complex networks
arXiv:2103.04668 · doi:10.1093/comnet/cnab021
Abstract
Redundancy needs more precise characterization as it is a major factor in the evolution and robustness of networks of multivariate interactions. We investigate the complexity of such interactions by inferring a connection transitivity that includes all possible measures of path length for weighted graphs. The result, without breaking the graph into smaller components, is a distance backbone subgraph sufficient to compute all shortest paths. This is important for understanding the dynamics of spread and communication phenomena in real-world networks. The general methodology we formally derive yields a principled graph reduction technique and provides a finer characterization of the triangular geometry of all edges -- those that contribute to shortest paths and those that do not but are involved in other network phenomena. We demonstrate that the distance backbone is very small in large networks across domains ranging from air traffic to the human brain connectome, revealing that network robustness to attacks and failures seems to stem from surprisingly vast amounts of redundancy.
To appear in the Journal of Complex Networks
References in corpus (25)
- Statistical mechanics of complex networks
- Community structure in social and biological networks
- Community detection in graphs
- Power-law distributions in empirical data
- Finding community structure in networks using the eigenvectors of matrices
- The structure of scientific collaboration networks
- The architecture of complex weighted networks
- Evolution of networks
- Who is the best connected scientist? A study of scientific coauthorship networks
- Powerlaw: a Python package for analysis of heavy-tailed distributions
- Extracting the multiscale backbone of complex weighted networks
- Reaction-diffusion processes and metapopulation models in heterogeneous networks
- High-resolution measurements of face-to-face contact patterns in a primary school
- A High-Resolution Human Contact Network for Infectious Disease Transmission
- Weighted evolving networks: coupling topology and weights dynamics
- Computational fact checking from knowledge networks
- General Dynamics of Topology and Traffic on Weighted Technological Networks
- Simplicial complexes and complex systems
- Control of complex networks requires both structure and dynamics
- Network Transitivity and Matrix Models
- Mining social media data for biomedical signals and health-related behavior
- Nonlocal evolution of weighted scale-free networks
- City-wide Analysis of Electronic Health Records Reveals Gender and Age Biases in the Administration of Known Drug-Drug Interactions
- Uncovering protein interaction in abstracts and text using a novel linear model and word proximity networks
- Semi-metric Behavior in Document Networks and its Application to Recommendation Systems