Optimized Gillespie algorithms for the simulation of Markovian epidemic processes on large and heterogeneous networks

Abstract

Numerical simulation of continuous-time Markovian processes is an essential and widely applied tool in the investigation of epidemic spreading on complex networks. Due to the high heterogeneity of the connectivity structure through which epidemics is transmitted, efficient and accurate implementations of generic epidemic processes are not trivial and deviations from statistically exact prescriptions can lead to uncontrolled biases. Based on the Gillespie algorithm (GA), in which only steps that change the state are considered, we develop numerical recipes and describe their computer implementations for statistically exact and computationally efficient simulations of generic Markovian epidemic processes aiming at highly heterogeneous and large networks. The central point of the recipes investigated here is to include phantom processes, that do not change the states but do count for time increments. We compare the efficiencies for the susceptible-infected-susceptible, contact process and susceptible-infected-recovered models, that are particular cases of a generic model considered here. We numerically confirm that the simulation outcomes of the optimized algorithms are statistically indistinguishable from the original GA and can be several orders of magnitude more efficient.

12 pages, 9 figures

References in corpus (8)

• Critical phenomena in complex networks
• Thresholds for epidemic spreading in networks
• Epidemic thresholds of the Susceptible-Infected-Susceptible model on networks: A comparison of numerical and theoretical results
• Finite-size scaling in complex networks
• Langevin approach for the dynamics of the contact process on annealed scale-free networks
• Routes to thermodynamic limit on scale-free networks
• Multiple phase transitions of the susceptible-infected-susceptible epidemic model on complex networks
• Susceptible-infected-susceptible dynamics on the rewired configuration model

Cited by in corpus (32)

• Fundamentals of spreading processes in single and multilayer complex networks
• EoN (Epidemics on Networks): a fast, flexible Python package for simulation, analytic approximation, and analysis of epidemics on networks
• Epidemic outbreaks with adaptive prevention on complex networks
• Outbreak diversity in epidemic waves propagating through distinct geographical scales
• Infectious disease dynamics in metapopulations with heterogeneous transmission and recurrent mobility
• Robustness and fragility of the susceptible-infected-susceptible epidemic models on complex networks
• Spectral properties and the accuracy of mean-field approaches for epidemics on correlated networks
• Efficient sampling of spreading processes on complex networks using a composition and rejection algorithm
• An overview of epidemic models with phase transitions to absorbing states running on top of complex networks
• Non massive immunization to contain spreading on complex networks
• Griffiths phases in infinite-dimensional, non-hierarchical modular networks
• Phase transition of the susceptible-infected-susceptible dynamics on time-varying configuration model networks
• High prevalence regimes in the pair quenched mean-field theory for the susceptible-infected-susceptible model on networks
• Gillespie algorithms for stochastic multiagent dynamics in populations and network
• Activation thresholds in epidemic spreading with motile infectious agents on scale-free networks
• Controversy-seeking fuels rumor-telling activity in polarized opinion networks
• Simple quasistationary method for simulations of epidemic processes with localized states
• Multistage onset of epidemics in heterogeneous networks
• Rejection-Based Simulation of Non-Markovian Agents on Complex Networks
• Dynamical correlations and pairwise theory for the symbiotic contact process on networks
• Epidemic modelling requires knowledge of the social network
• Biased versus unbiased numerical methods for stochastic simulations
• Visibility graphs of critical and off-critical time series for absorbing state phase transitions
• Correlation between transition probability and network structure in epidemic model
• Epidemic threshold and localization of the SIS model on directed complex networks
• Influence of individual nodes for continuous-time Susceptible-Infected-Susceptible dynamics on synthetic and real-world networks
• Comparison of theoretical approaches for epidemic processes with waning immunity in complex networks
• Limited efficacy of forward contact tracing in epidemics
• Impacts of bridging nodes on the epidemic activation mechanisms
• The effect of delayed awareness and fatigue on the efficacy of self-isolation in epidemic control
• OG-SPACE: Optimized Stochastic Simulation of Spatial Models of Cancer Evolution
• Nonuniversal critical dynamics on planar random lattices with heterogeneous degree distributions