李蘭英+周秋麗+孔銀+董義明

摘要：針對傳統(tǒng)PageRank算法難以高效處理Web圖數(shù)據(jù)網(wǎng)頁排序問題，文章在不犧牲準確度的前提下，提出一種在MapReduce平臺上基于改進PageRank的加速算法：topKRank.為識別出排名為前k的網(wǎng)頁，通過在迭代過程中裁剪掉不必要的節(jié)點及邊的形式，動態(tài)構(gòu)建子圖，由子圖迭代計算出PageRank值的上下限。理論分析和實驗結(jié)果表明：該算法不僅可以保證結(jié)果的準確性，還可以更快地找到用戶所需網(wǎng)頁數(shù)。

關(guān)鍵詞：web圖數(shù)據(jù)；網(wǎng)頁排序；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引言

當今世界，大數(shù)據(jù)運算無所不在。面對數(shù)以TB甚至PB級的數(shù)據(jù)，通過傳統(tǒng)單機環(huán)境進行網(wǎng)頁分析處理是不可能的。如何設(shè)計面向分布式的有效算法吸引了許多研究者的關(guān)注。由Google實驗室提出的 MapReduce[1]是一個簡單的分布式編程模型，它因簡單和有效性而被許多計算軟件廣泛使用[2]，這其中就包括Web圖計算[3]。

PageRank[4]是在搜索引擎中計算網(wǎng)頁排名的常用算法，它根據(jù)網(wǎng)頁之間鏈接關(guān)系進行計算，除用以計算網(wǎng)頁的重要程度外，也可作為Web圖中結(jié)點重要性的評測方法。該算法基于“隨機游走模型”[5]，更加接近用戶瀏覽行為。雖然最初提出PageRank是為了提高信息檢索的高效性，但因其有效性和堅實的理論基礎(chǔ)，在人工智能及網(wǎng)絡(luò)社區(qū)的很多應(yīng)用軟件中也得以廣泛使用，如評論總結(jié)、同義詞擴展和Web內(nèi)容提取等[6]。

盡管PageRank算法有效，但用傳統(tǒng)方法[7]對大圖做出快速反應(yīng)卻是困難的。因為PageRank算法基于全局網(wǎng)絡(luò)拓撲結(jié)構(gòu)，每次迭代需要對各個節(jié)點進行計算，直至收斂，計算復(fù)雜度高。為解決該問題，出現(xiàn)了多種加速算法。目前有3種主流加速算法：線性代數(shù)法、動態(tài)規(guī)劃算法和蒙特-卡洛法。

文[8]提出線性代數(shù)機制：一旦收斂，該算法立即停止迭代，缺點是無法保證最終節(jié)點收斂。文[9]研究了另一種線性代數(shù)機制，區(qū)別于在傳統(tǒng)方法中采用迭代冪方式來計算PageRank值，它使用克雷洛夫子空間方法。該方法的實現(xiàn)雖快于傳統(tǒng)方式，但由于該機制最終匯聚是非靜態(tài)的，因此最終得到的PageRank值不規(guī)律。針對圖計算中增量變化大，且只影響局部PageRank值的問題，文[10]提出了基于動態(tài)規(guī)劃算法的近似機制。然而，一來圖并非總按增量方式變化；二來只有當請求被提交到上層軟件以后，才能得到圖中各節(jié)點的關(guān)系，這類近似方法很難保證結(jié)果的準確性。文[11-12]提出蒙特-卡洛機制，使用隨機步長行走模型對所有路徑進行取樣。取樣后，求出經(jīng)過某節(jié)點的所有取樣路徑的概率并用以估算實際的PageRank值。該方法因采用遠程方式在給定的圖中完成隨機游走，故可以大致計算出點對點中排名為前k（k為最終所需的網(wǎng)頁數(shù)）的節(jié)點集（簡稱topk）。然而蒙特-卡洛法需要預(yù)先手動設(shè)置隨機游走步數(shù)，需要權(quán)衡效率與近似質(zhì)量之間的利弊。

