An Inner-Outer Iteration for Computing PageRank
An Inner-Outer Iteration for Computing PageRank
复制标题
DOI：
10.1137/080727397
复制
发表时间：
2010-02
期刊：
影响因子：
--
通讯作者：
D. Gleich;Andrew P. Gray;C. Greif;Tracy Lau
中科院分区：
文献类型：
--
作者：
D. Gleich;Andrew P. Gray;C. Greif;Tracy Lau
我们提出了一种新的迭代PageRank计算方案。该算法适用于线性系统制定的问题，使用内部外固定迭代。它很简单，可以很容易地实现和并行化，并需要最小的存储开销。我们的收敛性分析表明，该算法是有效的一个粗糙的内公差，是不敏感的参数的选择。同样的思想也可以作为非平稳格式的预处理技术。在顺序和并行环境中，具有超过100，000，000维矩阵的数值例子证明了我们的技术的优点。我们的代码可以在线查看和测试，沿着几个大型示例。
We present a new iterative scheme for PageRank computation. The algorithm is applied to the linear system formulation of the problem, using inner-outer stationary iterations. It is simple, can be easily implemented and parallelized, and requires minimal storage overhead. Our convergence analysis shows that the algorithm is effective for a crude inner tolerance and is not sensitive to the choice of the parameters involved. The same idea can be used as a preconditioning technique for nonstationary schemes. Numerical examples featuring matrices of dimensions exceeding 100,000,000 in sequential and parallel environments demonstrate the merits of our technique. Our code is available online for viewing and testing, along with several large scale examples.