子图估算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]提出蒙特-卡洛机制，使用随机步长行走模型对所有路径进行取样。取样后，求出经过某节点的所有取样路径的概率并用以估算实际的PageRank值。该方法因采用远程方式在给定的图中完成随机游走，故可以大致计算出点对点中排名为前k（k为最终所需的网页数）的节点集（简称topk）。然而蒙特-卡洛法需要预先手动设置随机游走步数，需要权衡效率与近似质量之间的利弊。

伴随计算机技术迅猛发展，将PageRank算法实现并行化也成为必然。文[13]在Hadoop云计算环境下，对PageRank算法进行了并行化计算，将PageRank算法与MapReduce编程模型有效地结合起来，利用集群对不同规模的Web数据集进行了测试，与单机串行比，算法计算性能明显提高，时间复杂度降低。文[14]提出了基于块结构划分的并行方法，减少了map 和 reduce 操作的调用次数，降低了 I/O 传输造成的开销，提高了计算的效率。文[15]引入一个状态转移矩阵实现对用户重要性排名的迭代运算从而得到较为精确的量化结果。 该结果不仅合理反映了用户粉丝的数量，而且有效兼顾了用户粉丝的质量，改善了搜索排名。但已有并行算法普遍存在需要大量反复迭代运算、频繁访问HDFS、集群间通信次数过多而耗费时间等问题。

为克服现有方法的局限性，本文选取MapReduce[16]作为并行计算的框架，使用 Apache 开源的Hadoop[17]平台来实现一种新颖的算法：topKRank。该算法可快速准确地找到topk的节点集。为减少计算代价：①在每次迭代中，采用估算方式由子图得出节点PageRank得分的最大最小值；②为高效地找到topk节点集，采用动态构建子图的方式，减少迭代次数。本文算法优势如下：

1）快速。topKRank快于传统方法。

2）准确。topKRank 不牺牲准确性，可返回准确的topk节点集。

3）灵活。对任意给定图，topKRank可高效地进行点对点处理，无需预计算。

4）参数自由。topKRank无需任何内部参数，提供给用户一种简单方法来处理基于PageRank的应用。

1PageRank算法

1.1PageRank算法描述

PageRank（简称PR）算法[18]建立在随机冲浪者模型上，其基本思想是：网页重要性排序是由网页间链接关系决定，算法依靠网页间链接结构来评价各页面等级和重要性，一个网页的PR值不仅考虑指向它的链接网页数，还要考虑指向它的网页本身的重要性。

PageRank算法描述如下：

式中：PR（pi）为pi页面PageRank值；n为所有页面数量，e为1/n；pi为不同网页p1，p2，p3，…；M（i）为pi链入网页集合；L（j）为pj链出网页数量；W为列标准化邻接矩阵；d为阻尼系数，任意时刻用户到达某页面并继续向后浏览的概率，取值范围0

1.2PageRank的并行实现

分步式PageRank算法[19]原理，简单说，即是通过矩阵计算实现并行化。首先将邻接矩阵进行转置处理，然后进行反复迭代：求取矩阵特征值，直至特征值收敛或达到预定迭代次数。并行化过程分为Map和Reduce两个阶段。

Map阶段完成键值对的映射，输入参数为<邻接矩阵，初始PR值> 组成的键值对，其中邻接矩阵的列为源页面集，行为目标页面集，初始PR值为1-d；经内部处理后，输出参数为组成的键值对。

Reduce阶段针对相同的键值key进行归并操作，将map过程的输出作为输入，经过处理后，输出参数为组成的键值对。

Reduce阶段完成后，将最后一次迭代结果的文件名和PR值读出，将PR值按照从大到小顺序排序，最终获得所有网页对应的PR值排名。

2topKRank算法

2.1topK算法详述

