Analytical results for the distribution of first return times of random walks on random regular graphs

Abstract

We present analytical results for the distribution of first return (FR) times of random walks (RWs) on random regular graphs (RRGs) consisting of $N$ nodes of degree $c\ge 3$. Starting from a random initial node $i$ at time $t=0$, at each time step $t\ge 1$ an RW hops into a random neighbor of its previous node. We calculate the distribution $P(T_{\mathrm{FR}}=t)$ of first return times to the initial node $i$. We distinguish between first return trajectories in which the RW retrocedes its own steps backwards all the way back to the initial node $i$ and those in which the RW returns to $i$ via a path that does not retrocede its own steps. In the retroceding scenario, each edge that belongs to the RW trajectory is crossed the same number of times in the forward and backward directions. In the non-retroceding scenario the subgraph that consists of the nodes visited by the RW and the edges it has crossed between these nodes includes at least one cycle. In the limit of $N\to \infty$ the RRG converges towards the Bethe lattice. The Bethe lattice exhibits a tree structure, in which all the first return trajectories belong to the retroceding scenario. Moreover, in the limit of $N\to \infty$ the trajectories of RWs on RRGs are transient in the sense that they return to the initial node with probability $<1$. In this sense they resemble the trajectories of RWs on regular lattices of dimensions $d\ge 3$. The analytical results are found to be in excellent agreement with the results obtained from computer simulations.

arXiv comment27 pages, 9 figures. arXiv admin note: text overlap with arXiv:2102.12195

References in corpus (11)

• Epidemic spreading in scale-free networks
• Random graphs with arbitrary degree distributions and their applications
• Random walks and diffusion on networks
• First Passage Properties of the Erdos-Renyi Random Graph
• Return times of random walk on generalized random graphs
• First encounters on Bethe Lattices and Cayley Trees
• The average number of distinct sites visited by a random walker on random graphs
• Return probabilities and hitting times of random walks on sparse Erdos-Renyi graphs
• Exact clesed form of the return probability on the Bethe lattice
• The distribution of first hitting times of random walks on Erdős-Rényi networks
• Analytical results for the distribution of first hitting times of random walks on random regular graphs

Cited by in corpus (7)

• Analytical results for the distribution of cover times of random walks on random regular graphs
• Analytical results for the distribution of first-passage times of random walks on random regular graphs
• A Gaussian integral that counts regular graphs
• First return times on sparse random graphs
• The joint distribution of first return times and of the number of distinct sites visited by a 1D random walk before returning to the origin
• An approximation for return time distributions of random walks on sparse networks
• Analytical results for the distribution of first return times of non-backtracking random walks on configuration model networks