A Reordering For The PageRank Problem
 ABSTRACT

We describe a reordering particularly suited to the PageRank problem,
which reduces the computation of the PageRank vector to that of
solving a much smaller system, then using forward substitution to get
the full solution vector. We compare the theoretical rates of convergence of the
original PageRank algorithm to that of the new reordered PageRank algorithm,
showing that the new algorithm can do no worse than the original algorithm. We
present results of an experimental comparison on five datasets, which demonstrate
that the reordered PageRank algorithm can provide a speedup as much as a factor of
8. We also note potential additional benefits that result from the proposed
reordering.
 JOURNAL
 SISC (SIAM J. Scientific and Statistical Computing)
 Vol 27, No, 6, 2006, pp. 21122120
 COAUTHORS
 Amy N. Langville
 Carl D. Meyer
 THE PDF FILE
 The pdf file for the entire paper is 1.1MB.
 To receive the PDF file, click on
ReorderingPageRank.pdf
Return To Meyer's Home Page
Return To Abstracts