Efficient sampling of spreading processes on complex networks using a composition and rejection algorithm

Abstract

Efficient stochastic simulation algorithms are of paramount importance to the study of spreading phenomena on complex networks. Using insights and analytical results from network science, we discuss how the structure of contacts affects the efficiency of current algorithms. We show that algorithms believed to require $\mathcal{O}(\log N)$ or even $\mathcal{O}(1)$ operations per update---where $N$ is the number of nodes---display instead a polynomial scaling for networks that are either dense or sparse and heterogeneous. This significantly affects the required computation time for simulations on large networks. To circumvent the issue, we propose a node-based method combined with a composition and rejection algorithm, a sampling scheme that has an average-case complexity of $\mathcal{O}[\log (\log N)]$ per update for general networks. This systematic approach is first set-up for Markovian dynamics, but can also be adapted to a number of non-Markovian processes and can enhance considerably the study of a wide range of dynamics on networks.

arXiv comment12 pages, 7 figures

References in corpus (33)

• Epidemic processes in complex networks
• The spread of epidemic disease on networks
• Connectivity of Growing Random Networks
• Epidemic dynamics on an adaptive network
• Epidemic outbreaks in complex heterogeneous networks
• Generation of uncorrelated random scale-free networks
• Epidemic spreading in correlated complex networks
• A message passing approach for general epidemic models
• Unification of theoretical approaches for epidemic spreading on complex networks
• Localization and Spreading of Diseases in Complex Networks
• Second look at the spread of epidemics on networks
• Epidemic threshold for the SIS model on networks
• Griffiths phases on complex networks
• Competing activation mechanisms in epidemics on networks
• Temporal Gillespie algorithm: Fast simulation of contagion processes on time-varying networks
• Markovian Dynamics on Complex Reaction Networks
• The limitations of discrete-time approaches to continuous-time contagion dynamics
• Prestige drives epistemic inequality in the diffusion of scientific ideas
• Prudent behaviour accelerates disease transmission
• A message-passing approach for recurrent-state epidemic models on networks
• A Gillespie algorithm for non-Markovian stochastic processes
• Epidemic threshold and control in a dynamic network
• Optimized Gillespie algorithms for the simulation of Markovian epidemic processes on large and heterogeneous networks
• Eigenvector localization in real networks and its implications for epidemic spreading
• Heterogeneous pair-approximation for the contact process on complex networks
• Multiple phase transitions of the susceptible-infected-susceptible epidemic model on complex networks
• Sampling methods for the quasistationary regime of epidemic processes on regular and complex networks
• Exact equations for SIR epidemics on tree graphs
• Structural preferential attachment: Network organization beyond the link
• Griffiths effects of the susceptible-infected-susceptible epidemic model on random power-law networks
• Phase transition of the susceptible-infected-susceptible dynamics on time-varying configuration model networks
• Localization transition, Lifschitz tails and rare-region effects in network models
• Multistate dynamical processes on networks: Analysis through degree-based approximation frameworks

Cited by in corpus (9)

• Social confinement and mesoscopic localization of epidemics on networks
• Master equation analysis of mesoscopic localization in contagion dynamics on higher-order networks
• Fast and principled simulations of the SIR model on temporal networks
• Immunization Strategies in Networks with Missing Data
• Gillespie algorithms for stochastic multiagent dynamics in populations and network
• Effective Resistance for Pandemics: Mobility Network Sparsification for High-Fidelity Epidemic Simulation
• Inference for growing trees
• Simple quasistationary method for simulations of epidemic processes with localized states
• Rejection-Based Simulation of Non-Markovian Agents on Complex Networks