topKRank算法核心思想是：为减少计算代价，与使用全图来计算每个页面PR值的传统方法不同，该算法通过制定裁剪规则，裁掉不必要的节点及边，得到相应子图，计算子图中候选节点集的节点估值，获得最终所需PR值。表1列出了本文用到的主要符号及含义。

2.3算法的时间复杂度

为取得最终所需topk节点集，topKRank算法的时间复杂度为O（（n+m+logclogk）t），其中n，m分别是子图对应的节点集和边集；c为子图候选节点集个数，t为topKRank迭代次数。显然c≤n。

证明：topKRank算法首先按照深度优先搜索方法以时间复杂度为O（（n+m）t）来构建子图，计算子图中各節点随机游走概率d，共耗时O（（n+m）t）；在每次迭代中以O（1）计算出各节点估值上下限，故计算候选节点集估值共耗时O（ct）；由候选节点集Ci按照估值下限来计算εi，耗时O（logclogk）。这是因为（1）在Ci中每次更新最小估计值，其间耗时O（logk）；（2）随机地访问Ci，预计的更新数目为O（logc）。通过使用和最小估计值，从Ci中以O（ct）得到Ci+1，因此，该算法的时间复杂度为O（（n+m+logclogk）t）。

3实验及结果分析

3.1实验平台及数据

本实验采用六台CPU为Intel Xeon X3330；内存16GB；硬盘1TB的PC机，通过10M交换机相连搭建Hadoop云环境，其中1台作为NameNode和JobTracker的Master服务节点，其他5台作为DateNode和TaskTracker的Slave服务节点。每台节点均安装Ubuntu14.04，Hadoop1.2.1，jdk1.8，开发环境采用eclipse3.6 + hadoop1.2.1 plugin + maven3.2.3.实验数据集采用美国社会网络研究平台提供的图数据，如表3所示。

3.2实验及结果分析

3.2.1函数迭代次数对比

与传统并行PageRank算法采用全图来迭代计算各节点PageRank值不同，本算法应用子图来估算PageRank值，直至候选节点个数满足最终需求。首先子图比给定图小，可大大减少迭代次数；其次子图得到的候选节点集单调递减，反复迭代中可快速减少节点集/边集数目。表4详细列出当k=50时，各数据集的内部参数。表中参数都是按照给定图和topKRank算法自动设定的。

3.2.2效率对比

对比topKRank算法和传统并行算法时间复杂度。在图1中：topKRank算法结果用topKRank（k）标识，其中k为最终所求节点个数。

已有研究表明，传统方法只有当剩余1范数低于10-10时，迭代才会结束，且需要计算所有节点PR值，因此所求节点个数不影响时间复杂度。

图1表明，topKRank算法要快于传统方法。对应各数据集，topKRank算法相应将搜索时间缩短了42%，72%，92%；随着图尺寸增长，topKRank能更加有效地找到topk节点集。传统算法利用整个图来迭代计算PR值，直至该PR值收敛，所以时间复杂度为O（（N+M）T）；本文算法通过子图来计算估值，直至候选节点的数目变为k，所以时间复杂度为O（（n+m+logclogk）t）。

3.2.3精确度分析

topKRank算法的最大优势在于最终输出结果与传统方法相同。为了证明这点，将topKRank与Avrachenkov[20]提出的“停在悬挂节点中MC完整路径”进行对比。与传统蒙特-卡洛方法相比，Avrachenkov。提出的方法可以更加有效地估算PR值，不存在如无法保证收敛、增量图变化和高I/O代价等技术上的局限性。它采用随机游走统计各节点访问总次数，估算各节点PR值，故节点随机游走次数影响搜索时间和估算精确度。因此，我们采用多种随机步数进行对比实验。图2和3分别展示了当k=50时，对应数据集P2P中两方法精度和搜索时间。图2中用精确度来作为准确度度量，图3中用挂钟时间来评估各方法的效率。

综上所述，在处理大规模图数据时，基于子图估算PageRank的快速准确topk算法，具有较高效率和准确性，更符合实际应用需求。

