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

Inner-outer iteration method modified with multi-step power for computing PageRank

引用两种加速计算PageRank的算法,分别为内外迭代法和两步分裂迭代算法.从这两种方法中,得到多步幂法修正的内外迭代方法.首先,详细介绍了算法实施过程.然后,对此算法的收敛性进行证明,并且将此算法的谱半径与两步分裂迭代算法的谱半径进行比较.最后,数值试验说明该算法的计算速度比两步分裂迭代法要快.

This paper presents two methods for speeding up the computation of the PageRank,which are the inner-outer iteration method and the two-step splitting iteration method.From the two methods,we achieve the inner-outer iteration method modified with the multi-step power method.First,we introduce the algorithm implementation process in detail.Second,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 power inner-outer iteration method.Last,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 two-step splitting iteration method.