Rejection-Based Simulation of Non-Markovian Agents on Complex Networks

Abstract

Stochastic models in which agents interact with their neighborhood according to a network topology are a powerful modeling framework to study the emergence of complex dynamic patterns in real-world systems. Stochastic simulations are often the preferred - sometimes the only feasible - way to investigate such systems. Previous research focused primarily on Markovian models where the random time until an interaction happens follows an exponential distribution. In this work, we study a general framework to model systems where each agent is in one of several states. Agents can change their state at random, influenced by their complete neighborhood, while the time to the next event can follow an arbitrary probability distribution. Classically, these simulations are hindered by high computational costs of updating the rates of interconnected agents and sampling the random residence times from arbitrary distributions. We propose a rejection-based, event-driven simulation algorithm to overcome these limitations. Our method over-approximates the instantaneous rates corresponding to inter-event times while rejection events counterbalance these over-approximations. We demonstrate the effectiveness of our approach on models of epidemic and information spreading.

arXiv comment14 pages including 2 pages Appendix and 2 pages references

References in corpus (19)

• Epidemic processes in complex networks
• Identification of influential spreaders in complex networks
• The origin of bursts and heavy tails in human dynamics
• Modeling bursts and heavy tails in human dynamics
• Simulating non-Markovian stochastic processes
• Temporal Gillespie algorithm: Fast simulation of contagion processes on time-varying networks
• Dynamical Systems on Networks: A Tutorial
• Markovian Dynamics on Complex Reaction Networks
• Pairwise-like models for non-Markovian epidemics on networks
• A Gillespie algorithm for non-Markovian stochastic processes
• Optimized Gillespie algorithms for the simulation of Markovian epidemic processes on large and heterogeneous networks
• Equivalence between non-Markovian and Markovian dynamics in epidemic spreading processes
• Analytically Solvable Model of Spreading Dynamics with Non-Poissonian Processes
• Stochastic cellular automata model of neural networks
• Application of SIR epidemiological model: new trends
• Efficient sampling of spreading processes on complex networks using a composition and rejection algorithm
• Copula-based algorithm for generating bursty time series
• Rescaling, thinning or complementing? On goodness-of-fit procedures for point process models and Generalized Linear Models
• Mean-field models for non-Markovian epidemics on networks: from edge-based compartmental to pairwise models