Non-backtracking PageRank

Tutkimustuotos: Lehtiartikkelivertaisarvioitu

Tutkijat

Organisaatiot

  • University of Strathclyde
  • University of Edinburgh

Kuvaus

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.

Yksityiskohdat

AlkuperäiskieliEnglanti
Sivut1419-1437
Sivumäärä19
JulkaisuJOURNAL OF SCIENTIFIC COMPUTING
Vuosikerta80
Numero3
TilaJulkaistu - 15 syyskuuta 2019
OKM-julkaisutyyppiA1 Julkaistu artikkeli, soviteltu

Lataa tilasto

Ei tietoja saatavilla

ID: 36784596