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. 2112-2120
- CO-AUTHORS
- 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