A Reordering for the PageRank Problem
Authors:
- Amy N. LangvilleALAmy N. Langville
- Carl D. MeyerCMCarl D. Meyer
- 1 January 2006
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Scientific Computing
- Vol. 27 (6) , 2112-2120
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 and 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 of as much as a factor of 6. We also note potential additional benefits that result from the proposed reordering.Keywords
This publication has 6 references indexed in Scilit:
- Ranking the web frontier2004
- Deeper Inside PageRankInternet Mathematics, 2004
- Extrapolation methods for accelerating PageRank computations2003
- Matrix Analysis and Applied Linear Algebra2000
- Authoritative sources in a hyperlinked environmentJournal of the ACM, 1999
- The anatomy of a large-scale hypertextual Web search engineComputer Networks and ISDN Systems, 1998