Memory and burstiness in dynamic networks

A discrete-time random process is described, which can generate bursty sequences of events. A Bernoulli process, where the probability of an event occurring at time $t$ is given by a fixed probability $x$, is modified to include a memory effect where the event probability is increased proportionally to the number of events that occurred within a given amount of time preceding $t$. For small values of $x$ the interevent time distribution follows a power law with exponent $-2-x$. We consider a dynamic network where each node forms, and breaks connections according to this process. The value of $x$ for each node depends on the fitness distribution, $\rho \left(x\right)$, from which it is drawn; we find exact solutions for the expectation of the degree distribution for a variety of possible fitness distributions, and for both cases where the memory effect either is, or is not present. This work can potentially lead to methods to uncover hidden fitness distributions from fast changing, temporal network data, such as online social communications and fMRI scans.

Figure 1

The interevent time distribution for a sequence of events generated by the process described in Sec. 2a. The simulation lasted for ${10}^8$ iterations with $M={10}^3$ and $\epsilon =1$. The markers show the log-binned frequencies (normalized to give the proportion of interevent times of length $\tau$). The dotted lines show the corresponding slope predicted by Eq. (2).

Figure 2

Three iterations of the network model starting from a random initial configuration. The number of stripes inside each node corresponds to the fitness; the node with the least stripes has fitness $x=0.5$, the others have $x=1,x=1.5,x=2,x=2.5$, and $x=3$. The number of dashes in each edge corresponds to its age with the oldest having the most dashes. In each iteration the oldest edge is removed and a new edge is added between nodes selected either with probability proportional to their fitness [shown in (a)] or with probability proportional to the sum of their fitness and their degree [shown in (b)]. Note that in (a) the fittest node is also the most active. In (b) this is not the case.

Figure 3

The interevent time distribution for attachment events of a single node $i$ with fitness equal to the mean of the fitness distribution $\left(x_i=\langle x\rangle \right)$ on log-log axes (main), and log-linear axes (inset). The plotted results consider a dense network where $N=10$ and $E=100$. The attachment events of $i$ are described by the process introduced in Sec. 2 with $M=E$ and $\epsilon =(N/2-1)\langle x\rangle$. When $x_i$, and hence $N\langle x\rangle$, are very large, the event probability is dominated by the contribution from $x_i$ and is therefore weakly dependent on the memory of $i$. In this case the interevent times are distributed exponentially (as expected in a Bernoulli process). As $\langle x\rangle \to 0$ the contribution from the memory of previous events becomes dominant and the distribution approaches a power law with exponent $-2$.

Figure 4

The degree distributions for both types of attachment kernel and two different forms of $\rho \left(x\right)$. In each plot the markers show the results of a single numerical simulation of a network of $2\times {10}^3$ nodes, the smooth lines show the corresponding analytical results. In (a) $E=4\times {10}^3$ and the fitness distribution is $\rho \left(x\right)=\lambda e^{-\lambda x}$, which is special case of the gamma distribution [Eq. (C1) with $\alpha =1$ and $\beta =1/\lambda$]. For a range of values of $\lambda$, an exponential fitness distribution is plotted with filled markers and the degree distribution is plotted with unfilled markers of the same shape. We see that in this particular case the parameter $\lambda$ does not effect the result. This is not the case when memory effects are introduced, shown in (b); as $\lambda$ increases the degree distribution approaches a power law [see Eq. (C8)]. In (c) the power-law fitness distribution [given by Eq. (C9) with $x_{\text{min}}=1$ and $\gamma =2.5$] is plotted next to the degree distributions for a range of values of $E$ (giving different densities). For large values of $k$ the degree distribution has the same power-law exponent as the fitness distribution, even when memory effects are introduced as we see in (d). The effect of including memory is however seen in the small values of $k$.