A Hessenberg-type algorithm for computing PageRank Problems

Xian Ming Gu, Siu Long Lei*, Ke Zhang, Zhao Li Shen, Chun Wen, Bruno Carpentieri

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

3 Citations (Scopus)
13 Downloads (Pure)

Abstract

PageRank is a widespread model for analysing the relative relevance of nodes within large graphs arising in several applications. In the current paper, we present a cost-effective Hessenberg-type method built upon the Hessenberg process for the solution of difficult PageRank problems. The new method is very competitive with other popular algorithms in this field, such as Arnoldi-type methods, especially when the damping factor is close to 1 and the dimension of the search subspace is large. The convergence and the complexity of the proposed algorithm are investigated. Numerical experiments are reported to show the efficiency of the new solver for practical PageRank computations.

Original languageEnglish
Pages (from-to)1845-1863
Number of pages19
JournalNumerical algorithms
Volume89
Issue number4
DOIs
Publication statusPublished - Apr-2022

Keywords

  • Arnoldi process
  • Hessenberg process
  • Krylov subspace method
  • PageRank vector
  • Ritz values

Cite this