English

上海大学学报(自然科学版) ›› 2017, Vol. 23 ›› Issue (4): 555-562.doi: 10.12066/j.issn.1007-2861.1867

• • 上一篇    下一篇

求解PageRank 问题的Arnoldi-PIO 算法

顾传青1, 聂影1, 王金波2   

  1. 1. 上海大学理学院, 上海 200444; 2. 保密通信重点实验室, 成都 610041
  • 收稿日期:2016-10-13 出版日期:2017-08-30 发布日期:2017-08-30
  • 通讯作者: 顾传青(1955—), 男, 教授, 博士生导师, 研究方向为数值逼近、数值代数及其应用. E-mail: cqgu@shu.edu.cn
  • 作者简介:顾传青(1955—), 男, 教授, 博士生导师, 研究方向为数值逼近、数值代数及其应用. E-mail: cqgu@shu.edu.cn
  • 基金资助:

    国家自然科学基金资助项目(11371243); 上海市重点学科建设资助项目(S30104); 中国电子科技集团公司第三十研究所委托项目

Arnoldi-PIO algorithm for PageRank

GU Chuanqing1, NIE Ying1, WANG Jinbo2   

  1. 1. College of Sciences, Shanghai University, Shanghai 200444, China;
    2. Science and Technology on Communication Security Laboratory, Chengdu 610041, China
  • Received:2016-10-13 Online:2017-08-30 Published:2017-08-30

PDF

177

摘要：

PageRank 算法能帮助用户快速、准确地在巨量杂乱无章的信息中检索出有用的信息. 两步分裂迭代法是用幂法来修正内外分裂(power-inner-outer, PIO)迭代法以加速PageRank算法. 基于两步分裂迭代法, 将预处理思想运用于求解PageRank 问题, 提出了求解Page-Rank 问题的深度重启的Arnoldi 算法加速的两步分裂迭代法, 然后对此算法的收敛性进行了证明. 数值实验结果证明, 该算法的计算速度要快于两步分裂迭代法.

关键词: 两步分裂迭代法, 深度重启的Arnoldi 算法, 内外迭代法

Abstract:

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.

Key words: thick restarted Arnoldi algorithm, two-step splitting iteration, inner-outer iteration

© 2019 上海大学学报(自然科学版)编辑部
办公地址：上海市宝山区南陈路333号上海大学东区3#楼221室电话：021-66135508　 传真：021-66132736　 E-mail： xuebao@mail.shu.edu.cn
通信地址：上海市上大路99号上海大学126信箱 邮编：200444
本系统由北京玛格泰克科技发展有限公司设计开发 技术支持：support@magtech.com.cn