Application of an extrapolation method in the Hessenberg algorithm for computing PageRank

PageRank can be viewed as a hyperlink-based method for estimating the importance of nodes in a network, and has attracted a lot of attention from researchers. In this paper, we first propose an extrapolation procedure for PageRank vector estimation based on the linear combination of the Ritz values computed from the Hessenberg process and eigenvectors from the classical power method. In order to improve the convergence rate of the PageRank computations, the extrapolation procedure is introduced into the Hessenberg-type algorithm by Gu et al. (Numer. Algorithms, 89(4): 1845–1863, 2022), then a new algorithm is derived and named Hessenberg-extrapolation algorithm whose convergence and construction are investigated in detail. In addition, we further analyze the convergence of the Hessenberg-type algorithm and discuss the relationship between the approximate vectors of the Hessenberg-type algorithm and the Arnoldi-type algorithm. Numerical experiments on several examples demonstrate that our presented algorithm has great potential in PageRank approximation.