Temporal Gillespie algorithm: Fast simulation of contagion processes on time-varying networks
arXiv:1504.01298 · doi:10.1371/journal.pcbi.1004579
Abstract
Stochastic simulations are one of the cornerstones of the analysis of dynamical processes on complex networks, and are often the only accessible way to explore their behavior. The development of fast algorithms is paramount to allow large-scale simulations. The Gillespie algorithm can be used for fast simulation of stochastic processes, and variants of it have been applied to simulate dynamical processes on static networks. However, its adaptation to temporal networks remains non-trivial. We here present a temporal Gillespie algorithm that solves this problem. Our method is applicable to general Poisson (constant-rate) processes on temporal networks, stochastically exact, and up to multiple orders of magnitude faster than traditional simulation schemes based on rejection sampling. We also show how it can be extended to simulate non-Markovian processes. The algorithm is easily applicable in practice, and as an illustration we detail how to simulate both Poissonian and non-Markovian models of epidemic spreading. Namely, we provide pseudocode and its implementation in C++ for simulating the paradigmatic Susceptible-Infected-Susceptible and Susceptible-Infected-Recovered models and a Susceptible-Infected-Recovered model with non-constant recovery rates. For empirical networks, the temporal Gillespie algorithm is here typically from 10 to 100 times faster than rejection sampling.
arXiv commentMinor changes and updates to references
References in corpus (27)
- Epidemic processes in complex networks
- Temporal Networks
- Structure and tie strengths in mobile communication networks
- Multiscale mobility networks and the large scale spreading of infectious diseases
- Dynamics of person-to-person interactions from distributed RFID sensor networks
- High resolution dynamical mapping of social interactions with active RFID
- Activity driven modeling of time varying networks
- Small But Slow World: How Network Topology and Burstiness Slow Down Spreading
- Estimating Potential Infection Transmission Routes in Hospital Wards Using Wearable Proximity Sensors
- Simulation of an SEIR infectious disease model on the dynamic contact network of conference attendees
- A modified Next Reaction Method for simulating chemical systems with time dependent propensities and delays
- Impact of non-Poisson activity patterns on spreading processes
- Time varying networks and the weakness of strong ties
- Contact patterns among high school students
- The dynamical strength of social ties in information spreading
- Epidemic thresholds of the Susceptible-Infected-Susceptible model on networks: A comparison of numerical and theoretical results
- Scaling laws of human interaction activity
- Data on face-to-face contacts in an office building suggests a low-cost vaccination strategy based on community linkers
- Simulating non-Markovian stochastic processes
- Contact tracing and epidemics control in social networks
- Birth and death of links control disease spreading in empirical contact networks
- On the Dynamics of Human Proximity for Data Diffusion in Ad-Hoc Networks
- Activity clocks: spreading dynamics on temporal networks of human contact
- The interplay of intrinsic and extrinsic bounded noises in genetic networks
- Uncoupled Analysis of Stochastic Reaction Networks in Fluctuating Environments
- Behavior of susceptible-vaccinated--infected--recovered epidemics with diversity in the infection rate of the individuals
- Modeling ant battles by means of a diffusion-limited Gillespie algorithm
Cited by in corpus (26)
- Dynamical Systems on Networks: A Tutorial
- The limitations of discrete-time approaches to continuous-time contagion dynamics
- A Gillespie algorithm for non-Markovian stochastic processes
- Optimized Gillespie algorithms for the simulation of Markovian epidemic processes on large and heterogeneous networks
- Compensating for population sampling in simulations of epidemic spread on temporal contact networks
- Randomized reference models for temporal networks
- Sampling of Temporal Networks: Methods and Biases
- Efficient sampling of spreading processes on complex networks using a composition and rejection algorithm
- From interacting agents to density-based modeling with stochastic PDEs
- Mathematical modeling of spatio-temporal population dynamics and application to epidemic spreading
- Gillespie algorithms for stochastic multiagent dynamics in populations and network
- Social distancing in pedestrian dynamics and its effect on disease spreading
- Simulating SIR processes on networks using weighted shortest paths
- Endemicity and prevalence of multipartite viruses under heterogeneous between-host transmission
- Covid-19 epidemic under the K-quarantine model: Network approach
- Turbulent coherent structures and early life below the Kolmogorov scale
- Analytical and cellular automaton approach to a generalized SEIR model for infection spread in an open crowded space
- Hybrid metapopulation agent-based epidemiological models for efficient insight on the individual scale: a contribution to green computing
- Impact of temporal correlations on high risk outbreaks of independent and cooperative SIR dynamics
- Transition from time-variant to static networks: timescale separation in NIMFA SIS epidemics
- Rejection-Based Simulation of Non-Markovian Agents on Complex Networks
- Cohorting to isolate asymptomatic spreaders: An agent-based simulation study on the Mumbai Suburban Railway
- Study of lockdown/testing mitigation strategies on stochastic SIR model and its comparison with South Korea, Germany and New York data
- The Augmented Jump Chain -- a sparse representation of time-dependent Markov jump processes
- Low Complexity Method for Simulation of Epidemics Based on Dijkstra's Algorithm
- Containment strategies and statistical measures for the control of Bovine Viral Diarrhea spread in livestock trade networks