Non-backtracking PageRank

The notion of a walk around a graph is both natural and useful. The walker may follow any available edge, with nodes and edges being revisited at any stage. However, in some settings, walks that backtrack—leave a node and then return to it on the next step—are best avoided. The concept of restricting attention to non-backtracking walks has arisen, essentially independently, in a wide range of seemingly unrelated fields, including spectral graph theory [2, 13, 14], number theory [30], discrete mathematics [4, 28], quantum chaos [26], random matrix theory [27], stochastic analysis [1], applied linear algebra [29] and computer science [24, 33]. Non-backtracking has more recently been considered in the context of matrix computation, where it has been shown to form the basis of effective algorithms in network science for community detection, centrality and alignment [3, 10, 16, 18, 20, 21, 23, 31]. We note that non-backtracking walks have typically been studied on undirected networks, but the definition continues to make sense in the directed case.

For network science applications, non-backtracking can be imposed at very little extra cost and offers quantifiable benefits: centrality measures can avoid localization [3, 10, 20] and discover key influencers [21, 31], and community detection algorithms perform optimally on the stochastic block model [18]. In terms of classical random walks on a graph, it is also known that non-backtracking enhances mixing [1].

Given that the PageRank algorithm [22] computes the steady state of a particular (teleporting) random walk, it is therefore natural to ask whether there is any scope for designing and analysing a non-backtracking analog. We emphasize that the PageRank philosophy has been extended well beyond the WWW into a diverse range of areas including bioinformatics, bibliometrics, business, chemistry, neuroscience, social media, and sports [9], where non-backtracking may be a natural requirement. In particular, PageRank-like measures have been extensively used in transport modelling; see, for example, [6, 25]. In this setting it is reasonable to assume that a vehicle will not immediately head back to the same road junction, train station or bus stop.

In this work, we therefore consider the following general questions:At the core of our analysis is the Hashimoto matrix, which arises when we work on the dual graph, or line graph. It is interesting to note a connection with the space syntax approach in the analysis of road networks, where edges in a graph represent crossroads and nodes are the streets [7]. This representation is the dual of the more intuitive setting where edges represent roads and nodes are intersections; however, in [25] the authors argue that “the dual graphs carry more information than the corresponding primal graph.”

The material is organized as follows. In Sect. 2 we describe background material on PageRank. Section 3 gives a transposition of standard PageRank to the dual space and verifies the equivalence of the two formulations. Section 4 defines and analyzes a new non-backtracking analog. In particular, we show that, even for undirected graphs, non-backtracking generally leads to a different ranking of the nodes. In Sect. 5 we derive a computable description of the new measure and show how to exploit the structure and sparsity of the Hashimoto matrix. In Sect. 6 we comment on some numerical experiments performed on road networks. Section 7 gives some conclusions.

Let \(A = (a_{ij})\in {\mathbb {R}}^{n\times n}\) be the adjacency matrix of an unweighted, weakly connected, directed graph with n nodes and \({\widetilde{m}}\) directed edges. We further assume that there are no multiple edges linking nodes in the network. Under these assumptions, \(a_{ij} = 1\) if there is an edge from node i to node j, otherwise \(a_{ij} = 0\). A node that has no outgoing links is called a dangling node. We use the common approach of removing dangling nodes by modifying the adjacency matrix; all-zeros rows in A are replaced by all-ones rows [15]. This corresponds to adding n edges from each dangling node to all the nodes in the network, itself included.

Let \(G = (V,E)\) be the graph obtained once these edges have been added to the original network in order to remove dangling nodes. In the remainder of the paper, we shall work on this network. Let \(W = A + \varvec{\chi }{\mathbf {1}}^T\) be its adjacency matrix, where \(\varvec{\chi }\) is the indicator vector for the set containing the dangling nodes in the original digraph. Here, \({\mathbf {1}}\in {\mathbb {R}}^n\) denotes the vector of all ones, and we will sometimes write \({\mathbf {1}}_n\) when its dimension may be in doubt. We let k be the number of dangling nodes in the original network, so the new graph G contains \(m:={\widetilde{m}}+kn\) edges among n nodes.

Let \(\mathbf{d}= (d_{i}) = W{\mathbf {1}}\) be the vector of out-degrees for the nodes in the graph represented by W, i.e., let \(d_i\) be the number of edges leaving node i in G. We will denote by D the diagonal matrix whose diagonal entries are \(D_{ii} = d_{i}\) for all i. Since all the nodes have positive out-degree, D is invertible.

