Supporting programs

Our experimental code is online, see the innout package.

Abstract

We present a new iterative scheme for PageRank computation. The algorithm is
applied to the linear system formulation of the problem, using inner-outer stationary iterations. It is simple, can be easily implemented and parallelized, and requires minimal storage overhead. Our convergence analysis shows that the algorithm is effective for a crude inner tolerance and is not sensitive to the choice of the parameters involved. The same idea can be used as a preconditioning technique for non-stationary schemes. Numerical examples featuring matrices of dimensions exceeding 100,000,000 in sequential and parallel environments demonstrate the merits of our technique. Our code is available online for viewing and testing, along with several large scale examples

Available

Accepted draft
Personal site
An inner-outer algorithm for PageRank

Bibtex

@ARTICLE{gleich2010-inner-outer,
  author = {David F. Gleich and Andrew P. Gray and Chen Greif and Tracy Laure},
  title = {An inner-outer iteration for PageRank},
  journal = {SIAM Journal of Scientific Computing},
  year = {to appear},
  keywords = {self},
  owner = {David F. Gleich},
  timestamp = {2009.07.10}
}