EconPapers    
Economics at your fingertips  
 

Distance backbones optimize spreading dynamics and centrality ranks in the sparsification of complex networks

Bernardo Pereira, Felipe Xavier Costa and Luís M Rocha

PLOS Complex Systems, 2026, vol. 3, issue 11, 1-18

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.

Date: 2026
References: Add references at CitEc
Citations:

Downloads: (external link)
https://journals.plos.org/complexsystems/article?id=10.1371/journal.pcsy.0000137 (text/html)
https://journals.plos.org/complexsystems/article/f ... 00137&type=printable (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:plo:pcsy00:0000137

DOI: 10.1371/journal.pcsy.0000137

Access Statistics for this article

More articles in PLOS Complex Systems from Public Library of Science
Bibliographic data for series maintained by complexsystem ().

 
Page updated 2026-11-08
Handle: RePEc:plo:pcsy00:0000137