We assume that the edges have been labelled in some arbitrary order \(\{ e \}_{e = 1}^m\). We also use the notation \(i\rightarrow j\) to denote an edge from node i to node j and \(i\rightarrow \star \) to denote an edge that starts from node i. We then define the matrices \(L, R\in {\mathbb {R}}^{m\times n}\) as follows:andIn words \(L_{ei}\) records whether edge e starts at node i, and \(R_{ej}\) records whether edge e ends at node j. The matrices L and R will be referred to as the source matrix and target matrix, respectively. It is readily seen that \(W = L^TR\) and \(D = L^TL\). Moreover, the matrix \(R^TR\) is diagonal with the in-degree of the nodes as its diagonal entries.

As discussed in the original work [22], the PageRank algorithm may be motivated from two different perspectives: (a) the long-term behavior of a web surfer who randomly follows outgoing links and occasionally teleports (jumps) to a random page, and (b) the outcome of an iterative voting procedure where a page votes for pages that it follows, with more important pages given more influence.

From the random surfer viewpoint, the PageRank vector \(\mathbf{x}\) may be defined as the stationary distribution of a Markov chain that is constructed from a random walk on the graph plus teleporting:where \(P = \alpha D^{-1}W +(1-\alpha ){\mathbf {1}}\mathbf{v}^T\) is row stochastic and \(\Vert \mathbf{x}\Vert _1 = 1\), [9]. Here, \(W^TD^{-1}\) is column-stochastic, \(\alpha \in (0,1)\), and \(\mathbf{v}\ge {\mathbf {0}}\) is such that \(\Vert \mathbf{v}\Vert _1 = 1\). The matrix \(F = {\mathbf {1}}\mathbf{v}^T\) is sometimes referred to as the teleportation matrix and \(\mathbf{v}\) the teleportation distribution vector [9] or personalization vector [19]. The scalar \(\alpha \) is known as the teleportation parameter [5, 9] or amplification factor [34].

Based on the voting procedure, we may equivalently define the PageRank vector as the normalized version, \(\mathbf{x}= {{\widetilde{\mathbf{x}}}}/\Vert {{\widetilde{\mathbf{x}}}} \Vert _1\), of the non-negative solution to the following linear system:To see that these two formulations of the PageRank problem are equivalent, starting from (1) we haveand (2) follows by rearranging the terms and noting \(({\mathbf {1}}^T\mathbf{x}) = 1\). In our work, the random walk interpretation will be used as the basis for a non-backtracking extension.

In the following, for simplicity, we use the original uniform teleporting distribution vector \(\mathbf{v}= \frac{1}{n}{\mathbf {1}}\), so that (1) rewrites asand (2) rewrites asLet us briefly recall here that if we let \(D_A\) be the diagonal matrix whose diagonal entries are \((D_A)_{ii} = (A{\mathbf {1}})_i\) and if we use the symbol \(\dagger \) to denote the Moore–Penrose pseudo-inverse of a matrix [12], then the solution to the linear systemis strictly related to the solution of the PageRank problem, i.e., to the solution of (5). Indeed, let us first recall that, since the matrix \(A^TD_A^\dagger \ge 0\) is column-substochastic, i.e., it is such that \({\mathbf {1}}^TA^TD_A^\dagger \le {\mathbf {1}}^T\), the problem of finding the non-negative solution to the linear system (6) is usually referred to as the pseudo-PageRank problem. Moreover, the following result holds.

This theorem shows that, in order to compute the PageRank vector \(\mathbf{x}\) one can solve the pseudo-PageRank problem and then normalize the solution. Therefore, underlying every pseudo-PageRank system there is a true PageRank problem.

