Solvable non-Markovian dynamic network

Non-Markovian processes are widespread in natural and human-made systems, yet explicit modeling and analysis of such systems is underdeveloped. We consider a non-Markovian dynamic network with random link activation and deletion (RLAD) and heavy-tailed Mittag-Leffler distribution for the interevent times. We derive an analytically and computationally tractable system of Kolmogorov-like forward equations utilizing the Caputo derivative for the probability of having a given number of active links in the network and solve them. Simulations for the RLAD are also studied for power-law interevent times and we show excellent agreement with the Mittag-Leffler model. This agreement holds even when the RLAD network dynamics is coupled with the susceptible-infected-susceptible spreading dynamics. Thus, the analytically solvable Mittag-Leffler model provides an excellent approximation to the case when the network dynamics is characterized by power-law-distributed interevent times. We further discuss possible generalizations of our result.

Figure 1

Comparison between Monte Carlo simulations and theory. The discrete markers are the estimated probabilities $p_{190,j}\left(250\right)$, averaged over $10000$ Monte Carlo simulations starting from a fully connected network with $N=20$ nodes and for $\beta =1,0.7,0.5$, as we move from left to right. The Monte Carlo simulations were performed using an event-driven algorithm taking non-Markovianity into account. The solid curves are the theoretical predictions as dictated by Eq. (21).

Figure 2

(a)–(c) Distribution of links at $t=2000$ and comparison between the Mittag-Leffler and Pareto distributions. The distribution of singly counted link numbers at $t=2000$ is shown with theoretical equilibrium prediction (solid line) and simulation results (discrete markers). The theoretical equilibrium is the same for all values of $\beta \in (0,1]$ and is given by the binomial distribution (25) here drawn as a solid line for ease of representation. The $\square$ markers in (a), (b), and (c) correspond to $(\beta ,\gamma )=(1,1),(0.7,3.14),(0.5,4)$, respectively, and $◊$ markers are for the corresponding ${\mathcal{D}}_{\text{P}}\left(\delta \right)$. Also shown are (d) the expected number of singly counted links in the network [the dashed line is the theoretical prediction of $N(N-1)/4=95$] and (e) the expected prevalence. The solid (noisy) line is for $(\beta ,\gamma )=(1,1),(0.7,3.14),(0.5,4)$, respectively, from bottom to top and $\square$ markers are the corresponding values for the matched Pareto network. The networks have $N=20$ nodes and simulations start with a completely connected network. The SIS epidemic is simulated as a Markovian process with transmission and recovery rates ${\tau }_I=0.25$ and ${\tau }_H=1$, respectively. The spreading process initializes with five infectious nodes. Since we start with a fully connected network and a slow network dynamics, the prevalence rapidly increases from 25% to almost 80%. This also reflects the relation between the time scales of the network and epidemic dynamics, with the epidemics being much faster in this example. The simulation is event driven and is implemented by keeping track of all events and their waiting times. These are averaged over 5000 simulations and use $\alpha =0$ (periodic case), so all events create a change in the network and equilibrium is reached earlier.

Figure 3

The CCDF of a Pareto distribution with tail exponent $\delta$ and that matching with the corresponding ${\mathcal{D}}_{{\text{ML}}_{\gamma }}\left(\beta \right)$. The left panel presents the case $\beta =0.7, \gamma =4$, and $\delta =1.7$, whereas the right panel presents the case $\beta =0.5, \gamma =3.14$, and $\delta =1.5$. The Pareto distribution is drawn using diamonds, whereas the Mittag-Leffler distribution is drawn using a solid line.