An Inner/Outer Stationary Iteration for Computing PageRank

Gray, Andrew P.; Greif, Chen; Lau, Tracy

doi:10.4230/DagSemProc.07071.5

Document

An Inner/Outer Stationary Iteration for Computing PageRank

Authors Andrew P. Gray, Chen Greif, Tracy Lau

Part of: Volume: Dagstuhl Seminar Proceedings, Volume 7071
Part of: Series: Dagstuhl Seminar Proceedings (DagSemProc)
License: Creative Commons Attribution 4.0 International license
Publication Date: 2007-06-28

PDF

File

PDF

DagSemProc.07071.5.pdf

Filesize: 123 kB
8 pages

Document Identifiers

DOI: 10.4230/DagSemProc.07071.5
URN: urn:nbn:de:0030-drops-10628

Subject Classification

Keywords

PageRank
power method
stationary method
inner/outer iterations
damping factor

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

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.

Cite As Get 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

Author Details

Andrew P. Gray

Chen Greif

Tracy Lau

Questions / Remarks / Feedback

Feedback for Dagstuhl Publishing

Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail