The distance backbone of complex networks

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 (6)

• Power-law distributions in empirical data
• Finding community structure in networks using the eigenvectors of matrices
• Extracting the multiscale backbone of complex weighted networks
• Reaction-diffusion processes and metapopulation models in heterogeneous networks
• 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

Cited by in corpus (3)

• Effective Resistance for Pandemics: Mobility Network Sparsification for High-Fidelity Epidemic Simulation
• The distance backbone of directed networks
• Computing well-balanced spanning trees of unweighted networks