收稿日期: 2016-10-13
网络出版日期: 2017-08-30
基金资助
国家自然科学基金资助项目(11371243); 上海市重点学科建设资助项目(S30104); 中国电子科技集团公司第三十研究所委托项目
Arnoldi-PIO algorithm for PageRank
Received date: 2016-10-13
Online published: 2017-08-30
PageRank 算法能帮助用户快速、准确地在巨量杂乱无章的信息中检索出有用的信息. 两步分裂迭代法是用幂法来修正内外分裂(power-inner-outer, PIO)迭代法以加速PageRank算法. 基于两步分裂迭代法, 将预处理思想运用于求解PageRank 问题, 提出了求解Page-Rank 问题的深度重启的Arnoldi 算法加速的两步分裂迭代法, 然后对此算法的收敛性进行了证明. 数值实验结果证明, 该算法的计算速度要快于两步分裂迭代法.
关键词： 两步分裂迭代法; 深度重启的Arnoldi 算法; 内外迭代法
顾传青1, 聂影1, 王金波2 . 求解PageRank 问题的Arnoldi-PIO 算法[J]. 上海大学学报(自然科学版), 2017 , 23(4) : 555 -562 . DOI: 10.12066/j.issn.1007-2861.1867
The PageRank algorithm plays an important role in determining the importance of Web pages. The power-inner-outer (PIO) method is a two-step splitting iteration framework that combines the inner-outer scheme with the classical power method to accelerate the computation of PageRank algorithm. This paper proposes an Arnoldi-PIO algorithm, which is a PIO iteration algorithm modified with the thick restarted Arnoldi method. Description and convergence of the proposed algorithm are discussed in details. Numerical results show efficiency and convergence behaviors of the algorithm.
[1] Page L, Brin S, Motwani R, et al. The PageRank citation ranking: bring order to the web [R/OL]. (2001-10-30)[2014-06-20]. http://ilpubs.stanford.edu:8090/422/1/1999-66.pdf.
[2] Gleich D, Gray A, Greif C, et al. An inner-outer iteration method for computing PageRank [J]. SIAM J Sci Compute, 2010, 32(1): 349-371.
[3] Gu C Q, Xie F, Zhang K. A two-step splitting iteration for computing PageRank [J]. Journal of Computational and Applied Mathematics, 2015, 278: 19-28.
[4] Wu G, Wei Y M. A Power-Arnoldi algorithm for compuring PageRank [J]. Numer Linear Algebra Appl, 2007, 14: 521-546.
[5] Wu K, Simon H. Thick-restart Lanczos method for large symmetric eigenvalue problems [J]. SIAM Journal on Matrix Analysis and Applications, 2000, 22: 602-616.
[6] Morgan R. A harmonic restarted Arnoldi algorithm for calculating eigenvalues and determing multiplicity [J]. Linear Algebra and Its Applications, 2006, 415: 96-113.
[7] Sorensen D. Implicit application of polynomial filters in a k-step Arnoldi method [J]. SIAM Journal on Matrix Analysis and Applications, 1992, 13: 357-385.
/
| 〈 |
|
〉 |