Let us consider the line graph associated with the network represented by W. We will use a calligraphic font to denote matrices associated with the line graph. In the line graph, nodes are edges in the original network G and there is a connection between two edges if the endpoint of the first is the source point of the second. Let \(\mathcal{W}\in {\mathbb {R}}^{m\times m}\) be the adjacency matrix of the line graph, i.e., the matrix whose entries are:where \(\delta _{jk}\) is the Kronecker delta. It is easily proved that \(\mathcal{W}= RL^T\). Let us define the diagonal matrix \(\mathcal{D}\) whose diagonal entries are the entries of the vector \(\mathcal{W}{\mathbf {1}}\). This stores the “out-degree” of each edge in the network, i.e., the number of edges leading out of the current edge. Therefore, an edge \(i\rightarrow j\), has out-degree in the line graph coinciding with the number of edges leaving node j, i.e., the out-degree \(d_{j}\) of node j. We are assuming that the network does not contain dangling nodes, so \(\mathcal{W}{\mathbf {1}}>{\mathbf {0}}\) and \(\mathcal{D}\) is invertible.

Our immediate goal is to define a PageRank vector in the dual space, i.e., the edge space, as the solution of a linear system involving \(\mathcal{W}\) that, once projected, will allow us to retrieve the PageRank vector \(\mathbf{x}\) defined earlier in the primal space. This forms the basis of the non-backtracking version that we develop in Sect. 4.

In this Section we want to exploit the definition of PageRank in the dual space to describe a PageRank-like system in the non-backtracking framework. Recall that a walk is said to be backtracking if it contains at least one instance of \(i\rightarrow j \rightarrow i\), where i, j are two nodes in the network connected by reciprocated edges. Let \(\mathcal{B}\in {\mathbb {R}}^{m\times m}\) be the matrix whose entries areThis matrix has a 1 in position \((i\rightarrow j,k\rightarrow \ell )\) if the two edges are consecutive (i.e., if \(j = k\)) but they do not form a backtracking walk (i.e., if \(i\ne \ell \)). We will refer to this matrix as the non-backtracking edge-matrix or the Hashimoto matrix [11]. If we let \(\circ \) represent the Schur product, i.e., the entry-wise product, between two matrices, then the Hashimoto matrix can be described as \(\mathcal{B}=\mathcal{W}- \mathcal{W}\circ \mathcal{W}^T\). Even though this matrix is built after all dangling nodes have been removed from the network, it is still possible for it to have zero rows. This happens when some of the nodes have no outgoing links, apart from exactly one reciprocated edge. Let us assume that there is one node of this type in the network, node i, connected to node j through a reciprocated edge. If the random walker reaches node i using the edge \(j\rightarrow i\), then it will not be able to leave this node without backtracking; therefore, the row corresponding to the edge \(j\rightarrow i\) only contains zeros. We will refer to edges of this type as dangling edges. Thanks to Theorem 1 we do not need to correct for the presence of these edges in the Hashimoto matrix in order to compute the non-backtracking version of PageRank in the edge space. Indeed, a rescaled solution to the pseudo-PageRank problem formulated with \(\mathcal{B}\) will be the solution to the PageRank problem, where the zero rows in the matrix \(\mathcal{B}\) have been replaced with the vector \({{\varvec{\upsilon }}}^T = (LD^{-1}{\mathbf {1}})^T\). We note that this correction has the effect of allowing backtracking in this very special circumstance.

In the following we will assume that there are no dangling edges in the graph; the remainder of this section can be adapted to the case where such edges existed.

To finalize the description of the transition matrix that will allow us to compute the non-backtracking version of PageRank, we need to describe the teleportation matrix. Here we must make a choice: should we allow backtracking during a teleportation step? In this work we allow such behavior on the basis that the original PageRank philosophy is to make teleportation independent of the network topology. (Further, we note that teleportation in the original PageRank algorithm allows a step of the form \(i \rightarrow i\) even when the graph has no loops, violating the classical definition of a walk. Hence, teleportation can be regarded as a separate process, independent of the underlying random walk.) We also note that backtracking due to teleportation will be an extremely low probability event in large networks, which are the ones of interest in this context. We therefore usewith \({{\varvec{\upsilon }}} = LD^{-1}{\mathbf {1}}\). Recall that \(\Vert {{\varvec{\upsilon }}}\Vert _1 = n\).

