Efficient Computation of PageRank

Abstract This paper discusses efficient techniques for computing PageRank, a ranking met-ric 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 machineswith limited main memory. Running-time measurements on various memory configurations are presented for PageRank computation over the 24-million-pageStanford WebBase archive. We discuss several methods for analyzing the convergence of PageRank based on the induced ordering of the pages. We presentconvergence results helpful for determining the number of iterations necessary to achieve a useful PageRank assignment, both in the absence and presence ofsearch queries.