A Gillespie algorithm for non-Markovian stochastic processes
arXiv:1601.01490 · doi:10.1137/16M1055876
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.
arXiv comment3 figures, 1 table
References in corpus (29)
- Temporal Networks
- The origin of bursts and heavy tails in human dynamics
- Fractional Calculus: Integral and Differential Equations of Fractional Order
- Adaptive Coevolutionary Networks: A Review
- Activity driven modeling of time varying networks
- Unified Scaling Law for Earthquakes
- Modeling bursts and heavy tails in human dynamics
- Small But Slow World: How Network Topology and Burstiness Slow Down Spreading
- Long-Term Clustering, Scaling, and Universality in the Temporal Occurrence of Earthquakes
- Waiting-times and returns in high-frequency financial data: an empirical study
- A Poissonian explanation for heavy-tails in e-mail communication
- A modified Next Reaction Method for simulating chemical systems with time dependent propensities and delays
- Sub-critical and Super-critical Regimes in Epidemic Models of Earthquake Aftershocks
- The dynamical strength of social ties in information spreading
- Quantifying reflexivity in financial markets: towards a prediction of flash crashes
- A continuous time random walk model for financial distributions
- Temporal Heterogeneities Increase the Prevalence of Epidemics on Evolving Networks
- Simulating non-Markovian stochastic processes
- 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
- Birth and death of links control disease spreading in empirical contact networks
- Update rules and interevent time distributions: Slow ordering vs. no ordering in the Voter Model
- Estimating inter-event time distributions from finite observation periods in communication networks
- Spreading dynamics on networks: the role of burstiness, topology and non-stationarity
- Voter model with non-Poissonian interevent intervals
- Solvable non-Markovian dynamic network
- Suppression of epidemic outbreaks with heavy-tailed contact dynamics
- 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