The metric backbone preserves community structure and is a primary transmission subgraph in contact networks

Abstract

The structure of social networks strongly affects how different phenomena spread in human society, from the transmission of information to the propagation of contagious diseases. It is well-known that heterogeneous connectivity strongly favors spread, but a precise characterization of the redundancy present in social networks and its effect on the robustness of transmission is still lacking. This gap is addressed by the metric backbone, a weight- and connectivity-preserving subgraph that is sufficient to compute all shortest paths of weighted graphs. This subgraph is obtained via algebraically-principled axioms and does not require statistical sampling based on null-models. We show that the metric backbones of nine contact networks obtained from proximity sensors in a variety of social contexts are generally very small, 49% of the original graph for one and ranging from about 6% to 20% for the others. This reflects a surprising amount of redundancy and reveals that shortest paths on these networks are very robust to random attacks and failures. We also show that the metric backbone preserves the full distribution of shortest paths of the original contact networks--which must include the shortest inter- and intra-community distances that define any community structure--and is a primary subgraph for epidemic transmission based on pure diffusion processes. This suggests that the organization of social contact networks is based on large amounts of shortest-path redundancy which shapes epidemic spread in human populations. Thus, the metric backbone is an important subgraph with regard to epidemic spread, the robustness of social networks, and any communication dynamics that depend on complex network shortest paths. Author summaryIt is through social networks that contagious diseases spread in human populations, as best illustrated by the current pandemic and efforts to contain it. Measuring such networks from human contact data typically results in noisy and dense graphs that need to be simplified for effective analysis, without removal of their essential features. Thus, the identification of a primary subgraph that maintains the social interaction structure and likely transmission pathways is of relevance for studying epidemic spreading phenomena as well as devising intervention strategies to hinder spread. Here we propose and study the metric backbone as an optimal subgraph for sparsification of social contact networks in the study of simple spreading dynamics. We demonstrate that it is a unique, algebraically-principled network subgraph that preserves all shortest paths. We also discover that nine contact networks obtained from proximity sensors in a variety of social contexts contain large amounts of redundant interactions that can be removed with very little impact on community structure and epidemic spread. This reveals that epidemic spread on social networks is very robust to random interaction removal. However, extraction of the metric backbone subgraph reveals which interventions--strategic removal of specific social interactions--are likely to result in maximum impediment to epidemic spread.