Distance backbones optimize spreading dynamics and centrality ranks in the sparsification of complex networks
- 1Dipartimento di Scienze Matematiche, Politecnico di Torino, Turin, Italy
- 2Universidade Católica Portuguesa, Católica Medical School, Católica Biomedical Research Centre, Lisbon, Portugal
- 3School of Systems Science and Industrial Engineering, Binghamton University (State University of New York), Binghamton, New York, United States of America
Abstract
Detailed network models of social, biological, and other complex systems are often dense, which increases their computational complexity in simulations and analyses. To address this computational challenge, graph sparsification is used to remove edges while preserving desired network properties. For instance, distance backbones of weighted graphs are very sparse graphs that preserve community structure and spreading dynamics. Such backbones omit original graph edges that break a generalized triangle inequality for any given path-length measure and preserve all shortest paths of weighted graphs. They also best preserve node centrality ranks, as well as local and global dynamics in spreading phenomena. This superior performance of backbones is found by introducing the distance backbone synthesis (DBS), which progressively sparsifies weighted graphs according to a general family of nested distance backbones, whereby each edge is associated with the smallest distance backbone in which it appears. DBS provides a principled and natural method to span all ranks of sparsification possible while preserving connectivity, which allows for the precise study of (directed and undirected) weighted graph sparsification under multi-objective criteria. It provides an algebraically principled explanation of edge importance by revealing the precise topological space associated with each edge. The theory is demonstrated with a battery of social contact networks obtained from real-world social activity in different scenarios. This study also shows that the optimal preservation of node centrality and spreading dynamics happens for the distance backbone that obeys the generalized triangle inequality for the path-length measure g(x,y)=(x3+y3)3, which removes more than half of the edges from the empirical networks studied. Author summary: Detailed complex systems models, from social networks to biological interactions, are often represented as dense networks that are challenging to analyze. This can be overcome by using sparsification methods, which simplify dense networks to their essential components, like an X-ray view of a transportation network that keeps the essential routes for navigation. Our research systematically compares the ability of different methods to preserve structural and dynamical network features, and we introduce a novel approach to studying sparsification via distance backbone synthesis (DBS). This new approach provides a principled explanation of why certain connections are crucial, offering valuable insights for applications ranging from epidemic forecasting to understanding social influence. Most importantly, DBS identifies optimal network backbones, which not only speed up analysis and simulation but are also scalable and exact sparsification of networks. Such backbones can be achieved by removing more than half of all connections, those that have alternative shorter paths.
Related
- DISCCO: Distance-Based Bayesian Spatial Clustering of Complex Objects with Node-Frailty Centrality
- Streaming Hypergraph Coloring via Palette Sparsification
- Layerwise Decoupling for Stable Structured Sparsification of Fully Connected Layers
- Convex Regression at Scale: Geometry-Preserving Constraint Sparsification
- Generic Machine Learning-Based Sparsification for Arc Flow Formulation of Combinatorial Optimization Problems
BibTeX
@article{pereira2026distance,
title = {{Distance backbones optimize spreading dynamics and centrality ranks in the sparsification of complex networks}},
author = {Bernardo Pereira and Felipe Xavier Costa and Luís M. Rocha},
journal = {PLOS Complex Systems},
year = {2026},
month = nov,
doi = {10.1371/journal.pcsy.0000137},
url = {https://journals.plos.org/complexsystems/article?id=10.1371/journal.pcsy.0000137},
note = {CC BY 4.0},
}
RIS
TY - JOUR
TI - Distance backbones optimize spreading dynamics and centrality ranks in the sparsification of complex networks
AU - Bernardo Pereira
AU - Felipe Xavier Costa
AU - Luís M. Rocha
PY - 2026
DA - 2026/11/03
JO - PLOS Complex Systems
DO - 10.1371/journal.pcsy.0000137
UR - https://journals.plos.org/complexsystems/article?id=10.1371/journal.pcsy.0000137
AB - Detailed network models of social, biological, and other complex systems are often dense, which increases their computational complexity in simulations and analyses. To address this computational challenge, graph sparsification is used to remove edges while preserving desired network properties. For instance, distance backbones of weighted graphs are very sparse graphs that preserve community structure and spreading dynamics. Such backbones omit original graph edges that break a generalized triangle inequality for any given path-length measure and preserve all shortest paths of weighted graphs. They also best preserve node centrality ranks, as well as local and global dynamics in spreading phenomena. This superior performance of backbones is found by introducing the distance backbone synthesis (DBS), which progressively sparsifies weighted graphs according to a general family of nested distance backbones, whereby each edge is associated with the smallest distance backbone in which it appears. DBS provides a principled and natural method to span all ranks of sparsification possible while preserving connectivity, which allows for the precise study of (directed and undirected) weighted graph sparsification under multi-objective criteria. It provides an algebraically principled explanation of edge importance by revealing the precise topological space associated with each edge. The theory is demonstrated with a battery of social contact networks obtained from real-world social activity in different scenarios. This study also shows that the optimal preservation of node centrality and spreading dynamics happens for the distance backbone that obeys the generalized triangle inequality for the path-length measure g(x,y)=(x3+y3)3, which removes more than half of the edges from the empirical networks studied. Author summary: Detailed complex systems models, from social networks to biological interactions, are often represented as dense networks that are challenging to analyze. This can be overcome by using sparsification methods, which simplify dense networks to their essential components, like an X-ray view of a transportation network that keeps the essential routes for navigation. Our research systematically compares the ability of different methods to preserve structural and dynamical network features, and we introduce a novel approach to studying sparsification via distance backbone synthesis (DBS). This new approach provides a principled explanation of why certain connections are crucial, offering valuable insights for applications ranging from epidemic forecasting to understanding social influence. Most importantly, DBS identifies optimal network backbones, which not only speed up analysis and simulation but are also scalable and exact sparsification of networks. Such backbones can be achieved by removing more than half of all connections, those that have alternative shorter paths.
SN - 2837-8830
ER -