How to Thin a Network Without Tearing It express
A dense social network: everyone is connected to almost everyone else, and in this web it's hard to see who really matters. Too many threads — computers choke, simulations stall. Scientists have figured out how to prune such networks without losing what's essential.
The idea is to remove connections that don't participate in shortest paths. Imagine a city where you keep only the streets that are actually used, demolishing dead ends and redundant alleys. This 'skeleton' of the network preserves all important routes, as well as community structure and the dynamics of information or disease spread.
They tested it on real social contact networks — from schools, hospitals, and workplaces. It turned out that the variant that best preserves people's importance rankings and spreading dynamics uses a path measure defined by the formula g(x,y) = (\sqrt[3]{x}+\sqrt[3]{y})^3. This skeleton removes more than half of the links, yet the network keeps functioning as it should.
The result is not just a trimmed copy but an accurate map of the most heavily used pathways. This helps speed up epidemic models, find key players in social graphs, and understand where the network is fragile — where it's thin, it tears.
Original abstract
as written by the authors arXiv:2603.14564
Detailed network models of social, biological and other complex systems are often dense, which increases their computational complexity in simulations and analysis. To address this challenge, graph sparsification is used to remove edges while preserving desired network properties. Distance backbones of weighted graphs, which remove edges that break a generalized triangle inequality for any given path-length measure, preserve all shortest paths of weighted graphs. They have been shown to typically sparsify graphs more, as well as preserve community structure and spreading dynamics better than alternative state-of-the-art methods. Here, We show that they significantly best preserve node centrality ranks, as well as local and global dynamics in spreading phenomena. This is done by introducing the distance backbone synthesis (DBS) to progressively sparsify 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 sweep all degrees of sparsification possible while preserving connectivity, allowing us to precisely study (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. Our study also shows that the optimal preservation of node centrality and spreading dynamics happens for the distance backbone obeying the generalized triangle inequality for the path-length measure $$g(x, y) = (\sqrt[3]{x}+\sqrt[3]{y})^3$$, which removes more than half of the edges from the empirical networks studied.
In some real networks, after thinning, less than half of the links remained, yet the shortest paths between all pairs of nodes were fully preserved.