A heuristic search algorithm based on subspaces for PageRank computation
A heuristic search algorithm based on subspaces for PageRank computation
复制标题
DOI：
10.1007/s11227-018-2383-9
复制
发表时间：
2018-07
期刊：
影响因子：
--
通讯作者：
T. Miyata
中科院分区：
文献类型：
--
作者：
T. Miyata
研究了一种用于大规模PageRank计算的快速算法。PageRank是谷歌搜索引擎用来模拟网页重要性的东西。它由与网页图相关的特定随机矩阵的特征向量定义。幂方法是计算特征向量的典型方法，而Krylov子空间方法具有较快的收敛速度，可以看作是一种两步算法。第一步对特征向量进行预测，第二步对预测结果进行修正。更准确地说，首先迭代幂方法来近似计算特征向量。其次，从最小化残差的角度出发，在Krylov子空间中搜索近似的特征向量。为了更有效地获得更好的逼近，我们不仅在第二步考虑使用子空间，而且在第一步也考虑使用子空间。具体地说，首先使用Krylov子空间来计算近似特征向量，通过该近似特征向量来扩展另一个子空间。其次，搜索这个非Krylov子空间，以寻找一个更好的近似特征向量，使其在子空间上的残差最小。本文描述了一种交替迭代这两步的启发式搜索算法，并给出了它的有效实现。用庞大的Google矩阵进行的实验结果表明，该算法在性能上有了改进。
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.