姜双双　廖　群　杨愚鲁　李　涛

(南开大学计算机与控制工程学院　天津　300350)



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

姜双双廖群杨愚鲁李涛

(南开大学计算机与控制工程学院天津300350)

(highfly@mail.nankai.edu.cn)

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

PageRank；Web数据挖掘；增量计算；蒙特卡罗算法；并行与分布式处理

随着电子商务、物联网、社交网络、生物信息学等诸多领域的蓬勃发展，大量有价值的数据快速地产生并积累，“大数据”的计算处理成为近年来的研究热点之一.大量的统计结果显示，大数据应用问题普遍具有数据的总量大且增长速度快的特点[1].截止到2016年3月，Google抓取的网页已超过60万亿，并以每天超过450亿个网页的速度增长[2-3]；FaceBook的用户数量已达到13亿并保持每秒5位用户的增长速度[4].当数据发生变……