4结论

本文提出一种基于子图估算PageRank的快速高效topk算法：topKRank，可保证结果的准确性。算法按照估值的最值范围裁剪掉无关节点和边，并在每次迭代中，动态构建子图来得到最终所需topk节点集。实验结果表明，本方法比传统方法要有优势，可以更高效地处理许多基于PageRank的应用。然而也存在一些挑战，如web图的规模可能超过主存容量，分块算法是一个有趣且富有挑战性的问题。

参 考 文 献：

[1]LAMEL R. Googles Mapreduce Programming Model revisited [M].Science of Computer Programming，2008：208-237.

[2]DING Huafu，ZHOU Hongbo.A Multiagent Based Personalized Meta search Engine Using Automatic Fuzzy Concept Networks[J].Journal of Harbin University of Science and Technology，2014，19（2） ：31-35.

[3]潘巍，李战怀，伍赛. 基于消息传递机制的 MapReduce 图算法研究[J].计算机学报，2011，34（10）：768-785.

[4]LANGVILLE A N， MEYER C D.Googles PageRank and Beyond：The Science of Search Engine Rankings[J].Princeton University Press，2012，5（8）：17-19.

[5]金弟，杨博，刘杰，等.复杂网络簇结构探测——基于随机游走的蚁群算法[J].软件学报，2012，23（3）：451-464.

[6]陆勇，侯汉清.基于PageRank算法的汉语同义词自动识别[J].西华大学学报，2008，27（2）：13-16.

[7]李稚楹，杨武，谢治军.PageRank算法研究综述[J].计算机科学，2011（S1）.

[8]KAMVAR S.HAVELIWALA.Adaptive Methods for the Computation of PageRank：Linear Algebra and its Applications[J].Special Issue on the Conference on the Numerical Solution of Markov Chains，2008，13（6）：11-15.

[9]GLEICH D.ZHUKOV P.Fast Parallel Page Rank：A Linear System Approach. Research of mining the mutative knowledge with extension data mining[J].Engineering Sciences，2007，11（18）：70-78.

[10]MCSHERRY F.A Uniform Approach to Accelerated PageRank Computation [J].Princeton University Press，2012，35（8）：17-20.

[11]FOGARAS D，RACZ B.Towards Scaling fully personalized PageRank[D].Computer and Automation Research Institute of the Hungarian Academy of Sciences：Budapest University of Technology and Economics，2010：12-34.

[12]蒋凯，关佶红.基于重启型随机游走模型的图上关键字搜索[J].计算机工程，2011，37（3）：68-71.

[13]平宇，向阳，张波.基于MapReduce的并行PageRank算法实现[J].计算机工程，2014，40（2）：31-35.

[14]张永，尹传晔，吴崇正.基于MapReduce的PageRank算法优化研究[J].计算机工程，2014，31（2）：431-434.

[15]梁秋实，吴一雷，封磊.基于MapReduce的PageRank算法优化研究[J].计算机工程，2012，32（11） ：2989-2993.

[16]覃雄派，王会举，杜小勇，等.大数据分析——RDBMS与MapReduce的竞争与共生[J].软件学报，2012， 23（1）：32-45.

[17]王玉凤，梁毅.Hadoop平台数据访问监控机制研究[J].计算机工程与应用，2014，50（22）：54-58.

[18]廖松博，陶岳，汪卫，等.GCPR一种在MapReduce平台上基于图划分的PageRank加速方法[J].小型微型计算机系统，2012，33（6）：43-50.

[19]陈再良，凌力，周强.dPageRank——一种改进的分布式PageRank 算法[J].计算机工程，2006，26（1）：21-25.

[20]AVRACHENKOV K，LITVAK N.Nemirovsky，D.Monte Carlo Method sin PageRank Computation：When One Iteration is Sufficient[C].SIAM J Press，2007：42-51.

（編辑：温泽宇）