求解PageRank问题的多步幂法修正的内外迭代法

《求解PageRank问题的多步幂法修正的内外迭代法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2014年12月第28卷第4期Dec．2014CommunicationOilAppliedMathematicsandComputationVo1．28NO．4DOI10．3969／j．issn．1006—6330．2014．04．009求解PageRank问题的多步幂法修正的内外迭代法顾传青，马先磊(上海大学理学院，上海200444)摘要引用两种加速计算PageRank的算法，分别为内外迭代法和两步分裂迭代算法．从这两种方法中，得到多步幂法修正的内外迭代方法．首先，详细介绍了算法实施过程．然后，对此算法的收敛性进行证明，并且

2、将此算法的谱半径与两步分裂迭代算法的谱半径进行比较．最后，数值试验说明该算法的计算速度比两步分裂迭代法要快．关键词内外迭代法；幂法；两步分裂迭代；多步分裂迭代；阻尼因子2010数学分类号65F10；65F50中图分类号TP391．9；0242．2文献标志码A文章编号1006—6330(2014)04-0454—07Inner．outeriterationmethOdmodifledwithmulti—steppowerforcomputingPageRankGUChuan—qing，MAXian—lei(CollegeofSci

3、ences，ShanghaiUniversity，Shanghai200444，China)AbstractThispaperpresentstwomethodsforspeedingupthecomputationofthePageRank．whicharetheinner—outeriterationmethodandthetwo—stepsplittingiterationmethod．Fromthetwomethods，weachievetheinner—outeriterationmethodmodifiedwitht

4、hemulti—steppowermethod．First．weintroducethealgorithmimplementationprocessindetail．Second．weprovethetheoreticalratesoftheconvergenceofthenewapproach．WeprovethespectralradiusofourapproachiSlessthanthespectralradiusofthepowerinner—outeriterationmethod．Last，wepresentres

5、ultsofanexperimentalcomparisontodemonstratethattheCPUtimeofournewapproachachievingtheprescribedaccuracyiSlessthantheCPUtimeofthetwo—stepsplittingiterationmethod．Keywordsinner—outeriterationmethod；powermethod；two—stepsplittingiter—ation；multi-stepsplittingiteration；da

6、mpingfactor2010MathematicsSubiectClassification65F10；65F50ChineseLibraryClassificationTP391．9：O242．2收稿日期2014—09—10；修订日期2014—11—15基金项目国家自然科学基金资助项目(11371243)；上海市教委科研创新重点资助项目(13ZZ068)；上海市重点学科建设资助项目($30104)通信作者顾传青，研究方向为数值逼近、数值代数及其应用．E—mail：cqgu@shu．edu．ca第4期顾传青，等：求解PageR

7、ank问题的多步幂法修正的内外迭代法4550引言随着互联网的快速发展，网络搜索引擎已经成为重要的信息检索工具【1-5】．如何能够在大量杂乱无章的信息中找到所需要的部分，既是互联网使用者的愿望，也是搜索技术研究人员所不断追求的目标．搜索引擎最核心的部分就是其搜索算法的设计，一个好的搜索算法应当尽可能减少从搜索目标提出到搜索结果反馈给网页浏览者的滞后时间．在网络搜索算法中最著名的算法之一就是PageRank算法[6-r]，它是当今网络搜索引擎巨匠Google的核心技术，正是它的出现，使得搜索引擎的使用效果提升到了一个新的高度．Goo

8、gle矩阵是矩阵P与矩阵E的凸组合，其定义如下：G=P+(1一)E，式中，∈(0，1)是阻尼因子，E=veT，e=(1，l，⋯，1)T∈”，：e／n，矩阵P由网络的超链接结构[]所定义，n为矩阵P的维数．PageRank问题就是求解Google矩阵G的首特征值1