Limitations of discrete-time approaches to continuous-time contagion dynamics

Free to Read

Limitations of discrete-time approaches to continuous-time contagion dynamics

Peter G. Fennell, Sergey Melnik, and James P. Gleeson

Phys. Rev. E 94, 052125 – Published 16 November 2016

Abstract

Continuous-time Markov process models of contagions are widely studied, not least because of their utility in predicting the evolution of real-world contagions and in formulating control measures. It is often the case, however, that discrete-time approaches are employed to analyze such models or to simulate them numerically. In such cases, time is discretized into uniform steps and transition rates between states are replaced by transition probabilities. In this paper, we illustrate potential limitations to this approach. We show how discretizing time leads to a restriction on the values of the model parameters that can accurately be studied. We examine numerical simulation schemes employed in the literature, showing how synchronous-type updating schemes can bias discrete-time formalisms when compared against continuous-time formalisms. Event-based simulations, such as the Gillespie algorithm, are proposed as optimal simulation schemes both in terms of replicating the continuous-time process and computational speed. Finally, we show how discretizing time can affect the value of the epidemic threshold for large values of the infection rate and the recovery rate, even if the ratio between the former and the latter is small.

Received 4 March 2016

DOI:https://doi.org/10.1103/PhysRevE.94.052125

Physics Subject Headings (PhySH)

Epidemic Stochastic processes

Statistical Physics & Thermodynamics

Authors & Affiliations

Peter G. Fennell^1,2, Sergey Melnik¹, and James P. Gleeson¹

¹MACSI, Department of Mathematics and Statistics, University of Limerick, Ireland
²Information Sciences Institute, University of Southern California, Marina del Rey, California 90291, USA

Article Text

Click to Expand

References

Click to Expand

Issue

Vol. 94, Iss. 5 — November 2016

Reuse & Permissions

Author publication services for translation and copyediting assistance advertisement

Images

Figure 1
Schematics of both (a) the Gillespie algorithm and (b) the synchronous updating scheme. Vertical ticks on the $t$ axis indicate the moments through which the simulation advances—in synchronous updating the interval between these moments is a fixed time step with value $Δ t$ while in the Gillespie algorithm the interval is a random variable $τ$ given by Lemma 1. The light green and dark red circles are nodes in the network, which are in the susceptible and infected states, respectively. A square around a node means that the node has been chosen for updating at a certain moment and may change its state. In the Gillespie algorithm a node is chosen according to Lemma 2 and will always change its state while in the synchronous updating scheme every node has the chance to change state and will do so with a probability that depends on their state and the states of their nearest neighbors.
Reuse & Permissions
Figure 2
The actual probability (blue solid line) that a rate $λ$ event will occur in a time step of length $Δ t$ plotted along with the approximate probability $\tilde{λ}$ (black dash-dotted line) as used in discrete-time formalisms. The error $ε$ is defined as the absolute distance between the two.
Reuse & Permissions
Figure 3
SIS dynamics with $β = μ = 1$ on a complete graph with $N = 10$ nodes. (a) Time evolution of the expected fraction of infected nodes $η_{t}$ for both the exact master equation Eq. (9) (solid line) and synchronous updating simulations with time steps $Δ t = 0.1$ and $Δ t = 1$ (dashed lines). The Gillespie algorithm and Exact curves are indistinguishable. (b) and (c) Histograms showing the exact probability mass function $p (z, t)$ at $t = 3$ —calculated from numerical integration of Eq. (9)—and the probability mass functions obtained empirically from $10^{6}$ simulation realizations for both (b) synchronous updating simulations with time steps $Δ t = 0.01, Δ t = 0.1$ , and $Δ t = 1$ and (c) the Gillespie algorithm, respectively.
Reuse & Permissions
Figure 4
Time evolution of the expected fraction of infected nodes $η_{t}$ for SIS dynamics with infection rate $β = 0.2$ and recovery rates (a) $μ = 0.48$ and (b) $μ = 0.72$ . The network here is an Erdős-Rényi network with 1000 nodes and average degree $〈 k 〉 = 4$ . Each trajectory is averaged over $10^{4}$ realisations. Synchronous updating with a time step of $Δ t = 1$ —as in [36]—is given by the circular symbols ( $S_{Δ t = 1}$ ). This significantly deviates from Gillespie algorithm simulations (GA, triangular symbols) and synchronous updating simulations with a small time step of $Δ t = 0.01$ ( $S_{Δ t = 0.01}$ , square symbols) if the transition rates $μ$ and/or $β$ are too large.
Reuse & Permissions
Figure 5
The fraction of infected nodes $η_{\infty}$ in the metastable state in an Erdős-Rényi network with $10^{4}$ nodes and mean degree $〈 k 〉 = 4$ for various values of the transition probabilities $\tilde{μ}$ and $\tilde{β}$ . Along each of the five curves shown from left to right, $\tilde{μ}$ is fixed at the values 1, 0.775, 0.55, 0.325, and 0.1 respectively and $\tilde{β}$ varies so that $γ = \tilde{β} / \tilde{μ}$ varies between 0.15 and 0.35. The vertical dashed line indicates the epidemic threshold $γ_{c} = 0.25$ predicted by both the NLDS and HMF theories.
Reuse & Permissions

Physical Review E

covering statistical, nonlinear, biological, and soft matter physics