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

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.