Skip navigation

A gillespie algorithm for non-markovian stochastic processes

A gillespie algorithm for non-markovian stochastic processes

Masuda, Naoki and Rocha, Luis E.C. ORCID: 0000-0001-9046-8739 (2018) A gillespie algorithm for non-markovian stochastic processes. SIAM Review, 60 (1). pp. 95-115. ISSN 0036-1445 (doi:https://doi.org/10.1137/16M1055876)

[img]
Preview
PDF (Publisher's PDF - Open Access)
19628 ROCHA_A_Gillespie_Algorithm_(OA)_2018.pdf - Published Version
Available under License Creative Commons Attribution.

Download (655kB) | Preview

Abstract

The Gillespie algorithm provides statistically exact methods for simulating stochastic dynamics modeled 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.

Item Type: Article
Additional Information: © 2018 SIAM. Published by SIAM under the terms of the Creative Commons 4.0 license.
Uncontrolled Keywords: Dynamic networks, Gillespie algorithm, Numerical simulation
Subjects: H Social Sciences > HG Finance
Faculty / Department / Research Group: Faculty of Business
Faculty of Business > Centre for Business Network Analysis (CBNA)
Faculty of Business > Networks and Urban Systems Centre (NUSC) > Centre for Business Network Analysis (CBNA)
Faculty of Business > Department of International Business & Economics
Last Modified: 08 May 2018 15:21
Selected for GREAT 2016: None
Selected for GREAT 2017: None
Selected for GREAT 2018: None
Selected for GREAT 2019: None
URI: http://gala.gre.ac.uk/id/eprint/19628

Actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics