Hitting times for second-order random walks

Dario Fasino, Arianna Tonetto
Department of Mathematics, Computer Science and Physics
University of Udine
33100, Udine (Italy)
[email protected] &Francesco Tudisco
School of Mathematics
Gran Sasso Science Institute
67100, L’Aquila (Italy)
[email protected]

Abstract

A second-order random walk on a graph or network is a random walk where transition probabilities depend not only on the present node but also on the previous one. A notable example is the non-backtracking random walk, where the walker is not allowed to revisit a node in one step. Second-order random walks can model physical diffusion phenomena in a more realistic way than traditional random walks and have been very successfully used in various network mining and machine learning settings. However, numerous questions are still open for this type of stochastic processes. In this work we extend well-known results concerning mean hitting and return times of standard random walks to the second-order case. In particular, we provide simple formulas that allow us to compute these numbers by solving suitable systems of linear equations. Moreover, by introducing the “pullback” first-order stochastic process of a second-order random walk, we provide second-order versions of the renowned Kac’s and random target lemmas.

Keywords

Second-order random walks; non-backtracking walks; hitting times; return times.

1 Introduction

Random walks on graphs are a key concept in network theory used to model various dynamics such as user navigation and epidemic spreading [29], to quantify node centrality [30, 31], or to reveal communities and core-periphery structures [9, 10, 33, 37]. The standard random walk on a graph considers a hypothetical walker that starting from node $i$ moves to a new node of the graph choosing it uniformly at random among the neighbors of $i$ . This defines a memoryless stochastic process which corresponds to a Markov chain on the nodes. However, the process described by a standard graph random walk is often localized and may fail to capture the underlying physical model as well as to fully exploit the global graph structure. For this reason, there is a growing interest in recent years towards so-called higher-order stochastic processes whose evolution may depend on past states, including stochastic processes modeled by transition probability tensors [5, 12] as well as non-local diffusion mappings [7, 11] and non-backtracking random walks [13].

The latter is one of the best known examples of second-order stochastic processes, where node transitions depend on both the current and the previous state spaces as the process is not allowed to backtrack, i.e. to immediately revisit the previous space in the next step. Non-backtracking random walks are often more appropriate than classical random walks to model real-world diffusive phenomena on networks where a message-passing or disease-spreading analogy is relevant. In particular, non-backtracking walks can avoid unwanted localization effects on the leading eigenvector of the adjacency matrix of a graph [17, 20, 24] and their mixing rate, in many cases, is faster than the one of classical random walks [27, 6]. Furthermore, many computations with non-backtracking walks have negligible overheads compared to standard approaches [1, 14].

The non-backtracking paradigm is at the basis of several second-order stochastic processes appearing in recent graph-theoretic, network mining and machine learning literature. For example, the mixing time of a clique-based version of the non-backtracking random walk on regular graphs is studied in [6]. Similarity measures based on second-order random walks are used in [38] to measure node proximity and improve classical walk-based link-prediction and clustering algorithms. Eigenvalues and eigenvectors of non-backtracking matrices have been shown to provide remarkable performances in community detection and in various centrality measurements [1, 20, 35]. The graph-embedding generated by the popular node2vec algorithm [15] is based on a flexible second-order random walk depending on two parameters: one used to control the likelihood of backtracking (i.e. immediately revisiting a node in the walk), the other used to bias the navigation towards or away from the immediately preceding nodes.

In this work we are concerned with hitting and return times of second-order random walks on graphs with possibly countably many vertices. Roughly speaking, a hitting time is the first time at which a stochastic process reaches a given subset of its state space, while a return time is the first time the process gets back to a given starting state. Hitting and return times are well understood for Markov chains, which include as a particular case the stochastic process that describes a standard random walk on a graph. In this case, the state space is given by the set of nodes and explicit formulas are available to compute mean hitting and return times by means of suitable systems linear equations which, for finite and connected graphs, have unique solutions. Moreover, these quantities have numerous applications to, for example, quantify node distances and similarities. For this reason, they are an important tool to evaluate network cohesion and node centrality and are at the basis of popular node classification and link prediction algorithms [22, 28].

In this paper, we extend several results concerning mean hitting and return times of standard first-order stochastic processes to the second-order setting. In particular, we show that also mean hitting times of second-order random walks can be obtained from a set of linear equations, which has potential applications in higher-order classification and link prediction methods [3, 4, 36]. Moreover, we prove that mean return times of second-order random walks coincide with standard return times of suitably defined random walks in the original graph. In particular, mean return times for non-backtracking random walks coincide with the usual mean return times in all finite undirected graphs.

The paper is organized as follows. In Section 2 and 3 we present the notations used in this work and some basic results about random walks and second-order random walks, respectively. In Section 4 we introduce mean hitting times and return times for second-order random walks and we present first results concerning possible ways to compute them numerically via the solution of systems of linear equations. Our main results are in Section 5. There, we analyze second-order mean hitting and return times under what we call “equilibrium assumption”, corresponding to the condition that the second-order random walk is at the steady state. In particular, we derive an algebraic relationship between the hitting time matrix for a second-order random walk and the one corresponding to a standard random walk on the directed line graph of the original graph. Moreover, we show second-order analogues of the Kac’s and the random target lemmas for standard Markov chains. Finally, in Section 6, we illustrate some of the results of this paper on some real-world examples.

2 Notations and basic results

An oriented graph (or network) is a pair $\mathcal{G}=(V,E)$ , where $V$ is the vertex (or node) set and $E$ is the set of oriented edges, i.e., ordered pairs of nodes. We say that $(i,j)\in E$ is an edge going from $i$ to $j$ . From here onward, letters $i,j,k$ denote generic nodes of $\mathcal{G}$ , while $e,f$ are used to denote generic edges of $\mathcal{G}$ . Furthermore,

•

if $e=(i,j)\in E$ then we set ${\tt S}(e)=i$ and ${\tt T}(e)=j$ , the source and terminal node of the edge $e$ ;
•

for $i\in V$ we denote by $\mathcal{I}_{i}=\{e\in E:{\tt T}(e)=i\}$ and $\mathcal{O}_{i}=\{e\in E:{\tt S}(e)=i\}$ the in-neighborhood and out-neighborhood of $i$ , respectively. The in-degree and the out-degree of node $i$ are $d^{-}_{i}=|\mathcal{O}_{i}|$ and $d^{+}_{i}=|\mathcal{I}_{i}|$ , respectively.

In the present work, $\mathcal{G}$ can have a countably infinite number of nodes. However, we will assume that $\mathcal{G}$ is locally finite, that is, $V$ is possibly infinite but each node has finite in- and out-degree.

A graph $\mathcal{G}=(V,E)$ can be completely described by its (possibly infinite dimensional) adjacency matrix $A=(A_{ij})$ , defined as

A_{ij}=\begin{cases}1&\hbox{ if }(i,j)\in E;\\ 0&\hbox{ otherwise.}\end{cases}

If the adjacency matrix is symmetric then $\mathcal{G}$ is called undirected. Hence, in an undirected graph each edge $(i,j)$ has its own reciprocal edge $(j,i)$ . In that case we have $d^{-}_{i}=d^{+}_{i}$ and this common value is the degree of node $i$ , denoted as $d_{i}$ .

A walk of length $m$ on $\mathcal{G}$ is a sequence $v_{0},v_{1},\ldots,v_{m}\in V$ of nodes such that $(v_{i-1},v_{i})\in E$ for $i=1,\ldots,m$ . If for all $i,j\in V$ there exists a walk from $i$ to $j$ , then the graph $\mathcal{G}$ is called strongly connected.

Finally, the symbols $\mathbb{P}$ and $\mathbb{E}$ denote the probability and the expectation, respectively. All vectors used in the text are column vectors, with possibly infinitely many entries. In particular, the symbol $\mathbbx{1}$ denotes the column vector with all entries equal to 1, the size of which should be clear from the context.

2.1 Random walks

In this section, we recall from [18, 32] some basic concepts and results in Markov chain theory. A random walk on $\mathcal{G}$ is a sequence of nodes $v_{0},v_{1},\ldots,v_{k},\ldots$ where $v_{k+1}$ is chosen at random between the out-neighbours of $v_{k}$ , according to specified probabilities $p_{i,j}:=\mathbb{P}(v_{k+1}=j|v_{k}=i)$ such that $p_{i,j}=0$ if $(i,j)\notin E$ and $\sum_{j\in\mathcal{O}_{i}}p_{i,j}=1$ for every $i\in V$ . The last condition implies that $d^{+}_{i}\geq 1$ for every $i\in V$ , which will be assumed henceforth. A standard choice for $p_{i,j}$ is $p_{i,j}=1/d^{+}_{i}$ , for $j\in\mathcal{O}_{i}$ . In this case the random walk is called uniform. Our subsequent discussion is not restricted to this case.

A random walk can be viewed as a Markov chain $\{Y_{n},n\in\mathbb{N}\}$ with state space $V$ and transition matrix $P$ with entries $P_{ij}=p_{i,j}$ . Clearly, $P$ is a row-stochastic matrix. The random variable $Y_{n}$ represents the state of the walker at time $n$ .

For a fixed subset $S\subset V$ we call hitting time to $S$ the random variable $T_{S}$ defined as $T_{S}=\min\{n\in\mathbb{N}:Y_{n}\in S\}$ . In other words, $T_{S}$ is the first time the random walker reaches the subset $S$ , starting from a given initial state $Y_{0}$ . Based on $T_{S}$ , we can define the hitting probability $\varphi_{i\to S}$ from $i$ to $S$ as:

\varphi_{i\to S}=\mathbb{P}(T_{S}<+\infty|Y_{0}=i),

(1)

i.e., the probability that, starting from node $i$ , the random walker ever hits $S$ . When $\varphi_{i\to S}=1$ , it is interesting to compute the average time taken by the random walker to reach $S$ , starting from $i$ . This quantity is given by

\tau_{i\to S}=\mathbb{E}(T_{S}|Y_{0}=i)

and is called the mean hitting time from $i$ to $S$ . It is well-known that the quantities $\varphi_{i\to S}$ and $\tau_{i\to S}$ can be obtained from the solution of certain linear systems, as shown by the next two theorems, whose proofs can be found in, e.g., [32].

Theorem 2.1.

For a graph $\mathcal{G}=(V,E)$ and for a subset $S\subset V$ , the hitting probabilities $\{\varphi_{i\to S}:i\in V\}$ are the minimal non-negative solution of the following linear system:

\begin{cases}\varphi_{i\to S}=1&\hbox{if $i\in S$}\\ \varphi_{i\to S}=\sum_{j\in V}P_{i,j}\varphi_{j\to S}&\hbox{if $i\notin S$.}\end{cases}

(2)

In the previous theorem, minimality of the solution means that if $\{x_{i}:i\in V\}$ is another non-negative solution of (2) then $\varphi_{i\to S}\leq x_{i}$ for all $i\in V$ .

Theorem 2.2.

For a graph $\mathcal{G}=(V,E)$ and for a subset $S\subset V$ , suppose that $\varphi_{i\to S}=1$ for all $i\in V$ . Then the mean hitting times $\{\tau_{i\to S}:i\in V\}$ are the minimal non-negative solution of the following linear system:

\begin{cases}\tau_{i\to S}=0&\hbox{if }i\in S\\ \tau_{i\to S}=1+\sum_{j\in V}P_{i,j}\tau_{j\to S}&\hbox{if }i\notin S.\end{cases}

(3)

The case of finite graphs is the most usual in applications. In this case, a well-known result shows that for strongly connected graphs (3) has a unique solution, see e.g., Chap. VI of [18]. Precisely:

Theorem 2.3.

Let $\mathcal{G}=(V,E)$ be finite and strongly connected. For any given subset $S\subset V$ , all the hitting probabilities to $S$ are equal to $1$ and the linear system (3) has a unique solution.

It is interesting to note that Equation (3) can be written in compact matrix-vector form as follows. Let $t^{S}$ and $r^{S}$ be the vectors entrywise defined as follows:

t^{S}_{i}=\begin{cases}0&i\in S\\ \tau_{i\to S}&i\notin S\end{cases}\qquad r^{S}_{i}=\begin{cases}\tau^{+}_{i\to S}&i\in S\\ 0&i\notin S,\end{cases}

(4)

where the numbers $\tau^{+}_{i\to S}$ are defined as

\tau^{+}_{i\to S}=1+\sum_{j\in V}P_{i,j}\tau_{j\to S},\qquad(i\in S)\,.

(5)

Then, the vector $t^{S}$ solves the singular equation

(I-P)x=\mathbbx{1}-r^{S}.

(6)

In particular, among the infinitely many solutions $x$ of this equation, the vector $t^{S}$ is the one characterized by the condition $t^{S}_{i}=0$ for $i\in S$ . The quantities (5) are called mean return times and represent the average number of steps required to return to $S$ after leaving it from $i\in S$ . Indeed, if we consider the random variable $T^{+}_{S}=\min\{n\geq 1:Y_{n}\in S\}$ , then it holds $\tau^{+}_{i\to S}=\mathbb{E}(T^{+}_{S}|Y_{0}=i)$ . The special case when $S$ is a singleton deserves a special attention, and we adopt the simplified notation $\tau_{i}=\mathbb{E}(T^{+}_{i}|Y_{0}=i)$ . This quantity is called mean return time to $i$ .

When $\mathcal{G}$ is finite and strongly connected, by means of the Perron–Frobenius theorem (see, e.g., [25]) we can conclude that the random walk $\{Y_{n},n\in\mathbb{N}\}$ admits a unique positive invariant distribution, i.e., a vector $\pi>0$ such that $\pi^{T}\mathbbx{1}=1$ and $\pi^{T}P=\pi^{T}$ . More generally, when $V$ is countable, the same conclusion holds true if and only if the associated Markov chain is irreducible and positive recurrent, that is, $\tau_{i}$ is finite for at least one $i\in V$ , see e.g., Thm. 21.12 of [21] or Thm. 1.7.7 of [32]. The latter property also implies that all hitting probabilities (1) are equal to $1$ and all hitting times are finite.

With the help of the invariant distribution we can obtain an explicit formula for the mean return time to a set $S\subset V$ ,

	$\displaystyle\tau_{S}$	$\displaystyle=\mathbb{E}(T^{+}_{S}\|Y_{0}\in S)$
		$\displaystyle=\sum_{i\in S}\mathbb{P}(Y_{0}=i\|Y_{0}\in S)\mathbb{E}(T^{+}_{S}\|Y_{0}=i)=\frac{1}{\sum_{j\in S}\pi_{j}}\sum_{i\in S}\pi_{i}\tau^{+}_{i\to S}.$

This number quantifies the average number of steps taken by a random walker initially placed in $S$ to hit again $S$ , given that its probability of being in node $i$ is proportional to $\pi_{i}$ . Indeed, the number $\pi_{i}/\sum_{j\in S}\pi_{j}$ gives the conditional probability that the random walker is in $i$ given that it is in $S$ . The average return time $\tau_{S}$ can be computed by means of Kac’s lemma, see e.g., [16] or [21, Lemma 21.13]:

Lemma 2.4.

Let $\pi$ be the stationary density of an irreducible Markov chain on the state space $V$ . Then for any $S\subset V$ ,

\tau_{S}=\frac{1}{\sum_{i\in S}\pi_{i}}.

In particular, $\tau_{i}=1/\pi_{i}$ for every $i\in V$ .

If $\mathcal{G}$ is finite then the mean hitting times fulfill the so-called random target lemma, see e.g., Lemma 10.1 of [21].

Lemma 2.5.

Let $P$ be irreducible, and let $\pi$ be its stationary density. Then, there exists a constant $\kappa$ such that

\sum_{j\in V}\pi_{j}\tau_{i\to j}=\kappa,

independently on $i\in V$ .

The number $\kappa=\kappa(P)$ appearing in the preceding Lemma is the renowned Kemeny’s constant of $P$ . This constant quantifies the expected number of steps to get from node $i$ to a node $j$ , selected randomly according to the stationary density.

Introducing the matrix $T=(\tau_{i\to j})$ , whose $ij$ -th entry is the mean hitting time from $i$ to $j$ , the claim of Lemma 2.5 can be compactly expressed via the identity $T\pi=\kappa\mathbbx{1}$ . Since the $j$ -th column of $T$ fulfills equation (6) with $S=\{j\}$ , using Lemma 2.4 it is not difficult to verify that this matrix solves the equation

(I-P)T=\mathbbx{1}\mathbbx{1}^{T}-\mathrm{Diag}(\pi)^{-1},

(7)

where $\mathrm{Diag}(\pi)$ is the diagonal matrix with diagonal entries given by the entries of the vector $\pi$ . Actually, the matrix $T$ is the unique solution of (7) with zero diagonal entries.

We conclude this review on random walks with a technical lemma of independent interest and that will be useful for later. This result shows that, apart of a constant term, the vector $t^{S}$ defined in (4) can be expressed by a convex linear combination of the vectors $\{t^{i},i\in S\}$ . Hence, mean access times to a subset can be computed from mean access times to the single elements of the set.

Lemma 2.6.

For any fixed subset $S\subset V$ there exist positive coefficients $\beta$ and $\{\alpha_{i}\}$ , for $i\in S$ , such that $\sum_{i\in S}\alpha_{i}=1$ , and

t^{S}=\sum_{i\in S}\alpha_{i}t^{i}-\beta\mathbbx{1}.

In particular, $\tau_{i\to S}=\sum_{j\in S}\alpha_{j}\tau_{i\to j}-\beta$ for every $i\in V$ .

Proof.

Consider the vector $a=(\alpha_{i})_{i\in V}$ with entries

\alpha_{i}=\begin{cases}0&i\notin S\\ \pi_{i}\tau^{+}_{i\to S}&i\in S.\end{cases}

(8)

By (6) we have

0=\pi^{T}(I-P)t^{S}=\pi^{T}(\mathbbx{1}-r^{S})=1-\sum_{i\in S}\pi_{i}\tau^{+}_{i\to S}.

Hence $\sum_{i}\alpha_{i}=\sum_{i\in S}\pi_{i}\tau^{+}_{i\to S}=1$ . Moreover, from (7) we derive

(I-P)Ta=(\mathbbx{1}\mathbbx{1}^{T}-\mathrm{Diag}(\pi)^{-1})a=\mathbbx{1}(\mathbbx{1}^{T}a)-r^{S}=\mathbbx{1}-r^{S}.

This proves that the difference $Ta-t^{S}$ belongs to the kernel of $I-P$ , that is, $\sum_{i\in S}\alpha_{i}t^{i}-t^{S}=\beta\mathbbx{1}$ for some $\beta\in\mathbb{R}$ . Considering the $k$ -th entry of this identity for $k\in S$ , we have

\beta=\sum_{i\in S}\alpha_{i}\tau_{k\to i}-t^{S}_{k}=\sum_{i\in S}\alpha_{i}\tau_{k\to i}>0,

and the proof is complete. ∎

3 Second-order random walks

A second-order random walk on a graph $\mathcal{G}=(V,E)$ is a walk $v_{0},v_{1},\ldots,v_{k},\ldots$ where the probability of choosing $v_{k+1}$ depends not only on $v_{k}$ but also on $v_{k-1}$ . More precisely, we describe this random walk by means of a stochastic process $\{X_{n},n\in\mathbb{N}\}$ , where $X_{n}\in V$ represents the node where the walker is located at time $n$ . Hence, there exists constant probabilities $p_{i,j,k}$ such that, for $n\geq 0$

\mathbb{P}(X_{n+2}=k|X_{n+1}=j,X_{n}=i)=p_{i,j,k}.

(9)

We additionally assume that there are specific probabilities $p^{\prime}_{i,j}$ for the first transition, that is,

\mathbb{P}(X_{1}=j|X_{0}=i)=p^{\prime}_{i,j}\qquad(i,j)\in E.

(10)

A second-order random walk is not a Markov chain because it does not fulfill the Markov condition, as we need to remember the previous step in order to take the next step. However, it can be turned into a Markov chain by changing the state space from the vertices of the graph to the directed edges. More precisely, let $\widehat{\mathcal{G}}=(\widehat{V},\widehat{E})$ be the (directed) line graph of $\mathcal{G}=(V,E)$ , where $\widehat{V}=E$ and $(e,f)\in\widehat{E}$ if and only if ${\tt T}(e)={\tt S}(f)$ . Then, the second-order random walk can be seen as a (first-order) walk on $\widehat{\mathcal{G}}$ , that is, a sequence of directed edges $e_{0},e_{1},\ldots,e_{k},\ldots$ where $v_{0}={\tt S}(e_{0})$ and $v_{i}={\tt S}(e_{i})={\tt T}(e_{i-1})$ , for $n\geq 1$ . However, we must keep in mind that a walk of length $m$ in $\mathcal{G}$ corresponds to a walk of length $m-1$ in $\widehat{\mathcal{G}}$ .

For $n\geq 0$ consider the random variable $W_{n}\in E$ defined as

W_{n}=(i,j)\ \Longleftrightarrow\ X_{n+1}=j,\ X_{n}=i.

(11)

On the basis of (9) and (10), the sequence $\{W_{n}\}$ is a Markov chain with initial distribution $\mathbb{P}(W_{0}=(i,j))=\mathbb{P}(X_{0}=i)p^{\prime}_{i,j}$ and transition matrix $\widehat{P}$ given by $\widehat{P}_{(i,j)(j,k)}=p_{i,j,k}$ . Hence, if $(e,f)\in\widehat{E}$ then $\widehat{P}_{ef}\geq 0$ while $\widehat{P}_{ef}=0$ if $(e,f)\notin\widehat{E}$ . Note that we allow the case $\widehat{P}_{ef}=0$ for some pair $(e,f)\in\widehat{E}$ , which may occur in some special circumstances, notably the non-backtracking random walk on $\mathcal{G}$ , see Example 3.2 below.

Example 3.1.

The uniform random walk on $\widehat{\mathcal{G}}$ is the Markov chain governed by the transition matrix $\widehat{P}$ ,

\widehat{P}_{ef}=\begin{cases}1/d^{+}_{{\tt S}(f)}&{\tt S}(f)={\tt T}(e)\\ 0&\hbox{otherwise.}\end{cases}

As $\widehat{P}_{ef}$ do not depend on ${\tt S}(e)$ , the corresponding stochastic process on $\mathcal{G}$ is the uniform random walk where $P_{ij}=\mathbb{P}(X_{n+1}=j|X_{n}=i)=1/d^{+}_{i}$ . If $\mathcal{G}$ is undirected, then $\widehat{P}$ is bi-stochastic.

Example 3.2.

The Hashimoto graph of $\mathcal{G}=(V,E)$ is the (directed) graph $\mathcal{H}=(V_{\mathcal{H}},E_{\mathcal{H}})$ where $V_{\mathcal{H}}=E$ and $(e,f)\in E_{\mathcal{H}}$ if and only if both ${\tt T}(e)={\tt S}(f)$ and ${\tt T}(f)\neq{\tt S}(e)$ . A random walk on the Hashimoto graph is obviously related to a non-backtracking random walk on $\mathcal{G}$ . We can look at a random walk on $\mathcal{H}$ as a weighted random walk on the directed line graph $\widehat{\mathcal{G}}=(\widehat{V},\widehat{E})$ by applying a null weight on the edges $(e,f)\in\widehat{E}$ such that ${\tt T}(f)={\tt S}(e)$ . The corresponding transition matrix $\widehat{P}$ is defined as follows. If $e=(i,j)$ and $A$ is the adjacency matrix of $\mathcal{G}$ , then

\widehat{P}_{ef}=\begin{cases}1/(d^{+}_{j}-A_{ji})&{\tt S}(f)=j\hbox{ and }i\neq{\tt T}(f)\\ 0&\hbox{otherwise.}\end{cases}

(12)

A directed edge $e=(i,j)\in E$ such that $\mathcal{O}_{j}=(j,i)$ is called dangling. The stochasticity condition $\sum_{f\in E}\widehat{P}_{ef}=1$ implies that no edge in $\mathcal{G}$ is dangling, otherwise the out-degree of the corresponding node in $\mathcal{H}$ would be zero. Hence, the non-backtracking random walk on $\mathcal{G}$ is well defined if (and only if) $d^{+}_{i}\geq 1$ for $i\in V$ and there are no dangling edges. Finally, we recall from e.g., [19] that, if $\mathcal{G}$ is undirected then $\widehat{P}$ is bi-stochastic.

Example 3.3.

Let $\widehat{P}^{(1)}$ and $\widehat{P}^{(0)}$ be the stochastic matrices defined in the Example 3.1 and Example 3.2, respectively. For any $\alpha\in(0,1)$ the matrix $\widehat{P}^{(\alpha)}=\alpha\widehat{P}^{(1)}+(1-\alpha)\widehat{P}^{(0)}$ is stochastic (bi-stochastic, if $\mathcal{G}$ is undirected). The corresponding Markov chain describes random walks in $\mathcal{G}$ where backtracking steps are not completely eliminated, but rather the probability of performing one such step is downweighted by a factor depending on $\alpha$ . Thus, the corresponding second-order process can be called a backtrack-downweighted random walk. Combinatorial aspects of this kind of walks are addressed in, e.g., [2].

Remark 3.4.

The Markov chain $\{W_{n}\}$ defined by (11) may not be irreducible even if $\mathcal{G}$ is strongly connected. For example, if $\mathcal{G}$ is an undirected graph consisting of a cycle, then the Hashimoto graph of $\mathcal{G}$ is not connected, and the matrix $\widehat{P}$ built as in Example 3.2 is reducible. However, the matrix $\widehat{P}^{(\alpha)}$ defined in Example 3.3 is irreducible in the sole assumption that $\mathcal{G}$ is strongly connected.

4 Second-order mean hitting times

In this section, we introduce the concept of mean hitting time for the second-order random walk $\{X_{n},n\in\mathbb{N}\}$ defined by (9) and (10) and we give results analogous to Theorems 2.1 and 2.2 for it. For each node $k\in V$ , let $\widetilde{T}_{k}$ be the random variable counting the first time the process arrives at node $k$ ,

\widetilde{T}_{k}=\min\{n\geq 0:X_{n}=k\}.

The aim of this section is to compute the corresponding mean second-order hitting time $\widetilde{\tau}_{i\to k}=\mathbb{E}(\widetilde{T}_{k}|X_{0}=i)$ , i.e., how many steps are required by a second-order random walk on average to reach $k$ , starting from $i$ . To this goal, we first compute the mean second-order hitting times to a node $k$ , given both the first and the second node,

\widetilde{\tau}_{i,j\to k}=\mathbb{E}(\widetilde{T}_{k}|X_{1}=j,X_{0}=i)\,,

(13)

and then we use these values to compute $\widetilde{\tau}_{i\to k}$ by means of the formula

	$\displaystyle\widetilde{\tau}_{i\to k}$	$\displaystyle=\mathbb{E}(\widetilde{T}_{k}\|X_{0}=i)$
		$\displaystyle=\sum_{j\in V}\mathbb{P}(X_{1}=j\|X_{0}=i)\mathbb{E}(\widetilde{T}_{k}\|X_{1}=j,X_{0}=i)=\sum_{j\in V}p^{\prime}_{ij}\widetilde{\tau}_{i,j\to k}.$		(14)

The above formula shows that, unlike mean hitting times for Markov chains, second-order mean hitting times depend on the choice of the first transition probabilities, as defined in (10). In the sequel, we will see that there is a quite natural choice for these probabilities. On the other hand, the finiteness of the numbers $\widetilde{\tau}_{i,j\to k}$ , which is essential for the finiteness of second-order hitting times, is not influenced by the values of the probabilities $p^{\prime}_{ij}$ . Indeed, in an infinite network it can happen that $\mathbb{P}(\widetilde{T}_{k}=+\infty|X_{1}=j,X_{0}=i)>0$ for some $(i,j)\in E$ and $k\in V$ . For example, this happens when $\widehat{P}$ is the transition matrix of the uniform random walk on $\widehat{\mathcal{G}}$ and this chain is transient. In this case, $\widetilde{\tau}_{i,j\to k}=+\infty$ because $\widetilde{\tau}_{i,j\to k}$ is the expectation of a random variable that is equal to $+\infty$ with positive probability. For this reason, we first compute $\varphi_{i,j\to k}=\mathbb{P}(\widetilde{T}_{k}<+\infty|X_{1}=j,X_{0}=i)$ , the probability that, starting with $X_{0}=i$ and $X_{1}=j$ , the random walker reaches $k$ in finite time. For these quantities, the following result holds:

Theorem 4.1.

For all $k\in V$ , $\{{\varphi}_{i,j\to k}:(i,j)\in E\}$ is the minimal non-negative solution of the following linear system:

\begin{cases}{\varphi}_{i,j\to k}=1&\hbox{if }i=k\text{ or }j=k\\ {\varphi}_{i,j\to k}=\sum_{\ell\in V}p_{i,j,\ell}{\varphi}_{j,\ell\to k}&\hbox{otherwise.}\end{cases}

(15)

Proof.

We first show that $\{{\varphi}_{i,j\to k}:(i,j)\in E\}$ solves the linear system (15). Let us consider an edge $(i,j)\in E$ . If $i=k$ then $X_{0}=k$ , so $\widetilde{T}_{k}=0$ ; if $j=k$ then $X_{1}=k$ and $\widetilde{T}_{k}=1$ . In both cases it immediately follows that ${\varphi}_{i,j\to k}=\mathbb{P}(\widetilde{T}_{k}<+\infty|X_{1}=j,X_{0}=i)=1$ . In the other cases, we have

	$\displaystyle{\varphi}_{i,j\to k}$	$\displaystyle=\mathbb{P}(\widetilde{T}_{k}<+\infty\|X_{1}=j,X_{0}=i)$
		$\displaystyle=\sum_{\ell\in V}\mathbb{P}(X_{2}=\ell\|X_{1}=j,X_{0}=i)\mathbb{P}(\widetilde{T}_{k}<+\infty\|X_{2}=\ell,X_{1}=j,X_{0}=i)$
		$\displaystyle=\sum_{\ell\in V}p_{i,j,\ell}{\varphi}_{j,\ell\to k},$

that is, (15). Now let $\{x_{i,j}:(i,j)\in E\}$ be another non-negative solution of (15) for a fixed $k$ . We show that $x_{i,j}\geq{\varphi}_{i,j\to k}$ for all $(i,j)\in E$ . Indeed, if $i=k$ or $j=k$ then $x_{i,j}={\varphi}_{i,j\to k}$ and the claim follows. Otherwise, for $i,j\neq k$ we have $x_{i,j}=p_{i,j,k}+\sum_{\ell\neq k}p_{i,j,\ell}x_{j,l}$ . Let $\ell_{0}=i$ and $\ell_{1}=j$ . For any $\bar{n}\geq 2$ we have

	$\displaystyle x_{\ell_{0},\ell_{1}}$	$\displaystyle=p_{\ell_{0},\ell_{1},k}+\sum_{\ell_{2}\neq k}p_{\ell_{0},\ell_{1},\ell_{2}}x_{\ell_{1},\ell_{2}}$
		$\displaystyle=p_{\ell_{0},\ell_{1},k}+\sum_{\ell_{2}\neq k}p_{\ell_{0},\ell_{1},\ell_{2}}\bigg{[}p_{\ell_{1},\ell_{2},k}+\sum_{\ell_{3}\neq k}p_{\ell_{1},\ell_{2},\ell_{3}}x_{\ell_{2},\ell_{3}}\Big{]}$
		$\displaystyle=\ldots$
		$\displaystyle=\sum_{n=1}^{\bar{n}}\Bigg{[}\sum_{\ell_{2},\ldots,\ell_{n}\neq k}\prod_{t=2}^{n}p_{\ell_{t-2},\ell_{t-1},\ell_{n}}\Bigg{]}p_{\ell_{n-1},\ell_{n},k}+\sum_{\ell_{2},\ldots,\ell_{\bar{n}+1}\neq k}\prod_{t=2}^{\bar{n}+1}p_{\ell_{t-2},\ell_{t-1},\ell_{t}}x_{\ell_{t-1}\ell_{t}}$
		$\displaystyle\geq\sum_{n=1}^{\bar{n}}\Bigg{[}\sum_{\ell_{2}\neq k}\cdots\sum_{\ell_{n}\neq k}\prod_{t=2}^{n}p_{\ell_{t-2},\ell_{t-1},\ell_{n}}\Bigg{]}p_{\ell_{n-1},\ell_{n},k},$

where we used the inequality $x_{\ell_{t-1}\ell_{t}}\geq 0$ and the empty sum (i.e., the square bracket in the $n=1$ case) must be considered equal to $1$ . Observe that for $n=1,2,3,\ldots$

\Bigg{[}\sum_{\ell_{2}\neq k}\cdots\sum_{\ell_{n}\neq k}\prod_{t=2}^{n}p_{\ell_{t-2},\ell_{t-1},\ell_{n}}\Bigg{]}p_{\ell_{n-1},\ell_{n},k}=\mathbb{P}(\widetilde{T}_{k}=n+1|X_{1}=j,X_{0}=i).

Hence we have $x_{i,j}\geq\mathbb{P}(\widetilde{T}_{k}\leq\bar{n}+1|X_{1}=j,X_{0}=i)$ . Finally,

	$\displaystyle x_{i,j}$	$\displaystyle\geq\lim_{\bar{n}\to+\infty}\mathbb{P}(\widetilde{T}_{k}\leq\bar{n}+1\|X_{1}=j,X_{0}=i)$
		$\displaystyle=\mathbb{P}(\widetilde{T}_{k}<+\infty\|X_{1}=j,X_{0}=i)={\varphi}_{i,j\to k}$

and the claim follows. ∎

On the basis of the preceding theorem we can compute the probability that the second-order process $\{X_{n}\}$ hits a node $k\in V$ in a finite number of steps.

Corollary 4.2.

For any fixed $k\in V$ define ${\varphi}_{i\to k}=\mathbb{P}(\widetilde{T}_{k}<+\infty|X_{0}=i)$ . Then, the vector $({\varphi}_{i\to k})_{i\in V}$ is the vector $({\varphi}_{i,j\to k})_{(i,j)\in E}$ premultiplied by the matrix $M\in\mathbb{R}^{|V|\times|E|}$ given by

M_{ie}=\begin{cases}p^{\prime}_{i,j}&e=(i,j)\in E\\ 0&\hbox{else.}\end{cases}

(16)

Proof.

By elementary considerations, we have

	$\displaystyle{\varphi}_{i\to k}$	$\displaystyle=\mathbb{P}(\widetilde{T}_{k}<+\infty\|X_{0}=i)$
		$\displaystyle=\sum_{j\in V}\mathbb{P}(X_{1}=j\|X_{0}=i)\mathbb{P}(\widetilde{T}_{k}<+\infty\|X_{1}=j,X_{0}=i)=\sum_{j\in V}p^{\prime}_{i,j}{\varphi}_{i,j\to k}.$

∎

In a similar way, we can compute the second-order mean hitting times, as shown in the next theorem:

Theorem 4.3.

In the previous notation, if ${\varphi}_{i,j\to k}=1$ for each $(i,j)\in E$ , then $\{\widetilde{\tau}_{i,j\to k}:(i,j)\in E\}$ is the minimal non-negative solution of the following linear system:

\begin{cases}\widetilde{\tau}_{i,j\to k}=0&\hbox{if }i=k\\ \widetilde{\tau}_{i,j\to k}=1&\hbox{if }j=k\hbox{ and }i\neq k\\ \widetilde{\tau}_{i,j\to k}=1+\sum_{\ell\in V}p_{i,j,\ell}\widetilde{\tau}_{j,\ell\to k}&\hbox{if }i\neq k\hbox{ and }j\neq k.\end{cases}

(17)

Proof.

We first show that $\{\widetilde{\tau}_{i,j\to k}:(i,j)\in E\}$ is a solution of the linear system (17). Let $(i,j)\in E$ . If $i=k$ then $\mathbb{P}(\widetilde{T}_{k}=0|X_{1}=j,X_{0}=i)=1$ and $\widetilde{\tau}_{i,j\to k}=0$ . If $j=k$ then $\mathbb{P}(\widetilde{T}_{k}=1|X_{1}=j,X_{0}=i)=1$ and $\widetilde{\tau}_{i,j\to k}=1$ . Otherwise, if both $i\neq k$ and $j\neq k$ then, by using the definition of expectation we obtain

\begin{split}\widetilde{\tau}_{i,j\to k}&=\mathbb{E}(\widetilde{T}_{k}|X_{1}=j,X_{0}=i)\\ &=2\mathbb{P}(\widetilde{T}_{k}=2|X_{1}=j,X_{0}=i)+\sum_{n\geq 3}n\mathbb{P}(\widetilde{T}_{k}=n|X_{1}=j,X_{0}=i).\end{split}

Now we observe that $\mathbb{P}(\widetilde{T}_{k}=2|X_{1}=j,X_{0}=i)=\mathbb{P}(X_{2}=k|X_{1}=j,X_{0}=i)=p_{i,j,k}$ . Then $\widetilde{\tau}_{i,j\to k}$ is given by

	$\displaystyle\widetilde{\tau}_{i,j\to k}=$	$\displaystyle\,2p_{i,j,k}+\sum_{n\geq 3}n\sum_{\ell\neq k}\mathbb{P}(X_{2}=\ell\|X_{1}=j,X_{0}=i)\mathbb{P}(\widetilde{T}_{k}=n\|X_{2}=\ell,X_{1}=j)$
	$\displaystyle=$	$\displaystyle\,2p_{i,j,k}+\sum_{\ell\neq k}p_{i,j,\ell}\sum_{n\geq 3}n\,\mathbb{P}(\widetilde{T}_{k}=n\|X_{2}=\ell,X_{1}=j)$
	$\displaystyle=$	$\displaystyle\,2p_{i,j,k}+\sum_{\ell\neq k}p_{i,j,\ell}\sum_{m\geq 2}(m+1)\mathbb{P}(\widetilde{T}_{k}=m\|X_{1}=\ell,X_{0}=j).$

Finally, since $\sum_{m\geq 2}m\mathbb{P}(\widetilde{T}_{k}=m|X_{1}=\ell,X_{0}=j)=\widetilde{\tau}_{j,\ell\to k}$ and $\sum_{m\geq 2}\mathbb{P}(\widetilde{T}_{k}=m|X_{1}=\ell,X_{0}=j)=1$ for $\ell\neq k$ , we have

	$\displaystyle\widetilde{\tau}_{i,j\to k}$	$\displaystyle=2p_{i,j,k}+\sum_{\ell\neq k}p_{i,j,\ell}(\widetilde{\tau}_{j,\ell\to k}+1)$
		$\displaystyle=2p_{i,j,k}+\sum_{\ell\neq k}p_{i,j,\ell}\widetilde{\tau}_{j,\ell\to k}+\sum_{\ell\neq k}p_{i,j,\ell}$
		$\displaystyle=1+p_{i,j,k}+\sum_{\ell\neq k}p_{i,j,\ell}\widetilde{\tau}_{j,\ell\to k}=1+\sum_{\ell\in V}p_{i,j,\ell}\widetilde{\tau}_{j,\ell\to k},$

where in the last passages we have used the fact that $\sum_{\ell\in V}p_{i,j,\ell}=1$ .

Now let $\{y_{i,j}:(i,j)\in E\}$ be another non-negative solution of (17). We show that $y_{i,j}\geq\widetilde{\tau}_{i,j\to k}$ for all $(i,j)\in E$ . If $i=k$ or $j=k$ then $y_{i,j}=\widetilde{\tau}_{i,j\to k}$ and the claim follows.

For $i,j\neq k$ we have $y_{i,j}=1+p_{i,j,k}+\sum_{\ell\neq k}p_{i,j,\ell}y_{j,l}$ . Now, let $\ell_{0}=i$ and $\ell_{1}=j$ . For any $\bar{n}\geq 2$ we have

	$\displaystyle y_{\ell_{0},\ell_{1}}$	$\displaystyle=1+p_{\ell_{0},\ell_{1},k}+\sum_{\ell_{2}\neq k}p_{\ell_{0},\ell_{1},\ell_{2}}y_{\ell_{1},\ell_{2}}$
		$\displaystyle=1+p_{\ell_{0},\ell_{1},k}+\sum_{\ell_{2}\neq k}p_{\ell_{0},\ell_{1},\ell_{2}}\bigg{[}1+p_{\ell_{1},\ell_{2},k}+\sum_{\ell_{3}\neq k}p_{\ell_{1},\ell_{2},\ell_{3}}y_{\ell_{2},\ell_{3}}\Big{]}$
		$\displaystyle=\ldots$
		$\displaystyle=\sum_{n=1}^{\bar{n}}\Bigg{[}\sum_{\ell_{2},\ldots,\ell_{n}\neq k}\prod_{t=2}^{n}p_{\ell_{t-2},\ell_{t-1},\ell_{n}}\Bigg{]}\big{(}1+p_{\ell_{n-1},\ell_{n},k}\big{)}+\sum_{\ell_{2},\ldots,\ell_{\bar{n}+1}\neq k}\prod_{t=2}^{\bar{n}+1}p_{\ell_{t-2},\ell_{t-1},\ell_{t}}y_{\ell_{t-1},\ell_{t}}$
		$\displaystyle\geq\sum_{n=1}^{\bar{n}}\Bigg{[}\sum_{\ell_{2},\ldots,\ell_{n}\neq k}\prod_{t=2}^{n}p_{\ell_{t-2},\ell_{t-1},\ell_{n}}\Bigg{]}\big{(}1+p_{\ell_{n-1},\ell_{n},k}\big{)},$

where the empty sum (i.e., the square bracket when $n=1$ ) must be considered equal to $1$ and the last inequality holds since $y_{\ell_{t-1},\ell_{t}}\geq 0$ . Rearranging terms,

	$\displaystyle y_{\ell_{0},\ell_{1}}$	$\displaystyle\geq 1+\sum_{\ell_{2}}p_{\ell_{0},\ell_{1},\ell_{2}}+\sum_{n=3}^{\bar{n}}\sum_{\ell_{2}\neq k}\cdots\sum_{\ell_{n-1}\neq k}\sum_{\ell_{n}}\prod_{t=2}^{n}p_{\ell_{t-2},\ell_{t-1},\ell_{n}}$
		$\displaystyle=\sum_{n=1}^{\bar{n}}\mathbb{P}(\widetilde{T}_{k}\geq n\|X_{1}=j,X_{0}=i)$
		$\displaystyle\geq\sum_{n=1}^{\bar{n}}n\,\mathbb{P}(\widetilde{T}_{k}=n\|X_{1}=j,X_{0}=i).$

Finally, passing to the limit $\bar{n}\to\infty$ we obtain

\displaystyle y_{i,j}

\displaystyle\geq\sum_{n=1}^{\infty}n\,\mathbb{P}(\widetilde{T}_{k}=n|X_{1}=j,X_{0}=i)=\mathbb{E}(\widetilde{T}_{k}|X_{1}=j,X_{0}=i)=\hat{\tau}_{i,j\to k},

and the proof is complete. ∎

Analogously to the argument of Corollary 4.2, we obtain the following characterization for the second-order hitting times directly from Equation (14).

Corollary 4.4.

For any fixed $k\in V$ , the vector $(\widetilde{\tau}_{i\to k})_{i\in V}$ coincides with the vector $(\widetilde{\tau}_{i,j\to k})_{(i,j)\in E}$ pre-multiplied by the matrix $M$ in (16).

4.1 An alternative approach

The linear system in Theorem 4.3 allows us to compute second-order mean hitting times by means of the transition probabilities of the stochastic process $\{X_{n},n\in\mathbb{N}\}$ . The same quantities can be obtained using the fact that to any second-order random walk $\{X_{n}\}$ on $\mathcal{G}$ , corresponds a suitable random walk $\{W_{n}\}$ in $\widehat{\mathcal{G}}$ , as in (11). The two walks have the same transition probability, but the second is shorter than the first by one step. By correcting this discrepancy, we can obtain mean hitting times for $\{X_{n}\}$ from those for $\{W_{n}\}$ .

To this end, for any fixed subset $S\subset E$ , consider the random variables

\widehat{T}_{S}=\min\{n\geq 0:W_{n}\in S\},\qquad\widehat{T}^{+}_{S}=\min\{n\geq 1:W_{n}\in S\},

and the corresponding expectations

\widehat{\tau}_{e\to S}=\mathbb{E}(T_{S}|W_{0}=e),\qquad\widehat{\tau}^{+}_{e\to S}=\mathbb{E}(T^{+}_{S}|W_{0}=e).

(18)

These quantities can be computed by means of the techniques recalled in Section 2.1, since $\{W_{n}\}$ is a classical Markov chain. The theorem below shows how mean hitting (18) for $\{W_{n}\}$ relate to the solution of the linear system in (17). It follows that the problem of computing second-order mean hitting times in $\mathcal{G}$ can be expressed as the problem of computing traditional mean hitting times in $\widehat{\mathcal{G}}$ .

Let us consider a node $k\in V$ . By Theorem 2.2, $\{\hat{\tau}_{e\to\mathcal{I}_{k}}:e\in E\}$ is the minimal non-negative solution of the following linear system:

\begin{cases}\hat{\tau}_{e\to\mathcal{I}_{k}}=0&\hbox{if }e\in\mathcal{I}_{k}\\ \hat{\tau}_{e\to\mathcal{I}_{k}}=1+\sum_{f\in E}\widehat{P}_{ef}\hat{\tau}_{f\to\mathcal{I}_{k}}&\hbox{if $e\notin\mathcal{I}_{k}$.}\end{cases}

(19)

Theorem 4.5.

In the previous notation, it holds

\widetilde{\tau}_{i,j\to k}=\begin{cases}0&\hbox{if }i=k\\ \hat{\tau}_{(i,j)\to\mathcal{I}_{k}}+1&\hbox{if }i\neq k.\end{cases}

Proof.

We show that each non-negative solution of (19) corresponds to a non-negative solution of (17) and vice-versa. Let $\{z_{i,j}:(i,j)\in E\}$ be a non-negative solution of (19). For all $(i,j)\in E$ , we define $y_{i,j}$ as

y_{i,j}=\begin{cases}0&\hbox{if }i=k\\ z_{i,j}+1&\hbox{if }i\neq k.\end{cases}

Then $\{y_{i,j}:(i,j)\in E\}$ is a non-negative solution of (17). In fact, if $j=k$ but $i\neq k$ then $y_{i,j}=1$ . On the other hand, when $i\neq k$ and $j\neq k$ we have

	$\displaystyle y_{i,j}=1+z_{i,j}$	$\displaystyle=1+\Bigl{(}1+\sum_{\ell\in V}\widehat{P}_{(i,j)(j,\ell)}z_{j,\ell}\Bigr{)}$
		$\displaystyle=1+\sum_{\ell\in V}\widehat{P}_{(i,j)(j,\ell)}(1+z_{\ell,m})=1+\sum_{\ell\in V}p_{i,j,\ell}\,y_{j,\ell}.$

In the previous passages we used the fact that $\widehat{P}$ is stochastic and $\widehat{P}_{(i,j)(\ell,m)}=0$ if $\ell\neq j$ . Conversely, if $\{y_{i,j}:(i,j)\in E\}$ is a non-negative solution of (17), then $y_{i,j}\geq 1$ if $i\neq k$ . Thus, if we put, for all $(i,j)\in E$ ,

z_{i,j}=\begin{cases}0&\hbox{if }i=k\\ y_{i,j}-1&\hbox{if }i\neq k,\end{cases}

then $\{z_{i,j}:(i,j)\in E\}$ is a non-negative solution of (19). The thesis follows by considering the minimal non-negative solution of both systems. ∎

4.2 Second-order mean return times

In this section, we formulate the concept of return time for second-order random walks and we give an explicit formula for their computation in arbitrary networks, whenever the numbers $\widetilde{\tau}_{i,j\to k}$ can be computed from (17). For a set $S\subset V$ , consider the random variable

\widetilde{T}^{+}_{S}=\min\{n\geq 1:X_{n}\in S\}.

We are interested in computing the second-order mean return time to $S$ , namely, $\widetilde{\tau}_{S}=\mathbb{E}(\widetilde{T}^{+}_{S}|X_{0}\in S)$ . This quantity represents the average number of steps that are required to reach again $S$ , starting from a node in $S$ and moving through the vertices of $\mathcal{G}$ according to a second-order random walk. For simplicity, in this section we limit ourselves to the single-node case $S=\{i\}$ . We will go back to the general case in Section 5.1. Firstly, we observe that

\widetilde{\tau}_{i}=\mathbb{E}(\widetilde{T}^{+}_{i}|X_{0}=i)=\sum_{j\in V}\mathbb{P}(X_{1}=j|X_{0}=i)\mathbb{E}(\widetilde{T}^{+}_{i}|X_{1}=j,X_{0}=i).

Introducing the auxiliary notation $\widetilde{\tau}_{i,j}=\mathbb{E}(\widetilde{T}^{+}_{i}|X_{1}=j,X_{0}=i)$ , we obtain

\widetilde{\tau}_{i}=\sum_{j}p^{\prime}_{i,j}\widetilde{\tau}_{i,j}.

(20)

The intuition behind this formula is that the random walker chooses at first an out-neighbour $j$ of $i$ at random and then follows a second-order random walk that ends with node $i$ . In fact, $\widetilde{\tau}_{i,j}$ can be easily computed by using the vector $\{\widetilde{\tau}_{i,j\to k}:(i,j)\in E\}$ obtained from (17). Indeed, it holds

	$\displaystyle\widetilde{\tau}_{i,j}$	$\displaystyle=\sum_{k\in V}\mathbb{P}(X_{2}=k\|X_{1}=j,X_{0}=i)\mathbb{E}(\widetilde{T}^{+}_{i}\|X_{2}=k,X_{1}=j,X_{0}=i)$
		$\displaystyle=\sum_{k\in V}p_{i,j,k}\bigl{(}1+\mathbb{E}(\widetilde{T}_{i}\|X_{1}=k,X_{0}=j)\bigr{)}$
		$\displaystyle=1+\sum_{k\in V}p_{i,j,k}\widetilde{\tau}_{j,k\to i}.$

Placing the formula above into (20), yields

\widetilde{\tau}_{i}=1+\sum_{j,k\in V}p^{\prime}_{i,j}p_{i,j,k}\widetilde{\tau}_{j,k\to i}.

Apparently, this formula does not admit a simple matrix-vector form as in Corollary 4.4. In the sequel, we propose to adopt a specific choice for the numbers $p^{\prime}_{i,j}$ that allows us to obtain a result for any $S\subset V$ analogous to Lemma 2.4.

5 The pullback of a second-order random walk

From now on, we suppose that the Markov chain associated to $\widehat{P}$ is ergodic, so that there exists a (unique) vector $\widehat{\pi}>0$ with $\widehat{\pi}^{T}\widehat{P}=\widehat{\pi}^{T}$ . In this case, we can consider the additional assumption that the random walk $\{W_{n}\}$ on $\widehat{\mathcal{G}}$ is at equilibrium, i.e., $\mathbb{P}(W_{n}=e)=\widehat{\pi}_{e}$ , for $n\geq 0$ . Indeed, if the Markov chain $\{W_{n}\}$ is at the stationary state, then, owing to the correspondence between the events $X_{n+1}=i$ and $W_{n}\in\mathcal{I}_{i}$ for $n\geq 0$ , the analysis of the process $\{X_{n}\}$ is simplified and reveals new properties.

For every $e\in E$ , define

\lambda_{e}=\frac{\widehat{\pi}_{e}}{\sum_{f:{\tt T}(f)={\tt T}(e)}\widehat{\pi}_{f}}.

(21)

The numbers $\lambda_{e}$ appearing in (21) have a simple probabilistic interpretation, namely $\lambda_{e}=\mathbb{P}(W_{n}=e|W_{n}\in\mathcal{I}_{{\tt T}(e)})$ is the conditional probability that the random walker in $\widehat{\mathcal{G}}$ is in $e$ , given that they are also in $\mathcal{I}_{{\tt T}(e)}$ . Moreover, let $L\in\mathbb{R}^{|V|\times|E|}$ be the “lifting” matrix defined as follows:

L_{ie}=\begin{cases}\lambda_{e}&{\tt T}(e)=i\\ 0&\hbox{else,}\end{cases}

(22)

Note that the scalars $\lambda_{e}$ fulfill the condition

\sum_{e\in\mathcal{I}_{i}}\lambda_{e}=1,\qquad i=1,\ldots,n.

This condition implies that $L$ is stochastic, $L\mathbbx{1}=\mathbbx{1}$ . If $p$ is a probability vector on the nodes of $\mathcal{G}$ , then $\widehat{p}^{T}=p^{T}L$ is a probability vector defined on the edges, and fulfills the identity $p_{i}=\sum_{e\in\mathcal{I}_{i}}\widehat{p}_{e}$ . Furthermore, let $R\in\mathbb{R}^{|E|\times|V|}$ be the “restriction” matrix

R_{ei}=\begin{cases}1&\hbox{if }{\tt T}(e)=i\\ 0&\hbox{else.}\end{cases}

(23)

Given any probability distribution $\widehat{p}$ on the edges of $\mathcal{G}$ , the product $p^{T}=\widehat{p}^{T}R$ defines a probability distribution on the nodes such that $p_{i}=\sum_{e\in\mathcal{I}_{i}}\widehat{p}_{e}$ . We note in passing that the product $LR$ is the identity in $\mathbb{R}^{n}$ .

Theorem 5.1.

Let $P=L\widehat{P}R\in\mathbb{R}^{n\times n}$ ,

P_{ij}=\sum_{e\in\mathcal{I}_{i}}\sum_{f\in\mathcal{I}_{j}}\lambda_{e}\widehat{P}_{ef}.

(24)

Then, $P$ is an irreducible stochastic matrix. Assuming that the Markov chain $\{W_{n}\}$ is at equilibrium with stationary density $\widehat{\pi}$ , then also $\{X_{n}\}$ is at equilibrium with stationary density $\pi^{T}=\widehat{\pi}^{T}R$ and, for $n\geq 1$ ,

P_{ij}=\mathbb{P}(X_{n+1}=j|X_{n}=i).

Moreover, the initial transition probabilities (10) are

p^{\prime}_{i,j}=\frac{\widehat{\pi}_{(i,j)}}{\sum_{f\in\mathcal{O}_{i}}\widehat{\pi}_{f}},\qquad(i,j)\in E,

(25)

and the vector $\pi^{T}=\widehat{\pi}^{T}R$ is the (unique) invariant vector of the Markov chain associated to $P$ .

Proof.

First, note that the matrix $P$ is non-negative and stochastic. To prove that $P$ is irreducible, let $i,j\in V$ be arbitrary. Owing to the irreducibility of $\widehat{P}$ , for any $e\in\mathcal{I}_{i}$ and $f\in\mathcal{I}_{j}$ there is a path in $\widehat{\mathcal{G}}$ from $e$ to $f$ . Let $e=e_{0},e_{1},\ldots,e_{m}=f$ be such path. Then, the sequence ${\tt T}(e_{0}),{\tt T}(e_{1}),\ldots,{\tt T}(e_{m})$ is a path in $\mathcal{G}$ from $i$ to $j$ .

Thus, owing to the correspondence between $X_{n+1}=i$ and $W_{n}\in\mathcal{I}_{i}$ , we have

	$\displaystyle\mathbb{P}(X_{n+1}=j\|X_{n}=i)$	$\displaystyle=\mathbb{P}(W_{n}\in\mathcal{I}_{j}\|W_{n-1}\in\mathcal{I}_{i})$
		$\displaystyle=\sum_{e\in\mathcal{I}_{i}}\sum_{f\in\mathcal{I}_{j}}\mathbb{P}(W_{n}=f\|W_{n-1}=e)\mathbb{P}(W_{n-1}=e\|W_{n-1}\in\mathcal{I}_{i})$
		$\displaystyle=\sum_{e\in\mathcal{I}_{i}}\sum_{f\in\mathcal{I}_{j}}\widehat{P}_{ef}\lambda_{e}=P_{ij}$

for any $n\geq 1$ . Moreover, consider the vector $\pi^{T}=\widehat{\pi}^{T}R$ . In detail,

\pi_{i}=\sum_{e\in\mathcal{I}_{i}}\widehat{\pi}_{e}>0,\qquad i=1,\ldots,n.

(26)

To prove that $\pi$ is an invariant vector of $P$ , first observe that $\widehat{\pi}^{T}RL=\widehat{\pi}$ . Indeed, owing to (21), for any fixed $e\in E$ we obtain

(\widehat{\pi}^{T}RL)_{e}=\lambda_{e}\sum_{f:{\tt T}(f)={\tt T}(e)}\widehat{\pi}_{f}=\widehat{\pi}_{e}.

Moreover, $\pi^{T}\mathbbx{1}=\widehat{\pi}^{T}R\mathbbx{1}=\widehat{\pi}^{T}\mathbbx{1}=1$ , eventually yielding

\pi^{T}P=\widehat{\pi}^{T}RL\widehat{P}R=\widehat{\pi}^{T}\widehat{P}R=\widehat{\pi}^{T}R=\pi^{T}.

To complete the proof it is sufficient to observe that, if $\{W_{n}\}$ is at equilibrium then also $\{X_{n}\}$ is at equilibrium and

	$\displaystyle\widehat{\pi}_{(i,j)}=\mathbb{P}(W_{0}=(i,j))$	$\displaystyle=\mathbb{P}(X_{1}=j,X_{0}=i)$
		$\displaystyle=\mathbb{P}(X_{1}=j\|X_{0}=i)\mathbb{P}(X_{0}=i)=p^{\prime}_{i,j}\sum_{f\in\mathcal{I}_{i}}\widehat{\pi}_{f}.$

Thus, $p^{\prime}_{i,j}=\widehat{\pi}_{(i,j)}/\sum_{f\in\mathcal{I}_{i}}\widehat{\pi}_{f}$ . Finally, as $\sum_{f\in\mathcal{I}_{i}}\widehat{\pi}_{f}=\sum_{f\in\mathcal{O}_{i}}\widehat{\pi}_{f}$ , we obtain (25), which concludes the proof. ∎

We call the matrix $P$ in (24) the pullback of $\widehat{P}$ on $\mathcal{G}$ . Note that these two matrices correspond to two different stochastic processes, as briefly pointed out in Remark 5.2 below. Moreover, as we may expect, we remark that the pullback operation is not injective, as different stochastic processes on $\widehat{\mathcal{G}}$ may have the same pullback in $\mathcal{G}$ . This is shown by the Example 5.3 below, where the classic and non-backtracking processes are shown to have the same pullback.

Remark 5.2.

As shown in Theorem 5.1, the entries of the pullback matrix $P$ correspond to first-order transition probabilities of the stochastic process $\{X_{n}\}$ . However, this does not mean that $\{X_{n}\}$ is a Markov chain, which would be true if (and only if) the sequence $\{X_{n}\}$ were to satisfy the Markov condition $\mathbb{P}(X_{n+1}=k|X_{n}=j)=\mathbb{P}(X_{n+1}=k|X_{n}=j,X_{n-1}=i)$ , for every $(i,j),(j,k)\in E$ , at least under the considered assumptions. On the other hand, Equation (24) yields

P_{ij}=\sum_{(h,i)\in E}\lambda_{(h,i)}p_{h,i,j},

that is, $P_{ij}$ is a convex combinations of the numbers $p_{h,i,j}$ . Consequently, the Markov condition holds true if and only if the second-order transition probabilities (9) are independent of the oldest state, in which case $\{X_{n}\}$ is trivially a Markov chain.

Actually, the construction of $P$ from $\widehat{P}$ is reminiscent of a so-called lumping of $\{W_{n}\}$ , see e.g., [34] and [18, Sec. 6.3-4]. Lumping methods are known to allow the construction of Markov chains with a reduced number of states from certain finite Markov chains with a larger states set. The corresponding transition matrices are related by an identity similar to the one defining $P$ from $\widehat{P}$ in Theorem 5.1. However, the process $\{X_{n}\}$ is not a lumping of $\{W_{n}\}$ since it is not a Markov chain, even when at equilibrium. This is the reason why second-order mean hitting times differ ostensibly from mean hitting times corresponding to $P$ , as shown in various numerical experiments in Section 6.

Example 5.3.

Let $\mathcal{G}$ be undirected and (strongly) connected, with adjacency matrix $A$ , and let $\widehat{\mathcal{G}}$ be its line graph. Consider the random walk on $\widehat{\mathcal{G}}$ defined as in Example 3.1, with transition matrix $\widehat{P}$ . It is not hard to verify that the pullback of $\widehat{P}$ on $\mathcal{G}$ coincides with the transition matrix of the standard random walk on $\mathcal{G}$ . The same conclusion is true also for the matrix $\widehat{P}$ considered in Example 3.2. Indeed, if $A_{ij}=0$ then

(L\widehat{P}R)_{ij}=\sum_{e\in\mathcal{I}_{i}}\sum_{f\in\mathcal{I}_{j}}\lambda_{e}\widehat{P}_{ef}=0

because the condition ${\tt S}(f)={\tt T}(e)$ is always false. On the other hand, if $A_{ij}=1$ then

	$\displaystyle(L\widehat{P}R)_{ij}$	$\displaystyle=\frac{1}{\sum_{e\in\mathcal{I}_{i}}}\sum_{f\in\mathcal{I}_{j}}\lambda_{e}\widehat{P}_{ef}$
		$\displaystyle=\sum_{e\in\mathcal{I}_{i}}\sum_{f\in\mathcal{I}_{j}}\frac{\lambda_{e}}{d^{+}_{{\tt S}(f)}-1}$
		$\displaystyle=(\|\mathcal{I}_{i}\|-1)\frac{1/d^{-}_{i}}{d^{+}_{i}-1}=\frac{1}{d_{i}},$

since $|\mathcal{I}_{i}|=d^{-}_{i}=d^{+}_{i}=d_{i}$ . By linearity, also the pullback of the backtrack-downweighted random walk in Example 3.3 coincides with the standard random walk on $\mathcal{G}$ .

5.1 Hitting and return times at equilibrium

Due to Theorem 5.1, it is convenient to assume that the initial probabilities of the second-order stochastic process under consideration (10) are equal to $\lambda_{(i,j)}$ . Hence, from here onward we consider the “equilibrium assumption” $\mathbb{P}(X_{0}=i)=\pi_{i}$ together with (25). With this assumption, the presentation of the mean hitting and return times introduced in the previous section can be carried out with greater clarity and simplicity. To begin with, we derive an algebraic expression for the second-order hitting times matrix $\widetilde{T}=(\widetilde{\tau}_{i\to j})$ of a very different nature from that at the basis of Equation (14).

Theorem 5.4.

Let $\widetilde{T}=(\widetilde{\tau}_{i\to j})_{i,j\in V}$ and $\widehat{T}=(\widehat{\tau}_{e\to f})_{e,f\in E}$ . There exists a vector $a=(\alpha_{e})_{e\in E}$ and a vector $b=(\beta_{i})_{i\in V}$ such that

\widetilde{T}=L\widehat{T}\,\mathrm{Diag}(a)R-\mathbbx{1}b^{T},

where $L$ is as in (22) and $R$ is as in (23).

Proof.

Introduce the matrix $C\in\mathbb{R}^{|E|\times|V|}$ such that $C_{ei}=\widehat{\tau}_{e\to\mathcal{I}_{i}}$ is defined as in Section 4.1. From the identity

	$\displaystyle\widetilde{\tau}_{i\to j}=\mathbb{E}(\widetilde{T}_{j}\|X_{0}=i)$	$\displaystyle=\mathbb{E}(\widehat{T}_{\mathcal{I}_{j}}\|W_{0}\in\mathcal{I}_{i})$
		$\displaystyle=\sum_{e\in\mathcal{I}_{i}}\mathbb{P}(W_{0}=e\|W_{0}\in\mathcal{I}_{i})\,\mathbb{E}(\widehat{T}_{\mathcal{I}_{j}}\|W_{0}=e)=\sum_{e\in\mathcal{I}_{i}}\lambda_{e}\widehat{\tau}_{e\to\mathcal{I}_{j}}$

it follows that $\widetilde{T}=LC$ . Using the technical Lemma 2.6, for every $e\in E$ and $i\in V$ there exist coefficients $\alpha_{e}$ and $\beta_{i}$ such that $\widehat{\tau}_{e\to\mathcal{I}_{i}}=\sum_{f\in\mathcal{I}_{i}}\alpha_{f}\widehat{\tau}_{e\to f}-\beta_{i}$ . The latter identity can be expressed in matrix terms as

C=\widehat{T}\,\mathrm{Diag}(a)R-\mathbbx{1}b^{T}.

Finally, as $L\mathbbx{1}=\mathbbx{1}$ , we conclude. ∎

The previous theorem yields a formula for the matrix $\widetilde{T}$ that is amenable to numerical computations, once the matrix $\widehat{T}$ has been computed by standard methods via, e.g., (7). The next result proves that second-order mean return times defined in Section 4.2 coincide with the usual return times of the random walk associated with the pullback of $\widehat{P}$ on $\mathcal{G}$ .

Theorem 5.5.

Let $\pi$ be the stationary density of the pullback of $\widehat{P}$ on $\mathcal{G}$ . For every $S\subset V$ it holds $\widetilde{\tau}_{S}=1/\sum_{i\in S}\pi_{i}$ . In particular, $\widetilde{\tau}_{i}=1/\pi_{i}$ for $i\in V$ .

Proof.

Let $\widehat{S}=\cup_{i\in S}\mathcal{I}_{i}$ . Then, $\widetilde{\tau}_{S}$ can be reformulated as the mean return time in $\widehat{S}$ of the chain $\{W_{n}\}$ . From Lemma 2.4 and (26), we get

\widetilde{\tau}_{S}=\mathbb{E}(\widehat{T}^{+}_{\widehat{S}}|W_{0}\in\widehat{S})=\frac{1}{\sum_{i\in S}\sum_{e\in\mathcal{I}_{i}}\widehat{\pi}_{e}}=\frac{1}{\sum_{i\in S}\pi_{i}},

and we have the claim. ∎

Example 5.6.

Let $\mathcal{G}=(V,E)$ be finite and undirected. For $\alpha\in[0,1]$ , the stationary density $\widehat{\pi}$ of the matrix $\widehat{P}^{(\alpha)}$ in Example 3.3 is a constant vector, $\widehat{\pi}_{e}=1/|E|$ , as the transition matrix is bi-stochastic. Consequently, the second-order mean return times coincides with the mean return times of the uniform random walk on $\mathcal{G}$ , namely, $\widetilde{\tau}_{i}=(\sum_{j}d_{j})/d_{i}$ , independently of $\alpha$ and the topology of $\mathcal{G}$ . Moreover, in this example Equation (25) becomes $\lambda_{(i,j)}=1/d_{i}$ being $\mathcal{G}$ undirected, i.e., the first step in the second-order process coincides with one step of a standard uniform random walk on $\mathcal{G}$ .

Theorem 5.5 yields a second-order analogous to Kac’s lemma, see Lemma 2.4. For a family of networks that exhibit some specific symmetries, Lemma 2.5 can also be extended to second-order random walks, as shown in the sequel.

The coefficients $\alpha_{e}$ appearing in the proof of Theorem 5.4 come from Lemma 2.6 and, according to (8), can be expressed as $\alpha_{e}=\widehat{\pi}_{e}\widehat{\tau}^{+}_{e\to\mathcal{I}_{i}}$ where $i={\tt T}(e)$ and $\widehat{\tau}^{+}_{e\to\mathcal{I}_{i}}$ represents the mean return time to $\mathcal{I}_{i}$ of $\{W_{n}\}$ , after leaving it from $e\in\mathcal{I}_{i}$ , as defined in (18). Suppose that these return times depend on $i$ but not on $e\in\mathcal{I}_{i}$ . This assumption is clearly verified if for every $e,f\in\mathcal{I}_{i}$ there is an automorphism of $\widehat{\mathcal{G}}$ that exchanges $e$ and $f$ , i.e., the nodes $e$ and $f$ in $\widehat{\mathcal{G}}$ can be exchanged without altering the topology of $\widehat{\mathcal{G}}$ . The latter condition is satisfied if, for example, $\{W_{n}\}$ is a uniform random walk on a bipartite regular graph, that is, an undirected, bipartite graph whose adjacency matrix has the form

\begin{pmatrix}O&\mathbbx{1}\mathbbx{1}^{T}\\ \mathbbx{1}\mathbbx{1}^{T}&O\end{pmatrix},

in which the diagonal blocks can have different sizes.

For notational simplicity, denote by $\rho_{i}=\widehat{\tau}^{+}_{e\to\mathcal{I}_{i}}$ that common value. Then, from Theorem 5.1 we have

1=\sum_{e\in\mathcal{I}_{i}}\alpha_{e}=\sum_{e\in\mathcal{I}_{i}}\widehat{\pi}_{e}\widehat{\tau}^{+}_{e\to\mathcal{I}_{i}}=\rho_{i}\sum_{e\in\mathcal{I}_{i}}\widehat{\pi}_{e}=\rho_{i}\pi_{i}.

Thus $\rho_{i}=1/\pi_{i}$ . Moreover, for $e\in\mathcal{I}_{i}$ we obtain

\alpha_{e}=\widehat{\pi}_{e}\rho_{i}=\widehat{\pi}_{e}/\pi_{i}.

Hence, in the notation of Theorem 5.4, we have that $\mathrm{Diag}(a)R\pi=\widehat{\pi}$ , and thus

\widetilde{T}\pi=L\widehat{T}\,\mathrm{Diag}(a)R\pi-\mathbbx{1}b^{T}\pi=L\widehat{T}\widehat{\pi}-\mathbbx{1}b^{T}\pi,

where $b=(\beta_{i})_{i\in V}$ is the coefficient vector defined in Theorem 5.4. By Lemma 2.5, we have $\widehat{T}\widehat{\pi}=\kappa\mathbbx{1}$ where $\kappa$ is the Kemeny’s constant of $\widehat{T}$ , and we eventually obtain:

\widetilde{T}\pi=\kappa L\mathbbx{1}-\mathbbx{1}b^{T}\pi=\mathbbx{1}(\kappa-b^{T}\pi).

Combining all the observations above, we obtain the following second-order equivalent of the random target lemma:

Corollary 5.7.

Let $\pi$ be the stationary density given in Theorem 5.1. In the equilibrium assumption discussed at the beginning of Section 5.1 and using the previous notation, we have that, if for every $i\in V$ the return time $\widehat{\tau}^{+}_{e\to\mathcal{I}_{i}}$ depends on $i$ but not on $e\in\mathcal{I}_{i}$ , then

\sum_{j\in V}\pi_{j}\widetilde{\tau}_{i\to j}=\widetilde{\kappa},

independently on $i$ , where $\widetilde{\kappa}=\kappa-b^{T}\pi$ .

6 Numerical experiments on real-world networks

In this section, we present numerical results on the computation of second-order mean hitting times on some real-world networks. We consider three undirected and unweighted networks: Guppy [8], that represents the social interactions of a population of free-ranging guppies (Poecilia reticulata), Dolphins [23], that represents the social structure of a group of dolphins, and Householder93 [26], that represents a collaboration network of a group of mathematicians. Since these graphs contain dangling edges, we remove in sequence all the nodes of degree $1$ until each vertex has degree greater or equal to $2$ . Table 1 shows the dimension of these networks before and after removing such leaf nodes. Our experiments illustrate various statistics on the second-order hitting times $\widehat{\tau}_{i\to j}$ for non-backtracking random walks in these graphs. Note that hitting times computed with the pullback transition matrix coincide with the hitting times $\tau_{i\to j}$ for the standard random walk, see Example 5.6.

	before the removal			after the removal
	nodes	edges	diameter	nodes	edges	diameter
Guppy	99	726	6	98	725	5
Dolphins	62	159	8	53	150	7
Householder93	104	211	7	73	180	5

Table 1: Dimension of the networks used in our experiments before and after the removal of leaf nodes.

In Figure 1 we scatter plot the average non-backtracking mean hitting times $\widehat{m}_{j}=\sum_{i\in V}\widehat{\tau}_{i\to j}/|V|$ against the average traditional mean hitting times $m_{j}=\sum_{i\in V}\tau_{i\to j}/|V|$ . The dotted red line is the bisector of the first quadrant. We observe that, in all these networks, the ratio between $m_{j}$ and $\widehat{m}_{j}$ is always smaller than $1$ . Intuitively, this means that, on average, non-backtracking random walks are shorter than classical random walks.

Refer to caption — Figure 1: Scatter plot of the average non-backtracking mean hitting times against the average traditional mean hitting times for the networks Guppy, Dolphins and Householder93. The dotted lines represent the bisectors.

Figure 2 displays the value of the non-backtracking mean access time

a_{i}=\sum_{j\in V}\pi_{j}\widehat{\tau}_{i\to j}

