Analytical Computation of the Epidemic Threshold on Temporal Networks

Abstract

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.

Alternate abstract:

Plain Language 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.