子圖估算PageRank網(wǎng)頁排序算法研究

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

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

關(guān)鍵詞：web圖數(shù)據(jù)；網(wǎng)頁排序；PageRank算法；MapReduce；子圖

DOI：10.15938/j.jhust.2017.02.022

中圖分類號(hào)： TP301

文獻(xiàn)標(biāo)志碼： A

文章編號(hào)： 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引言

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

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

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

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

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

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

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

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

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

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

1PageRank算法

1.1PageRank算法描述

PageRank（簡(jiǎn)稱PR）算法[18]建立在隨機(jī)沖浪者模型上，其基本思想是：網(wǎng)頁重要性排序是由網(wǎng)頁間鏈接關(guān)系決定，算法依靠網(wǎng)頁間鏈接結(jié)構(gòu)來評(píng)價(jià)各頁面等級(jí)和重要性，一個(gè)網(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為列標(biāo)準(zhǔn)化鄰接矩陣；d為阻尼系數(shù)，任意時(shí)刻用戶到達(dá)某頁面并繼續(xù)向后瀏覽的概率，取值范圍0

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

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

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

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

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

2topKRank算法

2.1topK算法詳述

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

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

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

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

3實(shí)驗(yàn)及結(jié)果分析

3.1實(shí)驗(yàn)平臺(tái)及數(shù)據(jù)

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

3.2實(shí)驗(yàn)及結(jié)果分析

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

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

3.2.2效率對(duì)比

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

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

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

3.2.3精確度分析

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

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

4結(jié)論

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

參 考 文 獻(xià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)懷，伍賽. 基于消息傳遞機(jī)制的 MapReduce 圖算法研究[J].計(jì)算機(jī)學(xué)報(bào)，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)探測(cè)——基于隨機(jī)游走的蟻群算法[J].軟件學(xué)報(bào)，2012，23（3）：451-464.

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

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

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

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

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

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

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

[18]廖松博，陶岳，汪衛(wèi)，等.GCPR一種在MapReduce平臺(tái)上基于圖劃分的PageRank加速方法[J].小型微型計(jì)算機(jī)系統(tǒng)，2012，33（6）：43-50.

[19]陳再良，凌力，周強(qiáng).dPageRank——一種改進(jìn)的分布式PageRank 算法[J].計(jì)算機(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.

（編輯：溫澤宇）