求解PageRank问题改进的多分裂迭代法  

Improved multi-splitting iteration method for computing PageRank

作　　者：顾传青[1] 徐慧慧 GU Chuanqing;XU Huihui(College of Sciences,Shanghai University,Shanghai 200444,China)

机构地区：[1]上海大学理学院,上海200444

出　　处：《应用数学与计算数学学报》2018年第2期305-314,共10页Communication on Applied Mathematics and Computation

基　　金：国家自然科学基金资助项目(11371243);上海市教委资助项目(13ZZ068);上海市重点学科建设资助项目(S30104)

摘　　要：引用两种加速计算PageRank的算法,分别为内外迭代法和多分裂迭代算法.从这两种方法中,得到改进的多分裂迭代方法.首先,详细介绍了算法实施过程.然后,对此算法的收敛性进行证明,并且将此算法的谱半径与原有的多分裂迭代算法的谱半径进行比较.最后,数值实验说明我们的算法的计算速度比原有的多分裂迭代法要快.This paper presents two methods for speeding up the computation of the PageRank, which are the inner-outer iteration method and the multi-splitting iteration method. From the two methods, we achieve the improved multi-splitting iteration method. Firstly, we introduce the algorithm implementation process in detail. Secondly, we prove the theoretical rates of the convergence of the new approach. We prove the spectral radius of our approach is less than the spectral radius of the original multi-splitting iteration method. Lastly, we present results of an experimental comparison to demonstrate that the CPU time of our new approach achieving the prescribed accuracy is less than the CPU time of the original multi-splitting iteration method.

关 键 词：PAGERANK 内外迭代法 多分裂迭代 改进的多分裂迭代法 阻尼因子 

分 类 号：O242[理学—计算数学]