Article,
Temporal Gillespie Algorithm: Fast Simulation of Contagion Processes on Time-Varying Networks
PLoS Comput Biol, 11 (10): e1004579+ (Oct 30, 2015)
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. When studying how e.g. diseases spread in a population, intermittent contacts taking place between individuals—through which the infection spreads—are best described by a time-varying network. This object captures both their complex structure and dynamics, which crucially affect spreading in the population. The dynamical process in question is then usually studied by simulating it on the time-varying network representing the population. Such simulations are usually time-consuming, especially when they require exploration of different parameter values. We here show how to adapt an algorithm originally proposed in 1976 to simulate chemical reactions—the Gillespie algorithm—to speed up such simulations. Instead of checking at each time-step if each possible reaction takes place, as traditional rejection sampling algorithms do, the Gillespie algorithm determines what reaction takes place next and at what time. This offers a substantial speed gain by doing away with the many rejected trials of the traditional methods, with the added benefit of giving stochastically exact results. In practice this new temporal Gillespie algorithm is tens to hundreds of times faster than the current state-of-the-art, opening up for thorough characterization of spreading phenomena and fast large-scale applications such as the simulation of city- or world-wide epidemics.
