IncPR：一种基于增量计算的并行PageRank算法

来源：计算机研究与发展杂志2016年第8期北京时间：

作者：姜双双,廖群,杨愚鲁,李涛,

摘要：广泛的互联网的商业应用使PageRank算法有重要地位.网络规模不断地增大，同时网络变化带来的时效性要求，也使PageRank计算对计算资源的要求不断地提高.为降低该问题对计算资源的消耗水平，降低计算成本，一种基于增量计算思想的PageRank算法：IncPR被提出.IncPR通过重用已有的结果，增量地获得数据变化后的结果.该算法在并行计算环境中，能够有效地降低计算量，缩短计算时间.理论分析表明，该算法计算结果的误差范围与蒙特卡罗PageRank算法相当，其时间复杂度优于其他已有的相关算法，且不引入额外的存储开销.在分布式集群Hama上进行的实验验证了理论分析的结果，IncPR在得到与蒙特卡罗PageRank算法同等(甚至更高)结果精度的情况下，显著地降低了计算量.

关键词：PageRank, Web数据挖掘, 增量计算, 蒙特卡罗算法, 并行与分布式处理,