We can now define for \(0<\alpha <1\) the matrix \(\mathcal{P}= \alpha \mathcal{D}^{-1}\mathcal{B}+ \frac{(1-\alpha )}{n}{\mathbf {1}}{{\varvec{\upsilon }}}^T \), where now \(\mathcal{D}\) is the diagonal matrix whose diagonal entries are the entries of the vector \(\mathcal{B}{\mathbf {1}}\). Since we assume that there are no dangling edges, \(\mathcal{B}{\mathbf {1}}>0\) and we have that \(\mathcal{P}{\mathbf {1}}= {\mathbf {1}}\); therefore, the PageRank vector in the dual space will be the unit 1-norm, non-negative vector \(\hat{\mathbf{y}}\) that solves the following linear systemIn order to then derive a nodal measure, we need to project \(\hat{\mathbf{y}}\) onto the node space; following Theorem 3, we use the matrix \(L^T\):This vector will be non-negative and will have unit 1-norm, since \(L{\mathbf {1}}= {\mathbf {1}}\) and \(\Vert \hat{\mathbf{y}}\Vert _1 =1\). Therefore, we can define the non-backtracking PageRank-like vector as follows.

Before commenting on the features of this new measure, let us point out that the new PageRank problem (8) is equivalent to the eigenproblemwhere \(\mathcal{P}= \alpha \mathcal{D}^{-1}\mathcal{B}+ \frac{(1-\alpha )}{n}{\mathbf {1}}\varvec{\upsilon }^T\) and \(\Vert \hat{\mathbf{y}}\Vert _1=1\), in line with the equivalent formulations (5) and (4) for standard PageRank.

Definition 1 allows us to introduce the non-backtracking aspect in PageRank. As we will see below, there are situations in which the newly introduced measure and standard PageRank return vectors that are the same or induce the same ranking. However, in applications where backtracking is best avoided, the two measures may differ, as we shall see in Sect. 6.

Let us now briefly discuss the case where the two measures behave similarly. It has been proved in [17] that for an undirected graph with nodes all having at least degree two (so that there are no dangling edges), the steady state of \(P = D^{-1}W\) coincides with that of \(\mathcal{P}= \mathcal{D}^{-1}\mathcal{B}\), once the latter has been projected in the node space via \(L^T\): so standard PageRank and the new non-backtracking PageRank-like measures are the same in the absence of teleportation. In other words, in this case where every edge is reciprocated and no teleportation is allowed, this result tells us that the long-term frequency of visits to a particular node during a random walk does not change when non-backtracking is imposed—the nodes benefit from non-backtracking precisely in proportion to their original PageRank score. Intuitively, nodes given higher PageRank scores are accessible through many different traversals, and hence are less reliant on backtracking walks than nodes given lower PageRank scores. We now show that this result carries over to the case where we allow teleporting, for a special class of graphs.

Before proving the result, let us recall that in the case of undirected networks every undirected edge is considered as a pair of directed edges when building the matrices \(\mathcal{W}\) and \(\mathcal{B}\).

We now show with a small example that without the hypothesis of regularity the two steady states are no longer related in general when \(\alpha \in (0,1)\). For \(\alpha = 0,1\) the conclusion still follows from an easy computation and from [17]. Let us consider the graph represented in Fig. 1, where we have represented each undirected edge as a pair of directed edges pointing in opposite directions. With this ordering of nodes and vertices, the source matrix readsFrom the symmetries in the graph it follows that, when working on the nodes, the entries of the PageRank vector \(\mathbf{x}= (x_i)\) are such that \(x_1 = x_3\) and \(x_2 = x_4\); exploiting those symmetries when working on the edges, it follows that the non-backtracking PageRank-like vector \(\hat{\mathbf{y}} = ({\hat{y}}_i)\) will have \({\hat{y}}_1 = {\hat{y}}_3 = {\hat{y}}_6 = {\hat{y}}_8\), \({\hat{y}}_2={\hat{y}}_4={\hat{y}}_5={\hat{y}}_7\) and \({\hat{y}}_9 = {\hat{y}}_{10}\). Using these relationships, the linear systems of interest may be solved to giveandThe entries of \(\mathbf{y}:= L^T\hat{\mathbf{y}}\) are thenIt is easily verified that \(y_1 = x_1\) and \(y_2 = x_2\) if and only if \(\alpha = 0,1\); hence the result in Theorem 4 does not hold for \(\alpha \in (0,1)\). We stress, however, that the ranking is preserved: nodes 1 and 3 rank first, while 2 and 4 rank second. The next example shows that this is not a universal behavior of the newly introduced measure, as we will also see experimentally in Sect. 6. Let us consider the network with n nodes whose adjacency matrix isIn Fig. 2 we illustrate the case \(n=6\). It can be proved analytically that when there is no teleporting and \(\alpha = 1\), the standard PageRank vector \(\mathbf{x}= (x_i)\) is such that \(x_1=x_2=x_3>x_4= x_5 \cdots = x_n\). This can be also be argued from first principles by considering the long-time frequency with which nodes are visited. After node 4 has been reached, a walk always continues with nodes 5, 6, ..., n, which explains why \(x_4 = x_5 = \cdots = x_n\). A visit to node 1 is equally likely to be followed by a visit to nodes 2 or 3. A visit to node 2 is equally likely to be followed by a visit to nodes 1 or 3. A visit to node 3 is equally likely to be followed by a visit to node 2 or (after passing through \(4,5,\ldots ,n\)) node 1. Hence \(x_1 = x_2 = x_3\), and this value exceeds the other frequencies. On the other hand, the new measure is such that \(y_1=y_3 > y_2=y_4= y_5 = \cdots = y_n\). Here, in the absence of backtracking the same argument explains why \(y_4 = y_5 = \cdots = y_n\). The key difference now is that a visit to nodes 1 or 3 can no longer be followed by a visit to node 2 if node 2 was used on the previous step. So, in the long term, although node 2 receives more visits than nodes \(4,5,\ldots ,n\) it loses out to nodes 1 and 3. Therefore the rankings derived from the two measures are different. The same conclusion holds when we take teleportation into account; in this situation similar arguments show that \(x_1>x_2 = x_3> x_4> \cdots > x_n\) and \(y_1>y_3>y_2>y_4> y_5> \cdots > y_n\).

