Quantifying edge relevance for epidemic spreading via the semi-metric topology of complex networks

Abstract

Sparsification aims at extracting a reduced core of associations that best preserves both the dynamics and topology of networks while reducing the computational cost of simulations. We show that the semi-metric topology of complex networks yields a natural and algebraically-principled sparsification that outperforms existing methods on those goals. Weighted graphs whose edges represent distances between nodes are semi-metric when at least one edge breaks the triangle inequality (transitivity). We first confirm with new experiments that the metric backbone-a unique subgraph of all edges that obey the triangle inequality and thus preserve all shortest paths-recovers susceptible-infected dynamics over the original non-sparsified graph. This recovery is improved when we remove only those edges that break the triangle inequality significantly, i.e. edges with large semi-metric distortion. Based on these results, we propose the new semi-metric distortion sparsification method to progressively sparsify networks in decreasing order of semi-metric distortion. Our method recovers the macro- and micro-level dynamics of epidemic outbreaks better than other methods while also yielding sparser yet connected subgraphs that preserve all shortest paths. Overall, we show that semi-metric distortion overcomes the limitations of edge betweenness in ranking the dynamical relevance of edges not participating in any shortest path, as it quantifies the existence and strength of alternative transmission pathways.

Keywords: distance backbone; epidemic dynamics; network sparsification; semi-metric distortion.

Figure 1.

Schematic representation of the construction of synthetic networks with tunable relative size of the backbone τ^m and semi-metric distortion distribution $P(s^m)$. The first step consists of setting the (connected) metric backbone of a synthetic network. This metric backbone is fully characterized by the number of nodes N, the number of edges E_m and the proximity matrix B containing the weights of associations. The next step involves computing the distance closure matrix ${\mathbf{\text{D}}}^{\text{T,m}}$, a graph of the same node set N, whose edge weights denote the shortest distance (length of shortest path) between every pair of nodes. Finally, we generate a synthetic network by adding E_sm edges, whose value is computed according to equation (7) in the Methods section, to obtain a desired relative backbone size τ^m. The semi-metric distortion values of the added edges $s_{ij}^m$ are drawn from the target distribution $P(s^m)$. Finally, the resulting proximity matrix P is obtained by applying equations (3) and (6) in Methods section to each $s_{ij}^m$ value.

Figure 2.

Panel (a): ratio between the time for the disease to reach half the population in the metric backbone and in the constructed network ${\xi }_{1/2}^B$ as a function of the parameter µ, i.e. the logarithm of the median of the semi-metric distortion distribution, and the relative size of the backbone τ^m (color code). For a given seed, we compute the time to reach half the population $t_{1/2}$ as the median value observed across 200 realizations of the SI dynamics. Dots show the average and error bars represent the standard deviation of the ratios obtained for 50 different infectious seeds. Panel (b): average time of infection of each individual i in the metric backbone $t_i^B$ as a function of its average time of infection in the entire network t_i for different values of the relative size of the backbone τ^m (color code). These results are obtained by averaging 200 realizations starting from the same initial seed. In both panels, we set β = 0.5 for the SI dynamics, fix σ = 1 in the semi-metric distortion distribution and consider the metric backbone B of a network capturing face-to-face interactions in a elementary school in the US [47].

Figure 3.

Ratio between the time for the disease to reach half the population in the sparsified network and in the original synthetic network ${\xi }_{1/2}^x$ as function of the parameter governing the size of the sparsified network χ for each sparsification method x (color code). χ ranges from χ = 1, corresponding to not removing any edge, to χ = 0 where E_sm edges are removed. Three different sparsification methods are compared: targeting edges with highest semi-metric distortion values (SMDS), lowest effective resistance values (EffRes) or lowest proximity values (W). The details of the simulations to obtain the ratios are the ones described for figure 2(a). EffRes and W curves are interrupted when breaking the largest connected component of the network. Insets: Number of components in the network as a function of the edges removed χ and the sparsification method (color code). The horizontal dashed line represents the SMDS, which always preserves the largest connected component. The original synthetic networks are constructed considering ${\tau }^m=0.1$ and µ = 1 (panel (a)) or µ = 2 (panel (b)) respectively.

Figure 4.

Panel (a): ratio between the time for the disease to reach half the population in the sparsified network and in the original synthetic network ${\xi }_{1/2}^x$ as a function of the parameter χ, governing the edges removed from the network, and the sparsification method x (color code). The contact network corresponds to face-to-face interactions recorded in an elementary school students (kindergarten to sixth grade) in Utah (USA) [47]. The details of the simulations to obtain the ratios are the ones described for figure 2(a). Panel (b): distribution of the relative difference ${\widetilde{\mathrm{\Delta }\xi }}_{1/2}^x$ between the mean ratio associated to each sparsification method x (color code) and SMDS as a function of the size of the sparsified network χ, for all emprical networks. Positive ${\widetilde{\mathrm{\Delta }\xi }}_{1/2}^x$ values reveal a better performance of SMDS with respect to the sparsification method x. Dots represent each of the 16 networks included in the dataset under study whereas solid lines show the median ${\widetilde{\mathrm{\Delta }\xi }}_{1/2}^x$ value observed across networks for each sparsification method x. Panel (c): fraction of disconnected networks in the dataset of real networks f^x as a function of the size of the sparsified network χ and the sparsification method x (color code). In panels (b) and (c), the horizontal dashed line represents the values obtained for the SMDS.