Efficient Computation of PageRank
Taher H. Haveliwala (taherh@db.stanford.edu)

Abstract:
This paper discusses efficient techniques for computing PageRank, a 
ranking metric for hypertext documents.  We show that
PageRank can be computed for very large subgraphs of the web (up
to hundreds of millions of nodes) on machines with limited main
memory.  Running-time measurements on various memory configurations
are presented for PageRank computation over the 24-million-page
Stanford WebBase archive.  We discuss several methods for analyzing the
convergence of PageRank based on the induced ordering of the pages.  We
present convergence results helpful for determining the number of iterations 
necessary to achieve a useful PageRank assignment, both in the absence
and presence of search queries.