Gray, Andrew P. ;
Greif, Chen ;
Lau, Tracy
An Inner/Outer Stationary Iteration for Computing PageRank
Abstract
We present a stationary iterative scheme for PageRank computation. The algorithm is based on a linear system formulation of the problem, uses inner/outer iterations, and amounts to a simple preconditioning technique. It is simple, can be easily implemented and parallelized, and requires minimal storage overhead. Convergence analysis shows that the algorithm is effective for a crude inner tolerance and is not particularly sensitive to the choice of the parameters involved. Numerical examples featuring matrices of dimensions up to approximately $10^7$ confirm the analytical results and demonstrate the accelerated convergence of the algorithm compared to the power method.
BibTeX - Entry
@InProceedings{gray_et_al:DagSemProc.07071.5,
author = {Gray, Andrew P. and Greif, Chen and Lau, Tracy},
title = {{An Inner/Outer Stationary Iteration for Computing PageRank}},
booktitle = {Web Information Retrieval and Linear Algebra Algorithms},
pages = {1--8},
series = {Dagstuhl Seminar Proceedings (DagSemProc)},
ISSN = {1862-4405},
year = {2007},
volume = {7071},
editor = {Andreas Frommer and Michael W. Mahoney and Daniel B. Szyld},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2007/1062},
URN = {urn:nbn:de:0030-drops-10628},
doi = {10.4230/DagSemProc.07071.5},
annote = {Keywords: PageRank, power method, stationary method, inner/outer iterations, damping factor}
}
|
Keywords: |
|
PageRank, power method, stationary method, inner/outer iterations, damping factor |
|
Seminar: |
|
07071 - Web Information Retrieval and Linear Algebra Algorithms
|
|
Issue date: |
|
2007 |
|
Date of publication: |
|
28.06.2007 |
28.06.2007
