Non-backtracking PageRank

Francesca Arrigo, Desmond J. Higham, Vanni Noferini

Research output: Contribution to journalArticle

Abstract

The PageRank algorithm, which has been “bringing order to the web” for more than 20 years, computes the steady state of a classical random walk plus teleporting. Here we consider a variation of PageRank that uses a non-backtracking random walk. To do this, we first reformulate PageRank in terms of the associated line graph. A non-backtracking analog then emerges naturally. Comparing the resulting steady states, we find that, even for undirected graphs, non-backtracking generally leads to a different ranking of the nodes. We then focus on computational issues, deriving an explicit representation of the new algorithm that can exploit structure and sparsity in the underlying network. Finally, we assess effectiveness and efficiency of this approach on some real-world networks.

LanguageEnglish
Pages1419-1437
Number of pages19
JournalJournal of Scientific Computing
Volume80
Issue number3
Early online date1 Jun 2019
DOIs
Publication statusPublished - 15 Sep 2019

Fingerprint

PageRank
Random walk
Line Graph
Sparsity
Undirected Graph
Ranking
Analogue
Vertex of a graph

Keywords

  • PageRank
  • non-backtracking
  • complex networks
  • centrality

Cite this

Arrigo, Francesca ; Higham, Desmond J. ; Noferini, Vanni. / Non-backtracking PageRank. In: Journal of Scientific Computing. 2019 ; Vol. 80, No. 3. pp. 1419-1437.
@article{17b2a19a87bf4e14b272e1bf5e30d2b2,
title = "Non-backtracking PageRank",
abstract = "The PageRank algorithm, which has been “bringing order to the web” for more than 20 years, computes the steady state of a classical random walk plus teleporting. Here we consider a variation of PageRank that uses a non-backtracking random walk. To do this, we first reformulate PageRank in terms of the associated line graph. A non-backtracking analog then emerges naturally. Comparing the resulting steady states, we find that, even for undirected graphs, non-backtracking generally leads to a different ranking of the nodes. We then focus on computational issues, deriving an explicit representation of the new algorithm that can exploit structure and sparsity in the underlying network. Finally, we assess effectiveness and efficiency of this approach on some real-world networks.",
keywords = "PageRank, non-backtracking, complex networks, centrality",
author = "Francesca Arrigo and Higham, {Desmond J.} and Vanni Noferini",
year = "2019",
month = "9",
day = "15",
doi = "10.1007/s10915-019-00981-8",
language = "English",
volume = "80",
pages = "1419--1437",
journal = "Journal of Scientific Computing",
issn = "0885-7474",
number = "3",

}

Non-backtracking PageRank. / Arrigo, Francesca; Higham, Desmond J.; Noferini, Vanni.

In: Journal of Scientific Computing, Vol. 80, No. 3, 15.09.2019, p. 1419-1437.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Non-backtracking PageRank

AU - Arrigo, Francesca

AU - Higham, Desmond J.

AU - Noferini, Vanni

PY - 2019/9/15

Y1 - 2019/9/15

N2 - The PageRank algorithm, which has been “bringing order to the web” for more than 20 years, computes the steady state of a classical random walk plus teleporting. Here we consider a variation of PageRank that uses a non-backtracking random walk. To do this, we first reformulate PageRank in terms of the associated line graph. A non-backtracking analog then emerges naturally. Comparing the resulting steady states, we find that, even for undirected graphs, non-backtracking generally leads to a different ranking of the nodes. We then focus on computational issues, deriving an explicit representation of the new algorithm that can exploit structure and sparsity in the underlying network. Finally, we assess effectiveness and efficiency of this approach on some real-world networks.

AB - The PageRank algorithm, which has been “bringing order to the web” for more than 20 years, computes the steady state of a classical random walk plus teleporting. Here we consider a variation of PageRank that uses a non-backtracking random walk. To do this, we first reformulate PageRank in terms of the associated line graph. A non-backtracking analog then emerges naturally. Comparing the resulting steady states, we find that, even for undirected graphs, non-backtracking generally leads to a different ranking of the nodes. We then focus on computational issues, deriving an explicit representation of the new algorithm that can exploit structure and sparsity in the underlying network. Finally, we assess effectiveness and efficiency of this approach on some real-world networks.

KW - PageRank

KW - non-backtracking

KW - complex networks

KW - centrality

UR - https://link.springer.com/journal/volumesAndIssues/10915

U2 - 10.1007/s10915-019-00981-8

DO - 10.1007/s10915-019-00981-8

M3 - Article

VL - 80

SP - 1419

EP - 1437

JO - Journal of Scientific Computing

T2 - Journal of Scientific Computing

JF - Journal of Scientific Computing

SN - 0885-7474

IS - 3

ER -