Random walks on networks with stochastic resetting

We study random walks with stochastic resetting to the initial position on arbitrary networks. We obtain the stationary probability distribution as well as the mean and global first passage times, which allow us to characterize the effect of resetting on the capacity of a random walker to reach a particular target or to explore a finite network. We apply the results to rings, Cayley trees, and random and complex networks. Our formalism holds for undirected networks and can be implemented from the spectral properties of the random walk without resetting, providing a tool to analyze the search efficiency in different structures with the small-world property or communities. In this way, we extend the study of resetting processes to the domain of networks.

Figure 1

A random walker with resetting can be illustrated as a tourist visiting places in a street network. In the present model, the possible movements from a node $l$ are as follows: a random walk step to an adjacent node (with probability $1-\gamma$) or a relocation to a fixed node $r$ (the hotel) with probability $\gamma$, from which the exploration of the network is resumed.

Figure 2

Stationary distribution and MFPT for random walks with resetting on a ring with $N=100$ nodes. (a) $P_j^{\infty }(i,\gamma )$ as given by Eq. (15) and (b) $〈T_{ij}\left(\gamma \right)〉$ as given by Eq. (16), as a function of the distance $d_{ij}$ between the initial node $i$ and the target node $j$ for different values of $\gamma$.

Figure 3

Random walks with stochastic resetting to the central node on Cayley trees with coordination number $z=3$ and $n$ shells. (a) MFPT $\langle T_{ij}\left(\gamma \right)\rangle$ vs. $\gamma$ in a Cayley tree with $n=7$ shells ($N=382$ nodes). The results are presented as a family of curves defined by the distance $d_{ij}$ (shown in the color bar) between the central node $i$ and the target node $j$. (b) Global MFPT $T(i,\gamma )$ defined in Eq. (14) with $0\le \gamma \le 0.99$ for different Cayley trees with $n$ shells. In each curve we include the number $n$ and the circles indicate the minima for Cayley trees with different numbers of shells.

Figure 4

Global time in networks with $N=100$ nodes: (a) Barbell, (b) Watts-Strogatz, (c) Erdös-Rényi, and (d) Barabási-Albert, where each newly introduced node connects to $m$ previous nodes ($m=1$). We depict the global time $T(i,\gamma )$ as a function of $\gamma$ for all the nodes $i=1,...,N$. To identify the effects of resetting, we colored each node $i$ and its corresponding curve according to its closeness centrality $C_i\equiv \frac{N}{{\sum }_{j=1}^N{d}_{ij}}$.