Before moving on to the numerical tests on real-world networks, we discuss in the next section how to implement the most expensive operation performed by an iterative solver when solving (8): matrix-vector multiplications involving \(\mathcal{B}^T\).

The Hashimoto matrix \(\mathcal{B}\) built from a directed network may be very large, especially if the original graph was large to begin with and contained several dangling nodes. Indeed, to remove such nodes one needs to add n edges to the network for each dangling node. While performing this correction to the graph in the node space corresponds to a low rank modification of the adjacency matrix A, it corresponds to adding n rows and columns to the non-backtracking edge-matrix for each of the dangling nodes originally present in the digraph.

In the following we describe how to label the edges in the network in order to highlight the structure and sparsity of \(\mathcal{B}\) and exploit such features in the computations. The notation adopted will be as follows:We will assume that the non-dangling nodes are labelled as \(\{1,2,\ldots ,n-k\}\) and the remaining k nodes \(\{n-k+1,\ldots ,n\}\) are the dangling nodes. Let us further assume that the \({\widetilde{m}}-K\) edges that do not point to the dangling nodes in the graph are labelled as \(\{1,2,\ldots ,{\widetilde{m}}-K\}\) so that the remaining K edges \(\{{\widetilde{m}}-K+1,\ldots ,{\widetilde{m}}\}\) are those pointing to the dangling nodes. With this labelling, the matrix A will have the following structure:where \(A_{11}\in {\mathbb {R}}^{(n-k)\times (n-k)}\) is the adjacency matrix of the graph obtained by removing the dangling nodes and the edges pointing to them and \(A_{12}\in {\mathbb {R}}^{(n-k)\times k}\) describes the edges pointing to the dangling nodes from the non-dangling nodes in the network. We then have that the source and target matrices of A, that we will denote by L(A) and R(A), respectively, have the following structure:andwhere \(L_1,\ R_1\in {\mathbb {R}}^{({\widetilde{m}}-K)\times (n-k)}\), \(L_2\in {\mathbb {R}}^{K\times (n-k)}\), and \(R_2\in {\mathbb {R}}^{K\times k}\).

After the correction of the dangling nodes, the adjacency matrix associated with the new graph G will be \(W = A + \varvec{\chi }{\mathbf {1}}^T\) with \( \varvec{\chi } = \sum _{i=n-k+1}^n \mathbf{e}_i\), where \(\mathbf{e}_i \in {\mathbb {R}}^n\) is the \(i\hbox {th}\) vector of the standard basis of \({\mathbb {R}}^n\). The source and target matrices associated with W arewhereWith this ordering of the nodes and edges, the edge matrix \(\mathcal{W}= RL^T\) has the formand thus the matrix \(\mathcal{B}^T\) involved in the computations iswhere the matrices \(S_1,S_2,S_4\), which effect the removal of \(\mathcal{W}\circ \mathcal{W}^T\) from \(\mathcal{W}= \mathcal{B}+ \mathcal{W}\circ \mathcal{W}^T\), have the formWe note that \(S_1\) and \(S_4\) are square and symmetric, whilst \(S_2\) is rectangular, in general. All three matrices contain at most one element equal to one in each row. We show below that, because they are highly structured, we do not need to explicitly form the matrices \(S_2\) and \(S_4\) in order to compute their action on a vector.

Let us describe the matrices \(S_2\in {\mathbb {R}}^{K\times k(n-k)}\) and \(S_4\in {\mathbb {R}}^{k^2\times k^2}\) in more detail. From the structure of \((L_2\otimes {\mathbf {1}}_k^T)\) and \(({\mathbf {1}}_{n-k}^T\otimes R_2)\) it can be deduced that the ones in the matrix \(S_2\) are found in position \((e,(i-1)k+j)\), where \(e\in \{{\widetilde{m}}-K+1,\ldots , {\widetilde{m}}\}\) is the label of the edge \(i\rightarrow n-k+j\) that points from a certain node \(i\in \{1,2,\ldots ,n-k\}\) to a dangling node \((n-k+j)\) for \(j\in \{1,2,\ldots ,k\}\). Similarly, the matrix \(S_4 = ({\mathbf {1}}_k^T\otimes I_k\otimes {\mathbf {1}}_k)\circ ({\mathbf {1}}_k\otimes I_k\otimes {\mathbf {1}}_k^T)\) has a one in position \(((i-1)k+j,(j-1)k+i)\) for all \(i,j=1,2,\ldots ,k\). Therefore, pre-multiplying a vector by these matrices corresponds to accessing certain entries of the vector.

In order to compute the non-backtracking PageRank vector, we can either solve a sparse linear system or use the power method to obtain the non-trivial eigenvector associated with the eigenvalue 1. In either case, we need to implement a matrix-vector product involving \(\mathcal{B}^T\) and a rescaled vector \(\mathbf{v}:=\mathcal{D}^{\dagger }{\overline{\mathbf{v}}}\). The rescaling can be performed at each iteration once the column sums of \(\mathcal{B}^T\) have been computed. Recall that we do not need to remove zero rows from \(\mathcal{B}\), equivalently, columns from \(\mathcal{B}^T\), as it is well known that the solution to the pseudo-PageRank problem (solve while retaining the zero columns in \(\mathcal{B}^T\)) only differs from the solution to the PageRank problem (solve after “correcting” the zero columns) by a positive multiplicative constant; see Theorem 1. Let \(\mathbf{v}=\mathcal{D}^\dagger {\overline{\mathbf{v}}} = [\mathbf{q}^T, \mathbf{r}^T,\mathbf{s}^T,\mathbf{t}^T]^T\ge {\mathbf {0}}\) be a non-zero vector with \(\mathbf{q}\in {\mathbb {R}}^{{\widetilde{m}}-K}\), \(\mathbf{r}\in {\mathbb {R}}^{K}\), \(\mathbf{s}\in {\mathbb {R}}^{k(n-k)}\), and \(\mathbf{t}\in {\mathbb {R}}^{k^2}\). Then, at each step, we computewhere \(({\widehat{\mathbf{s}}})_i = \sum _{j=1}^k s_{(i-1)k+j}\) and \(({\widehat{\mathbf{t}}})_i = \sum _{j=1}^k t_{(i-1)k+k}\).

We now present numerical results to compare the performance of non-backtracking PageRank in Definition 1 with standard PageRank. We perform our tests on four road networks corresponding to the cities of Birmingham (UK), Philadelphia (USA), Austin (USA), and the Federal State of Hesse (Germany). The data is available in [32]. Here, the edges represent roads and nodes represent road intersections (primal graph).

We computed both the new measure and standard PageRank as the solution of a linear system; see equations (5) and (8). For both problems we used the MATLAB implementation of the linear solver GMRES without restart and we gave as input a function handle that describes the matrix multiplication \(\mathcal{B}^T(\mathcal{D}^{-1}\mathbf{v})\) and \(W^T(D^{-1}\mathbf{v})\) for vectors \(\mathbf{v}\) of appropriate size. Both these functions were implemented exploiting the structure of the matrices \(\mathcal{B}\) (see Sect. 5) and \(W = A + {\varvec{\chi }}{\mathbf {1}}^T\).

