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

摘要：

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

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

所属期刊栏目：53

分类号：TP391(计算技术、计算机技术)

在线出版日期：2016-08-19（万方平台首次上网日期，不代表论文的发表时间）

页数：共13页

页码：1806-1818