DagSemProc.07071.5.pdf
- Filesize: 123 kB
- 8 pages
Document
An Inner/Outer Stationary Iteration for Computing PageRank
Authors
-
Part of:
Volume:
Dagstuhl Seminar Proceedings, Volume 7071
Series: Dagstuhl Seminar Proceedings (DagSemProc) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2007-06-28
Cite AsGet BibTex
Andrew P. Gray, Chen Greif, and Tracy Lau. An Inner/Outer Stationary Iteration for Computing PageRank. In Web Information Retrieval and Linear Algebra Algorithms. Dagstuhl Seminar Proceedings, Volume 7071, pp. 1-8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)
https://doi.org/10.4230/DagSemProc.07071.5
https://doi.org/10.4230/DagSemProc.07071.5
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.
Keywords
- PageRank
- power method
- stationary method
- inner/outer iterations
- damping factor
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads