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

Abstract

We present analytical results for the distribution of first-passage (FP) times of random walks (RWs) on random regular graphs that consist of $N$ nodes of degree $c\ge 3$. Starting from a random initial node at time $t=0$, at each time step $t\ge 1$ an RW hops into a random neighbor of its previous node. In some of the time steps the RW may hop into a yet-unvisited node while in other time steps it may revisit a node that has already been visited before. We calculate the distribution $P(T_{\mathrm{FP}}=t)$ of first-passage times from a random initial node $i$ to a random target node $j$, where $j\ne i$. We distinguish between FP trajectories whose backbone follows the shortest path (SPATH) from the initial node $i$ to the target node $j$ and FP trajectories whose backbone does not follow the shortest path ($\neg \mathrm{SPATH}$). More precisely, the SPATH trajectories from the initial node $i$ to the target node $j$ are defined as trajectories in which the subnetwork that consists of the nodes and edges along the trajectory is a tree network. Moreover, the shortest path between $i$ and $j$ on this subnetwork is the same as in the whole network. The SPATH scenario is probable mainly when the length ${\ell }_{ij}$ of the shortest path between the initial node $i$ and the target node $j$ is small. The analytical results are found to be in very good agreement with the results obtained from computer simulations.

arXiv comment32 pages, 10 figures. arXiv admin note: text overlap with arXiv:2110.13592, arXiv:2106.10449, arXiv:2102.12195

References in corpus (21)

• 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
• Asymptotic analysis of first passage time in complex networks
• Ring structures and mean first passage time in networks
• Return times of random walk on generalized random graphs
• Analytical results for the distribution of first return times of random walks on random regular graphs
• Distance distribution in configuration model networks
• Distribution of shortest cycle lengths in random networks
• Tree formulas, mean first passage times and Kemeny's constant of a Markov chain
• 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 cover times of random walks on random regular graphs
• The mean and variance of the distribution of shortest path lengths of random regular graphs
• Analytical results for the distribution of first hitting times of random walks on random regular graphs
• Exact and Approximate Mean First Passage Times on Trees and other Necklace Structures: a Local Equilibrium Approach
• Information retrieval and structural complexity of legal trees
• Random Walks on Complex Networks

Cited by in corpus (4)

• A Gaussian integral that counts regular 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
• First return times on sparse random graphs
• Analytical results for the distribution of first return times of non-backtracking random walks on configuration model networks