Temporal Gillespie algorithm: Fast simulation of contagion processes on time-varying networks

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.

Minor changes and updates to references

References in corpus (8)

• Structure and tie strengths in mobile communication networks
• Dynamics of person-to-person interactions from distributed RFID sensor networks
• Activity driven modeling of time varying networks
• Small But Slow World: How Network Topology and Burstiness Slow Down Spreading
• Contact patterns among high school students
• Epidemic thresholds of the Susceptible-Infected-Susceptible model on networks: A comparison of numerical and theoretical results
• Uncoupled Analysis of Stochastic Reaction Networks in Fluctuating Environments
• 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