Vestergaard Christian L, Génois Mathieu
Aix Marseille Université, Université de Toulon, CNRS, CPT, UMR 7332, Marseille, France.
PLoS Comput Biol. 2015 Oct 30;11(10):e1004579. doi: 10.1371/journal.pcbi.1004579. eCollection 2015 Oct.
Stochastic simulations are one of the cornerstones of the analysis of dynamical processes on complex networks, and are often the only accessible way to explore their behavior. The development of fast algorithms is paramount to allow large-scale simulations. The Gillespie algorithm can be used for fast simulation of stochastic processes, and variants of it have been applied to simulate dynamical processes on static networks. However, its adaptation to temporal networks remains non-trivial. We here present a temporal Gillespie algorithm that solves this problem. Our method is applicable to general Poisson (constant-rate) processes on temporal networks, stochastically exact, and up to multiple orders of magnitude faster than traditional simulation schemes based on rejection sampling. We also show how it can be extended to simulate non-Markovian processes. The algorithm is easily applicable in practice, and as an illustration we detail how to simulate both Poissonian and non-Markovian models of epidemic spreading. Namely, we provide pseudocode and its implementation in C++ for simulating the paradigmatic Susceptible-Infected-Susceptible and Susceptible-Infected-Recovered models and a Susceptible-Infected-Recovered model with non-constant recovery rates. For empirical networks, the temporal Gillespie algorithm is here typically from 10 to 100 times faster than rejection sampling.
随机模拟是复杂网络动态过程分析的基石之一，并且常常是探索其行为的唯一可行方法。快速算法的开发对于进行大规模模拟至关重要。 Gillespie算法可用于随机过程的快速模拟，其变体已被应用于模拟静态网络上的动态过程。然而，将其应用于时态网络仍然并非易事。我们在此提出一种时态Gillespie算法来解决这个问题。我们的方法适用于时态网络上的一般泊松（恒定速率）过程，具有随机精确性，并且比基于拒绝采样的传统模拟方案快多个数量级。我们还展示了如何将其扩展以模拟非马尔可夫过程。该算法在实践中易于应用，作为示例，我们详细说明如何模拟流行病传播的泊松模型和非马尔可夫模型。具体而言，我们提供了用于模拟典型的易感-感染-易感和易感-感染-康复模型以及具有非恒定康复率的易感-感染-康复模型的伪代码及其C++实现。对于实证网络，时态Gillespie算法在此通常比拒绝采样快10到100倍。
