, ,

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

Ido Tishby, Ofer Biham and Eytan Katzav  Racah Institute of Physics, The
Hebrew University, Jerusalem 9190401, Israel<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### 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\geq 3$. Starting from a random initial node at time $t=0$, at each
time step $t\geq 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_{\rm FP}=t)$ of first-passage times from a
random initial node $i$ to a random target node $j$, where $j\neq 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 ($\lnot{\rm 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.

Keywords: Random network, random regular graph, random walk, first-passage
time, shortest path, backtracking, retroceding.

##  1 Introduction

Random walk (RW) models were studied extensively in different geometries,
including continuous space [1], regular lattices [2], fractals [3] and random
networks [4, 5]. In the context of random networks [6, 7], random walks
provide useful tools for the analysis of dynamical processes such as the
spreading of rumours, opinions and infections [8, 9]. Consider an RW on a
random network. Starting at time $t=0$ from a random initial node $i=x_{0}$,
at each time step $t\geq 1$ it hops randomly to one of the neighbors of its
previous node. The RW thus generates a trajectory of the form
$x_{0}\rightarrow x_{1}\rightarrow\dots\rightarrow x_{t}\rightarrow\dots$,
where $x_{t}$ is the node visited at time $t$. In some of the time steps the
RW hops into nodes that have not been visited before, while in other time
steps it hops into nodes that have already been visited at an earlier time.
The mean number $\langle S\rangle_{t}$ of distinct nodes visited by an RW on a
random network in the first $t$ time steps was recently studied [10]. It was
found that in the infinite network limit it scales linearly with $t$, namely
$\langle S\rangle_{t}\simeq rt$, where the coefficient $r<1$ depends on the
network topology. These scaling properties resemble those obtained for RWs on
high dimensional lattices as well as on Bethe lattices and Cayley trees [11].

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\neq i$) is the first time
at which the RW visits the target node $j$ [12, 13]. The first-passage time
varies between different instances of the RW trajectory and its properties can
be captured by a suitable distribution. 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)$. This
problem was studied extensively on regular lattices [12, 13]. The mean first-
passage time $\langle T_{\rm FP}\rangle$ of an RW on a random network was
studied in Refs. [14, 15, 16, 17]. The statistical properties of first passage
processes in empirical networks were applied in order to characterize the
heterogeneity and correlations in these networks [18]. Such analyses rely on
the whole distribution of first passage times in the network and not only on
the mean first passage time. However, closed-form analytical expressions for
the distribution $P(T_{\rm FP}=t)$ of first-passage times in random networks
have not been derived.

The special case in which the initial node $i$ is also chosen as the target
node is called the first return (FR) problem. The distribution $P(T_{\rm
FR}=t)$ of first return times was studied on the Bethe lattice, which exhibits
a tree structure of an infinite size [20, 21, 19]. In a recent paper we
presented analytical results for the distribution of first return times of RWs
on random regular graphs (RRGs) consisting of $N$ nodes of degree $c\geq 3$
[22]. We considered separately the scenario in which the RW returns to the
initial node $i$ by retroceding (RETRO) its own steps and the scenario in
which it does not retrocede its steps ($\lnot{\rm RETRO}$) on the way back to
$i$. In the retroceding scenario an RW starting from the initial node $i$
eventually returns to $i$ by stepping backwards via the same edges that it
crossed in the forward direction. This implies that 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 an RW starting from $i$ eventually returns to $i$ without retroceding
its own steps. This means that in the non-retroceding scenario the RW
trajectory must include at least one cycle. Using combinatorial and
probabilistic methods we calculated the conditional distributions of first
return times, $P(T_{\rm FR}=t|{\rm RETRO})$ and $P(T_{\rm FR}=t|\lnot{\rm
RETRO})$, in the retroceding and non-retroceding scenarios, respectively. We
combined the results of the two scenarios with suitable weights and obtained
the overall distribution of first return times $P(T_{\rm FR}=t)$ of RWs on
RRGs of a finite size.

In this paper we present analytical results for the distribution of first-
passage times of RWs on RRGs that consist of $N$ nodes of degree $c\geq 3$. We
consider separately the case in which the first-passage trajectory from the
initial node $i$ to the target node $j$ ($j\neq i$) follows the shortest path
(SPATH) between $i$ and $j$ and the case in which it does not follow the
shortest path ($\lnot{\rm SPATH}$). In the SPATH trajectories 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$ on this subnetwork is the
same as in the whole network. In finite networks the SPATH scenario takes
place mainly for pairs of nodes for which the distance $\ell_{ij}$ is small.
We combine the results of the two cases with suitable weights and obtain the
overall distribution of first-passage times $P(T_{\rm FP}=t)$ of RWs on RRGs.
The analytical results are found to be in very good agreement with the results
obtained from computer simulations.

The paper is organized as follows. In Sec. 2 we briefly describe the random
regular graph. In Sec. 3 we present the random walk model. In Sec. 4 we
calculate the distribution of first-passage times via SPATH trajectories. In
Sec. 5 we calculate the distribution of first-passage times via non-SPATH
trajectories. The overall distribution of first passage times is calculated in
Sec. 6. The results are summarized and discussed in Sec. 7. In Appendix A we
calculate the number of distinct RW trajectories between a pair of random
nodes that are at a distance $\ell$ apart. In Appendix B we evaluate useful
sums that are used in the calculation of the moments of the distribution of
first-passage times.

##  2 The random regular graph

A random network (or graph) consists of a set of $N$ nodes that are connected
by edges in a way that is determined by some random process. For example, in a
configuration model network the degree of each node is drawn independently
from a given degree distribution $P(k)$ and the connections are random and
uncorrelated [23, 24, 25]. The RRG is a special case of a configuration model
network, in which the degree distribution is a degenerate distribution of the
form $P(k)=\delta_{k,c}$, namely all the nodes are of the same degree $c$.
Here we focus on the case of $3\leq c\leq N-1$, in which for a sufficiently
large value of $N$ the RRG consists of a single connected component [26]. RRGs
exhibit a local tree-like structure, while at larger scales there is a broad
spectrum of cycle lengths [27]. In that sense RRGs differ from Cayley trees,
which maintain their tree structure by reducing the most peripheral nodes to
leaf nodes of degree $1$.

The distribution of shortest path lengths (DSPL) of RRGs was studied in Refs.
[29, 28]. It was shown that the DSPL follows a discrete Gompertz distribution
[30, 31], whose tail distribution is given by

$P(L>\ell)=\exp\left[-\eta\left(e^{b\ell}-1\right)\right],$ (1)

where

$\eta=\left(\frac{c}{c-2}\right)\frac{1}{N},$ (2)

and

$b=\ln(c-1).$ (3)

The probability mass function of the DSPL is given by

$P(L=\ell)=P(L>\ell-1)-P(L>\ell).$ (4)

Consider a pair of nodes $i$ and $j$ that reside at a distance $\ell$ from
each other. This means that $i$ and $j$ are connected by at least one path of
length $\ell$ and that there is no path connecting them which is shorter than
$\ell$. For some pairs of nodes the shortest path connecting them is unique.
For other pairs of nodes the shortest path between them may be degenerate,
namely they may be connected by several paths of length $\ell$ (and no paths
shorter than $\ell$). The degenerate shortest paths may include overlapping
segments. Thus, two shortest paths are considered distinct if they differ by
at least one node. The distribution of first-passage times (in the SPATH
scenario) from an initial node $i$ to a target node $j$ depends both on the
shortest path length (or distance) $\ell$ between them and on its degeneracy.
The probability that the first-passage trajectory of an RW from the initial
node $i$ to a target node $j$ ($j\neq i$) will follow a shortest path is
proportional to the expectation value ${\mathbb{E}}[G|L=\ell]$ of the number
of degenerate shortest paths between $i$ and $j$. The degeneracy results from
branching of the shortest path, which may occur at any point along the path.
The SPATH scenario is probable mainly when the distance between $i$ and $j$ is
small. Therefore, we can use an approximation in which we take into account
only the degeneracy due to branching that occurs in the first shell around the
initial node $i$. In this approximation, the degeneracy is given by the number
of neighbors of $i$ that reside on a shortest path from $i$ to $j$. These
neighbors of $i$ are at a distance $\ell-1$ from $j$, where $\ell$ is the
distance between $i$ and $j$. The degeneracy is equal to the number of
possible first steps of an RW starting from $i$, which reside on one of the
shortest paths to $j$. The degeneracy may take values in the range between $1$
and $c$. The expectation value of the degeneracy of the shortest path between
the initial node $i$ and the target node $j$, which are at a distance
$\ell\geq 2$ from each other, can be approximated by

${\mathbb{E}}[G|L=\ell]\simeq
1+(c-1)\left[1-\widetilde{P}(L>\ell-1|L>\ell-2)\right],$ (5)

where

$\widetilde{P}(L>\ell-1|L>\ell-2)=\exp\left[-\frac{(c-1)^{\ell-1}}{N}\right]$
(6)

is the probability that the distance between a node $i^{\prime}$ selected via
a random edge and another random node $j$ is larger than $\ell-1$, given that
it is larger than $\ell-2$ on the reduced network from which that edge is
removed [28, 27, 32].

Below we explain the terms on the right hand side of Eq. (5), which
approximates the expectation value ${\mathbb{E}}[G|L=\ell]$ of the number of
degenerate shortest paths from $i$ to $j$ by the number of neighbors of $i$
that reside on shortest paths to $j$, given that the distance between $i$ and
$j$ is equal to $\ell$. Under this condition, there is at least one shortest
path of length $\ell$ from $i$ to $j$, thus there is at least one neighbor of
$i$ which is at a distance $\ell-1$ from $j$. The first term on the right hand
side of Eq. (5) accounts for this neighbor. However, for each one of the other
$c-1$ neighbors of $i$ there is a non-zero probability that it may also reside
at a distance $\ell-1$ from $j$. Since the distance between $i$ and $j$ is
$\ell$, the length of the shortest path between any neighbor of $i$ and $j$
must be larger than $\ell-2$. Therefore, for each one of the other $c-1$
neighbors of $i$, the probability that it is at a distance $\ell-1$ from $j$
is given by
$\widetilde{P}(L=\ell-1|L>\ell-2)=1-\widetilde{P}(L>\ell-1|L>\ell-2)$. Thus,
the second term on the right hand side of Eq. (5) accounts for the expected
number of neighbors of $i$ that reside at a distance $\ell-1$ from $j$, apart
from the neighbor accounted for in the first term. Overall, the right hand
side of Eq. (5) provides the expected number of neighbors of $i$ that reside
on shortest paths from $i$ to $j$.

In the special case of $\ell=1$ the expected number of degenerate shortest
paths satisfies ${\mathbb{E}}[G|L=1]=1$, due to the fact that in a simple
graph single edges cannot be degenerate. The expectation value of the
degeneracy increases as the path length $\ell$ is increased. In case that
$2\leq\ell\ll\ln N/\ln(c-1)$, Eq. (5) can be approximated by

${\mathbb{E}}[G|L=\ell]\simeq 1+\frac{(c-1)^{\ell}}{N}.$ (7)

