Steady state and mean recurrence time for random walks on stochastic temporal networks

Random walks are basic diffusion processes on networks and have applications in, for example, searching, navigation, ranking, and community detection. Recent recognition of the importance of temporal aspects on networks spurred studies of random walks on temporal networks. Here we theoretically study two types of event-driven random walks on a stochastic temporal network model that produces arbitrary distributions of interevent times. In the so-called active random walk, the interevent time is reinitialized on all links upon each movement of the walker. In the so-called passive random walk, the interevent time is reinitialized only on the link that has been used the last time, and it is a type of correlated random walk. We find that the steady state is always the uniform density for the passive random walk. In contrast, for the active random walk, it increases or decreases with the node's degree depending on the distribution of interevent times. The mean recurrence time of a node is inversely proportional to the degree for both active and passive random walks. Furthermore, the mean recurrence time does or does not depend on the distribution of interevent times for the active and passive random walks, respectively.

Figure 1

Schematic of the passive random walk on an example network possessing $N=3$ nodes. The walker starts at node 1 at $t=0$. The link activation is represented by horizontal bars. ${\tau }_{e,i} \left(i\ge 1\right)$ represents the $i\mathrm{th}$ interevent time on link $e$. The random walker follows the path indicated by the thick lines.

Figure 2

Schematic of the active random walk on an example network. The walker starts at node 1 at $t=0$ and follows the path indicated by the thick lines. Note that ${\tau }_{(2,3),2}$ is not the second interevent time on link $(2,3)$. It is a realization of the interevent time drawn at $t={\tau }_{(1,2),1}$.

Figure 3

Three distributions of interevent times, i.e., the exponential distribution given by $\psi \left(t\right)=e^{-t}$ (solid line), the power-law distribution given by Eq. (61) with $\alpha =3$ (dotted line), and the Weibull distribution given by Eq. (76) with $m=2$ and $\lambda =\sqrt{\pi }/2$ (dashed line).

Figure 4

Numerical results for the active and passive random walk on a scale-free network with $N=50$ nodes generated by the Barabási-Albert model [33]. The interevent time is assumed to obey the power-law distribution with exponent $\alpha =3$ for all links. (a) Steady state of the active (circles) and passive (triangles) random walks. (b) Mean time to return to an initial node for the active and passive random walks. The results for the case in which the interevent time obeys the exponential distribution are omitted because they are indistinguishable from the results for the passive random walk (triangles). The lines represent the theoretical estimates. The nodes are sorted in ascending order of the degree.

Figure 5

Numerical results for the active (circles) and passive (triangles) random walk when the interevent time obeys the Weibull distribution with $m=2$ and $\lambda =\sqrt{\pi }/2$. We used the same realization of the scale-free network as in Fig. 4. (a) Steady state. (b) Mean recurrence time. The lines represent the theory. The nodes are sorted in ascending order of the degree.