An Aitken-extrapolated Gauss-Seidel method for computing PageRank

Abstract

Power method is one of the basic iterative method used by Brin and Page to compute the PageRank vector. However, this method may not be efficient when the hyperlink matrix becomes large or damping factor value closes to 1. In last few years, Researchers have considered several numerical methods like Gauss-Seidel, Monte-Carlo, and Arnoldi extrapolation to accelerate the convergence of PageRank computation. In this paper, we have proposed a novel iterative method to compute the PageRank vector of hyperlink matrix by using Aitken extrapolation algorithm. Also, we have analyzed convergence behavior of proposed algorithm i.e. Aitken-extrapolation Gauss Seidel. Further, we have compared Aitken-extrapolation Gauss Seidel algorithm to existing methods such as Power method, Aitken-Power, and Gauss-Seidel method experimentally and found that our method is more feasible and efficient as compared to these existing approaches.

Keywords:

• PageRank
• Eigenvalues and Eigen-functions
• Markov processes
• Extrapolation
• Perron-Frobenius
• Iterative methods

Subject Classification:

• 68U35
• 65F10