PageRank算法的二级加速优化方案

刘健雄，王晓程，毛俐旻

(1.中国航天科工集团二院研究生院，北京 100854；2.中国航天科工集团二院706所，北京 100854)

0 引 言

本文将讨论当今最具研究价值的主流网页排序算法——PageRank算法，并对其进行改进。本算法由Larry Page和Sergey Brin提出，其思想是通过分析网络的链接结构来获得网络中网页的重要性排名，且该算法已应用于Google搜索引擎[1]，成为其评价网页好坏的唯一标准。不过，该算法的执行速度和资源损耗等方面已无法适应当今信息爆炸的时代特性，所以如何更有效更快速地提升该算法的运行效率成为研究该算法的重中之重。

如今对于PageRank算法优化研究多种多样，可从改善网络图结构、加快算法收敛速度、实现算法并行化等各种角度提高算法效率。Héctor Migallón等利用启发式松弛外推法对原算法中幂法实施加速[2]；Lanying Li等利用TopK算法删除网络图冗余节点得到优化子图进行网页评估[3]；Arne Koschel等利用Hadoop分布式计算网络图节点值[4]。上述各方案均对PageRank算法的某一方面进行单次加速，加速效果有待提升。

本文将通过多级加速幂法迭代收敛的方式继续提升PageRank算法的执行效率。其中，原点平移法和Aitken加速算法已被证明为加速幂法收敛的有效方法，所以本文将提出一种基于以上方法的二级加速优化算法，通过仿真实验分析该方案的加速效果，并且原理上可与算法并行化等其它优化方案相结合，拥有更高的普适性、可行性，从而达到完善PageRank算法优化的目的。

1 PageRank算法研究

1.1 算法原理

PageRank算法基于网页的入链数量和网页质量两方面进行分析计算[5]，即一个网页接收到其它网页指向的链接越多，或指向它的网页的质量越高，则该网页越重要，PageRank值越高。……