伴隨計算機技術(shù)迅猛發(fā)展，將PageRank算法實現(xiàn)并行化也成為必然。文[13]在Hadoop云計算環(huán)境下，對PageRank算法進行了并行化計算，將PageRank算法與MapReduce編程模型有效地結(jié)合起來，利用集群對不同規(guī)模的Web數(shù)據(jù)集進行了測試，與單機串行比，算法計算性能明顯提高，時間復(fù)雜度降低。文[14]提出了基于塊結(jié)構(gòu)劃分的并行方法，減少了map 和 reduce 操作的調(diào)用次數(shù)，降低了 I/O 傳輸造成的開銷，提高了計算的效率。文[15]引入一個狀態(tài)轉(zhuǎn)移矩陣實現(xiàn)對用戶重要性排名的迭代運算從而得到較為精確的量化結(jié)果。 該結(jié)果不僅合理反映了用戶粉絲的數(shù)量，而且有效兼顧了用戶粉絲的質(zhì)量，改善了搜索排名。但已有并行算法普遍存在需要大量反復(fù)迭代運算、頻繁訪問HDFS、集群間通信次數(shù)過多而耗費時間等問題。

為克服現(xiàn)有方法的局限性，本文選取MapReduce[16]作為并行計算的框架，使用 Apache 開源的Hadoop[17]平臺來實現(xiàn)一種新穎的算法：topKRank。該算法可快速準確地找到topk的節(jié)點集。為減少計算代價：①在每次迭代中，采用估算方式由子圖得出節(jié)點PageRank得分的最大最小值；②為高效地找到topk節(jié)點集，采用動態(tài)構(gòu)建子圖的方式，減少迭代次數(shù)。本文算法優(yōu)勢如下：

1）快速。topKRank快于傳統(tǒng)方法。

2）準確。topKRank 不犧牲準確性，可返回準確的topk節(jié)點集。

3）靈活。對任意給定圖，topKRank可高效地進行點對點處理，無需預(yù)計算。

4）參數(shù)自由。topKRank無需任何內(nèi)部參數(shù)，提供給用戶一種簡單方法來處理基于PageRank的應(yīng)用。

1PageRank算法

1.1PageRank算法描述

PageRank（簡稱PR）算法[18]建立在隨機沖浪者模型上，其基本思想是：網(wǎng)頁重要性排序是由網(wǎng)頁間鏈接關(guān)系決定，算法依靠網(wǎng)頁間鏈接結(jié)構(gòu)來評價各頁面等級和重要性，一個網(wǎng)頁的PR值不僅考慮指向它的鏈接網(wǎng)頁數(shù)，還要考慮指向它的網(wǎng)頁本身的重要性。

PageRank算法描述如下：

式中：PR（pi）為pi頁面PageRank值；n為所有頁面數(shù)量，e為1/n；pi為不同網(wǎng)頁p1，p2，p3，…；M（i）為pi鏈入網(wǎng)頁集合；L（j）為pj鏈出網(wǎng)頁數(shù)量；W為列標準化鄰接矩陣；d為阻尼系數(shù)，任意時刻用戶到達某頁面并繼續(xù)向后瀏覽的概率，取值范圍0

1.2PageRank的并行實現(xiàn)

分步式PageRank算法[19]原理，簡單說，即是通過矩陣計算實現(xiàn)并行化。首先將鄰接矩陣進行轉(zhuǎn)置處理，然后進行反復(fù)迭代：求取矩陣特征值，直至特征值收斂或達到預(yù)定迭代次數(shù)。并行化過程分為Map和Reduce兩個階段。

Map階段完成鍵值對的映射，輸入?yún)?shù)為<鄰接矩陣，初始PR值> 組成的鍵值對，其中鄰接矩陣的列為源頁面集，行為目標頁面集，初始PR值為1-d；經(jīng)內(nèi)部處理后，輸出參數(shù)為組成的鍵值對。

Reduce階段針對相同的鍵值key進行歸并操作，將map過程的輸出作為輸入，經(jīng)過處理后，輸出參數(shù)為組成的鍵值對。

