Random Walks and Search in Time-Varying Networks

The random walk process underlies the description of a large number of real-world phenomena. Here we provide the study of random walk processes in time-varying networks in the regime of time-scale mixing, i.e., when the network connectivity pattern and the random walk process dynamics are unfolding on the same time scale. We consider a model for time-varying networks created from the activity potential of the nodes and derive solutions of the asymptotic behavior of random walks and the mean first passage time in undirected and directed networks. Our findings show striking differences with respect to the well-known results obtained in quenched and annealed networks, emphasizing the effects of dynamical connectivity patterns in the definition of proper strategies for search, retrieval, and diffusion processes in time-varying networks.

Figure 1

Activity-driven random walk process. Active nodes are shown as fully colored (red) nodes. Walkers are presented as small (green) particles inside nodes. Links used by walkers to move from one node to another are shown in solid (red) lines, while edges connecting empty nodes are shown as dashed lines. Here we considered $m=2$.

Figure 2

Main plot: Stationary density $W_a$ of random walkers in activity-driven networks with activity distribution $F(a)\sim a^{-\gamma }$. We consider $\gamma =2$ (circles) and $\gamma =2.8$ (diamonds). Solid lines represent the analytical prediction of Eq. (4). Inset: Stationary density $W_a$ for random walks on top of an activity-driven network with $F(a)\sim a^{-2}$, integrated over $T=50$ time steps. The solid line corresponds to the curve $W_a\sim a$, fitting the simulation points for large values of $a$. Simulation parameters: $N={10}^5$, $m=6$, $ϵ={10}^{-3}$, and $w={10}^2$. Averages are performed over ${10}^3$ independent simulations.

Figure 3

Main plot: MFPT of a random walker as a function of the activity $a$ in activity-driven networks with activity distribution $F(a)\sim a^{-2}$. Full line corresponds to the theoretical prediction of Eq. (6). Right inset: MFPT as a function of activity for directed Type I activity-driven networks. Left inset: MFPT as a function of activity for directed Type II activity-driven networks. Simulation parameters: $N={10}^4$ ($N={10}^3$ for Type I, blue dots in right inset), $m=6$, and $ϵ={10}^{-3}$. Averages are performed over ${10}^3$ independent simulations for each activity class.