A Gillespie algorithm for non-Markovian stochastic processes

Abstract

The Gillespie algorithm provides statistically exact methods for simulating stochastic dynamics modelled as interacting sequences of discrete events including systems of biochemical reactions or earthquake occurrences, networks of queuing processes or spiking neurons, and epidemic and opinion formation processes on social networks. Empirically, the inter-event times of various phenomena obey long-tailed distributions. The Gillespie algorithm and its variants either assume Poisson processes (i.e., exponentially distributed inter-event times), use particular functions for time courses of the event rate, or work for non-Poissonian renewal processes, including the case of long-tailed distributions of inter-event times, but at a high computational cost. In the present study, we propose an innovative Gillespie algorithm for renewal processes on the basis of the Laplace transform. The algorithm makes use of the fact that a class of point processes is represented as a mixture of Poisson processes with different event rates. The method is applicable to multivariate renewal processes whose survival function of inter-event times is completely monotone. It is an exact algorithm and works faster than a recently proposed Gillespie algorithm for general renewal processes, which is exact only in the limit of infinitely many processes. We also propose a method to generate sequences of event times with a tunable amount of positive correlation between inter-event times. We demonstrate our algorithm with exact simulations of epidemic processes on networks, finding that a realistic amount of positive correlation in inter-event times only slightly affects the epidemic dynamics.

3 figures, 1 table

References in corpus (13)

• Fractional Calculus: Integral and Differential Equations of Fractional Order
• Adaptive Coevolutionary Networks: A Review
• Activity driven modeling of time varying networks
• Small But Slow World: How Network Topology and Burstiness Slow Down Spreading
• A Poissonian explanation for heavy-tails in e-mail communication
• Temporal Heterogeneities Increase the Prevalence of Epidemics on Evolving Networks
• Temporal Gillespie algorithm: Fast simulation of contagion processes on time-varying networks
• Self-exciting hurdle models for terrorist activity
• Scaling in the Inter-Event Time of Random and Seasonal Systems
• Update rules and interevent time distributions: Slow ordering vs. no ordering in the Voter Model
• Spreading dynamics on networks: the role of burstiness, topology and non-stationarity
• Solvable non-Markovian dynamic network
• Activity spectrum from waiting-time distribution

Cited by in corpus (22)

• Fast and principled simulations of the SIR model on temporal networks
• Efficient sampling of spreading processes on complex networks using a composition and rejection algorithm
• Modeling temporal networks with bursty activity patterns of nodes and links
• Burstiness in activity-driven networks and the epidemic threshold
• Gillespie algorithms for stochastic multiagent dynamics in populations and network
• Small inter-event times govern epidemic spreading on temporal networks
• Correlated bursts in temporal networks slow down spreading
• A hierarchical model of non-homogeneous Poisson processes for Twitter retweets
• Long-tailed distributions of inter-event times as mixtures of exponential distributions
• Non-Markovian Majority-Vote model
• Generative models of simultaneously heavy-tailed distributions of inter-event times on nodes and edges
• Copula-based algorithm for generating bursty time series
• Unifying continuous, discrete, and hybrid susceptible-infected-recovered processes on networks
• Reduction from non-Markovian to Markovian dynamics: The case of aging in the noisy-voter model
• Rejection-Based Simulation of Non-Markovian Agents on Complex Networks
• Temporal scaling theory for bursty time series with clusters of arbitrarily many events
• Finite-size scaling analysis of the two-dimensional random transverse-field Ising ferromagnet
• A Network Epidemic Model for Online Community Commissioning Data
• Non-Markovian Rock-Paper-Scissors games
• Spline tie-decay temporal networks
• Effects of concurrency on epidemic spreading in Markovian temporal networks
• A competing risks interpretation of Hawkes processes