Network Science,Naoki Masuda

Gillespie algorithm

Keywords: network, time series, point process, Laplace transform

Social networks we form and other networks often change over time, and such networks are analysed under the umbrella term temporal networks. Many temporal networks have burstiness. Suppose you meet somebody and have discrete conversation events. Your conversation events would not occur uniformly at random. A chunk of events tends to occur in a burst, which occurs in an intermittent manner (Figure). In technical terms, the inter-event times obey a long-tailed distribution.

Fig: A bursty time series. The vertical bar represents the time a conversation event happens e.g. between two particular persons.

Before burstiness was known, it had been common to assume that conversation events occur as if people arrive at a sales counter sporadically and completely randomly, lacking burstiness (technically, exponential-like distribution of inter-event times). Now we know that this is an oversimplification in many cases.

The Gillespie algorithm, invented in 1970s, is a mathematical/computational technique with which one can numerically simulate systems of interacting event sequences (e.g. a population of humans or molecules) efficiently and without error. In the original form, this algorithm generates non-bursty event sequences. We invented a new variant of the Gillespie algorithm to be able to generate bursty event sequences. We used mathematical tools so-called the Laplace transform and completely monotone functions.