In Fig. 1 we present analytical results (solid lines) for the expectation
value of the degeneracy ${\mathbb{E}}[G|L=\ell]$ of shortest paths between
pairs of nodes $i$ and $j$ as a function of the distance $\ell$ between them
for $c=3$ (left), $c=4$ (center) and $c=5$ (right), obtained from Eq. (7). The
results are found to be in good agreement with the results obtained from
computer simulations (circles).

Figure 1:  Analytical results (solid lines) for the expectation value of the
degeneracy ${\mathbb{E}}[G|L=\ell]$ of shortest paths between pairs of nodes
$i$ and $j$, as a function of the distance $\ell$ between them, for an RRG
that consists of $N=10^{4}$ nodes of degree $c=3$ (left), $c=4$ (center) and
$c=5$ (right), obtained from Eq. (7). The results are found to be in good
agreement with the results obtained from computer simulations (circles).

A convenient way to construct an RRG of size $N$ and degree $c$ ($Nc$ must be
an even number) is to prepare the $N$ nodes such that each node is connected
to $c$ half edges or stubs [7]. At each step of the construction, one connects
a pair of random stubs that belong to two different nodes $i$ and $j$ that are
not already connected, forming an edge between them. This procedure is
repeated until all the stubs are exhausted. The process may get stuck before
completion whenever all the remaining stubs belong to the same node or to
pairs of nodes that are already connected. In such case one needs to perform
some random reconnections in order to complete the construction.

##  3 The random walk model

Consider an RW on an RRG that consists of $N$ nodes of degree $c\geq 3$.
Starting from a random initial node at time $t=0$, at each time step $t\geq 1$
the RW hops into a random neighbor of its previous node. The probability to
hop into each one of these neighbors is $1/c$. For sufficiently large $N$ the
RRG consists of a single connected component, thus an RW starting from any
initial node may eventually reach any other node in the network. In some of
the time steps an RW may visit nodes that have not been visited before while
in other time steps it may revisit nodes that have already been visited
before. For example, at each time step $t\geq 3$ the RW may backtrack into the
previous node with probability of $1/c$. In the infinite network limit the RRG
exhibits a tree structure. Therefore, in this limit the backtracking mechanism
is the only way in which an RW may hop from a newly visited node to a node
that has already been visited before. Such backtracking step may be followed
by retroceding steps in which the RW continues to go backwards along its own
path. However, in finite networks the RW may also utilize cycles to retrace
its path and revisit nodes it has already visited three or more time steps
earlier. In Fig. 2 we present a schematic illustration of some of the events
that may take place along the path of an RW on an RRG. In Fig. 2(a) we show a
path segment that includes a backtracking step, in which the RW moves back
into the previous node (step no. 4). In Fig. 2(b) we show a path segment that
includes a backtracking step (step no. 4) which is followed by a retroceding
step (step no. 5). In Fig. 2(c) we show a path segment that includes a
retracing step (step no. 6), in which the RW enters a node that was already
visited five time steps earlier.

Figure 2:  Schematic illustrations of possible events taking place along the
path of an RW on an RRG: (a) a path segment that includes a backtracking step
into the previous node (step no. 4); (b) a path segment that includes a
backtracking step (step no. 4), which is followed by a retroceding step (step
no. 5); (c) a path that includes a retracing step (step no. 6) in which the RW
hops into a node that was already visited a few time steps earlier. Retracing
steps are not possible in the infinite network limit. They take place only in
finite RRGs, which include cycles. Note that in this illustration the RRG is
of degree $c=4$.

##  4 The distribution of first-passage times via SPATH trajectories

Consider an RW on an RRG of a finite size $N$, starting at $t=0$ from an
initial node $i$. The time at which the RW visits a given target node $j$
($j\neq i$) for the first time is called the first-passage time from $i$ to
$j$. We first consider the case in which the initial node $i$ is random and
the target node $j$ is a random node that resides at a distance $\ell$ from
$i$, where $\ell\geq 1$. Clearly, for $t<\ell$ the first-passage probability
satisfies $P(T_{\rm FP}=t|\ell)=0$. For $t\geq\ell$ the first-passage
probability satisfies $P(T_{\rm FP}=t|\ell)>0$ and for any finite network

$\sum_{t=\ell}^{\infty}P(T_{\rm FP}=t|\ell)=1.$ (8)

The probability that an RW trajectory will follow the shortest path from the
initial node $i$ to the target node $j$ (or one of the shortest paths in case
they are degenerate) is denoted by $P({\rm SPATH}|\ell)$. In the simplest
trajectory of this type the RW moves forward along a shortest path from $i$ to
$j$ at all time steps, such that the first-passage time is $t=\ell$. However,
in some of the time steps the RW may backtrack its path and possibly
retrocede, resulting in a longer trajectory that still follows the shortest
path. Furthermore, the RW may also step away from the shortest path and then
return to the same point along the shortest path by a combination of
backtracking and retroceding steps. Such trajectories are included in the
SPATH scenario. More formally, for a first-passage trajectory to be an SPATH
trajectory it must satisfy two conditions: (a) the subnetwork that consists of
the nodes and edges along the trajectory is a tree network; (b) the distance
between $i$ and $j$ on this subnetwork is the same as the distance $\ell_{ij}$
in the whole network. First-passage trajectories that do not satisfy one or
both of these conditions are non-SPATH trajectories.

In Fig. 3 we present a schematic illustration of first-passage RW trajectories
from the initial node $i$ to the target node $j$ that follow the shortest path
from $i$ to $j$. The simplest among these paths is an RW trajectory that goes
along the shortest path without any backtracking moves or diversions [Fig.
3(a)]. Such RW trajectories may also include backtracking and retroceding
steps along the shortest path [Fig. 3(b)] as well as diversion segments in
which the RW leaves the shortest path and then returns to the same node by
retroceding its steps and then continues to follow the shortest path towards
the target node $j$ [Fig. 3(c)].

Figure 3:  Schematic illustration of first passage RW trajectories from node
$i$ to node $j$ that follow the shortest path between $i$ and $j$: (a) an RW
trajectory that goes along the shortest path without any backtracking moves or
diversions; (b) an RW trajectory that includes backtracking and retroceding
steps along the shortest path; (c) an RW trajectory that leaves the shortest
path and then returns by retroceding its steps. It then follows the shortest
path towards $j$. In this illustration the RRG is of degree $c=4$ and the
shortest path length between $i$ and $j$ is $\ell_{ij}=4$.

The probability that an RW trajectory starting from a random initial node $i$
will follow a shortest path (SPATH) from $i$ to a random target node $j$ that
resides at a distance $\ell$ from $i$, and that the first-passage time will be
$t$ is denoted by $P(T_{\rm FP}=t,{\rm SPATH}|\ell)$. Clearly, for $t<\ell$ it
satisfies $P(T_{\rm FP}=t,{\rm SPATH}|\ell)=0$. For $t\geq\ell$, this
probability is given by