Reduce階段完成后，將最后一次迭代結(jié)果的文件名和PR值讀出，將PR值按照從大到小順序排序，最終獲得所有網(wǎng)頁對應(yīng)的PR值排名。

2topKRank算法

2.1topK算法詳述

topKRank算法核心思想是：為減少計算代價，與使用全圖來計算每個頁面PR值的傳統(tǒng)方法不同，該算法通過制定裁剪規(guī)則，裁掉不必要的節(jié)點及邊，得到相應(yīng)子圖，計算子圖中候選節(jié)點集的節(jié)點估值，獲得最終所需PR值。表1列出了本文用到的主要符號及含義。

2.3算法的時間復(fù)雜度

為取得最終所需topk節(jié)點集，topKRank算法的時間復(fù)雜度為O（（n+m+logclogk）t），其中n，m分別是子圖對應(yīng)的節(jié)點集和邊集；c為子圖候選節(jié)點集個數(shù)，t為topKRank迭代次數(shù)。顯然c≤n。

證明：topKRank算法首先按照深度優(yōu)先搜索方法以時間復(fù)雜度為O（（n+m）t）來構(gòu)建子圖，計算子圖中各節(jié)點隨機游走概率d，共耗時O（（n+m）t）；在每次迭代中以O(shè)（1）計算出各節(jié)點估值上下限，故計算候選節(jié)點集估值共耗時O（ct）；由候選節(jié)點集Ci按照估值下限來計算εi，耗時O（logclogk）。這是因為（1）在Ci中每次更新最小估計值，其間耗時O（logk）；（2）隨機地訪問Ci，預(yù)計的更新數(shù)目為O（logc）。通過使用和最小估計值，從Ci中以O(shè)（ct）得到Ci+1，因此，該算法的時間復(fù)雜度為O（（n+m+logclogk）t）。

3實驗及結(jié)果分析

3.1實驗平臺及數(shù)據(jù)

本實驗采用六臺CPU為Intel Xeon X3330；內(nèi)存16GB；硬盤1TB的PC機，通過10M交換機相連搭建Hadoop云環(huán)境，其中1臺作為NameNode和JobTracker的Master服務(wù)節(jié)點，其他5臺作為DateNode和TaskTracker的Slave服務(wù)節(jié)點。每臺節(jié)點均安裝Ubuntu14.04，Hadoop1.2.1，jdk1.8，開發(fā)環(huán)境采用eclipse3.6 + hadoop1.2.1 plugin + maven3.2.3.實驗數(shù)據(jù)集采用美國社會網(wǎng)絡(luò)研究平臺提供的圖數(shù)據(jù)，如表3所示。

3.2實驗及結(jié)果分析

3.2.1函數(shù)迭代次數(shù)對比

與傳統(tǒng)并行PageRank算法采用全圖來迭代計算各節(jié)點PageRank值不同，本算法應(yīng)用子圖來估算PageRank值，直至候選節(jié)點個數(shù)滿足最終需求。首先子圖比給定圖小，可大大減少迭代次數(shù)；其次子圖得到的候選節(jié)點集單調(diào)遞減，反復(fù)迭代中可快速減少節(jié)點集/邊集數(shù)目。表4詳細列出當k=50時，各數(shù)據(jù)集的內(nèi)部參數(shù)。表中參數(shù)都是按照給定圖和topKRank算法自動設(shè)定的。

3.2.2效率對比

對比topKRank算法和傳統(tǒng)并行算法時間復(fù)雜度。在圖1中：topKRank算法結(jié)果用topKRank（k）標識，其中k為最終所求節(jié)點個數(shù)。

已有研究表明，傳統(tǒng)方法只有當剩余1范數(shù)低于10-10時，迭代才會結(jié)束，且需要計算所有節(jié)點PR值，因此所求節(jié)點個數(shù)不影響時間復(fù)雜度。

圖1表明，topKRank算法要快于傳統(tǒng)方法。對應(yīng)各數(shù)據(jù)集，topKRank算法相應(yīng)將搜索時間縮短了42%，72%，92%；隨著圖尺寸增長，topKRank能更加有效地找到topk節(jié)點集。傳統(tǒng)算法利用整個圖來迭代計算PR值，直至該PR值收斂，所以時間復(fù)雜度為O（（N+M）T）；本文算法通過子圖來計算估值，直至候選節(jié)點的數(shù)目變?yōu)閗，所以時間復(fù)雜度為O（（n+m+logclogk）t）。

