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

摘要：針對傳統(tǒng)PageRank算法難以高效處理Web圖數據網頁排序問題，文章在不犧牲準確度的前提下，提出一種在MapReduce平臺上基于改進PageRank的加速算法：topKRank.為識別出排名為前k的網頁，通過在迭代過程中裁剪掉不必要的節(jié)點及邊的形式，動態(tài)構建子圖，由子圖迭代計算出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級的數據，通過傳統(tǒng)單機環(huán)境進行網頁分析處理是不可能的。如何設計面向分布式的有效算法吸引了許多研究者的關注。由Google實驗室提出的 MapReduce[1]是一個簡單的分布式編程模型，它因簡單和有效性而被許多計算軟件廣泛使用[2]，這其中就包括Web圖計算[3]。

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

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

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

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

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

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

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

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為阻尼系數，任意時刻用戶到達某頁面并繼續(xù)向后瀏覽的概率，取值范圍0

1.2PageRank的并行實現

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

Map階段完成鍵值對的映射，輸入參數為<鄰接矩陣，初始PR值> 組成的鍵值對，其中鄰接矩陣的列為源頁面集，行為目標頁面集，初始PR值為1-d；經內部處理后，輸出參數為組成的鍵值對。

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

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

2topKRank算法

2.1topK算法詳述

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

2.3算法的時間復雜度

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

證明：topKRank算法首先按照深度優(yōu)先搜索方法以時間復雜度為O（（n+m）t）來構建子圖，計算子圖中各節(jié)點隨機游走概率d，共耗時O（（n+m）t）；在每次迭代中以O（1）計算出各節(jié)點估值上下限，故計算候選節(jié)點集估值共耗時O（ct）；由候選節(jié)點集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云環(huán)境，其中1臺作為NameNode和JobTracker的Master服務節(jié)點，其他5臺作為DateNode和TaskTracker的Slave服務節(jié)點。每臺節(jié)點均安裝Ubuntu14.04，Hadoop1.2.1，jdk1.8，開發(fā)環(huán)境采用eclipse3.6 + hadoop1.2.1 plugin + maven3.2.3.實驗數據集采用美國社會網絡研究平臺提供的圖數據，如表3所示。

3.2實驗及結果分析

3.2.1函數迭代次數對比

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

3.2.2效率對比

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

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

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

3.2.3精確度分析

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

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

4結論

本文提出一種基于子圖估算PageRank的快速高效topk算法：topKRank，可保證結果的準確性。算法按照估值的最值范圍裁剪掉無關節(jié)點和邊，并在每次迭代中，動態(tài)構建子圖來得到最終所需topk節(jié)點集。實驗結果表明，本方法比傳統(tǒng)方法要有優(yōu)勢，可以更高效地處理許多基于PageRank的應用。然而也存在一些挑戰(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].計算機學報，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算法優(yōu)化研究[J].計算機工程，2014，31（2）：431-434.

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

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

[17]王玉鳳，梁毅.Hadoop平臺數據訪問監(jiān)控機制研究[J].計算機工程與應用，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.

（編輯：溫澤宇）