Backbone reconstruction in temporal networks from epidemic data

Many complex systems are characterized by time-varying patterns of interactions. These interactions comprise strong ties, driven by dyadic relationships, and weak ties, based on node-specific attributes. The interplay between strong and weak ties plays an important role on dynamical processes that could unfold on complex systems. However, seldom do we have access to precise information about the time-varying topology of interaction patterns. A particularly elusive question is to distinguish strong from weak ties, on the basis of the sole node dynamics. Building upon analytical results, we propose a statistically-principled algorithm to reconstruct the backbone of strong ties from data of a spreading process, consisting of the time series of individuals' states. Our method is numerically validated over a range of synthetic datasets, encapsulating salient features of real-world systems. Motivated by compelling evidence, we propose the integration of our algorithm in a targeted immunization strategy that prioritizes influential nodes in the inferred backbone. Through Monte Carlo simulations on synthetic networks and a real-world case study, we demonstrate the viability of our approach.

Figure 1

Illustration of a backbone network (a) along with three consecutive realizations of an RADN (b–d) at time $t=0,1,2$, respectively. Red dashed links are the strong ties in the backbone, and black solid links are temporal links generated from nodes' activity.

Figure 2

Empirical estimation of ${\mathcal{P}}_{j\to i}$ in a realization of an RADN with $n=200$ nodes, $\gamma =0.95, \lambda =0.9, \mu =0.1$, and $a_i=0.3$ for all nodes, over all the pairs of nodes $(i,j)\in V\times V$. The orange distribution relates to nodes that share a strong tie and the blue one to the opposite case. The backbone network is a 4-regular random graph. The network is simulated for $35000$ time steps. The figure suggests that conditioning on the state of node $j$ affects the infection probability for nodes that share a strong tie with $j$, confirming our analytical results. The red dotted line is the lower bound on ${\mathcal{P}}_{j\to i}$ in the presence of the strong tie $\{i,j\}$, computed using Eq. (4a).

Figure 3

Fraction of strong ties identified by our algorithm in the scenario with both homogeneous activity distribution and backbone degrees, for different values of the parameter $\gamma$. The backbone is a 4-regular network with 200 nodes. The other parameters are $\lambda =0.9, \mu =0.1$, and $a_i=0.3$, for all the nodes.

Figure 4

Fraction of strong ties correctly identified by our algorithm for both heterogeneous (“he”) and homogeneous (“ho”) activity distributions, and for homogeneous degree in the backbone. The backbone is a 4-regular network with $n=200$ nodes. The other parameters are $\gamma =0.95, \lambda =0.9$, and $\mu =0.1$. Three cases for the activity distribution are examined: all the nodes have the same activity $a_i=0.2$ (ho-low, dashed), $a_i=0.8$ (ho-high, dotted), and half the nodes have $a_i=0.2$ and half have $a_i=0.8$ (he, colored). For the last case of heterogeneous activities, the TPR curve is plotted with respect to links between nodes with low activity (blue), links between nodes of different activity (orange), and links between nodes with high activity (green). Only one FDR curve is plotted for all the cases, since they are practically indistinguishable (he, red).

Figure 5

Fraction of strong ties correctly identified by our algorithm for both heterogeneous (“he”) and homogeneous (“ho”) backbones, and homogeneous activities $a_i=0.3$, for all the nodes. The other parameters are $n=200, \gamma =0.95, \lambda =0.9$, and $\mu =0.1$. Three cases for the backbone are examined: all the nodes have the same low-degree $d_i=2$ (ho-low, dashed); all the nodes have the same high-degree $d_i=8$ (ho-high, dotted); and half the nodes have $d_i=2$ and half have $d_i=8$ (he, colored). For the last case of heterogeneous degrees, the TPR curve is plotted with respect to links between nodes with low degree (blue), links between nodes of different degree (orange), and links between nodes with high degree (green). Only one FDR curve is plotted for all the cases, since they are practically indistinguishable (he, red).

Figure 6

TPR (a, b) and FDR (c, d) of our algorithm implemented on a network of $n=300$ nodes with heterogeneity in both activity distribution and backbone degree, for an observation window of $T=10000$ time steps (a, c) or $T=30000$ time steps (a, c). Both activities and backbone degrees follow power-law distributions with exponents ${\beta }_a$ and ${\beta }_d$, respectively. Other parameters are set to $\lambda =0.9, \mu =0.1$, and $\gamma =0.5$. Each point is an average of ten independent simulations.

Figure 7

Monte Carlo estimation over 100 runs of the effect of randomized (orange) and targeted (blue) immunization on the fraction of infected nodes. Dotted lines indicate the fraction of infected nodes in the absence of any immunization technique. In (a), we show the entire realizations for $\gamma =0.95$. The solid line is the average, while the light band is one standard deviation. In (b), we compare the average fraction of infected nodes for different values of $\gamma$. Bands identify $95\%$ confidence intervals. Other parameters are $n=300, {\beta }_d={\beta }_a=-3, \lambda =0.9$, and $\mu =0.1$.

Figure 8

Difference in the fraction of infected nodes after the immunization phase, between the randomized and the targeted strategy (color coded) in the high-school case study [65]. The dashed line represents the epidemic threshold [56], below which none of the nodes is infected at the onset of the immunization strategy. Darker blue areas identify parameter regions where targeted immunization has superior outcome. Each point is an average of $1000$ independent simulations.