3.2.3精確度分析

topKRank算法的最大優(yōu)勢在于最終輸出結(jié)果與傳統(tǒng)方法相同。為了證明這點，將topKRank與Avrachenkov[20]提出的“停在懸掛節(jié)點中MC完整路徑”進行對比。與傳統(tǒng)蒙特-卡洛方法相比，Avrachenkov。提出的方法可以更加有效地估算PR值，不存在如無法保證收斂、增量圖變化和高I/O代價等技術(shù)上的局限性。它采用隨機游走統(tǒng)計各節(jié)點訪問總次數(shù)，估算各節(jié)點PR值，故節(jié)點隨機游走次數(shù)影響搜索時間和估算精確度。因此，我們采用多種隨機步數(shù)進行對比實驗。圖2和3分別展示了當k=50時，對應(yīng)數(shù)據(jù)集P2P中兩方法精度和搜索時間。圖2中用精確度來作為準確度度量，圖3中用掛鐘時間來評估各方法的效率。

綜上所述，在處理大規(guī)模圖數(shù)據(jù)時，基于子圖估算PageRank的快速準確topk算法，具有較高效率和準確性，更符合實際應(yīng)用需求。

4結(jié)論

本文提出一種基于子圖估算PageRank的快速高效topk算法：topKRank，可保證結(jié)果的準確性。算法按照估值的最值范圍裁剪掉無關(guān)節(jié)點和邊，并在每次迭代中，動態(tài)構(gòu)建子圖來得到最終所需topk節(jié)點集。實驗結(jié)果表明，本方法比傳統(tǒng)方法要有優(yōu)勢，可以更高效地處理許多基于PageRank的應(yīng)用。然而也存在一些挑戰(zhàn)，如web圖的規(guī)?？赡艹^主存容量，分塊算法是一個有趣且富有挑戰(zhàn)性的問題。

參 考 文 獻：

[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]潘巍，李戰(zhàn)懷，伍賽. 基于消息傳遞機制的 MapReduce 圖算法研究[J].計算機學(xué)報，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]金弟，楊博，劉杰，等.復(fù)雜網(wǎng)絡(luò)簇結(jié)構(gòu)探測——基于隨機游走的蟻群算法[J].軟件學(xué)報，2012，23（3）：451-464.

[6]陸勇，侯漢清.基于PageRank算法的漢語同義詞自動識別[J].西華大學(xué)學(xué)報，2008，27（2）：13-16.

[7]李稚楹，楊武，謝治軍.PageRank算法研究綜述[J].計算機科學(xué)，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]蔣凱，關(guān)佶紅.基于重啟型隨機游走模型的圖上關(guān)鍵字搜索[J].計算機工程，2011，37（3）：68-71.

[13]平宇，向陽，張波.基于MapReduce的并行PageRank算法實現(xiàn)[J].計算機工程，2014，40（2）：31-35.

[14]張永，尹傳曄，吳崇正.基于MapReduce的PageRank算法優(yōu)化研究[J].計算機工程，2014，31（2）：431-434.

[15]梁秋實，吳一雷，封磊.基于MapReduce的PageRank算法優(yōu)化研究[J].計算機工程，2012，32（11） ：2989-2993.

[16]覃雄派，王會舉，杜小勇，等.大數(shù)據(jù)分析——RDBMS與MapReduce的競爭與共生[J].軟件學(xué)報，2012， 23（1）：32-45.

[17]王玉鳳，梁毅.Hadoop平臺數(shù)據(jù)訪問監(jiān)控機制研究[J].計算機工程與應(yīng)用，2014，50（22）：54-58.

[18]廖松博，陶岳，汪衛(wèi)，等.GCPR一種在MapReduce平臺上基于圖劃分的PageRank加速方法[J].小型微型計算機系統(tǒng)，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.

（編輯：溫澤宇）