$P(T_{\rm FP}=t,{\rm
SPATH}|\ell)=\left\\{\begin{array}[]{ll}{\mathbb{E}}[G|\ell]B(t,\ell)\left(\frac{1}{c}\right)^{t}&\
\ \ \ \ \ t-\ell\ \ {\rm even}\\\ 0&\ \ \ \ \ \ t-\ell\ \ \ \ {\rm
odd},\end{array}\right.$ (9)

where ${\mathbb{E}}[G|\ell]$ is the expected number of degenerate shortest
paths of length $\ell$. The coefficient $B(t,\ell)$ is a combinatorial factor
that accounts for the number of distinct RW trajectories that follow a given
shortest path from $i$ to a target node $j$, which resides at a distance
$\ell$ from $i$, and reach $j$ for the first time after $t$ time steps. The
term $(1/c)^{t}$ accounts for the probability that an RW will follow any
specific trajectory of $t$ time steps. This is due to the fact that at each
time step the probability that the RW will hop to each neighbor of the current
node is $1/c$. The right hand side of Eq. (9) is thus a product of the total
number of SPATH trajectories of $t$ time steps by the probability that an RW
will follow a given trajectory.

We now focus on a single shortest path of length $\ell$ between a pair of
nodes $i$ and $j$. The coefficients $B(t,\ell)$ satisfy the recursion
equations

$B(t,\ell)=B(t-1,\ell-1)+(c-1)B(t-1,\ell+1),$ (10)

where the distance satisfies $\ell\geq 1$, the first-passage time satisfies
$t\geq\ell$, and the difference $t-\ell$ is an even number [otherwise
$B(t,\ell)=0$]. The recursion equation (10) is illustrated in Fig. 4,
depicting a pair of nodes $i$ and $j$, at a distance $\ell$ apart. One
neighbor of $i$ resides along the shortest path to $j$ and is thus at a
distance $\ell-1$ from $j$, while the other $c-1$ neighbors of $i$ are at a
distance $\ell+1$ from $j$. Therefore, an RW trajectory starting from $i$ and
ending up at $j$ may step at time $t=1$ either into the neighbor of $i$ that
resides along the shortest path to $j$ or into one of the other $c-1$
neighbors. The boundary condition is $B(\ell,\ell)=1$ for $\ell\geq 1$. In the
special case of $\ell=1$ and $t\geq 3$, the recursion equation is given by

$B(t,1)=(c-1)B(t-1,2).$ (11)

Actually, the $B(t,\ell)$ coefficients are also defined for $\ell=0$. In this
case, they provide the number of RW trajectories that return to the initial
node for the first time at time $t$, and are thus important in the analysis of
the first return problem, recently studied in Ref. [22].

Figure 4:  Illustration of the recursion equation (10) for the number
$B(t,\ell)$ of distinct RW trajectories that start from a random node $i$ and
follow the shortest path to some other node $j$, which resides at a distance
$\ell$ from $i$. In this illustration the RRG is of degree $c=4$.

In Appendix A we present a solution of the recursion relations given by Eq.
(10) for $\ell\geq 1$ and $t\geq\ell$ with the boundary conditions specified
above. It is found that for any distance $\ell\geq 1$ between the initial node
$i$ and the target node $j$ and for any time $t\geq\ell$ the number of
distinct RW trajectories that follow a given shortest path from $i$ to $j$ and
for which the first-passage time is $t$, is given by

$B(t,\ell)=\left\\{\begin{array}[]{ll}\frac{\ell}{t}\binom{t}{\frac{t+\ell}{2}}(c-1)^{\frac{t-\ell}{2}}&\
\ \ \ \ \ \ t-\ell\ \ {\rm even}\\\ 0&\ \ \ \ \ \ \ t-\ell\ \ {\rm
odd},\end{array}\right.$ (12)

where $\binom{n}{m}$ is the binomial coefficient. The coefficient $B(t,\ell)$
captures the contribution of a single shortest path to the distribution of
first passage times via the SPATH scenario.

In order to proceed one needs to account for the contributions of all the
degenerate shortest paths between the initial node and the target node. The
probability that an RW starting from a random initial node $i$ will reach a
random target node $j$ that resides at a distance $\ell$ from $i$ for the
first time via the SPATH scenario is given by

$P({\rm SPATH}|\ell)=\sum_{t=\ell}^{\infty}P(T_{\rm FP}=t,{\rm SPATH}|\ell).$
(13)

Inserting $P(T_{\rm FP}=t,{\rm SPATH}|\ell)$ from Eq. (9) [with $B(t,\ell)$
from Eq. (12)] into Eq. (13) and carrying out the summation, we obtain

$P({\rm SPATH}|\ell)=\left(\frac{1}{c-1}\right)^{\ell}{\mathbb{E}}[G|\ell].$
(14)

The first term on the right hand side of Eq. (14) accounts for the
contribution of a single shortest path while the second term accounts for the
expected number of such paths. Inserting the approximated result for the
degeneracy ${\mathbb{E}}[G|\ell]$, given by Eq. (7), into Eq. (14), we obtain

$P({\rm SPATH}|\ell)\simeq\left(\frac{1}{c-1}\right)^{\ell}+\frac{1}{N}.$ (15)

The first term in Eq. (15) accounts for the contribution of the single
shortest path which is guaranteed to exist, given that the distance between
the initial node $i$ and the target node $j$ is equal to $\ell$. The second
term accounts for the expected contribution of degenerate shortest paths of
length $\ell$.

The complementary probability is given by

$P(\lnot{\rm SPATH}|\ell)\simeq
1-\left(\frac{1}{c-1}\right)^{\ell}-\frac{1}{N}.$ (16)

In Fig. 5 we present analytical results (solid lines) for the probability
$P({\rm SPATH}|\ell)$ that the first-passage of an RW from a random initial
node $i$ to a random target node $j$ which is at a distance $\ell$ from $i$,
will take place via the ${\rm SPATH}$ scenario, as a function of the distance
$\ell$. The results are shown for RRGs of size $N=1000$ and $c=3$ (left),
$c=4$ (center) and $c=10$ (right). The analytical results, obtained from Eq.
(15) are found to be in good agreement with the results obtained from computer
simulations (circles).

Figure 5:  Analytical results (solid lines) for the probability $P({\rm
SPATH}|\ell)$ that the first passage of an RW from a random initial node $i$
to a random target node $j$, which is at a distance $\ell$ from $i$, will
occur via the ${\rm SPATH}$ scenario. The results are presented for RRGs of
size $N=1000$ and for $c=3$ (left), $c=4$ (center) and $c=10$ (right). The
analytical results, obtained from Eq. (15) are in very good agreement with the
results obtained from computer simulations (circles).

The distribution of first-passage times via SPATH trajectories, from a random
node $i$ to a random node $j$ that resides at a distance $\ell$ from $i$, is
given by

$P(T_{\rm FP}=t|\ell,{\rm SPATH})=\frac{P(T_{\rm FP}=t,{\rm
SPATH}|\ell)}{P({\rm SPATH}|\ell)}.$ (17)

Plugging in $P(T_{\rm FP}=t,{\rm SPATH}|\ell)$ from Eq. (9) and $P({\rm
SPATH}|\ell)$ from Eq. (14) into Eq. (17), it is found that $P(T_{\rm
FP}=t|\ell,{\rm SPATH})=0$ for $t<\ell$, while for $t\geq\ell$ it is given by

$P(T_{\rm FP}=t|\ell,{\rm
SPATH})=\left\\{\begin{array}[]{ll}\frac{\ell}{t}\binom{t}{\frac{t+\ell}{2}}\left(1-\frac{1}{c}\right)^{\frac{t+\ell}{2}}\left(\frac{1}{c}\right)^{\frac{t-\ell}{2}}&\
\ \ \ t-\ell\ \ {\rm even}\\\ 0&\ \ \ \ t-\ell\ \ {\rm
odd}.\end{array}\right.$ (18)

The corresponding tail distribution is given by

$P(T_{\rm FP}>t|\ell,{\rm SPATH})=\sum_{t^{\prime}=t+1}^{\infty}P(T_{\rm
FP}=t^{\prime}|\ell,{\rm SPATH}).$ (19)

In Fig. 6 we present analytical results (solid line) for the tail distribution
$P(T_{\rm FP}>t|\ell,{\rm SPATH})$ of first-passage times for RW trajectories
that follow the shortest path between pairs of nodes which are at a distance
$\ell$ from each other, for $\ell=1$ (left), $\ell=2$ (center) and $\ell=3$
(right). The results are shown for RRGs of size $N=1000$ and degree $c=3$. The
analytical results, obtained from Eq. (19) are in very good agreement with the
results obtained from computer simulations (circles).

Figure 6:  Analytical results (solid line) for the tail distribution $P(T_{\rm
FP}>t|\ell,{\rm SPATH})$ of first-passage times of RWs that follow the
shortest paths between pairs of nodes which are at a distance $\ell$ from each
other. The results are presented for RRGs of size $N=1000$ and degree $c=3$
and $\ell=1$ (left), $\ell=2$ (center) and $\ell=3$ (right). The analytical
results, obtained from Eq. (19), are in very good agreement with the results
obtained from computer simulations (circles).

The generating function of the distribution $P(T_{\rm FP}=t|\ell,{\rm SPATH})$
is given by

$V_{\ell}(x)=\sum_{t=1}^{\infty}x^{t}P(T_{\rm FP}=t|\ell,{\rm SPATH}).$ (20)

Such generating functions were studied extensively in the context of RWs on
regular lattices [13]. Inserting $P(T_{\rm FP}=t|\ell,{\rm SPATH})$ from Eq.
(18) into Eq. (20) and carrying out the summation, we obtain

$V_{\ell}(x)=\left(1-\frac{1}{c}\right)^{\ell}x^{\ell}\,_{2}F_{1}\left[\left.\begin{array}[]{c}\frac{\ell}{2},\frac{\ell+1}{2}\\\
\ell+1\end{array}\right|\frac{4(c-1)}{c^{2}}x^{2}\right],$ (21)

where ${}_{2}F_{1}\left[\left.\begin{array}[]{c}a,b\\\
c\end{array}\right|z\right]$ is the hypergeometric function [33]. Applying
identity (98) from Appendix A on the hypergeometric function on the right hand
side of Eq. (21), it can be simplified to

$V_{\ell}(x)=\left[\frac{c-\sqrt{c^{2}-4(c-1)x^{2}}}{2x}\right]^{\ell}.$ (22)

The $r$’th moment of $P(T_{\rm FP}=t|\ell,{\rm SPATH})$ is given by

$\mathbb{E}[T_{\rm FP}^{r}|\ell,{\rm SPATH}]=\sum_{t=1}^{\infty}t^{r}P(T_{\rm
FP}=t|\ell,{\rm SPATH}).$ (23)

Inserting $r=1$ in Eq. (23) we obtain the mean first-passage time
$\mathbb{E}[T_{\rm FP}|\ell,{\rm SPATH}]$. It can also be obtained directly
from the generating function $V_{\ell}(x)$ by

$\mathbb{E}[T_{\rm FP}|\ell,{\rm
SPATH}]=\frac{dV_{\ell}(x)}{dx}\bigg{|}_{x=1},$ (24)

which yields

$\mathbb{E}[T_{\rm FP}|\ell,{\rm SPATH}]=\frac{c}{c-2}\ell.$ (25)

The second factorial moment is given by

$\mathbb{E}[T_{\rm FP}(T_{\rm FP}-1)|\ell,{\rm
SPATH}]=\frac{d^{2}V_{\ell}(x)}{dx^{2}}\bigg{|}_{x=1},$ (26)

which yields

$\mathbb{E}[T_{\rm FP}(T_{\rm FP}-1)|\ell,{\rm
SPATH}]=\frac{c^{2}\ell^{2}}{(c-2)^{2}}-\frac{c^{2}-8c+8}{(c-2)^{2}}c\ell.$
(27)

Combining the results for the first moment and the second factorial moment, we
obtain

$\mathbb{E}[T_{\rm FP}^{2}|\ell,{\rm
SPATH}]=\frac{4c(c-1)}{(c-2)^{3}}\ell+\left(\frac{c}{c-2}\right)^{2}\ell^{2}.$
(28)

Using the results presented above for the first and second moments we obtain
the variance, which is given by

${\rm Var}[T_{\rm FP}|\ell,{\rm SPATH}]=\frac{4c(c-1)}{(c-2)^{3}}\ell.$ (29)

The probability that the first-passage trajectory of an RW from a random
initial node $i$ to a random target node $j$ in an RRG of a finite size $N$
will follow the shortest path from $i$ to $j$ is given by

$P({\rm SPATH})=\sum_{\ell=1}^{N-1}P({\rm SPATH}|\ell)P(L=\ell),$ (30)

where $P({\rm SPATH}|\ell)$ is given by Eq. (14) and $P(L=\ell)$ is given by
Eqs. (1)-(4). Using Eq. (4), we obtain

$P({\rm SPATH})=\sum_{\ell=1}^{N-1}P({\rm
SPATH}|\ell)\left[P(L>\ell-1)-P(L>\ell)\right].$ (31)

Rearranging the summation indices, we obtain

$P({\rm SPATH})=P({\rm SPATH}|1)+\sum_{\ell=1}^{N-2}\left[P({\rm
SPATH}|\ell+1)-P({\rm SPATH}|\ell)\right]P(L>\ell).$ (32)

The transformation from Eq. (30) to Eq. (32) essentially amounts to a
summation by parts. Inserting $P({\rm SPATH}|\ell)$ from Eq. (14) into Eq.
(32) and rearranging terms, we obtain

$P({\rm SPATH})\simeq
1+\frac{1}{N}-\frac{c-2}{c-1}\sum_{\ell=0}^{N-1}\left(\frac{1}{c-1}\right)^{\ell}P(L>\ell),$
(33)

where we use the fact that $P(L>0)=1$. Clearly, the upper limit of the
summation in Eq. (33) can be replaced by $\infty$ with negligible effect on
the result. Using the definition of $b$ from Eq. (3), we rewrite Eq. (33) in
the form

$P({\rm SPATH})\simeq
1+\frac{1}{N}-\frac{c-2}{c-1}\sum_{\ell=0}^{\infty}e^{-b\ell}P(L>\ell).$ (34)

It can also be written in the form

$P({\rm SPATH})\simeq 1+\frac{1}{N}-\frac{c-2}{c-1}M_{0}$ (35)

where

$M_{0}=\mathcal{L}[P(L>\ell)](s=b)=\sum_{\ell=0}^{\infty}e^{-b\ell}P(L>\ell)$
(36)

and $\mathcal{L}[P(L>\ell)](s)$ is the discrete Laplace transform (or the
unilateral Z-transform) of the tail distribution $P(L>\ell)$, evaluated at
$s=b$. An explicit expression for $M_{0}$ is given by Eq. (114). It is based
on a recent calculation of the discrete Laplace transform
$\mathcal{L}[P(L>\ell)](s)$ [32]. In the large network limit it can be reduced
to Eq. (115).

Eqs. (33)-(36) provide an interesting relation between the geometric
properties of the network, captured by $P(L>\ell)$, and the probability
$P({\rm SPATH})$ which is a dynamical property of the RW trajectories. It
exemplifies the potential use of the DSPL in the analysis of dynamical
processes on networks. Inserting $M_{0}$ from Eq. (115) into Eq. (35) and
rearranging terms, we obtain

$P({\rm
SPATH})\simeq\left(\frac{c}{c-1}\right)\frac{1}{N}\left[\frac{\ln\left(\frac{c-2}{c}N\right)-\gamma+1}{\ln(c-1)}+\frac{c^{2}-6c+4}{2c(c-2)}\right]+{\mathcal{O}}\left(\frac{1}{N^{2}}\right),$
(37)

where $\gamma$ is the Euler-Mascheroni constant [33]. Using the result for the
mean distance $\langle L\rangle$, presented in Ref. [32], Eq. (37) can be
written in the form

$P({\rm SPATH})\simeq\left(\frac{c}{c-1}\right)\frac{1}{N}\left[\langle
L\rangle+\frac{1}{\ln(c-1)}-2\frac{c-1}{c(c-2)}\right]+\mathcal{O}\left(\frac{1}{N^{2}}\right).$
(38)

In the limit of large and dense networks, Eq. (38) can be simplified to

$P({\rm SPATH})\simeq\left(\frac{c}{c-1}\right)\frac{\langle
L\rangle}{N}+\mathcal{O}\left[\frac{1}{N\ln(c-1)}\right].$ (39)

In the infinite network limit one expects the probability $P({\rm SPATH})$ to
vanish. This is due to the fact that as $N$ is increased (keeping $c$
constant) the typical distance between pairs of random nodes increases. Thus
the probability that an RW starting from a random initial node will follow the
shortest path to a random target node decreases as $N$ is increased.

In Fig. 7 we present analytical results (solid line) for the probability
$P({\rm SPATH})$ that the first-passage of an RW from a random initial node
$i$ to a random target node $j$ will occur via the ${\rm SPATH}$ scenario on
RRGs of size $N=1000$ as a function of the degree $c$. The analytical results
are obtained from Eq. (35), where $M_{0}$ is given by Eq. (114). They are
found to be in very good agreement with the results obtained from computer
simulations. The simulations are performed on an ensemble of RRGs that are
constructed using the procedure presented in Sec. 2. For each instance of a
first-passage RW trajectory we select a random initial node $i$ and a random
target node $j$. The trajectory of an RW that starts from node $i$ is recorded
until it visits node $j$ for the first time. In order to qualify as an SPATH
trajectory it should pass two tests. First, it should not include any cycles.
This means that the subgraph consisting of the nodes that the RW visited and
the edges it used along the way from $i$ to $j$ must be a tree. Second, the
distance between $i$ and $j$ on this subgraph must be equal to the distance
between $i$ and $j$ on the underlying RRG. The fraction of first-passage RW
trajectories that meet these two criteria is used to estimate $P({\rm
SPATH})$.

Figure 7:  Analytical results (solid line) for the probability $P({\rm
SPATH})$ that the first passage of an RW from a random initial node $i$ to a
random target node $j$ will occur via the ${\rm SPATH}$ scenario on RRGs of
size $N=1000$ as a function of the degree $c$. The analytical results,
obtained from Eq. (35), where $M_{0}$ is given by Eq. (114) They are found to
be in very good agreement with the results obtained from computer simulations
(circles).

The distribution of first-passage times from a random initial node $i$ to a
random target node $j$, under the condition that the RW follows the shortest
path from $i$ to $j$, is given by

$P(T_{\rm FP}=t|{\rm SPATH})=\sum_{\ell=1}^{t}P(T_{\rm FP}=t|\ell,{\rm
SPATH})P(L=\ell|{\rm SPATH}),$ (40)

where

$P(L=\ell|{\rm SPATH})=\frac{P({\rm SPATH}|\ell)P(L=\ell)}{P({\rm SPATH})}.$
(41)

The probability $P(T_{\rm FP}=t|\ell,{\rm SPATH})$ makes a non-vanishing
contribution to the sum only for even (and non-negative) values of $t-\ell$.
Therefore, in Eq. (40) we need to distinguish between even and odd values of
$t$. In case that $t$ is even, the sum on the right hand side is over even
values of $\ell$, while if $t$ is odd the sum is over odd values of $\ell$.
Inserting $P(T_{\rm FP}=t|\ell,{\rm SPATH})$ from Eq. (18) into Eq. (40), we
find that for even values of the time $t$

$\displaystyle P(T_{\rm FP}$ $\displaystyle=t|{\rm
SPATH})\simeq\frac{(c-1)^{\frac{t}{2}}}{tc^{t}P({\rm SPATH})}\times$ (42)
$\displaystyle\sum\limits_{k=1}^{\frac{t}{2}}\frac{2k}{(c-1)^{k}}\binom{t}{\frac{t}{2}+k}\left[1+\frac{(c-1)^{2k}}{N}\right]P(L=2k),$

while for odd values of $t$

$\displaystyle P(T_{\rm FP}$ $\displaystyle=t|{\rm
SPATH})\simeq\frac{(c-1)^{\frac{t+1}{2}}}{tc^{t}P({\rm SPATH})}\times$ (43)
$\displaystyle\sum\limits_{k=1}^{\frac{t+1}{2}}\frac{2k-1}{(c-1)^{k}}\binom{t}{\frac{t-1}{2}+k}\left[1+\frac{(c-1)^{2k-1}}{N}\right]P(L=2k-1).$

The tail distribution of first-passage times in the SPATH scenario is given by

$P(T_{\rm FP}>t|{\rm SPATH})=\sum_{t^{\prime}=t+1}^{\infty}P(T_{\rm
FP}=t^{\prime}|{\rm SPATH}).$ (44)

In Fig. 8 we present analytical results for the tail distribution $P(T_{\rm
FP}>t|{\rm SPATH})$ of first-passage times (solid lines) for RW trajectories
that follow the shortest path from a random initial node $i$ to a random
target node $j$ on an RRG of size $N=1000$ and degrees $c=3$, $c=4$ and
$c=10$. The analytical results, obtained from Eq. (44) are in very good
agreement with the results obtained from computer simulations (circles).

Figure 8:  Analytical results (solid lines) for the tail distribution
$P(T_{\rm FP}>t|{\rm SPATH})$ of first-passage times of RWs that follow the
shortest path from a random initial node $i$ to a random target node $j$ on an
RRG of size $N=1000$ and degrees $c=3$ (left), $c=4$ (center) and $c=10$
(right). The analytical results, obtained from Eqs. (44), are in very good
agreement with the results obtained from computer simulations (circles).

The first and second moments of the distribution of first-passage times
between a random initial node $i$ and a random target node $j$, under the
condition that the RW follows the shortest path between $i$ and $j$ are given
by

$\mathbb{E}[T_{\rm FP}^{r}|{\rm SPATH}]=\sum_{\ell=1}^{N-1}\mathbb{E}[T_{\rm
FP}^{r}|\ell,{\rm SPATH}]P(L=\ell|{\rm SPATH}),$ (45)

where $r=1$ and $2$, respectively. Inserting the first moment
$\mathbb{E}[T_{\rm FP}|\ell,{\rm SPATH}]$ from Eq. (25) into Eq. (45) and
carrying out the summation, we obtain

$\mathbb{E}[T_{\rm FP}|{\rm SPATH}]\simeq\frac{1}{P({\rm
SPATH})}\left(\frac{c}{c-2}\right)\sum_{\ell=1}^{N-1}\ell\left[\left(\frac{1}{c-1}\right)^{\ell}+\frac{1}{N}\right]P(L=\ell).$
(46)

Using summation by parts and collecting terms, we obtain

$\mathbb{E}[T_{\rm FP}|{\rm SPATH}]\simeq\frac{1}{P({\rm
SPATH})}\left(\frac{c}{c-2}\right)\left[\frac{\langle
L\rangle}{N}+\frac{1}{c-1}\sum_{\ell=0}^{N-1}\frac{1-(c-2)\ell}{(c-1)^{\ell}}P(L>\ell)\right].$
(47)

Using the results presented in Appendix B for the sums $M_{0}$ and $M_{1}$, we
obtain

$\mathbb{E}[T_{\rm FP}|{\rm SPATH}]\simeq\frac{1}{P({\rm
SPATH})}\left(\frac{c}{c-2}\right)\left[\frac{\langle
L\rangle}{N}+\frac{M_{0}-(c-2)M_{1}}{c-1}\right],$ (48)

where $M_{0}$ is given by Eq. (114), $M_{1}$ is given by Eq. (119) and
$\langle L\rangle$ is the mean distance. In the large network limit, one can
express $M_{0}$ by Eq. (115), $M_{1}$ by Eq. (127) and $P({\rm SPATH})$ by Eq.
(38). This yields

$\mathbb{E}[T_{\rm FP}|{\rm
SPATH}]\simeq\frac{1}{2}\left(\frac{c}{c-2}\right)\left[\langle
L\rangle+1-4\frac{c-1}{c(c-2)}+\frac{2}{\ln(c-1)}\right]+{\mathcal{O}}\left(\frac{1}{\ln
N}\right).$ (49)

The variance can be calculated by applying a similar approach to Eq. (29). It
yields

${\rm Var}[T_{\rm FP}|{\rm SPATH}]\simeq\frac{1}{P({\rm
SPATH})}\frac{4c(c-1)}{(c-2)^{3}}\left[\frac{\langle
L\rangle}{N}+\frac{M_{0}-(c-2)M_{1}}{c-1}\right].$ (50)

Comparing Eqs. (48) and (50) it is found that

${\rm Var}[T_{\rm FP}|{\rm SPATH}]\simeq
4\frac{c-1}{(c-2)^{2}}\mathbb{E}[T_{\rm FP}|{\rm SPATH}].$ (51)

This implies that the distribution $P(T_{\rm FP}|{\rm SPATH})$ becomes
narrower as $c$ is increased.

##  5 The distribution of first-passage times via non-SPATH trajectories

In this section we derive a closed form expression for the distribution
$P(T_{\rm FP}>t|\lnot{\rm SPATH})$ of first-passage times between a random
initial node $i$ and a random target node $j$, under the condition that the
first-passage trajectory does not follow the shortest path from $i$ to $j$. In
case that the distance $\ell$ between $i$ and $j$ is known, the distribution
of first-passage times, conditioned on $\ell$, is denoted by $P(T_{\rm
FP}>t|\ell,\lnot{\rm SPATH})$. Since an RW trajectory from $i$ to $j$ that
does not follow the shortest path must be longer than $\ell$, we conclude that
$P(T_{\rm FP}>t|\ell,\lnot{\rm SPATH})=1$ for $t\leq\ell$.

Starting from a random initial node $i$ the RW visits, on average, $\langle
S\rangle_{t}$ distinct nodes up to time $t$. In case that the distance between
$i$ and $j$ is $\ell$, the earliest time at which the RW may visit the target
node via a trajectory that does not follow the shortest path is $t=\ell+1$.
Therefore, the tail distribution of first-passage times, conditioned on the
distance $\ell$, satisfies

$P(T_{\rm FP}>t|\ell,\lnot{\rm SPATH})=1-\frac{\langle S\rangle_{t-\ell}}{N},$
(52)

where [22, 34]

$\langle
S\rangle_{t}=N\left[1-e^{-\left(\frac{c-2}{c-1}\right)\frac{t}{N}}\right].$
(53)

Inserting $\langle S\rangle_{t}$ from Eq. (53) into Eq. (52), we obtain

$P(T_{\rm FP}>t|\ell,\lnot{\rm SPATH})=\left\\{\begin{array}[]{ll}1&\ \ \ \
t\leq\ell\\\ \exp\left[-\left(\frac{c-2}{c-1}\right)\frac{t-\ell}{N}\right]&\
\ \ \ t>\ell.\end{array}\right.$ (54)

The tail distribution of first-passage times is given by

$P(T_{\rm FP}>t|\lnot{\rm SPATH})=\sum_{\ell=1}^{\infty}P(T_{\rm
FP}>t|\ell,\lnot{\rm SPATH})P(L=\ell|\lnot{\rm SPATH}),$ (55)

where

$P(L=\ell|\lnot{\rm SPATH})=\frac{P(\lnot{\rm
SPATH}|\ell)P(L=\ell)}{P(\lnot{\rm SPATH})}.$ (56)

In Eq. (56) the probability $P(\lnot{\rm SPATH}|\ell)$ is given by Eq. (16)
and the probability $P(\lnot{\rm SPATH})=1-P({\rm SPATH})$, where $P({\rm
SPATH})$ is given by Eq. (35). Inserting $P(T_{\rm FP}>t|\ell,\lnot{\rm
SPATH})$ from Eq. (54) into Eq. (55), we obtain

$\displaystyle P(T_{\rm FP}>t|\lnot{\rm
SPATH})=\sum_{\ell=t+1}^{\infty}P(L=\ell|\lnot{\rm SPATH})$
$\displaystyle+\exp\left[-\left(\frac{c-2}{c-1}\right)\frac{t}{N}\right]\sum_{\ell=1}^{t}\exp\left[\left(\frac{c-2}{c-1}\right)\frac{\ell}{N}\right]P(L=\ell|\lnot{\rm
SPATH}).$ (57)

Since the diameter of an RRG scales logarithmically with the network size
[35], in the large network limit and for $t\gg\ln N$ Eq. (57) can be
simplified to the form

$P(T_{\rm FP}>t|\lnot{\rm
SPATH})=\exp\left[-\left(\frac{c-2}{c-1}\right)\frac{t}{N}\right].$ (58)

The conditional probability mass function of first-passage times for
trajectories that do not follow the shortest path is given by

$\displaystyle P(T_{\rm FP}=t|\lnot{\rm SPATH})$ $\displaystyle=$
$\displaystyle P(T_{\rm FP}>t-1|\lnot{\rm SPATH})$ (59) $\displaystyle-$
$\displaystyle P(T_{\rm FP}>t|\lnot{\rm SPATH}).$

Inserting $P(T_{\rm FP}>t|\lnot{\rm SPATH})$ from Eq. (58) into Eq. (59) we
obtain

$P(T_{\rm FP}=t|\lnot{\rm
SPATH})=\left\\{\exp\left[{\left(\frac{c-2}{c-1}\right)\frac{1}{N}}\right]-1\right\\}\exp\left[-\left(\frac{c-2}{c-1}\right)\frac{t}{N}\right].$
(60)

In the large network limit, where $N\gg 1$, Eq. (60) can be approximated by

$P(T_{\rm FP}=t|\lnot{\rm
SPATH})=\left(\frac{c-2}{c-1}\right)\frac{1}{N}\exp\left[-\left(\frac{c-2}{c-1}\right)\frac{t}{N}\right].$
(61)

The moments $\mathbb{E}[T_{\rm FP}^{r}|\lnot{\rm SPATH}]$, $r=1,2,\dots$, can
be obtained from the tail-sum formula [36]

$\mathbb{E}[T_{\rm FP}^{r}|\lnot{\rm
SPATH}]=\sum_{t=0}^{\infty}[(t+1)^{r}-t^{r}]P(T_{\rm FP}>t|\lnot{\rm SPATH}).$
(62)

In particular, the mean first-passage time $\mathbb{E}[T_{\rm FP}|\lnot{\rm
SPATH}]$ can be obtained by inserting $r=1$ in Eq. (62), which yields

$\mathbb{E}[T_{\rm FP}|\lnot{\rm SPATH}]=\sum_{t=0}^{\infty}P(T_{\rm
FP}>t|\lnot{\rm SPATH}).$ (63)

Similarly, inserting $r=2$ in Eq. (62) we obtain the second moment
$\mathbb{E}[T_{\rm FP}^{2}|\lnot{\rm SPATH}]$ of the distribution of first-
passage times, which is given by

$\mathbb{E}[T_{\rm FP}^{2}|\lnot{\rm SPATH}]=\sum_{t=0}^{\infty}(2t+1)P(T_{\rm
FP}>t|\lnot{\rm SPATH}).$ (64)

Inserting the tail distribution of Eq. (58) into Eq. (63) we obtain the mean
first-passage time, which is given by

$\mathbb{E}[T_{\rm FP}|\lnot{\rm
SPATH}]=\frac{1}{1-\exp\left[-\left(\frac{c-2}{c-1}\right)\frac{1}{N}\right]}.$
(65)

In the large network limit, where $N\gg 1$, Eq. (65) can be approximated by

$\mathbb{E}[T_{\rm FP}|\lnot{\rm SPATH}]\simeq\frac{c-1}{c-2}N,$ (66)

where $c\geq 3$. The result of Eq. (66) was obtained in Ref. [37] using
different considerations. Interestingly, in the dense network limit of $c\gg
1$ it is found that $\langle T_{\rm FP}\rangle\simeq N$, while in the dilute
network limit of $c=3$, $\langle T_{\rm FP}\rangle\simeq 2N$. This reflects
the larger fraction of backtracking steps in RRGs of low degree.

Inserting the tail distribution of Eq. (58) into Eq. (64) we obtain the second
moment

$\mathbb{E}[T_{\rm FP}^{2}|\lnot{\rm
SPATH}]=\frac{1+\exp\left[-\left(\frac{c-2}{c-1}\right)\frac{1}{N}\right]}{\left\\{1-\exp\left[-\left(\frac{c-2}{c-1}\right)\frac{1}{N}\right]\right\\}^{2}}.$
(67)

Combining the results for the first and second moments, we obtain the
variance, which is given by

${\rm Var}[T_{\rm FP}|\lnot{\rm
SPATH}]=\frac{\exp\left[-\frac{c-2}{(c-1)N}\right]}{\left\\{1-\exp\left[-\frac{c-2}{(c-1)N}\right]\right\\}^{2}}.$
(68)

##  6 The overall distribution of first-passage times

For any value of the distance $\ell$ between the initial node $i$ and the
target node $j$, the conditional distribution of first-passage times can be
written in the form

$\displaystyle P(T_{\rm FP}=t|\ell)$ $\displaystyle=$ $\displaystyle P(T_{\rm
FP}=t|\ell,{\rm SPATH})P({\rm SPATH}|\ell)$ (69) $\displaystyle+$
$\displaystyle P(T_{\rm FP}=t|\ell,\lnot{\rm SPATH})P(\lnot{\rm SPATH}|\ell),$

where the conditional tail distributions $P(T_{\rm FP}=t|\ell,{\rm SPATH})$
and $P(T_{\rm FP}=t|\ell,\lnot{\rm SPATH})=P(T_{\rm FP}=t|\lnot{\rm SPATH})$
are given by Eqs. (18) and (61), respectively, while the probabilities $P({\rm
SPATH}|\ell)$ and $P(\lnot{\rm SPATH}|\ell)$ are given by Eqs. (15) and (16),
respectively.

The mean first-passage time from a random initial node $i$ to a random target
node $j$, under the condition that the distance between $i$ and $j$ is $\ell$,
is given by

$\displaystyle\mathbb{E}[T_{\rm FP}|\ell]$ $\displaystyle=$
$\displaystyle\mathbb{E}[T_{\rm FP}|\ell,{\rm SPATH}]P({\rm SPATH}|\ell)$ (70)
$\displaystyle+$ $\displaystyle\mathbb{E}[T_{\rm FP}|\ell,\lnot{\rm
SPATH}]P(\lnot{\rm SPATH}|\ell),$

where $\mathbb{E}[T_{\rm FP}|\ell,{\rm SPATH}]$ and $\mathbb{E}[T_{\rm
FP}|\ell,\lnot{\rm SPATH}]=\mathbb{E}[T_{\rm FP}|\lnot{\rm SPATH}]$ are given
by Eqs. (25) and (65), respectively.

The overall distribution of first-passage times can be written in the form

$\displaystyle P(T_{\rm FP}=t)$ $\displaystyle=$ $\displaystyle P(T_{\rm
FP}=t|{\rm SPATH})P({\rm SPATH})$ (71) $\displaystyle+$ $\displaystyle
P(T_{\rm FP}=t|\lnot{\rm SPATH})P(\lnot{\rm SPATH}),$

where $P(T_{\rm FP}=t|{\rm SPATH})$ is given by Eqs. (42) and (43), for even
and odd times, respectively, while $P(T_{\rm FP}=t|\lnot{\rm SPATH})$ is given
by Eq. (60). The corresponding tail distribution is given by

$P(T_{\rm FP}>t)=\sum_{t^{\prime}=t+1}^{\infty}P(T_{\rm FP}=t^{\prime}),$ (72)

where $P(T_{\rm FP}=t)$ is given by Eq. (71).

The mean first-passage time $\langle T_{\rm FP}\rangle$ can be expressed in
the form

$\displaystyle\langle T_{\rm FP}\rangle$ $\displaystyle=$
$\displaystyle\mathbb{E}[T_{\rm FP}|{\rm SPATH}]P({\rm SPATH})$ (73)
$\displaystyle+$ $\displaystyle\mathbb{E}[T_{\rm FP}|\lnot{\rm
SPATH}]P(\lnot{\rm SPATH}),$

where $\mathbb{E}[T_{\rm FP}|{\rm SPATH}]$ is given by Eq. (48) and
$\mathbb{E}[T_{\rm FP}|\lnot{\rm SPATH}]$ is given by Eq. (65). The mean first
passage time $\langle T_{\rm FP}\rangle$ was recently calculated for specific
network instances and a given pair of initial and target nodes. [38, 17, 39,
40]. These calculations were done using matrix methods that apply to a wide
range of network structures inclusing weighted networks.

In Fig. 9 we present analytical results for the tail distribution $P(T_{\rm
FP}>t)$ of first-passage times of RWs on RRGs of size $N=1000$ and $c=3$
(left), $c=4$ (center) and $c=10$ (right). The analytical results, obtained
from Eq. (72) are in very good agreement with the results obtained from
computer simulations (circles). At the time scales shown here the first
passage process is dominated by the non-SPATH scenario. Thus, the tail
distribution of first passage times is essentially an exponential
distribution.

Figure 9:  Analytical results (solid lines) for the tail distribution
$P(T_{\rm FP}>t)$ of first-passage times of RWs on RRGs of size $N=1000$ and
degrees $c=3$ (left), $c=4$ (center) and $c=10$ (right). The analytical
results, obtained from Eqs. (72) are in very good agreement with the results
obtained from computer simulations (circles).

In Fig. 10 we present analytical results (solid line) for the mean first-
passage time $\langle T_{\rm FP}\rangle$ as a function of the degree $c$ for
RWs on RRGs of size $N=1000$. The analytical results, obtained from Eq. (73)
are in very good agreement with the results obtained from computer simulations
(circles). The mean first passage time is a monotonically decreasing function
of $c$, that converges towards $\langle T_{\rm FP}\rangle\simeq N$ in the
dense-network limit. We also present analytical results for the conditional
expectation values ${\mathbb{E}}[T_{\rm FP}|L=\ell]$ for $\ell=1$ (dashed
line), $\ell=2$ (dashed-dotted line) and $\ell=3$ (dotted line). The
analytical results, obtained from Eq. (70), are in very good agreement with
the simulation results (symbols). In the special case of $\ell=1$ the
conditional expectation value ${\mathbb{E}}[T_{\rm FP}|L=1]$ is essentially
independent of $c$, resulting in a plateau in Fig. 10. More precisely, it
satisfies ${\mathbb{E}}[T_{\rm FP}|L=1]=N-1+\mathcal{O}(1/c)$. This result is
consistent with the result for the mean first return time, $\langle T_{\rm
FR}\rangle=N$ [22]. The difference of one step is due to the fact that the
first step in the first return problem brings the RW to a distance $\ell=1$
from the initial node (which is also the target node). This implies that
$\langle T_{\rm FR}\rangle={\mathbb{E}}[T_{\rm FP}|L=1]+1$. As $\ell$ is
increased the conditional expectation values ${\mathbb{E}}[T_{\rm FP}|L=\ell]$
converge towards $\langle T_{\rm FP}\rangle$. This convergence exemplifies the
fact that the SPATH scenario is significant only in the sparse network limit
where $c$ is small and only when the distance $\ell$ between the initial node
and target node is very small.

Figure 10:  Analytical results (solid line) for the mean first-passage time
$\langle T_{\rm FP}\rangle$ of RWs on RRGs of size $N=1000$ as a function of
the degree $c$. The analytical results, obtained from Eq. (73) are in very
good agreement with the results obtained from computer simulations (circles).
We also present analytical results for the conditional expectation values
${\mathbb{E}}[T_{\rm FP}|L=\ell]$ for $\ell=1$ (dashed line), $\ell=2$
(dashed-dotted line) and $\ell=3$ (dotted line). The analytical results,
obtained from Eq. (70), are in very good agreement with the simulation results
($\times$, $\square$ and $\triangledown$, respectively). As $\ell$ is
increased the conditional expectation values converge towards $\langle T_{\rm
FP}\rangle$.

##  7 Summary and Discussion

We presented analytical results for the distribution of first-passage times of
RWs on RRGs of degree $c\geq 3$ and of a finite size $N$. We calculated the
tail distribution of first-passage times $P(T_{\rm FP}>t)$ from a random
initial node $i$ to a random target node $j$. We identified two types of
first-passage trajectories, namely trajectories that follow the shortest path
between $i$ and $j$ (SPATH trajectories) and those that deviate from the
shortest path (non-SPATH trajectories). Using this distinction we derived
closed form analytical expressions for the tail distribution of first-passage
times for each one of the two scenarios. It was found that the probability
$P({\rm SPATH}|\ell)$ that the first passage trajectory from an initial node
$i$ to a target node $j$ that resides at a distance $\ell$ from $i$ will be an
SPATH trajectory decays exponentially like $1/(c-1)^{\ell}$ with the distance
$\ell$. Therefore, the SPATH scenario is probable only when the network is
sparse and the distance $\ell$ between the initial node and the target node is
small. The probability that the first passage trajectory from a random initial
node $i$ to a random target node $j$ will be an SPATH trajectory scales like
$P({\rm SPATH})\sim\ln N/N$, which decreases as the network size is increased.
Thus, overall the SPATH scenario is a low probability scenario. In the SPATH
scenario, the mean first passage time scales like $\mathbb{E}[T_{\rm FP}|{\rm
SPATH}]\sim\langle L\rangle\sim\ln N$, where $\langle L\rangle$ is the mean
distance between pairs of nodes in the network. In the non-SPATH scenario, the
mean first passage time scales like $\mathbb{E}[T_{\rm FP}|\lnot{\rm
SPATH}]\sim N$.

The first passage process studied in this paper is an important landmark in
the life-cycle of an RW on an RRG. Another important event is the first
hitting process, which is the first time in which the RW enters a previously
visited node [41, 42]. This event represents the interaction of an RW with its
own trajectory rather than with a pre-defined target node. The characteristic
time scale of the first hitting process is $t\sim\min\\{c,\sqrt{N}\\}$, namely
$t\sim c$ in dilute networks and $t\sim\sqrt{N}$ in dense networks. In both
cases the first hitting time is typically much shorter than the first-passage
time [41, 42]. Note that the terminology on first hitting processes in not
universal across the scientific literature, and in some cases first passage
times are referred to as first hitting times.

Yet 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$ [34, 43]. This means that on average an RW visits each node $\ln N$ times
before it completes visiting all the nodes in the network at least once. The
distribution $P(T_{\rm C}\leq t)$ of cover times can be obtained from the
distribution of first passage times using the framework of extreme-value
theory. The cover time can be considered as the maximum among $N-1$ first
passage times from the initial node $i$ to all the other nodes in the network.
Therefore, under the assumption that the distributions of first passage times
for different nodes are independent, the distribution of cover times satisfies

$P(T_{\rm C}>t)=1-[1-P(T_{\rm FP}>t)]^{N-1}.$ (74)

The cover time involves very long trajectories, where the non-SPATH scenario
is dominant over the SPATH scenario. Thus, in this context it is suitable to
approximate the distribution of first passage times $P(T_{\rm FP}>t)$ by
$P(T_{\rm FP}>t|\lnot{\rm SPATH})$, which is given by Eq. (58). Inserting this
expression into Eq. (74), it is found that the distribution of cover times
follows a discrete Gumbel distribution, known from extreme value theory, which
takes the form [44]

$P(T_{\rm C}>t)\simeq
1-\exp\left[-\exp\left({-\frac{t-\mu}{\beta}}\right)\right],$ (75)

where

$\mu=\frac{c-1}{c-2}N\ln(N-1)$ (76)

is called the location parameter and

$\beta=\frac{c-1}{c-2}N$ (77)

is called the scale parameter. This is in agreement with the results of Ref.
[34]. The location parameter $\mu$ is equal to the mode of the Gumbel
distribution. The scale parameter $\beta$ is equal to the standard deviation
up to a constant factor of order $1$. The Gumbel distribution often emerges as
the distribution of the maxima among sets of $n$ independent random variables
drawn from the same distribution. It is one of the three possible families of
extreme value distributions specified by the extreme value theory, namely the
Gumbel, Fréchet and Weibull families [44, 45, 46, 47, 48]. The distribution of
first passage times exhibits an exponential tail. It thus meets the criterion
for the emergence of the Gumbel distribution in the Fisher-Tippet-Gnedenko
theorem [45, 46, 47, 48]. Note that the first passage times of adjacent target
nodes may be correlated. However, such correlations appear to have little
effect on the distribution of cover times.

This work was supported by the Israel Science Foundation grant no. 1682/18.

##  Appendix A Calculation of the combinatorial factor $B(t,\ell)$

In this Appendix we solve the recursion equations for the number $B(t,\ell)$
of distinct RW trajectories of length $t$ between a pair of nodes $i$ and $j$
which reside at a distance $\ell$ apart from each other and reach $j$ for the
first time after $t$ time steps. The recursion equations are shown in Eq.
(10). To solve the equation we express $B(t,\ell)$ in the form

$B(t,0)=c(c-1)^{\frac{t-2}{2}}b(t,0)$ (78)

for $\ell=0$, and in the form

$B(t,\ell)=(c-1)^{\frac{t-\ell}{2}}b(t,\ell)$ (79)

for $\ell\geq 1$. Inserting these relations into Eq. (10), we obtain

$b(t,\ell)=b(t-1,\ell-1)+b(t-1,\ell+1),$ (80)

for $\ell\geq 2$ and $t\geq\ell$. In the special cases of $\ell=0,1$ and
$t\geq 2$, we obtain $b(t,\ell)=b(t-1,\ell+1)$. The transformation presented
in Eqs. (78) and (79) factors out the dependence on the mean degree $c$ and
greatly simplifies the recursion equations for $b(t,\ell)$. In order to solve
the recursion equations given by Eq. (80), we introduce the generating
function

$G_{t}(x)=\sum_{\ell=0}^{\infty}b(t,\ell)x^{\ell}.$ (81)

Multiplying Eq. (80) by $x^{\ell}$ and summing up over $\ell$, we obtain

$G_{t}(x)=\left(x+\frac{1}{x}\right)\left[G_{t-1}(x)-G_{t-1}(0)\right],$ (82)

for $t\geq 2$, while for $t=1$, $G_{1}(x)=x$. Applying the Z-transform with
respect to time, we obtain another generating function of the form

$\Phi(x,\omega)=\sum_{t=1}^{\infty}G_{t}(x)\omega^{t}.$ (83)

Multiplying Eq. (82) by $\omega^{t}$ and summing up over $t$, we obtain

$\Phi(x,\omega)=\omega
x+\omega\left(x+\frac{1}{x}\right)\left[\Phi(x,\omega)-\Phi(0,\omega)\right].$
(84)

Solving for $\Phi(x,\omega)$, we obtain

$\Phi(x,\omega)=\left[1-\left(1-\frac{x^{2}+1}{x}\omega\right)^{-1}\right]\left[\Phi(0,\omega)-\frac{x^{2}}{x^{2}+1}\right],$
(85)

where $\Phi(0,\omega)$ is a boundary condition. In fact, one can determine
$\Phi(0,\omega)$ directly from combinatorial considerations. Note that

$\Phi(0,\omega)=\sum_{t=1}^{\infty}b(t,0)\omega^{t}.$ (86)

As mentioned in the main text, the coefficient $B(t,0)$ accounts for the
number of distinct RW trajectories that return to the initial node after $t$
time under the condition that these trajectories have not visited the initial
node at earlier times [22]. It can be expressed in terms of the Catalan
numbers $C_{k}$, which count the number of mountain ranges of length $2k$
[49]. More specifically,

$B(t,0)=\left\\{\begin{array}[]{ll}c(c-1)^{\frac{t}{2}-1}C_{\frac{t}{2}-1}&\ \
\ \ \ \ \ t\ \ {\rm even}\\\ 0&\ \ \ \ \ \ \ t\ \ {\rm
odd},\end{array}\right.$ (87)

where

$C_{k}=\frac{(2k)!}{k!\left(k+1\right)!}=\frac{1}{2k+1}\binom{2k+1}{k+1},$
(88)

and $\binom{n}{m}$ is the binomial coefficient.

From the definition of $b(t,0)$ and Eq. (87), it is found that for even time
steps $b(t,0)$ coincides with the Catalan number $C_{\frac{t-2}{2}}$, while
for odd time steps it vanishes. Therefore,

$\Phi(0,\omega)=\sum_{k=0}^{\infty}C_{k}\omega^{2k+2}.$ (89)

Inserting $\Phi(0,\omega)$ from Eq. (89) into Eq. (85) and expanding it in
powers of $\omega$, we obtain

$\displaystyle\Phi(x,\omega)$ $\displaystyle=$ $\displaystyle
x\omega+(x^{2}+1)\omega^{2}$ (90) $\displaystyle+$
$\displaystyle\sum_{t=3}^{\infty}\left[x\left(\frac{x^{2}+1}{x}\right)^{t-1}-\sum_{k=0}^{\lfloor\frac{t-3}{2}\rfloor}C_{k}\left(\frac{x^{2}+1}{x}\right)^{t-2k-2}\right]\omega^{t},$

where the floor function $\lfloor x\rfloor$ is the largest integer which is
smaller than $x$. Following Eq. (83) one can extract the generating function
$G_{t}(x)$ from the last equation. For $t=2$ we obtain $G_{2}(x)=x^{2}+1$
while for $t\geq 3$ we obtain

$G_{t}(x)=x\left(\frac{x^{2}+1}{x}\right)^{t-1}-\sum_{k=0}^{\lfloor\frac{t-3}{2}\rfloor}C_{k}\left(\frac{x^{2}+1}{x}\right)^{t-2k-2}.$
(91)

Summarizing these results, we obtain

$G_{t}(x)=\left\\{\begin{array}[]{ll}\frac{2}{t}\binom{t-2}{\frac{t-2}{2}}\,_{2}F_{1}\left[\left.\begin{array}[]{c}1,\frac{t-1}{2}\\\
\frac{t+2}{2}\end{array}\right|\frac{4x^{2}}{(x^{2}+1)^{2}}\right]&\ \ \ \ \ \
\ t\ \ {\rm even}\\\
\frac{2}{t+1}\binom{t-1}{\frac{t-1}{2}}\frac{x}{x^{2}+1}\,_{2}F_{1}\left[\left.\begin{array}[]{c}1,\frac{t}{2}\\\
\frac{t+3}{2}\end{array}\right|\frac{4x^{2}}{(x^{2}+1)^{2}}\right]&\ \ \ \ \ \
\ t\ \ \ {\rm odd}.\end{array}\right.$ (92)

For the analysis below we use the identity (Section 2.11, Eq. (11) in Ref.
[50])

$\,{}_{2}F_{1}\left(\left.\begin{array}[]{c}a,b\\\
a+b+\frac{1}{2}\end{array}\right|z\right)$
$\displaystyle=\left(\frac{2}{\sqrt{1-z}+1}\right)^{2a}\times$ (95)
$\,{}_{2}F_{1}\left(\left.\begin{array}[]{c}2a,a-b+\frac{1}{2}\\\
a+b+\frac{1}{2}\end{array}\right|\frac{\sqrt{1-z}-1}{\sqrt{1-z}+1}\right).$
(98)

Inserting $a=1$ and $b=k+1/2$ into Eq. (98), we obtain

$\,{}_{2}F_{1}\left[\left.\begin{array}[]{c}1,k+\frac{1}{2}\\\
k+2\end{array}\right|\frac{4x^{2}}{(x^{2}+1)^{2}}\right]=\left(x^{2}+1\right)^{2}\,_{2}F_{1}\left(\left.\begin{array}[]{c}2,1-k\\\
k+2\end{array}\right|-x^{2}\right).$ (99)

Using the definition of the hypergeometric function on the right hand side, we
obtain

$\,{}_{2}F_{1}\left[\left.\begin{array}[]{c}1,k+\frac{1}{2}\\\
k+2\end{array}\right|\frac{4x^{2}}{(x^{2}+1)^{2}}\right]=\left(x^{2}+1\right)^{2}\sum_{m=0}^{\infty}\left[\frac{(2)_{m}(1-k)_{m}}{(k+2)_{m}}\right]\left[\frac{(-x^{2})^{m}}{m!}\right],$
(100)

where $(a)_{m}$ is the (rising) Pochhammer symbol [33]. For integer values
$a>0$ it can be expressed as

$(a)_{m}=\frac{(a+m-1)!}{(a-1)!},$ (101)

while for negative integer values $a<0$

$(a)_{m}=\left\\{\begin{array}[]{ll}(-1)^{m}\frac{(-a)!}{(-a-m)!}&m\leq-a\\\
0&m>-a\end{array}\right.$ (102)

Inserting these expressions into Eq. (100), we obtain

$\,{}_{2}F_{1}\left[\left.\begin{array}[]{c}1,k+\frac{1}{2}\\\
k+2\end{array}\right|\frac{4x^{2}}{(x^{2}+1)^{2}}\right]=\left(x^{2}+1\right)^{2}\sum_{m=0}^{k-1}\frac{\binom{k-1}{m}}{\binom{k+1+m}{m}}(m+1)x^{2m}.$
(103)

Therefore,

$G_{t}(x)=\left\\{\begin{array}[]{ll}\frac{1}{t-1}\binom{t-1}{\frac{t}{2}}+\sum\limits_{m=1}^{\frac{t-2}{2}}\frac{2m}{t}\binom{t}{\frac{t}{2}+m}x^{2m}+x^{t}&\
\ \ \ \ \ t\ \ {\rm even}\\\
\sum\limits_{m=0}^{\frac{t-3}{2}}\frac{2m+1}{t}\binom{t}{\frac{t+1}{2}+m}x^{2m+1}+x^{t}&\
\ \ \ \ \ t\ \ \ {\rm odd}.\end{array}\right.$ (104)

Going back to the definition of the generating function $G_{t}(x)$ in Eq. (81)
one can identify the coefficients $b(t,\ell)$. It turns out that the results
for both even and odd values of $t$ can be expressed by the same expression,
which takes the form

$b(t,\ell)=\frac{\ell}{t}\binom{t}{\frac{t+\ell}{2}},$ (105)

under the condition that $t-\ell$ is even. Interestingly, for $\ell>0$ these
combinatorial factors coincide with the number of RW trajectories in a semi-
infinite one dimensional system that start from $x=0$ and reach the site
$x=\ell$ for the first time at time $t$ [12]. Inserting $b(t,\ell)$ from Eq.
(105) into Eqs. (78) and (79) it is found that

$B(t,\ell)=\left\\{\begin{array}[]{ll}\frac{\ell}{t}\binom{t}{\frac{t+\ell}{2}}(c-1)^{\frac{t-\ell}{2}}&\
\ \ \ \ \ \ t-\ell\ \ {\rm even}\\\ 0&\ \ \ \ \ \ \ t-\ell\ \ {\rm
odd}.\end{array}\right.$ (106)

##  Appendix B Useful sums involving $P(L>\ell)$

The discrete Laplace transform of $P(L>\ell)$ is defined by

${\mathcal{L}}[P(L>\ell)](s)=\sum_{\ell=0}^{\infty}e^{-s\ell}P(L>\ell).$ (107)

Carrying out the summation, it was found in Ref. [32] that

$\displaystyle\mathcal{L}$
$\displaystyle\\{P(L>\ell)\\}(s)=\frac{\exp\left[\left(\frac{c}{c-2}\right)\frac{1}{N}\right]}{\ln(c-1)}{\rm
E}_{1+\frac{s}{\ln(c-1)}}\left[\left(\frac{c}{c-2}\right)\frac{1}{N}\right]+\frac{1}{2}$
(108)
$\displaystyle-\left[\left(\frac{c}{c-2}\right)\frac{1}{N}\right]\left\\{\frac{1}{2}\coth\left[\frac{s-\ln(c-1)}{2}\right]-\frac{1}{s-\ln(c-1)}\right\\}$
$\displaystyle+\left[\frac{1}{2}\coth\left(\frac{s}{2}\right)-\frac{1}{s}\right]\left[1+\left(\frac{c}{c-2}\right)\frac{1}{N}\right]+\mathcal{O}\left(\frac{1}{N^{2}}\right),$

where ${\rm E}_{m}(x)$ is the generalized exponential integral (Eq. 8.19.3 in
Ref. [33]).

The Laplace transform is a useful tool for the evaluation of various sums that
include $P(L>\ell)$. In particular, the mean distance $\langle L\rangle$
between pairs of nodes in an RRG can be expressed using the tail-sum formula
[36]. It takes the form

$\langle
L\rangle=\sum_{\ell=0}^{\infty}P(L>\ell)=\mathcal{L}\\{P(L>\ell)\\}(s=0).$
(109)

Plugging in $s=0$ in Eq. (108), we obtain

$\displaystyle\langle L\rangle$ $\displaystyle=$
$\displaystyle\frac{\exp\left[\left(\frac{c}{c-2}\right)\frac{1}{N}\right]}{\ln(c-1)}{\rm
E_{1}}\left[\left(\frac{c}{c-2}\right)\frac{1}{N}\right]+\frac{1}{2}$ (110)
$\displaystyle+$
$\displaystyle\frac{1}{2}\left[\left(\frac{c}{c-2}\right)\frac{1}{N}\right]\left\\{\coth\left[\frac{\ln(c-1)}{2}\right]-\frac{2}{\ln(c-1)}\right\\}$
$\displaystyle+$ $\displaystyle\mathcal{O}\left(\frac{1}{N^{2}}\right).$

In the large network limit, Eq. (110) can be reduced to

$\langle L\rangle=\frac{\ln
N}{\ln(c-1)}+\frac{1}{2}-\frac{\ln\left(\frac{c}{c-2}\right)+\gamma}{\ln(c-1)}+\mathcal{O}\left(\frac{\ln
N}{N}\right).$ (111)

Below we evaluate several other sums that appear in the calculation of the
moments $\mathbb{E}[T_{\rm FP}^{r}|{\rm SPATH}]$ of the distribution of first-
passage times. In particular, we consider the family of sums given by

$M_{n}=\sum_{\ell=0}^{\infty}\ell^{n}\left(\frac{1}{c-1}\right)^{\ell}P(L>\ell),$
(112)

where $P(L>\ell)$ is give by Eq. (1). These sums can be expressed by

$M_{n}=(-1)^{n}\frac{d^{n}}{ds^{n}}{\mathcal{L}}[P(L>\ell)](s)\bigg{|}_{s=\ln(c-1)}.$
(113)

Inserting $\mathcal{L}\\{P(L>\ell)\\}(s)$ from Eq. (108) into Eq. (113) for
$n=0$, we obtain

$\displaystyle M_{0}=\frac{c-1}{c-2}$
$\displaystyle+\frac{\exp\left[\left(\frac{c}{c-2}\right)\frac{1}{N}\right]{\rm
E_{1}}\left[-\left(\frac{c}{c-2}\right)\frac{1}{N}\right]-1}{\ln(c-1)}\left(\frac{c}{c-2}\right)\frac{1}{N}$
(114)
$\displaystyle+\frac{1}{2}\left(\frac{c}{c-2}\right)^{2}\frac{1}{N}+{\mathcal{O}}\left(\frac{1}{N^{2}}\right).$

In the large network limit, Eq. (114) can be reduced to

$M_{0}=\frac{c-1}{c-2}-\frac{c}{c-2}\left[\frac{\ln
N}{\ln(c-1)}+\frac{\ln\left(\frac{c-2}{c}\right)-\gamma+1}{\ln(c-1)}-\frac{1}{2}\left(\frac{c}{c-2}\right)\right]\frac{1}{N}+{\mathcal{O}}\left(\frac{1}{N^{2}}\right).$
(115)

Inserting $\mathcal{L}\\{P(L>\ell)\\}(s)$ from Eq. (108) into Eq. (113) for
$n=1$, we obtain

$\displaystyle M_{1}=\frac{c-1}{(c-2)^{2}}-\frac{1}{[\ln(c-1)]^{2}}$
$\displaystyle+\left(\frac{c}{c-2}\right)\left\\{\frac{c-1}{(c-2)^{2}}+\frac{\exp\left[\left(\frac{c}{c-2}\right)\frac{1}{N}\right]G_{2,3}^{3,0}\left[\left(\frac{c}{c-2}\right)\frac{1}{N}\left|\begin{array}[]{c}1,1\\\
-1,0,0\end{array}\right.\right]-1}{[\ln(c-1)]^{2}}\right\\}\frac{1}{N}$ (118)
$\displaystyle+{\mathcal{O}}\left(\frac{1}{N^{2}}\right),$ (119)

where $G(\cdot)$ is the Meijer function [33]. The Meijer function can be
expressed in terms of more elementary functions, in the form

$\displaystyle G_{2,3}^{3,0}$
$\displaystyle\left[\left(\frac{c}{c-2}\right)\frac{1}{N}\left|\begin{array}[]{c}1,1\\\
-1,0,0\end{array}\right.\right]=\left(\frac{c-2}{c}\right)N\exp\left[-\left(\frac{c}{c-2}\right)\frac{1}{N}\right]$
$\displaystyle-\frac{1}{2}\left[\ln\left(\frac{c-2}{c}N\right)\right]^{2}+\gamma\ln\left(\frac{c-2}{c}N\right)-\frac{\pi^{2}}{12}-\frac{\gamma^{2}}{2}$
$\displaystyle+\left(\frac{c}{c-2}\right)\frac{1}{N}\
_{3}F_{3}\left[\left.\begin{array}[]{c}1,1,1\\\
2,2,2\end{array}\right|-\left(\frac{c}{c-2}\right)\frac{1}{N}\right]$ (125)
$\displaystyle+{\rm
Chi}\left[\left(\frac{c}{c-2}\right)\frac{1}{N}\right]-{\rm
Shi}\left[\left(\frac{c}{c-2}\right)\frac{1}{N}\right],$ (126)

where ${\rm Chi}(x)$ and ${\rm Shi}(x)$ are the hyperbolic cosine and sine
integrals, respectively [33]. In the large network limit, Eq. (119) can be
reduced to

$\displaystyle M_{1}$ $\displaystyle=$
$\displaystyle\frac{c-1}{(c-2)^{2}}-\frac{c}{2(c-2)[\ln(c-1)]^{2}}\frac{\left[\ln\left(\frac{c-2}{c}N\right)\right]^{2}}{N}$
(127) $\displaystyle+$
$\displaystyle\frac{(\gamma-1)c}{(c-2)[\ln(c-1)]^{2}}\frac{\ln\left(\frac{c-2}{c}N\right)}{N}+\frac{c(c-1)}{(c-2)^{3}}\frac{1}{N}$
$\displaystyle-$
$\displaystyle\frac{c\left[\pi^{2}+6(\gamma-2)\gamma+12\right]}{12(c-2)[\ln(c-1)]^{2}}\frac{1}{N}+{\mathcal{O}}\left(\frac{1}{N^{2}}\right).$

## References

## References

  * [1] Lawler G F 2010 Random Walk and the Heat Equation (Providence: American Mathematical Society)
  * [2] Lawler G F and Limic V 2010 Random Walk: A Modern Introduction (Cambridge: Cambridge University Press)
  * [3] ben-Avraham D and Havlin S 2000 Diffusion and Reactions in Fractals and Disordered Systems (Cambridge: Cambridge University Press)
  * [4] Noh D J and Rieger H 2004 Random walks on complex networks Phys. Rev. Lett. 92 118701
  * [5] Masuda N, Porter M A and Lambiotte R 2017 Random walks and diffusion on networks Physics Reports 716 1
  * [6] Havlin S and Cohen R 2010 Complex Networks: Structure, Robustness and Function (Cambridge University Press, New York).
  * [7] Newman M E J 2018 Networks: an Introduction, Second Edition (Oxford: Oxford University Press).
  * [8] Pastor-Satorras R and Vespignani A 2001 Epidemic spreading in scale-free networks Phys. Rev. Lett. 86 3200
  * [9] Barrat A, Barthélemy M and Vespignani A 2012 Dynamical Processes on Complex Networks (Boston: Cambridge University Press)
  * [10] De Bacco C, Majumdar S N and Sollich P 2015 The average number of distinct sites visited by a random walker on random graphs J. Phys. A 48 205004
  * [11] Masuda N and Konno N 2004 Return times of random walk on generalized random graphs Phys. Rev. E 69 066113
  * [12] Redner S 2001 A Guide to First Passage Processes (Cambridge: Cambridge University Press)
  * [13] Finch S R 2003 Mathematical Constants, section 5.9 (Cambridge: Cambridge University Press)
  * [14] Sood V, Redner S and ben-Avraham D 2005 First-passage properties of the Erdős–Rényi random graph J. Phys. A 38 109
  * [15] Baronchelli A and Loreto V 2006 Ring structures and mean first passage time in networks Phys. Rev. E73 026103
  * [16] Lau H W and Szeto K Y 2010 Asymptotic analysis of first passage time in complex networks EPL 90 40005
  * [17] Bartolucci S, Caccioli F, Caravelli F and Vivo P 2021 ”Spectrally gapped” random walks on networks: a Mean First Passage Time formula SciPost Phys. 11 088
  * [18] Bassolas A and Nicosia V 2021 First-passage times to quantify and compare structural correlations and heterogeneity in complex systems Communications Physics 4 1
  * [19] Giacometti A 1995 Exact closed form of the return probability on the Bethe lattice J. Phys. A 28 L13
  * [20] Hughes B D and Sahimi M 1982 Random walks on the Bethe lattice J. Stat. Phys. 29 781
  * [21] Cassi D 1989 Random walks on Bethe lattices Europhys. Lett. 9 627
  * [22] Tishby I, Biham O and Katzav E 2021 Analytical results for the distribution of first return times of random walks on random regular graphs J. Phys. A 54 325001
  * [23] Molloy M and Reed A 1995 A critical point for random graphs with a given degree sequence Rand. Struct. Alg. 6 161-180
  * [24] Molloy M and Reed A 1998 The Size of the Giant Component of a Random Graph with a Given Degree Sequence Combinatorics, Probability and Computing 7 295-305
  * [25] Newman M E J, Strogatz S H and Watts D J 2001 Random graphs with arbitrary degree distributions and their applications, Phys. Rev. E 64, 026118 (2001).
  * [26] Bollobas B 2001 Random Graphs, Second Edition (London: Academic Press)
  * [27] Bonneau H, Hassid A, Biham O, Kühn R and Katzav E 2017 Distribution of shortest cycle lengths in random networks Phys. Rev. E 96 062307
  * [28] Nitzan M, Katzav E, Kühn R and Biham O 2016, Distance distribution in configuration-model networks Phys. Rev. E93 062309
  * [29] van der Hofstad R, Hooghiemstra G and Van Mieghem P 2005 Distances in random graphs with finite variance degrees Random Structures & Algorithms 27 76
  * [30] Gompertz B 1825 On the nature of the function expressive of the law of human mortality, and on a new mode of determining the value of life contingencies Philosophical Trans. R. Soc. London A 115 513
  * [31] Shklovskii B I 2005 A simple derivation of the Gompertz law for human mortality Theory in Biosciences 123 431
  * [32] Tishby I, Biham O, Kühn R and Katzav E 2022 The mean and variance of the distribution of shortest path lengths of random regular graphs J. Phys. A 55 265005
  * [33] Olver F W J, Lozier D M, Boisvert R R and Clark C W 2010 NIST Handbook of Mathematical Functions (Cambridge: Cambridge University Press)
  * [34] Tishby I, Biham O and Katzav E 2022 Analytical results for the distribution of cover times of random walks on random regular graphs J. Phys. A 55 015003
  * [35] Bollobas B and Fernandez de la Vega W 1982 The diameter of random regular graphs Combinatorica 2 125
  * [36] Pitman J 1993 Probability (New York: Springer-Verlag)
  * [37] Martin O and Šulc P 2010 Return probabilities and hitting times of random walks on sparse Erdős-Rényi graphs Phys. Rev. E 81 031111
  * [38] Pitman J and Tang W 2018 Tree formulas, mean first passage times and Kemeny’s constant of a Markov chain Bernoulli 24, 1942
  * [39] Förster Y-P, Gamberi L, Tzanis E, Vivo P and Annibale A 2022 Exact and approximate mean first passage times on trees and other necklace structures: a local equilibrium approach J. Phys. A 55, 115001
  * [40] Förster Y-P, Annibale A, Gamberi L, Tzanis E and Vivo P 2022 Information retrieval and structural complexity of legal trees J. Phys. Complex. 3, 035008
  * [41] Tishby I, Biham O and Katzav E 2017 The distribution of first hitting times of random walks on Erdős–Rényi networks J. Phys. A, 50 115001
  * [42] Tishby I, Biham O and Katzav E 2021 Analytical results for the distribution of first hitting times of random walks on random regular graphs J. Phys. A 54 145002
  * [43] Cooper C and Frieze A M 2005 The cover time of random regular graphs SIAM J. Discrete Math. 18 728
  * [44] Gumbel E J 1935 Les valeurs extrêmes des distributions statistiques Annales de l’Institut Henri Poincaré 5 115
  * [45] Fréchet M 1927 Sur la loi de probabilité de l’écart maximum Annales de la Société Polonaise de Mathématique 6 93
  * [46] Fisher R A, Tippett L H C 1928 Limiting forms of the frequency distribution of the largest and smallest member of a sample Proc. Camb. Phil. Soc. 24 180
  * [47] von Mises R 1936 La distribution de la plus grande de $n$ valeurs Rev. Math. Union Interbalcanique 1 141
  * [48] Gnedenko B V 1943 Sur la distribution limite du terme maximum d’une serie aleatoire Annals of Mathematics 44 423
  * [49] Audibert P 2010 Mathematics for Informatics and Computer Science (Hoboken: Wiley-ISTE).
  * [50] Erdelyi A (ed.) 1953 Higher Transcendental Functions, Vol. I (New York: McGraw-Hill)