We used the default setting of \({10}^{-6}\) for the tolerance in the stopping criterion and allowed for a maximum of 100 iterations. We select \(\alpha = 0.75\) for the teleporting parameter. Properties of the networks used in the tests are summarized in Table 1, where we report the number of nodes, n, the number of dangling nodes, k, the number of source nodes, \(s = n-N\), the number, \({\widetilde{m}}\), of edges in the network represented by A, and the number, K, of edges pointing to the dangling nodes. Moreover, we report the number, M, of dangling edges in the network and the fraction of edges in the graph that have a reciprocal: \(\delta := \frac{{\mathbf {1}}^T(A\circ A^T) {\mathbf {1}}}{{\widetilde{m}}}\). So, for example, the value \(\delta = 0.19\) for the Federal State of Hesse indicates that 81% of the road connections are one-way only. All experiments were performed using MATLAB Version 9.4.0.813654 (R2018a) on an HP EliteDesk running Scientific Linux 7.5 (Nitrogen), a 3.2 GHz Intel Core i7 processor, and 4 GB of RAM.

In Fig. 3 we scatter plot the new measure (NBT PR edge), projected as in (9), against standard PageRank (PR node). The measures show a strong overall linear correlation; the Pearson’s correlation coefficients are \(\rho = 0.94\) for the Federal State of Hesse, \(\rho = 0.90\) for both Austin and Philadelphia, and \(\rho = 0.81\) for Birmingham. However, it is readily seen that the two measures do not completely agree on the rankings. Indeed, the intersection of the sets containing the IDs of the top ten ranked nodes according to the two measures for Birmingham, the Federal State of Hesse, Austin and Philadelphia contain 8, 3, 5 and 6 elements, respectively. It is beyond the scope of this paper to determine which measure is returning the most meaningful results, since there is no ground truth for comparison. However, it may be argued that the non-backtracking version of the measure is the best fit for road networks since, as we mentioned in the introduction, the concept of non-backtracking walks is consistent with the typical behavior of a driver or a pedestrian traversing a city. It is notable that for all four scatter plots the low-ranked nodes are assigned the same score by non-backtracking PageRank, whilst they are being assigned different values by the classic version of the algorithm. A further analysis of the data showed that exactly \(M+s\) nodes fall in this class; these are the s source nodes and the M reciprocated leaves (i.e., nodes that have only one incoming link that is the reciprocal of their only outgoing edge) in the original graph associated with A.

We now turn to computation time and the number of iterations required to achieve convergence of GMRES. Table 2 shows the results. We see that standard PageRank requires slightly fewer iterations than its non-backtracking counterpart. However, the total computation time for non-backtracking PageRank, including pre-processing time to build the matrices \(L_1\), \(R_1\), \(S_1\), \(L_2\) and \(R_2\), is significantly smaller than for standard PageRank. We attribute this surprising result to the fact that the sparsity and structure of the matrix \(\mathcal{B}\) can be exploited by the iterative solver.

Finally, in Fig. 4 we display the evolution of the computation time required to achieve convergence of GMRES for the two algorithms as we let the teleportation parameter \(\alpha \) vary, as well as the evolution of the Pearson’s correlation coefficient between the two vectors for the city of Birmingham. Here we let \(\alpha = 0.1, 0.25, 0.3, 0.5, 0.75, 0.85, 0.99\). Table 3 reports the number of iterations required to achieve convergence. Similar results were obtained for the other networks and are therefore omitted. We see from the upper plot of Fig. 4 that the newly introduced measure is computed more quickly than the measure we are comparing with, while Table 3 shows that the number of iterations required by GMRES to achieve convergence is comparable. Note that when \(\alpha = 0.99\), in both cases GMRES iterated the maximum allowed number of times without achieving convergence. This follows from the fact that both systems become ill-conditioned as \(\alpha \rightarrow 1\). The lower plot of Fig. 4 shows that the correlation between the two measures decreases as the value of \(\alpha \) increases. This may be explained by the fact that reducing the frequency of teleporting emphasizes the difference between the two underlying types of walk.

In summary, for the networks studied here, using the ideas from Sects. 4 and 5 we can incorporate non-backtracking into PageRank in order to obtain a distinct node ranking at reduced computational cost.