loading page

A weighted Arnoldi-Extrapolation algorithm for computing PageRank
  • Qian-Ying Hu,
  • Chun Wen,
  • Bing-Yuan Pu
Qian-Ying Hu
University of Electronic Science and Technology of China
Author Profile
Chun Wen
University of Electronic Science and Technology of China
Author Profile
Bing-Yuan Pu
Chengdu Textile College
Author Profile

Abstract

The power method with the extrapolation process based on trace (PET) method was proposed by Tan (2017). It is an extrapolation strategy derived from the Google matrix. Considering the weighted inner product, a generalized Arnoldi (GArnoldi) method was constructed by Yin et al. (2012) for computing PageRank. In this paper, we present a new algorithm by employing the extrapolation strategy and the GArnoldi method together. In order to accelerate the convergence speed of PageRank computations, the weights are changed adaptively with the current residual corresponding to the approximate vector in each cycle. The new method is called as GArnoldi-PET algorithm, whose implementation and convergence are analyzed in detail. Numerical experiments on several examples are used to illustrate the effectiveness of our proposed algorithm.