Speaker
Description
We present analytical results for the distribution of first passage times of random walks (RWs) on random regular graphs (RRGs) [1]. RRGs are random networks, consisting of $N$ nodes, in which all the nodes are of the same degree $c \ge 3$ and the connections are random and uncorrelated. 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. For an RW starting from an initial node $i$, the first-passage (FP) time $T_{\rm FP}$ from $i$ to a target node $j$ (where $j \ne i$) is the first time at which the RW visits the target node $j$. The first-passage time varies between different instances of the RW trajectory. The distribution of first-passage times may depend on the choice of the initial node $i$ and the target node $j$. In particular, it may depend on the length $\ell_{ij}$ of the shortest path (also referred to as the distance) between $i$ and $j$. Averaging over all possible choices of the initial node $i$ and the target node $j$ one obtains the distribution of first-passage times $P(T_{\rm FP}=t)$.
We distinguish between the case in which the first-passage trajectory from the initial node $i$ to the target node $j$ ($j \ne i$) follows the shortest path (SPATH) between $i$ and $j$ and the case in which it does not follow the shortest path (non-SPATH). The SPATH trajectories are characterized by the property that the subnetwork that consists of the nodes and edges along the trajectory is a tree network and the distance $\ell_{ij}$ between $i$ and $j$ in this subnetwork is the same as in the whole network. The SPATH scenario takes place mainly for pairs of nodes for which the distance $\ell_{ij}$ is small, while most of the first passage trajectories follow the non-SPATH scenario.
The special case in which the initial node $i$ is also chosen as the target node ($i=j$) is called the first return (FR) problem. The distribution $P(T_{\rm FR}=t)$ of first return times of RWs on RRGs was studied in Ref. [2]. The characteristic time scale of first passage processes (when $i$ and $j$ are not too close to each other) is of order $t \sim N$. Another important event, which occurs at much longer time scales, is the step at which the RW completes visiting all the nodes in the network. The time at which this happens is called the cover time, which scales like $t \sim N \ln N$ [3]. More recent results for the broader class of configuration model networks will also be discussed.
[1] I. Tishby, O. Biham and E. Katzav, J. Stat. Mech (2022) 113403.
[2] I Tishby, O. Biham and E. katzav, J. Phys. A 54 (2021) 325001.
[3] I. Tishby, O. Biham and E. Katzav, J. Phys. A 55 (2022) 015003.
