子图估算PageRank网页排序算法探究.doc

子图估算PageRank网页排序算法探究 　　摘要：针对传统PageRank算法难以高效处理Web图数据网页排序问题，文章在不牺牲准确度的前提下，提出一种在MapReduce平台上基于改进PageRank的加速算法：topKRank.为识别出排名为前k的网页，通过在迭代过程中裁剪掉不必要的节点及边的形式，动态构建子图，由子图迭代计算出PageRank值的上下限。理论分析和实验结果表明：该算法不仅可以保证结果的准确性，还可以更快地找到用户所需网页数 关键词：web图数据；网页排序；PageRank算法；MapReduce；子图 DOI：10.15938/j.jhust.2017.02.022 中图分类号： TP301 文献标志码： A 文章编号： 1007-2683（2017）02-0117-07 Abstract：The traditional PageRank algorithm can not efficiently perform large data Webpage scheduling problem. This paper proposes an accelerated algorithm named topKRank， which is based on PageRank on the MapReduce platform. It can find top k nodes efficiently for a given graph without sacrificing accuracy. In order to identify top k nodes， topKRank algorithm prunes unnecessary nodes and edges in each iteration to dynamically construct subgraphs， and iteratively estimates lower/upper bounds of PageRank scores through subgraphs. Theoretical analysis shows that this method guarantees result exactness. Experiments show that topKRank algorithm can find k nodes much faster than the existing approaches. Keywords：web data； webpage scheduling； PageRank algorithm； MapReduce； subgraphs 0引言 当今世界，大数据运算无所不在。面对数以TB甚至PB级的数据，通过传统单机环境进行网页分析处理是不可能的。如何设计面向分布式的有效算法吸引了许多研究者的关注。由Google实验室提出的 MapReduce[1]是一个简单的分布式编程模型，它因简单和有效性而被许多计算软件广泛使用[2]，这其中就包括Web图计算[3] PageRank[4]是在有哪些信誉好的足球投注网站引擎中计算网页排名的常用算法，它根据网页之间链接关系进行计算，除用以计算网页的重要程度外，也可作为Web图中结点重要性的评测方法。该算法基于“随机游走模型”[5]，更加接近用户浏览行为。虽然最初提出PageRank是为了提高信息检索的高效性，但因其有效性和坚实的理论基础，在人工智能及网络社区的很多应用软件中也得以广泛使用，如评论总结、同义词扩展和Web内容提取等[6] 尽管PageRank算法有效，但用传统方法[7]对大图做出快速反应却是困难的。因为PageRank算法基于全局网络拓扑结构，每次迭代需要对各个节点进行计算，直至收敛，计算复杂度高。为解决该问题，出现了多种加速算法。目前有3种主流加速算法：线性代数法、动态规划算法和蒙特-卡洛法 文[8]提出线性代数机制：一旦收敛，该算法立即停止迭代，缺点是无法保证最终节点收敛。文[9]研究了另一种线性代数机制，区别于在传统方法中采用迭代幂方式来计算PageRank值，它使用克雷洛夫子空间方法。该方法的实现虽快于传统方式，但由于该机制最终汇聚是非静态的，因此最终得到的PageRank值不规律。针对图计算中增量变化大，且只影响局部PageRank值的??题，文[10]提出了基于动态规划算法的近似机制。然而，一来图并非总按增量方式变化；二来只有当请求被提交到上层软件以后，才能得到图中各节点的关系，这类近似方法很难保证结果的准确性。文[11-12]提出蒙特-卡洛机制，使用随机步长行走模型对所有路径进行取样。取样后，求出经过某节点的所有取样路