Analytical Computation of the Epidemic Threshold on Temporal Networks

The time variation of contacts in a networked system may fundamentally alter the properties of spreading processes and affect the condition for large-scale propagation, as encoded in the epidemic threshold. Despite the great interest in the problem for the physics, applied mathematics, computer science, and epidemiology communities, a full theoretical understanding is still missing and currently limited to the cases where the time-scale separation holds between spreading and network dynamics or to specific temporal network models. We consider a Markov chain description of the susceptible-infectious-susceptible process on an arbitrary temporal network. By adopting a multilayer perspective, we develop a general analytical derivation of the epidemic threshold in terms of the spectral radius of a matrix that encodes both network structure and disease dynamics. The accuracy of the approach is confirmed on a set of temporal models and empirical networks and against numerical results. In addition, we explore how the threshold changes when varying the overall time of observation of the temporal network, so as to provide insights on the optimal time window for data collection of empirical temporal networked systems. Our framework is of both fundamental and practical interest, as it offers novel understanding of the interplay between temporal networks and spreading dynamics.

Popular Summary

In today’s interconnected world, the dissemination of trends through social networks and the propagation of information or cyber viruses through digital networks are common phenomena. These processes are conceptually similar to the spread of infectious diseases among hosts since the dissemination of a spreading agent on a networked system is common to all of these phenomena. One critical problem underlying these situations is the characterization of the conditions leading to widespread dissemination of the agent, to be able to control it (e.g., for diseases) or to enhance it (e.g., for viral marketing). We propose a novel theoretical framework using a Markov description for the rigorous analytical derivation of the epidemic threshold for an arbitrary temporal network.

Scientifically, the computation of the critical spreading condition (called epidemic threshold) is not trivial since it depends on the contagion ability of the spreading agent but also, most importantly, on the structure of the underlying contact network and how it can change with time. Efforts have so far been limited to specific cases where one assumes that the temporal variation can be explicitly modeled. But what knowledge can be attained if we do not know the mechanistic temporal evolution of the network? We use data from three real social networks and build synthetic temporal networks from three models with between 100 and 10 000 nodes. We compute the value of the epidemic threshold, above which wide spreading occurs, for all networks, and we validate the accuracy of our predictions using numerical results. Our findings also allow us to assess the effect of a finite time window of observation of an empirical network, pointing to an optimal data-collection time for reaching an accurate prediction of the threshold.

Our mathematical modeling provides concrete insights for experiments and also a new theoretical perspective for the study of the interplay between network evolution and spreading dynamics.

Figure 1

Schematic example of the supra-adjacency matrix of the multilayer representation of the temporal network. For simplicity, we consider a network of two nodes $i,j$, and two time steps. The left panel represents the network as a sequence of static adjacency matrices. This is translated into a multilayer representation (right panel), where each node points to itself in the future and to the future image of its present neighbors.

Figure 2

Validation of the analytical method and comparison with microscopic numerical simulations. Top panel: Network models. Bottom panel: Empirical networks. Cross symbols represent $⟨i_{\mathrm{MC}}⟩$ as a function of $\lambda$ for two different values of $\mu$ ($\mu =0.2$ in blue and $\mu =0.5$ in red), i.e., the average prevalence obtained from the numerical solution of the Markov chain, Eq. (2). Circles represent $⟨i_{\mathrm{sim}}⟩$, i.e., the average prevalence obtained from stochastic microscopic numerical simulations of the SIS process, for the same values of $\mu$. The arrows indicate the analytical predictions of the threshold from Eq. (8) (one single realization of the network models is considered in each panel).

Figure 3

Epidemic threshold estimated from different period lengths. ${\lambda }_c(T)$ is the epidemic threshold computed by considering only the first $T$ snapshots of the network. For each panel, the blue (red) curve corresponds to $\mu =0.2$ ($\mu =0.5$), and its scale is reported on the left (right) side of the plot. The gray bar chart shows the mean network degree associated with the snapshot at time $T$. Bar charts are in linear scale, and min and max values are placed on the corresponding bars. For the empirical networks, the measure of the real time is also reported.