Distance backbones optimize spreading dynamics and centrality ranks in the sparsification of complex networks
Open Access
- 3 November 2026
- journal article
- research article
- Published by Public Library of Science (PLoS) in PLOS Complex Systems
- Vol. 3 (11) , e0000137
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 ) = ( x 3 + y 3 ) 3 , which removes more than half of the edges from the empirical networks studied.Keywords
Funding Information
- Fundação para a Ciência e a Tecnologia (2022.09122.PTDC)
- U.S. National Library of Medicine (01LM011945-01)
- HORIZON EUROPE Reforming and enhancing the European Research and Innovation system (101186558)
This publication has 35 references indexed in Scilit:
- A generalized fuzzy k-nearest neighbor regression model based on Minkowski distanceGranular Computing, 2021
- Centralities in Complex Networks2021
- Interaction data from the Copenhagen Networks StudyScientific Data, 2019
- Distance closures on complex networksNetwork Science, 2015
- Data on face-to-face contacts in an office building suggest a low-cost vaccination strategy based on community linkersNetwork Science, 2015
- Immunization strategies for epidemic processes in time-varying contact networksJournal of Theoretical Biology, 2013
- Robust classification of salient links in complex networksNature Communications, 2012
- What's in a crowd? Analysis of face-to-face behavioral networksJournal of Theoretical Biology, 2011
- SPREADING OF EPIDEMIC PROCESSES LEADING TO FRACTAL STRUCTURES1986
- A New Status Index Derived from Sociometric AnalysisPsychometrika, 1953