Paper Info
Title
A heuristic search algorithm based on subspaces for PageRank computation
Abstract
We studied a fast algorithm for the large-scale computation of PageRank. PageRank is what the Google search engine uses to simulate the importance of web pages. It is defined by the eigenvector of a particular stochastic matrix related to the graphs of web pages. The power method is the typical means to compute the eigenvector, while the Krylov subspace method shows faster convergence, which can be regarded as a two-step algorithm. The first step predicts the eigenvector, and the second step corrects the predicted result. More precisely, the power method is first iterated to compute the eigenvector approximately. Secondly, a Krylov subspace spanned by the approximations is searched for a better approximate eigenvector in terms of minimizing a residual. To get a better approximation efficiently, we consider using subspaces not only at the second step but also at the first step. Specifically, a Krylov subspace is first used to compute an approximate eigenvector, by which another subspace is expanded. Secondly, this non-Krylov subspace is searched for a better approximate eigenvector that minimizes its residual over the subspace. This paper describes a heuristic search algorithm iterating the two steps alternately and presents its efficient implementation. Experimental results with huge Google matrices illustrate improvements in performance of the algorithm.
Year
DOI
Venue
2018
https://doi.org/10.1007/s11227-018-2383-9
The Journal of Supercomputing
Keywords
Field
DocType
PageRank,Google matrix,Power iteration,Krylov subspace,Residual minimization,Parallel computing
Krylov subspace,PageRank,Stochastic matrix,Subspace topology,Computer science,Parallel computing,Algorithm,Linear subspace,Google matrix,Eigenvalues and eigenvectors,Power iteration
Journal
Volume
Issue
ISSN
74
7
0920-8542
Citations 
PageRank 
References 
0
0.34
4
Authors
1
Name
Order
Citations
PageRank
Takafumi Miyata111.39