求解PageRank问题的GMRES-Inout方法

doi:10.3969/j.issn.1007-2861.2016.07.010

上海大学学报(自然科学版) ›› 2017, Vol. 23 ›› Issue (2): 179-184.doi: 10.3969/j.issn.1007-2861.2016.07.010

求解PageRank问题的GMRES-Inout方法

顾传青, 邵晨晨

上海大学理学院, 上海 200444

收稿日期:2016-12-24 出版日期:2017-04-30 发布日期:2017-04-30
通讯作者: 顾传青(1955—), 男, 教授, 博士生导师, 博士, 研究方向为数值逼近、数值代数及其应用. E-mail: cqgu@staff.shu.edu.cn
作者简介:顾传青(1955—), 男, 教授, 博士生导师, 博士, 研究方向为数值逼近、数值代数及其应用. E-mail: cqgu@staff.shu.edu.cn
基金资助:
国家自然科学基金资助项目(11371243); 上海市教委科研创新资助项目(13ZZ068); 上海市重点学科建设资助项目(S30104)

A GMRES-Inout algorithm for computing PageRank problems

GU Chuanqing, SHAO Chenchen

College of Sciences, Shanghai University, Shanghai 200444, China

Received:2016-12-24 Online:2017-04-30 Published:2017-04-30

摘要/Abstract

摘要：

PageRank算法已经成为网络搜索中的核心技术. 首先基于内外迭代法, 运用预处理的思想, 提出GMRES-Inout方法, 即重启的GMRES方法修正的内外迭代法; 然后,详细介绍该方法的具体过程及收敛性分析; 最后, 通过数值实验说明该方法的有效性.

关键词: 收敛性, GMRES方法, 内外迭代法, PageRank

Abstract:

The PageRank algorithm for determining the importance of Web pages has become a central technique in Web search. Based on the inout method, a GMRESInout algorithm which modifying the inner-outer method preconditioned with the restarted GMRES algorithm is proposed. Description and convergence analysis of the proposed algorithm are given. Numerical results are reported to demonstrate the efficiency of the proposed algorithm.

Key words: convergence, GMRES algorithm , inner-outer iteration , PageRank

顾传青, 邵晨晨. 求解PageRank问题的GMRES-Inout方法[J]. 上海大学学报(自然科学版), 2017, 23(2): 179-184.

GU Chuanqing, SHAO Chenchen. A GMRES-Inout algorithm for computing PageRank problems[J]. Journal of Shanghai University（Natural Science Edition）, 2017, 23(2): 179-184.

参考文献

[1] Wu G, Wei Y M. A Power-Arnoldi algorithm for computing PageRank [J]. Numerical Linear Algebra with Applications, 2007, 14(7): 521-546.
[2] Page L, Brin S, Motwani R, et al. The PageRank citation ranking: bring order to the web [R/OL]. (2016-12-24)[2017-03-22]. http://homepages.dcc.ufmg.br/vnivio/cursos/rill/sources/pagerank.pdf.
[3] Kamvar S D, Haveliwala T H, Manning C D, et al. Extrapolation methods for accelerating PageRank computations [C]//12th International World Wide Web Conference. 2003: 261-270.
[4] Gleich D F, Gray A P, Greif C, et al. An inner-outer iteration method for computing Page-Rank [J]. SIAM Journal on Scientific Computing, 2010, 32(1): 349-371.
[5] 顾传青, 王磊. 一类修正的幂外推法加速PageRank 计算[J]. 上海大学学报(自然科学版), 2013, 19(2): 150-153.
[6] 顾传青, 马先磊. 求解PageRank 问题的多步幂法修正的内外迭代法[J]. 应用数学与计算数学学报, 2014, 28(4): 454-460.
[7] Saad Y, Schultz M H. GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems [J]. SIAM Journal on Scientific and Statistical Computing, 1986, 7(3): 856-869.
[8] Pu B Y, Huang T Z, Wen C. A preconditioned and extrapolation-accelerated GMRES method for PageRank [J]. Applied Mathematics Letters, 2014, 37(11): 95-100.
[9] 蒋尔雄. 矩阵计算[M]. 北京: 科学出版社, 2008.
[10] Haveliwala T H, Kamvar A D. The second eigenvalue of the google matrix [R/OL]. (2016-11-21)[2016-012-20]. http://ilpubs.stanford.edu:8090/582.
[11] 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.
[12] Gu C Q, Wang W W. An Arnoldi-Inout algorithm for computing PageRank problems [J]. Journal of Computational and Applied Mathematics, 2017, 309: 219-229.

求解PageRank问题的GMRES-Inout方法

A GMRES-Inout algorithm for computing PageRank problems

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 3

编辑推荐

Metrics

本文评价

[1]	顾传青, 王磊. 一类修正的幂外推法加速PageRank 计算[J]. 上海大学学报(自然科学版), 2013, 19(2): 150-153.
[2]	周广付，姚奕荣，王筱莉. 大步长路径跟踪内点新算法[J]. 上海大学学报(自然科学版), 2011, 17(5): 614-619.
[3]	杨毅;彭拯;严侃;邬冬华. 一种全局优化的随机水平值逼近算法[J]. 上海大学学报(自然科学版), 2008, 14(3): 265-270 .