An Inner/Outer Stationary Iteration for Computing PageRank

Andrew P. Gray, Chen Greif and Tracy Lau
Publishing date
December 20, 2007
12 pages
We present a stationary iterative scheme for PageRank computation. The algorithm is based on a linear system formulation of the problem, uses inner/outer iterations, and amounts to a simple preconditioning technique. It is simple, can be easily implemented and parallelized, and requires minimal storage overhead. Convergence analysis shows that the algorithm is effective for a crude inner tolerance and is not particularly sensitive to the choice of the parameters involved. Numerical examples featuring matrices of dimensions up to approximately 10⁷ confirm the analytical results and demonstrate the accelerated convergence of the algorithm compared to the power method.