(27)

with respect to the node index $i\in V$ . Recall that these values for the standard random walks are all equal to the Kemeny constant of the graph, see Lemma 2.5. Remarkably, the values for non-backtracking walks have a very narrow range, as shown by the small variation of the values in the $y$ -axes. This experiment shows that in these graphs the claim of Corollary 4.4 is approximately valid, even though the assumptions about the structure of the graph are not satisfied.

Finally, we computed mean hitting times for the backtrack-downweighted random walks introduced in Example 3.3, with varying $\alpha\in[0,1]$ . The corresponding stochastic processes interpolate between the standard random walk ( $\alpha=1$ ) and the non-backtracking variant ( $\alpha=0$ ). Nevertheless, the pullback matrix does not depend on $\alpha$ , as noted in Example 5.3. Let $\tau^{(\alpha)}_{i\to j}$ denote second-order mean hitting times associated with the transition matrix $\widehat{P}^{(\alpha)}$ . To better illustrate the effect of penalizing backtracking steps, we measure the mean hitting times ratio

r^{(\alpha)}_{j}=\frac{\sum_{i\in V}\tau^{(\alpha)}_{i\to j}}{\sum_{i\in V}\tau^{(1)}_{i\to j}}.

(28)

The curves in Figure 3 illustrate the behavior of the average value (magenta line), along with the maximum and the minimum value (black lines) of these ratios. The values for $\alpha=0$ correspond to the results shown in Figure 1.

7 Conclusions

Second-order random walks, which include non-backtracking random walks as a particular case, provide stochastic models for navigation and diffusion processes on networks that can offer improved modeling capacity with respect to classical random-walks, and thus allow us to better capture real-world dynamics on networks. In this paper, we propose a very general framework to properly define mean hitting times and mean return times for second-order random walks for directed graphs with finite or countably many nodes. Our approach is based on the correspondence between the second-order random walk and a standard random walk obtained by first lifting the second-random walk to the directed line graph and then pulling back onto the original graph. The “pullback” Markov chain obtained this way has the same stationary density as the initial second-order random process and allow us to transfer several well-known results for standard random walks to the second-order case. For example, we prove that second-order mean return times coincide with the mean return times of the corresponding pullback Markov chain and we show how to extend the Kac’s and random target lemmas to second-order random walks.

These results prompt us to further investigations concerning computational issues as well as theoretical properties of second-order random walks. For instance, it is certainly interesting to devise more efficient numerical methods to compute second-order hitting times than the one based on Corollary 4.4 and Theorem 5.4. Furthermore, numerical experiments show that non-backtracking hitting times are consistently smaller than their corresponding classical, backtracking versions. In fact, reducing the probability of backtracking results in a reduction of the mean hitting times. However, a formal explanation of this fact, at the best of our knowledge, is still missing.

Acknowledgement

The work of Dario Fasino and Arianna Tonetto has been carried out in the framework of the departmental research project ‘ICON: Innovative Combinatorial Optimization in Networks’, Department of Mathematics, Computer Science and Physics (PRID 2017), University of Udine, Italy. The work of Dario Fasino and Francesco Tudisco has been partly supported by Istituto Nazionale di Alta Matematica, INdAM-GNCS, Italy.

References

[1] F. Arrigo, P. Grindrod, D. J. Higham, and V. Noferini. Non-backtracking walk centrality for directed networks. Journal of Complex Networks, 6:54–78, 2018.
[2] F. Arrigo, D. J. Higham, and V. Noferini. A theory for backtrack-downweighted walks. SIAM J. Matrix Anal. Appl., 42:1229–1247, 2021.
[3] F. Arrigo, D. J. Higham, and F. Tudisco. A framework for second-order eigenvector centralities and clustering coefficients. Proceedings of the Royal Society A, 476(2236):20190724, 2020.
[4] A. R. Benson, R. Abebe, M. T. Schaub, A. Jadbabaie, and J. Kleinberg. Simplicial closure and higher-order link prediction. Proceedings of the National Academy of Sciences, 115(48):E11221–E11230, 2018.
[5] A. R. Benson, D. F. Gleich, and L.-H. Lim. The spacey random walk: A stochastic process for higher-order data. SIAM Review, 59(2):321–345, 2017.
[6] S. M. Cioabă and P. Xu. Mixing rates of random walks with little backtracking. In SCHOLAR—a Scientific Celebration Highlighting Open Lines of Arithmetic Research, volume 655 of Contemp. Math., pages 27–58. Amer. Math. Soc., Providence, RI, 2015.
[7] S. Cipolla, F. Durastante, and F. Tudisco. Nonlocal PageRank. ESAIM Mathematical Modelling and Numerical Analysis, 2020.
[8] D. P. Croft, J. Krause, and R. James. Social networks in the guppy (poecilia reticulata). Proceedings of the Royal Society B: Biological Sciences, 271, 2005.
[9] M. Cucuringu, P. Rombach, S. Lee, and M. Porter. Detection of core-periphery structure in networks using spectral methods and geodesic paths. European Journal of Applied Mathematics, 27:846–887, 2016.
[10] F. Della Rossa, F. Dercole, and C. Piccardi. Profiling core-periphery network structure by random walkers. Scientific reports, 3:1–8, 2013.
[11] E. Estrada, J.-C. Delvenne, N. Hatano, J. L. Mateos, R. Metzler, A. P. Riascos, and M. T. Schaub. Random multi-hopper model: super-fast random walks on graphs. Journal of Complex Networks, 6(3):382–403, 2017.
[12] D. Fasino and F. Tudisco. Ergodicity coefficients for higher-order stochastic processes. SIAM J. Mathematics of Data Science, 2:740–769, 2020.
[13] R. Fitzner and R. Hofstad. Non-backtracking random walk. Journal of Statistical Physics, 150:264–284, 2012.
[14] P. Grindrod, D. J. Higham, and V. Noferini. The deformed graph Laplacian and its applications to network centrality analysis. Journal of Statistical Physics, 39:310–341, 2018.
[15] A. Grover and J. Leskovec. Node2vec: Scalable feature learning for networks. In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 855–864, 2016.
[16] M. Kac. On the notion of recurrence in discrete stochastic processes. Bulletin of the American Mathematical Society, 53(10):1002–1010, 1947.
[17] T. Kawamoto. Localized eigenvectors of the non-backtracking matrix. Journal of Statistical Mechanics: Theory and Experiment, 2016(2):023404, 2016.
[18] J. G. Kemeny and J. L. Snell. Finite Markov chains. Undergraduate Texts in Mathematics. Springer-Verlag, New York-Heidelberg, 1976.
[19] M. Kempton. Non-backtracking random walks and a weighted Ihara’s theorem. Open Journal of Discrete Mathematics, 6:207–226, 2016.
[20] F. Krzakala, C. Moore, E. Mossel, J. Neeman, A. Sly, L. Zdeborová, and P. Zhang. Spectral redemption in clustering sparse networks. Proceedings of the National Academy of Sciences, 110(52):20935–20940, 2013.
[21] D. A. Levin, Y. Peres, and E. L. Wilmer. Markov Chains and Mixing Times. American Mathematical Society, Providence, RI, 2009.
[22] D. Liben-Nowell and J. Kleinberg. The link-prediction problem for social networks. Journal of the American society for information science and technology, 58(7):1019–1031, 2007.
[23] D. Lusseau, K. Schneider, O. J. Boisseau, P. Haase, E. Slooten, and S. M. Dawson. The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations. Behavioral Ecology and Sociobiology, 54(4):396–405, 2003.
[24] T. Martin, X. Zhang, and M. E. Newman. Localization and centrality in networks. Physical Review E, 90(5):052808, 2014.
[25] C. D. Meyer. Matrix Analysis and Applied Linear Algebra, volume 71. SIAM, 2000.
[26] C. Moler. Lake Arrowhead Coauthor Graph. http://blogs.mathworks.com/cleve/2013/06/10/lake-arrowhead-coauthor-graph/, 2013.
[27] A. N., I. Benjamini, E. Lubetzky, and S. Sodin. Non-backtracking random walks mix faster. Communications in Contemporary Mathematics, 9:585–603, 2007.
[28] B. Nadler, N. Srebro, and X. Zhou. Semi-supervised learning with the graph Laplacian: The limit of infinite unlabelled data. Advances in Neural Information Processing Systems, 22:1330–1338, 2009.
[29] M. Newman. Networks: An Introduction. Oxford University Press, 2010.
[30] M. E. Newman. A measure of betweenness centrality based on random walks. Social Networks, 27(1):39–54, 2005.
[31] J. D. Noh and H. Rieger. Random walks on complex networks. Physical Review Letters, 92(11):118701, 2004.
[32] J. R. Norris. Markov Chains. Number 2 in Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 1998.
[33] P. Rombach, M. A. Porter, J. H. Fowler, and P. J. Mucha. Core-periphery structure in networks (revisited). SIAM Review, 59(3):619–646, 2017.
[34] G. Rubino and B. Sericola. A finite characterization of weak lumpable Markov processes. I. The discrete time case. Stochastic Process. Appl., 38(2):195–204, 1991.
[35] L. Torres, K. S. Chan, H. Tong, and T. Eliassi-Rad. Nonbacktracking eigenvalues under node removal: X-centrality and targeted immunization. SIAM Journal on Mathematics of Data Science, 3(2):656–675, 2021.
[36] F. Tudisco, A. R. Benson, and K. Prokopchik. Nonlinear higher-order label spreading. In Proceedings of the Web Conference 2021, pages 2402–2413, 2021.
[37] F. Tudisco and D. J. Higham. A nonlinear spectral method for core-periphery detection in networks. SIAM J. Mathematics of Data Science, 1:269–292, 2019.
[38] Y. Wu, Y. Bian, and X. Zhang. Remember where you came from: On the second-order random walk based proximity measures. Proc. VLDB Endow., 10(1):13–24, 2016.

	$\displaystyle\mathbb{P}(X_{n+1}=j\|X_{n}=i)$	$\displaystyle=\mathbb{P}(W_{n}\in\mathcal{I}_{j}\|W_{n-1}\in\mathcal{I}_{i})$
		$\displaystyle=\sum_{e\in\mathcal{I}_{i}}\sum_{f\in\mathcal{I}_{j}}\mathbb{P}(W_{n}=f\|W_{n-1}=e)\mathbb{P}(W_{n-1}=e\|W_{n-1}\in\mathcal{I}_{i})$
		$\displaystyle=\sum_{e\in\mathcal{I}_{i}}\sum_{f\in\mathcal{I}_{j}}\widehat{P}_{ef}\lambda_{e}=P_{ij}$