IncPR：一種基于增量計算的并行PageRank算法

姜雙雙　廖　群　楊愚魯　李　濤

(南開大學(xué)計算機(jī)與控制工程學(xué)院　天津　300350)

?

IncPR：一種基于增量計算的并行PageRank算法

姜雙雙廖群楊愚魯李濤

(南開大學(xué)計算機(jī)與控制工程學(xué)院天津300350)

(highfly@mail.nankai.edu.cn)

廣泛的互聯(lián)網(wǎng)的商業(yè)應(yīng)用使PageRank算法有重要地位.網(wǎng)絡(luò)規(guī)模不斷地增大，同時網(wǎng)絡(luò)變化帶來的時效性要求，也使PageRank計算對計算資源的要求不斷地提高.為降低該問題對計算資源的消耗水平，降低計算成本，一種基于增量計算思想的PageRank算法：IncPR被提出.IncPR通過重用已有的結(jié)果，增量地獲得數(shù)據(jù)變化后的結(jié)果.該算法在并行計算環(huán)境中，能夠有效地降低計算量，縮短計算時間.理論分析表明，該算法計算結(jié)果的誤差范圍與蒙特卡羅PageRank算法相當(dāng)，其時間復(fù)雜度優(yōu)于其他已有的相關(guān)算法，且不引入額外的存儲開銷.在分布式集群Hama上進(jìn)行的實驗驗證了理論分析的結(jié)果，IncPR在得到與蒙特卡羅PageRank算法同等(甚至更高)結(jié)果精度的情況下，顯著地降低了計算量.

PageRank；Web數(shù)據(jù)挖掘；增量計算；蒙特卡羅算法；并行與分布式處理

隨著電子商務(wù)、物聯(lián)網(wǎng)、社交網(wǎng)絡(luò)、生物信息學(xué)等諸多領(lǐng)域的蓬勃發(fā)展，大量有價值的數(shù)據(jù)快速地產(chǎn)生并積累，“大數(shù)據(jù)”的計算處理成為近年來的研究熱點之一.大量的統(tǒng)計結(jié)果顯示，大數(shù)據(jù)應(yīng)用問題普遍具有數(shù)據(jù)的總量大且增長速度快的特點[1].截止到2016年3月，Google抓取的網(wǎng)頁已超過60萬億，并以每天超過450億個網(wǎng)頁的速度增長[2-3]；FaceBook的用戶數(shù)量已達(dá)到13億并保持每秒5位用戶的增長速度[4].當(dāng)數(shù)據(jù)發(fā)生變化時，需要對數(shù)據(jù)重新處理以更新結(jié)果，因此，高效地處理頻繁變化的大數(shù)據(jù)具有重大意義.

PageRank[5]算法在搜索引擎、信息檢索、社交網(wǎng)絡(luò)挖掘等多個領(lǐng)域得到廣泛的應(yīng)用，具有重要地位.PageRank算法所處理的互聯(lián)網(wǎng)絡(luò)和社交網(wǎng)絡(luò)數(shù)據(jù)是典型的頻繁變化的大數(shù)據(jù)集，具有總量大、更新速度快、每次更新的數(shù)據(jù)占總量比例小的特點.為滿足結(jié)果的時效性要求，只要數(shù)據(jù)更新就需要重計算以更新結(jié)果.在頻繁變化的大數(shù)據(jù)集上反復(fù)地進(jìn)行PageRank計算，會消耗巨大的計算資源，計算成本高.

盡管以MapReduce[6],Spark[7]及Pregel[8]集群等為代表的分布式計算技術(shù)、以及很多并行PageRank算法[9-11]能夠提高PageRank的計算速度.但這些技術(shù)仍不能有效地降低反復(fù)計算帶來的高資源消耗和高計算成本.

因此針對這一問題本文通過擴(kuò)展一種典型的PageRank計算算法——蒙特卡羅算法[12]，提出了一種基于增量計算的PageRank算法——IncPR.當(dāng)數(shù)據(jù)集發(fā)生變化時，IncPR利用的是已有的PageRank計算結(jié)果，不需要保存其他歷史數(shù)據(jù)，沒有引入額外的存儲開銷；在進(jìn)行處理時，IncPR根據(jù)數(shù)據(jù)的變化情況在已有的計算結(jié)果上增量地進(jìn)行更新，獲得新數(shù)據(jù)集的結(jié)果，這有效地降低了計算量，提高了計算效率.此外，IncPR能高效處理網(wǎng)頁增加、減少、網(wǎng)頁鏈接關(guān)系變更等多種情況，這也是其較之于部分相關(guān)增量算法的優(yōu)勢之一.

理論分析證明，IncPR得到結(jié)果的誤差范圍和蒙特卡羅PageRank算法得到的結(jié)果誤差范圍的量級相當(dāng)，即IncPR具有與蒙特卡羅PageRank算法相同的正確性.在增加m個節(jié)點和n條邊的情況下，IncPR的時間復(fù)雜度為O((cm+n)Rc2)，其中參數(shù)c和R分別代表蒙特卡羅方法的停止概率和啟動次數(shù).IncPR的時間復(fù)雜度優(yōu)于其他已有的增量PageRank算法.在分布式集群Hama[13]上進(jìn)行的實驗驗證了理論分析的結(jié)果，實驗數(shù)據(jù)表明在得到與蒙特卡羅PageRank算法同等(甚至更高)精度結(jié)果的情況下，IncPR顯著地降低了計算量.

綜上，本文工作的貢獻(xiàn)有3點：

1) 提出了一種基于增量計算的PageRank算法IncPR.通過在已有結(jié)果的基礎(chǔ)上，增量地更新得到新結(jié)果的方法，IncPR能有效地降低PageRank的計算量，且不引入額外的存儲開銷；

2) 通過理論分析證明了IncPR與蒙特卡羅PageRank算法的結(jié)果具有相等量級的精度，且時間復(fù)雜度優(yōu)于已有的增量PageRank算法；

3) 在Hama集群上基于大規(guī)模真實圖數(shù)據(jù)的大量實驗，驗證了IncPR的正確性和計算效率.IncPR在保證結(jié)果正確的前提下能有效降低PageRank的計算量.

1　相關(guān)工作

1.1PageRank算法

P=(1-c)Q+(cn)E；

(1)

(2)

(3)

當(dāng)前PageRank算法主要可以分成2類：線性代數(shù)方法和蒙特卡羅方法.前者利用線性代數(shù)方法根據(jù)式(3)求解π,PowerIteration[5]、Gauss-Southwell[14]、基于LUQR分解的PageRank算法[15]等是典型的線性代數(shù)計算方法.它們處理大規(guī)模矩陣效率高，且能夠根據(jù)需要權(quán)衡結(jié)果精度和計算開銷.蒙特卡羅方法[12,16-17]的基本思想是利用隨機(jī)游走模擬大量用戶隨機(jī)訪問網(wǎng)頁的行為，并通過統(tǒng)計各節(jié)點的被訪問次數(shù)估算PageRank的近似值.典型的蒙特卡羅方法[12]包括循環(huán)起點的全路徑算法、隨機(jī)起點的蒙特卡羅算法等.它們具有易于并行化的特點，且能夠以較小的計算開銷盡快地得到滿足精度要求的近似結(jié)果.

相關(guān)的研究結(jié)論已證明[12]相較于其他蒙特卡羅算法，循環(huán)起點的全路徑蒙特卡羅算法具有更高的計算效率，因此在已有PageRank算法優(yōu)化研究[18]中常被作為算法改進(jìn)的基礎(chǔ).該算法的計算方法更適于引入增量計算的思想.本文工作也將循環(huán)起點的全路徑算法作為蒙特卡羅算法的代表，簡稱為基準(zhǔn)蒙特卡羅算法，用BasicPR表示.BasicPR計算PageRank的方法是由每個節(jié)點為起點啟動R個隨機(jī)游走過程，隨機(jī)游走中的每一步以c的概率停止或走到等概率地隨機(jī)選中的某個鄰居節(jié)點，并以此選中的節(jié)點為起點繼續(xù)這個隨機(jī)游走過程.對于有n個網(wǎng)頁的情形，共進(jìn)行n×R次隨機(jī)游走，當(dāng)所有隨機(jī)游走過程都停止時，統(tǒng)計任意節(jié)點u的訪問次數(shù)VT(u)，用VT(u)除以所有節(jié)點的訪問次數(shù)的總和，就得到節(jié)點u的PageRank的近似結(jié)果.通過增加R，BasicPR的結(jié)果可以足夠接近PageRank的真實值.IncPR使用了和BasicPR相同的隨機(jī)游走方法并在其基礎(chǔ)上引入了增量計算思想加以改進(jìn).

1.2增量PageRank算法相關(guān)研究

為保證頻繁變化的網(wǎng)絡(luò)上獲得滿足時效性要求的PageRank值，通常需要反復(fù)進(jìn)行PageRank計算，從而造成對計算資源的巨大消耗.為解決這一問題，一些改進(jìn)的PageRank算法被提出.這些算法大致可以被歸納為4類:

1) 利用已有結(jié)果加速迭代收斂

Kamvar等人[19]提出了一種基于AitkenΔ2的推斷方法加快收斂的算法,該算法的收斂效率受變化數(shù)據(jù)位置影響，效率的提升并不明顯[18].Ohsaka等人[14]提出了一種通過重用已有結(jié)果的Guass-Southwell方法，該方法能夠提升算法的收斂速度，但該算法并沒有討論節(jié)點變化的情況的處理方法.

2) 控制及利用變化的數(shù)據(jù)的影響范圍

此類算法[20-23]通常將整個圖按照某種策略劃分成若干相互連通的子圖，當(dāng)某個子圖內(nèi)發(fā)生變化時，算法盡量將計算操作控制在子圖內(nèi)部，對其他子圖不產(chǎn)生影響或影響較小，從而達(dá)到降低計算量的目的.它們的局限性在于算法的表現(xiàn)受圖結(jié)構(gòu)的影響較大，且維護(hù)有效的圖劃分也比較困難.

3) 基于蒙特卡羅方法的增量改進(jìn)

與線性代數(shù)方法相比，蒙特卡羅方法顯然更易于按照增量計算的思想進(jìn)行改進(jìn)[12].Bahmani等人提出算法[18]保存之前的隨機(jī)游走路徑，當(dāng)數(shù)據(jù)發(fā)生變化時，根據(jù)圖的變化情況對隨機(jī)游走路徑進(jìn)行部分更新.Bahmani的算法假設(shè)圖中的邊隨機(jī)地逐條到達(dá)，每當(dāng)一條邊到達(dá)即進(jìn)行計算，當(dāng)累計增加n條邊時，處理包含|V|個節(jié)點的圖數(shù)據(jù)，該算法的時間復(fù)雜度為O(|V|lnnc2).Lofgren等人[24]在Bahmani等人工作[18]的基礎(chǔ)上，對算法復(fù)雜度的分析進(jìn)行了補(bǔ)充.該算法是一種高效的增量PagaRank算法，能有效應(yīng)對節(jié)點和邊發(fā)生變化的情況，但其保存隨機(jī)游走路徑的歷史數(shù)據(jù)的做法也引入了較大的存儲開銷.

4) 其他方法

Tong等人[25]提出了一種適合于二分圖的更新PageRank值的方法，該方法在|V|×l的圖上能夠獲得O(l2)的時間復(fù)雜度，然而互聯(lián)網(wǎng)和社交網(wǎng)絡(luò)中的l=|V|，當(dāng)n條邊到達(dá)時，更新的代價為O(n|V|2)，并不適合擴(kuò)展到大規(guī)模圖數(shù)據(jù)中來.Mcsherry等人[26]將多種啟發(fā)算法應(yīng)用到迭代算法中，以增量的更新操作計算流數(shù)據(jù)上的PageRank值，但該算法在控制計算量的情況下不能保證結(jié)果精度.

綜上，已有的增量PageRank算法，都需要消耗額外的存儲空間.本文提出的IncPR并不需要額外的存儲空間，且相較于已有的高效增量PageRank算法，IncPR的時間復(fù)雜度更低，在計算效率和存儲開銷2個方面優(yōu)勢明顯.

2　增量PageRank計算模型

為降低頻繁變化的海量數(shù)據(jù)集上反復(fù)計算PageRank的資源消耗，節(jié)約計算成本，本文提出了一種增量PageRank算法——IncPR.本節(jié)首先以一個示例介紹基于增量計算思想的PageRank計算方法，接著給出IncPR的計算模型的形式化概述.

2.1增量PageRank計算示例

增量PageRank計算將每一次數(shù)據(jù)更新作為一個新時刻.假設(shè)時刻t圖G形如圖1(a)所示，其中實線表示時刻t-1的圖數(shù)據(jù)，虛線表示的邊e3,5是在時刻t新增加的.圖1(b)表示時刻t-1使用BasicPR得到的隨機(jī)游走路徑的集合.

在使用BasicPR計算時刻t的圖數(shù)據(jù)時，節(jié)點5在隨機(jī)游走中被訪問的機(jī)會較時刻t-1增大.如果以圖1(b)所示的隨機(jī)游走路徑當(dāng)作時刻t的初始路徑，那么僅需要更改部分路徑(每次訪問節(jié)點3后的隨機(jī)游走路徑)即可以得到符合時刻t各節(jié)點的被訪問概率的隨機(jī)游走路徑.即每當(dāng)遇到隨機(jī)游走路徑中出現(xiàn)節(jié)點3，即按照時刻t的圖，為節(jié)點3重新選擇下一步的節(jié)點，并更新之后的隨機(jī)游走路徑.這樣即可得到如圖1(c)所示的隨機(jī)游走路徑.盡管這個集合是由圖1(b)變化來的，但該集合中各節(jié)點被訪問的概率和在時刻t的圖上重新產(chǎn)生的隨機(jī)游走路徑集合相等，其概率都是由圖的拓?fù)涮卣骱碗S機(jī)游走的停止概率參數(shù)共同決定的.

Fig. 1　An example of computing PageRank incrementally.圖1　增量PageRank計算示例

Fig. 2　Overview of incremental computation of PageRank.圖2　增量PageRank計算模型

基于這種考慮，就可以將增量計算的思想引入PageRank的計算過程.以時刻t-1的BasicPR得到的隨機(jī)游走路徑為基礎(chǔ)，在發(fā)生變化的邊(或節(jié)點)所影響的路徑上采用相同的隨機(jī)游走過程更新隨機(jī)游走路徑，并重新計算PageRank得到新結(jié)果.這樣的增量計算方式，避免了重新從頭生成全圖的隨機(jī)游走路徑，降低了計算量.這也是已有的基于蒙特卡羅方法的增量PageRank算法[12,18,24]的基本計算過程.此類算法能夠降低PageRank的計算量，但需要較大的存儲開銷來保存隨機(jī)游走路徑.

而從節(jié)點的訪問概率的角度觀察，對時刻t的圖進(jìn)行計算時，與時刻t-1相比，每次訪問節(jié)點3后，節(jié)點5被訪問的概率增加，節(jié)點6被訪問的概率減少，而且節(jié)點5被訪問的概率的增加量和節(jié)點6減少的量基本相當(dāng).這一特點即是IncPR的設(shè)計基礎(chǔ)之一.

2.2增量PageRank計算模型概述

IncPR是一種基于增量思想的PageRank算法，易于并行化實現(xiàn).與已有的基于蒙特卡羅算法的增量PageRank算法不同，IncPR并不需要保存任何隨機(jī)游走路徑的歷史信息.它利用之前一個時刻已經(jīng)得到的PageRank向量，逆推得到蒙特卡羅模擬的節(jié)點訪問次數(shù)統(tǒng)計，結(jié)合圖數(shù)據(jù)的變化情況，增量地更新得到新圖上的節(jié)點訪問次數(shù)統(tǒng)計，進(jìn)而更新PageRank的計算結(jié)果.

IncPR的計算過程借助于這樣的事實，即蒙特卡羅算法中節(jié)點的訪問次數(shù)的期望具有穩(wěn)定性[11]，來保證其正確性(相關(guān)證明見4.1節(jié)).IncPR的計算過程本質(zhì)上與2.1節(jié)中的增量計算過程類似，即以受增量影響的任意節(jié)點v為起點，生成若干新路徑片段，并用新路徑片段替換舊路徑片段的過程.

IncPR能有效地處理圖中節(jié)點和邊的增加與刪除的情況，且由于能較大程度地利用之前的結(jié)果，降低重復(fù)計算，因此該算法能夠有效地減少圖數(shù)據(jù)變更后重計算PageRank值的計算量.

IncPR在變化的圖數(shù)據(jù)上進(jìn)行增量的Page-Rank計算的過程，可以形式化地描述為以下的增量計算工作模型，如圖2所示.對于圖G(V,E),令時刻t圖的快照為Gt(Vt,Et).圖的變化部分ΔGt=diff(Gt-1,Gt)={ΔVt,ΔEt}.相應(yīng)地，從Gt得到的PageRank結(jié)果記作PRt.IncPR假設(shè)ΔGt已知，PRt-1已知，并通過預(yù)處理操作pre(PRt-1)得到BasicPR處理Gt-1時得到的所有節(jié)點的訪問次數(shù)的集合VTt-1.

IncPR算法以Gt,ΔGt和VTt-1為輸入，在VTt-1的基礎(chǔ)上，結(jié)合Gt,ΔGt采用改進(jìn)的蒙特卡羅方法增量地更新ΔGt對于PageRank新值的影響，最終得到新的PageRank計算結(jié)果PRt.一般使用Xt代表符號X在時刻t對應(yīng)的對象集合，而使用|X|代表集合X的元素的個數(shù).

VTt=SVTt×PRt.

(4)

預(yù)處理可以按照式(4)的方式求得VTt-1.其中，SVTt是時刻t的蒙特卡羅模擬中所有節(jié)點訪問次數(shù)的總和，SVTt=|Vt|Rc.值得注意的是，式(4)具有普遍性，即使PRt-1并不是通過蒙特卡羅方法得到，也可以通過式(4)得到VTt-1.也就是說IncPR可以利用任意PageRank算法得到的結(jié)果.

3　IncPR：增量PageRank算法

IncPR通過重用當(dāng)前已有的計算結(jié)果初始化節(jié)點的訪問次數(shù)，根據(jù)圖數(shù)據(jù)的變化對最終結(jié)果進(jìn)行計算.對于圖數(shù)據(jù)變化的不同情況，采用不同的計算策略.本文將圖的變化分為2種情況：1)邊的變化,僅有邊的增加和刪除；2)點的變化,節(jié)點和邊均有增加和刪除.本節(jié)將分別介紹對這2種情況的處理方法.

3.1IncPR處理邊的變化

IncPR處理邊的變化時采取2個主要步驟:

1) 對于每條變化的邊，按一定策略更新某些節(jié)點的訪問次數(shù)；

2) 訪問次數(shù)被更新的節(jié)點，按照訪問次數(shù)的更新量進(jìn)行若干次隨機(jī)游走，將新生成的隨機(jī)游走路徑上的節(jié)點的訪問次數(shù)(依據(jù)一定的原則)增或減1.

Fig. 3　Three cases of changing edges.圖3　邊變化的3種情況

圖3展示了一個節(jié)點上邊的變化的3種典型情況(與邊的變化無關(guān)的節(jié)點和邊被省略)，圖3(a)表示時刻t-1的圖數(shù)據(jù)Gt-1.圖3(b)(c)(d)表示時刻t的圖數(shù)據(jù)Gt，分別描繪了增加一條邊、刪除一條邊、同時增加刪除多條邊的示例.

為了利用時刻t-1的訪問次數(shù)得到時刻t的結(jié)果，節(jié)點v的訪問次數(shù)需要加上期望的變化量，節(jié)點w,s的訪問次數(shù)平均分?jǐn)俈T(v)t的增加量，作為各自訪問次數(shù)的減少量.當(dāng)VT(v)t,VT(w)t和VT(s)t都更新完畢，則按照步驟2操作，s,v和w分別進(jìn)行與各自訪問次數(shù)更新數(shù)量相等的隨機(jī)游走，從v發(fā)出的新隨機(jī)游走路徑上的節(jié)點的訪問次數(shù)增1，表示新路徑的添加；從s和w發(fā)出的新隨機(jī)游走路徑上的節(jié)點將訪問次數(shù)減1，表示舊路徑的刪除.上述操作的結(jié)果等價于經(jīng)過節(jié)點u的部分路徑被新路徑替換.總體上看，上述操作相當(dāng)于由于邊的增加，以s,v和w三節(jié)點為起點的隨機(jī)游走路徑中，從u獲得的訪問次數(shù)的重分配，重分配的結(jié)果與在圖Gt上重新進(jìn)行隨機(jī)游走分配節(jié)點u發(fā)出訪問的情況相當(dāng).

邊刪除情況與邊增加情況的處理辦法類似.區(qū)別僅在于訪問次數(shù)的增減數(shù)量和操作順序.如圖3(a)(c)所示，當(dāng)邊eu,s被刪除時，節(jié)點s的訪問次數(shù)VT(s)t減少，減少量的期望等于(1-c)×VT(u)t-1|S(u)t-1|,相應(yīng)的節(jié)點w的訪問次數(shù)VT(w)t增加，增加量的期望等于VT(s)t的減少量.之后，分別以w,s為起點進(jìn)行對應(yīng)數(shù)量的隨機(jī)游走，來更新節(jié)點w,s的變化對其子節(jié)點的影響.以w,s為起點的隨機(jī)游走經(jīng)過的節(jié)點分別進(jìn)行加1和減1的操作表示新路徑的生成和舊路徑被替換.

結(jié)合邊的增加和刪除的情況，可以得到更一般化的處理方法.令eu,x表示變化(增加或刪除)的邊，M代表VT(x)t變化量的大小,對于u的其他鄰居y，令N代表VT(y)t變化量的大小，如式(5)(6)所示:

(5)

(6)

圖3(d)反映了在時刻t分別增加和刪除多條邊的情況.由蒙特卡羅方法的計算特點可知，多條邊分別增加和刪除的情況，可以視作多次發(fā)生增加單條邊和刪除單條邊的情況，按照上述處理單條邊增加和刪除的辦法依次處理即可.

算法1使用偽代碼描述了IncPR針對圖中邊的變化的處理邏輯.

算法1.ProcessIncEdges(Gt,diff(Gt-1,Gt),VTt-1,c).

輸入：Gt={Et,Vt}表示時刻t的圖數(shù)據(jù)、diff(Gt-1,Gt)={diff(E)+,diff(E)-}代表時刻t-1到時刻t圖數(shù)據(jù)的變化量(邊的增加和刪除)、VTt-1代表時刻t-1的節(jié)點訪問次數(shù)的集合、c是隨機(jī)游走的停止概率；

輸出：VTt為圖Gt的節(jié)點訪問次數(shù)的集合.

① 初始化VTt=VTt-1;

②ListSRW_Array〈node,count,tag〉;

③foreu,v∈diff(Gt-1,Gt)do

④ 由式(5)(6)計算M,N；

⑤ifeu,v∈diff(E)+do

⑥ SRW_Array.add(v,M,+);

⑦forw∈S(u)t-1do

⑧ SRW_Array.add(w,N,-);

⑨endfor

⑩else

3.2IncPR處理點的變化

節(jié)點的增加通常伴隨邊的增加，可分為新增節(jié)點有入邊和無入邊2種情況討論.如果新增加的節(jié)點沒有入邊，則只要按照與時刻t-1相同的隨機(jī)游走方法補(bǔ)上R次以新節(jié)點為起點的隨機(jī)游走，再更新節(jié)點的PageRank值即得到最終結(jié)果.但如果新增節(jié)點有入邊，則需要在上述處理的基礎(chǔ)上按照3.1節(jié)的方法處理.如圖4所示，圖4(a)(b)分別表示時刻t-1和時刻t的圖數(shù)據(jù)，這種情況可以視作2個過程的疊加：先增加一個節(jié)點和節(jié)點的出邊，得到如圖4(c)所示的過渡圖數(shù)據(jù)和對應(yīng)的PageRank結(jié)果；再增加節(jié)點的入邊.

Fig. 4　An example of disassembly of adding a node.圖4　節(jié)點增加等價于節(jié)點和邊分別增加

類似地，節(jié)點的刪除則可以看作2個過程：節(jié)點的刪除和與節(jié)點相連邊的刪除.而稍有不同的是，對于刪除節(jié)點的情況，只需對變化的邊按照3.1節(jié)中的方法處理，而不需要再重復(fù)地減去R次以被刪除節(jié)點為起點的隨機(jī)游走對其他節(jié)點的影響，這個操作的影響在處理被刪除的邊時已被處理.

綜上，本文提出的IncPR可以概括為2個步驟：1)處理新增節(jié)點和節(jié)點的出邊；2)按照3.1的方法處理變化的邊.算法2為IncPR的偽代碼描述.

算法2.IncPR(Gt,diff(Gt-1,Gt),VTt-1,c,R).

輸入：Gt={Et,Vt}表示時刻t的圖數(shù)據(jù)、diff(Gt-1,Gt)={diff(E)+,diff(E)-,diff(V)+,diff(V)-}為時刻t-1到時刻t圖數(shù)據(jù)的變化量(邊和節(jié)點的增加和刪除)、VTt-1為時刻t-1得到的被訪問次數(shù)的集合、c是隨機(jī)游走的停止概率、R是各節(jié)點開始的隨機(jī)游走次數(shù);

輸出：PRt為圖Gt的PageRank向量.

① 初始化VTt=VTt-1;*新增節(jié)點的訪問次數(shù)為0*

②foru∈diff(V)+do

③ count=R;

④whilecount>0do

⑤ 以u為起點進(jìn)行停止概率為c的隨機(jī)游走，得到隨機(jī)游走路徑L;

⑥ 對任意節(jié)點yinL，VT(y)t++;

⑦ count--;

⑧endwhile

⑨endfor

4　算法正確性及時間復(fù)雜度分析

4.1算法的正確性證明

IncPR是一種增量的蒙特卡羅模擬算法，基于模擬的PageRank算法得到的結(jié)果是近似值.類似于文獻(xiàn)[11,18]中對BasicPR正確性的證明，本文證明了IncPR與BasicPR計算得的節(jié)點的訪問次數(shù)的期望相等且IncPR計算得到節(jié)點的訪問次數(shù)與真實的訪問次數(shù)足夠接近,這樣即證明IncPR是正確的.

定理1. 對于任意節(jié)點v, 在圖Gt上使用IncPR得到的訪問次數(shù)的期望E[VT(v)IncPR]，與使用BasicPR計算得到的訪問次數(shù)的期望E[VT(v)BasicPR]相等.

證明.IncPR在進(jìn)行計算時，利用圖Gt-1的訪問次數(shù)初始化Gt中節(jié)點的訪問次數(shù)，初始化的結(jié)果可以看作是從|Vt-1|個節(jié)點出發(fā)每個節(jié)點進(jìn)行R次隨機(jī)游走得到的|Vt-1|R條路徑.對于每一個變化的邊eu,v，IncPR會從節(jié)點u的子路徑中選出M條舊的子路徑，并生成M條新的子路徑替換舊路徑.此操作并沒有改變總路徑的起點和數(shù)量；對于每個變化的節(jié)點，IncPR沿用BasicPR從每個節(jié)點進(jìn)行R次隨機(jī)游走.因此，IncPR處理完Gt后，可以看作得到與BasicPR起點相同且對應(yīng)起點數(shù)目相同的路徑.

使用BasicPR計算圖Gt的PageRank值時，圖中任意節(jié)點v的訪問次數(shù)的期望為

(7)

其中，Pu,v表示以節(jié)點u為起點的隨機(jī)游走路徑經(jīng)過節(jié)點v的概率，αu表示以節(jié)點u為起點的隨機(jī)游走次數(shù)，由于2種算法每個節(jié)點都進(jìn)行了R次隨機(jī)游走，故任意節(jié)點u的αu=R.從節(jié)點u出發(fā)的隨機(jī)游走路徑經(jīng)過節(jié)點v的概率Pu,v是由每一條從節(jié)點u到節(jié)點v的路徑的概率累加得到的，如式(8)所示:

(8)

其中,qi j(i=u,w,…,y;j=w,x,…,v)如式(2)所示，表示節(jié)點u到節(jié)點w的跳轉(zhuǎn)概率，節(jié)點u選取某一條路徑訪問節(jié)點v的概率為該路徑上從u到v經(jīng)過的節(jié)點間的跳轉(zhuǎn)概率的乘積.BasicPR在進(jìn)行隨機(jī)游走時，任意節(jié)點間的跳轉(zhuǎn)概率只與圖結(jié)構(gòu)有關(guān)，若節(jié)點u，w之間存在連邊，則qu,w=(1-c)|S(u)|；IncPR在進(jìn)行隨機(jī)游走時，對于出邊發(fā)生變化的節(jié)點u，該節(jié)點的訪問次數(shù)按照期望值在子節(jié)點之間均勻分配，節(jié)點u到任意子節(jié)點的跳轉(zhuǎn)概率為(1-c)|S(u)|，這些節(jié)點與子節(jié)點間的跳轉(zhuǎn)概率與BasicPR中的相同；其他節(jié)點間的跳轉(zhuǎn)概率按照qu,w進(jìn)行處理，與BasicPR相等.因此，IncPR在得到|Vt|R條路徑時，任意節(jié)點間的跳轉(zhuǎn)概率均與BasicPR相同.2種算法在計算圖Gt的PageRank值時，任意節(jié)點間的Pu,v相等.

綜上，IncPR算法與BasicPR在計算相同圖數(shù)據(jù)的PageRank值時，任意節(jié)點的訪問次數(shù)的期望相等，定理1得證.

證畢.

定理2. 對于任意節(jié)點v, 在圖Gt上使用IncPR得到的節(jié)點v的PageRank值與節(jié)點v的PageRank的真實值非常接近，即有式(9)成立:

(9)

證明. 先討論R=1的情況(R>1的情況同理可證).假設(shè)隨機(jī)變量Xu是由u出發(fā)的隨機(jī)游走路徑上節(jié)點v的訪問次數(shù)的c倍.Yu是這條隨機(jī)游走路徑的長度.令Wu=cYu，xu=E[Xu].由于對于不同的節(jié)點u隨機(jī)變量Xu相互獨立，則有：

(10)

顯然有：0≤Xu≤Wu，E[Wu]=1.

則由期望的定義可知：

(11)

進(jìn)而得到：

E[et Xu]≤xuE[et Wu]+1-xu=

xu(E[et Wu]-1)+1.

(12)

由于對任意的y有1+y≤ey，因此可得到：

E[et Xu]≤e-xu(1-E[et Wu]).

(13)

由馬爾可夫不等式，可以得到：

(14)

類似地可以證明：

(15)

則定理2得證.

證畢.

綜合定理1，2可知，IncPR得到的計算結(jié)果能夠確保與BasicPR得到的結(jié)果同等正確.BasicPR計算PageRank的結(jié)果正確性在文獻(xiàn)[12]中已被證明，因此IncPR也具有與BasicPR同等的正確性.

4.2算法的時間復(fù)雜度分析

本節(jié)通過分析IncPR的處理過程，推導(dǎo)出其時間復(fù)雜度.使用IncPR計算PageRank向量時，對于每一個增加的節(jié)點，算法都會以該節(jié)點為起點進(jìn)行R次隨機(jī)游走；對于每一個變化的邊eu,v，都會以v為起點進(jìn)行M次隨機(jī)游走，作為新的子路徑；同時，會以u的其他子節(jié)點為起點進(jìn)行M次隨機(jī)游走，作為待被替換子路徑.一條變化的邊需要進(jìn)行2M次隨機(jī)游走，以更新結(jié)果.

因此，假設(shè)Gt在Gt-1的基礎(chǔ)上增加了m個節(jié)點且增加和刪除了共計n條邊，則增量算法需要進(jìn)行隨機(jī)游走的總次數(shù)TotalRW滿足式(16)，其中M按式(5)求得.

(16)

令TotalComp表示IncPR的計算量大小，則有式(17)，其中E[X]代表隨機(jī)游走路徑長度的期望值.

TotalComp=TotalRW×E[X].

(17)

由于圖中所有節(jié)點至少包含一個出邊(懸掛點被看作包含|Vt|個出邊)，發(fā)生變化邊的起點至少增加或刪除了一條邊.因此對于任意變化的邊eu,v的起點u，有：

|S(u)t-1∪S(u)t|≥2，

(18)

因此，可進(jìn)一步推導(dǎo)出：

(19)

(20)

令E[VT]表示節(jié)點訪問次數(shù)的均值.節(jié)點訪問次數(shù)與節(jié)點總數(shù)的乘積為總的訪問次數(shù)，總的訪問次數(shù)等于隨機(jī)游走路徑總長度，故E[VT]=RE[X].由于隨機(jī)游走路徑長度服從參數(shù)為c的幾何分布，故E[X]=1c，E[VT]=Rc.因此有:

TotalComp≤Rmc+Rnc2.

(21)

當(dāng)圖G發(fā)生變化的增量包含m個節(jié)點和n條邊時，IncPR算法根據(jù)圖G的中間數(shù)據(jù)更新結(jié)果的時間復(fù)雜度為O((cm+n)Rc2).

5　性能測試與分析

5.1實驗設(shè)置

本文分別以Bahmani提出的增量PageRank算法[19]和BasicPR作為比較基準(zhǔn)，對IncPR的結(jié)果正確性和計算量大小進(jìn)行了實驗.實驗在基于BSP計算模型的Hama分布式計算框架[27]上實現(xiàn)了IncPR和上述2種對比算法.Hama的體系結(jié)構(gòu)如圖5所示.實驗使用的Hama集群由6臺同構(gòu)節(jié)點組成，每個節(jié)點配備intel-i7 2600CPU、8GB內(nèi)存、2TB磁盤，并通過千兆以太網(wǎng)連接.各節(jié)點安裝Ubuntu14.04操作系統(tǒng)，主要的計算工具版本分別為Hama-0.6.4、zookeeper-3.4.6和Hadoop-1.2.1.

Fig. 5　Overview architecture of Hama.圖5　Hama 分布式計算框架體系結(jié)構(gòu)

實驗使用了多組具有不同應(yīng)用背景的真實數(shù)據(jù)集，對典型的數(shù)據(jù)集變化情況分別進(jìn)行了多組實驗，實驗結(jié)果驗證了IncPR的正確性和計算效率.權(quán)衡PageRank結(jié)果的精度和實驗運行時間，實驗選取參數(shù)R=20，c=0.15，默認(rèn)情況下，初始的PageRank結(jié)果由該參數(shù)下的BasicPR計算得到.

5.2評價指標(biāo)

實驗主要從算法的結(jié)果精度和計算量2個方面考慮，選取了2個評價指標(biāo)，以測試分析IncPR的正確性和計算效率.

1) 正確性指標(biāo)

類似于已有的相關(guān)研究工作[10,14]，本文定義算法正確性的評價指標(biāo)Err(Alg)如式(22).其中PR(u)代表由算法Alg得到的PageRank的計算結(jié)果，π(u)代表PageRank的真實值.顯然地，Err(Alg)的大小代表了算法Alg的結(jié)果的相對精度.對于相同的圖數(shù)據(jù)，Err(Alg)越小意味著算法得到的PageRank的計算結(jié)果的精度越高，即越接近真實的PageRank值.本文實驗中PageRank的真實值由PowerIteration算法計算獲得，參數(shù)ε=0.000 5.

(22)

2) 計算量指標(biāo)

本文定義Cost(Alg)作為算法計算效率的評價指標(biāo).基于蒙特卡羅的PageRank算法通過進(jìn)行大量的隨機(jī)游走來計算PageRank值，構(gòu)造隨機(jī)游走路徑是此類算法的主要開銷.由于隨機(jī)游走中每一步的開銷相同，算法的計算量可以由產(chǎn)生的隨機(jī)游走的總步數(shù)表示.本文實驗基于Hama框架實現(xiàn)，Page-Rank算法通過傳遞消息實現(xiàn)隨機(jī)游走，通過統(tǒng)計消息通信的總數(shù)即得到隨機(jī)游走的總步數(shù).Cost(Alg)的值即等于算法在Hama框架上的發(fā)送的消息的總數(shù).

5.3數(shù)據(jù)集及預(yù)處理

實驗使用了多組不同的真實圖數(shù)據(jù)集[28]，它們覆蓋了從P2P網(wǎng)絡(luò)到Web互聯(lián)網(wǎng)和社交網(wǎng)絡(luò)等多個不同應(yīng)用領(lǐng)域.數(shù)據(jù)集的主要特征參數(shù)詳見表1所示.類似于文獻(xiàn)[10]中的做法，在不影響實驗結(jié)果的準(zhǔn)確性和算法計算量的前提下，實驗對圖數(shù)據(jù)進(jìn)行了一定的預(yù)處理，將圖中所有的單向邊都改為雙向邊.

圖數(shù)據(jù)的變化包括點和邊的添加和刪除共4種情況.由于增量算法在處理增加刪除邊的2種操作類似(區(qū)別僅是在進(jìn)行隨機(jī)游走時經(jīng)過節(jié)點的操作)，因此實驗僅測試添加點和邊情況下算法的正確性和計算效率.僅增加邊的實驗中，先從原圖中隨機(jī)選擇最多10%的邊刪除，將得到的圖作為初始數(shù)據(jù)G，再從被刪除邊中，按固定比例(0.01%，0.05%，0.1%，0.5%，1%，5%，10%)隨機(jī)添加到圖G中作為變化后的圖數(shù)據(jù).增加點的實驗，以原圖為初始數(shù)據(jù)G，以G中的節(jié)點數(shù)為基準(zhǔn)，生成固定比例(0.01%，0.05%，0.1%，0.5%，1%，5%，10%)的新節(jié)點并添加到G中，隨機(jī)地為新節(jié)點選擇一條入邊和出邊.

Table 1　Main Parameters of Data Sets表1　數(shù)據(jù)集的主要特征參數(shù)

5.4結(jié)果準(zhǔn)確性

Fig. 6　Comparison of Err(Alg) with different proportion of ΔV.圖6　增加不同比例的節(jié)點的誤差比較

本節(jié)通過比較IncPR與Bahmani的增量算法和IncPR與BasicPR計算PageRank值的相對誤差的大小，來驗證IncPR的正確性.在比較IncPR與Bahmani的增量算法的正確性時，分別增加不同數(shù)量的邊比較2種算法的誤差，實驗表明2種算法具有相同量級的精度水平.在比較IncPR與BasicPR的正確性時，考慮在真實的數(shù)據(jù)集上，僅增加邊和增加點和邊2種情況下算法的正確性.此外，通過多組不同的實驗，驗證了不同的圖數(shù)據(jù)變化量、不同的初始結(jié)果精度對IncPR結(jié)果精度的影響.

如圖6所示，IncPR在結(jié)果精度上表現(xiàn)良好.當(dāng)增量規(guī)模較小時(小于1%)，IncPR和BasicPR的結(jié)果的誤差接近，隨著增加節(jié)點的比例的增大，IncPR與BasicPR的誤差的比在逐漸減小，這意味著IncPR在增加的點較多的情況下(5%和10%)得到比BasicPR更高的結(jié)果精度.最優(yōu)情況下，IncPR的誤差比BasicPR減小接近20%.

圖7反映了增加不同比例的邊(占原圖的0.01%到10%)的情況下，IncPR與BasicPR得到的結(jié)果誤差的比值.邊增加的情況下2種算法的誤差總體接近，僅有個別圖得到了最好情況下接近10%的精度提升.另一組增加不同數(shù)量的邊的實驗結(jié)果(如圖8所示)，也同樣驗證了IncPR得到與BasicPR的結(jié)果精度在相同量級的結(jié)論.

Fig. 7　Comparison of Err(Alg) with different proportion of ΔE.圖7　增加不同比例的邊的誤差比較

Fig. 8　Comparison of Err(Alg) with different number of ΔE.圖8　增加不同數(shù)量的邊的誤差比較

對于IncPR比BasicPR獲得的精度提升，一種合理的解釋是圖的變化一定程度地影響了其拓?fù)浣Y(jié)構(gòu)，BasicPR的結(jié)果精度受圖的變化的影響而略有上升，而IncPR采用增量的更新方法，避免了由圖的變化而引入更大的誤差，從而得到了更好的結(jié)果精度.圖9所反映的隨著節(jié)點的增加BasicPR的誤差上升，一定程度支持了這種解釋.

Fig. 9　Err(BasicPR) with different proportion of ΔV.圖9　增加不同比例的節(jié)點的BasicPR的結(jié)果誤差

此外，IncPR的一個有價值的特點是，其可以通過重用誤差較小的數(shù)據(jù)獲得精度較高的計算結(jié)果.這意味著如果以較大的計算代價計算出高精度的PageRank結(jié)果，再使用IncPR處理變化后的新圖，就可以利用較低的成本獲得新的高精度結(jié)果，相當(dāng)于將蒙特卡羅方法適于處理增量和適于并行化的特點與其他的計算代價大但結(jié)果精度高的PageRank算法結(jié)合了起來，可以充分發(fā)揮二者各自的優(yōu)勢.

圖10和圖11反映了當(dāng)以PI計算得到的PageRank向量作為初始結(jié)果時，增加固定比例的節(jié)點和邊的情況下分別得到的IncPR的結(jié)果誤差與BasicPR的誤差的比.顯然地，當(dāng)圖的變化量較小時(不超過1%)，IncPR得到的結(jié)果精度顯著優(yōu)于BasicPR，IncPR得到的結(jié)果精度接近PI算法，當(dāng)增量較大時(5%，10%)，最差情況IncPR的誤差也不到BasicPR的一半.

Fig. 10　Comparison of Err(Alg) with different proportion of ΔV (IncPR Starts from PI).圖10　增加不同比例的節(jié)點誤差比較(以PI結(jié)果作為初始值)

Fig. 11　Comparison of Err(Alg) with different proportion of ΔE (IncPR Starts from PI).圖11　增加不同比例的邊的誤差比較(以PI結(jié)果作為初始值)

由于篇幅所限，本文沒有給出IncPR與Bahmani的增量算法的正確性比較的數(shù)據(jù)，2種算法的結(jié)果誤差值相近.

5.5計算量對比

本文通過多組真實數(shù)據(jù)集上不同場景的實驗，分別比較了IncPR與Bahmani的增量算法及IncPR與BasicPR的計算量的大小，作為評價算法計算效率的標(biāo)準(zhǔn).

首先對IncPR與Bahmani的增量算法的計算量進(jìn)行了對比實驗，實驗結(jié)果如表2所示.實驗中令增加的邊數(shù)n分別為50,100和150，由于Bahmani的增量算法每增加一條邊就更新結(jié)果，因此，實驗中統(tǒng)計執(zhí)行n次Bahmani的增量算法累積的計算量.實驗結(jié)果均表明IncPR的計算量明顯優(yōu)于Bahmani的增量算法，實驗結(jié)果驗證了IncPR的時間復(fù)雜度優(yōu)于Bahmani的增量算法.雖然與Bahmani的增量算法的對比實驗中使用的n較小，但由理論分析可知，IncPR的計算量與n的大小呈線性關(guān)系，而Bahmani的增量算法的計算量與節(jié)點總數(shù)|V|的lnn倍呈線性關(guān)系，網(wǎng)絡(luò)數(shù)據(jù)中增量的比例占原數(shù)據(jù)比例較小，n?|V|.因此在n較大的情況下應(yīng)該會得到類似的結(jié)果.

Table 2　Performance Comparison of Bahmani’s and IncPR表2　Bahmani增量算法與IncPR計算量比較　K

進(jìn)而，本文分別在不同的數(shù)據(jù)變化量、初始結(jié)果精度等多種條件下進(jìn)行實驗，比較IncPR與BasicPR計算PageRank值的計算量大小，得到算法計算量的統(tǒng)計，作為評價算法計算效率的標(biāo)準(zhǔn).

Fig. 12　Comparison of Cost(Alg) with different proportion of ΔV.圖12　增加不同比例節(jié)點的計算量比較

圖12與圖13分別反映了增加固定比例的節(jié)點和邊的情況下，IncPR與BasicPR的計算量的比值.2組實驗數(shù)據(jù)都表現(xiàn)出相同的規(guī)律，IncPR的計算量明顯小于BasicPR.當(dāng)圖的變化量不超過0.01%時，IncPR的計算量最大僅為BasicPR的0.09%，當(dāng)圖的變化量達(dá)到10%時，IncPR的計算量最大僅相當(dāng)于BasicPR的20%.實驗結(jié)果表明IncPR能有效地降低PageRank計算的計算量，提高計算效率.

Fig. 13　Comparison of Cost(Alg) with different proportion of ΔE.圖13　增加不同比例邊的計算量比較

圖14反映了增加固定數(shù)量的邊的情況下，IncPR的計算量的變化趨勢，不同數(shù)據(jù)集上的多組實驗反映出相似的規(guī)律，即計算量和邊的變化量基本符合線性正比例關(guān)系，與理論分析得到的算法的時間復(fù)雜度大致相符.

Fig. 14　Relationship of Cost(IncPR) and the number of ΔE.圖14　增加邊的數(shù)量與增量算法計算量的關(guān)系

6　總　　結(jié)

旨在降低頻繁變化的海量數(shù)據(jù)集上反復(fù)計算PageRank帶來的資源消耗，本文提出了一種基于增量計算思想的并行PageRank算法——IncPR.IncPR在時間復(fù)雜度上優(yōu)于已有的相關(guān)算法，且不引入額外的存儲開銷.理論分析及基于真實圖數(shù)據(jù)的大量分布式計算實驗均驗證了IncPR的正確性和計算效率，在保證結(jié)果精度的前提下，較之于已有的增量PageRank算法和非增量的PageRank算法，IncPR能夠顯著地降低計算量.此外，IncPR的設(shè)計思想也可以用于改進(jìn)基于蒙特卡羅模擬技術(shù)的其他算法(如個性化PageRank、單源最短路徑算法等)，這也將有利于降低此類應(yīng)用問題的計算成本.

[1]ChinaComputerFederationExpertCommitteeofBigData.WhitePaperonBigDataandIndustryDevelopmentofChina2013[M//OL].Beijing:ChinaComputerFederation, 2013.[2016-03-20].http://www.ccf.org.cn//sites//ccf//ccfziliao.jsp?contentId=2774793649105 (inChinese)

(中國計算機(jī)學(xué)會大數(shù)據(jù)專家委員會. 中國大數(shù)據(jù)與產(chǎn)業(yè)發(fā)展白皮書2013[M//OL]. 北京: 中國計算機(jī)學(xué)會, 2013. [2016-03-20].http://www.ccf.org.cn//sites//ccf//ccfziliao.jsp?contentId=2774793649105)

[2]GoogleInc.Googleinsidesearch-google[EB//OL].[2016-03-20].https://www.google.com//intl//ta//insidesearch//howsearchworks//thestory//index.html

[3]KunderM.ThesizeoftheworldwideWeb:EstimatedsizeofGoogle’sindex[EB//OL].[2016-03-20].http://www.worldwidewebsize.com//

[4]WorldWideWebFoundation.Internetlivestats[EB//OL].[2016-03-20].http://www.internetlivestats.com//

[5]PageL,BrinS,MotwaniR,etal.ThePageRankcitationranking:BringingordertotheWeb, 422[R].Stanford,CA:StanfordInfoLab, 1999

[6]DeanJ,GhemawatS.MapReduce:Simplifieddataprocessingonlargeclusters[J].CommunicationsoftheACM, 2008, 51(1): 107-113

[7]ZahariaM,ChowdhuryM,FranklinMJ,etal.Spark:Clustercomputingwithworkingsets[C] //Procofthe2ndUSENIXWorkshoponHotTopicsinCloudComputing(HotCloud).Berkeley,CA:USENIXAssociation, 2010: 10-10

[8]MalewiczG,AusternMH,BikAJC,etal.Pregel:Asystemforlarge-scalegraphprocessing[C] //Procofthe2010ACMSIGMODIntConfonManagementofData.NewYork:ACM, 2010: 135-146

[9]GleichD,ZhukovL,BerkhinP.FastparallelPageRank:Alinearsystemapproach, 38[R].Berkeley,CA:Yahoo!Research, 2004

[10]BahmaniB,ChakrabartiK,XinD.Fastpersonalizedpagerankonmapreduce[C] //Procofthe2011ACMSIGMODIntConfonManagementofData.NewYork:ACM, 2011: 973-984

[11]SarmaAD,MollaAR,PanduranganG,etal.Fastdistributedpagerankcomputation[J].TheoreticalComputerScience, 2015, 561 (PartB): 113-121

[12]AvrachenkovK,LitvakN,NemirovskyD,etal.MonteCarlomethodsinPageRankcomputation:Whenoneiterationissufficient[J].SIAMJournalonNumericalAnalysis, 2007, 45(2): 890-904

[13]ApacheSoftwareFoundation.ApacheHama[EB//OL].[2016-03-20].https://hama.apache.org//

[14]OhsakaN,MaeharaT,KawarabayashiK.EfficientPageRanktrackinginevolvingnetworks[C] //Procofthe21stACMSIGKDDIntConfonKnowledgeDiscoveryandDataMining.NewYork:ACM, 2015: 875-884

[15]LangvilleAN,MeyerCD.Deeperinsidepagerank[J].InternetMathematics, 2004, 1(3): 335-380

[16]SarmaAD,GollapudiS,PanigrahyR.EstimatingPageRankongraphstreams[J].JournaloftheACM, 2011, 58(3): 1165-1182

[17]SarlósT,BenczúrAA,CsalogányK,etal.ToRandomizeornottorandomize:Spaceoptimalsummariesforhyperlinkanalysis[C] //Procofthe15thIntConfonWorldWideWeb.NewYork:ACM, 2006: 297-306

[18]BahmaniB,ChowdhuryA,GoelA.Fastincrementalandpersonalizedpagerank[J].ProceedingsoftheVLDBEndowment, 2010, 4(3): 173-184

[19]KamvarSD,HaveliwalaTH,ManningCD,etal.ExtrapolationmethodsforacceleratingPageRankcomputations[C] //Procofthe12thIntConfonWorldWideWeb.NewYork:ACM, 2003: 261-270

[20]KamvarS,HaveliwalaT,ManningC,etal.ExploitingtheblockstructureoftheWebforcomputingpagerank, 579[R].Stanford,CA:StanfordInfoLab, 2003

[21]LangvilleA,MeyerC.UpdatingPageRankusingthegroupinverseandstochasticcomplementation,CRSC-TR02-32[R].Raleigh:MathematicsDepartment,NorthCarolinaStateUniversity, 2002

[22]LangvilleAN,MeyerCD.Updatingpagerankwithiterativeaggregation[C] //Procofthe13thIntWorldWideWebConfonAlternateTrackPapers&Posters.NewYork:ACM, 2004: 392-393

[23]DesikanP,PathakN,SrivastavaJ,etal.IncrementalPageRankcomputationonevolvinggraphs[C] //SpecialInterestTracksandPostersofthe14thIntConfonWorldWideWeb.NewYork:ACM, 2005: 1094-1095

[24]LofgrenP.OnthecomplexityoftheMonteCarlomethodforincrementalPageRank[J].InformationProcessingLetters, 2014, 114(3): 104-106

[25]TongH,PapadimitriouS,PhilipSY,etal.Proximitytrackingontime-evolvingbipartitegraphs[C] //Procofthe8thSIAMIntConfonDataMining.Philadelphia:SocietyforIndustrialandAppliedMathematicsPublications, 2008: 704-715

[26]McsherryF.AuniformapproachtoacceleratedPageRankcomputation[C] //Procofthe14thIntConfonWorldWideWeb.NewYork:ACM, 2005: 575-582

[27]SeoS,YoonEJ,KimJ,etal.Hama:Anefficientmatrixcomputationwiththemapreduceframework[C] //Procofthe2ndIEEEIntConfonCloudComputingTechnologyandScience,CloudCom.Piscataway,NJ:IEEE, 2010: 721-726

[28]JureLeskovec.Stanfordlargenetworkdatasetcollection[EB//OL].[2016-03-20].http://snap.stanford.edu//data//index.html

JiangShuangshuang,bornin1990.Master.Hermainresearchinterestsincludedistributedcomputing,incrementalcomputinganddatamining.

LiaoQun,bornin1987.PhDcandidate.Hismainresearchinterestsincludedistributedcomputing,taskschedulinganddatamining.

YangYulu,bornin1961.ProfessorandPhDsupervisorinNankaiUniversity.Hismainresearchinterestsincludeinterconnectionnetwork,parallelanddistributedprocessing.

LiTao,bornin1977.PhDandassociateprofessorinNankaiUniversity.MemberoftheACMandtheIEEEComputerSociety,SeniormemberofChinaComputerFederation.Hismainresearchinterestsincludeparallelanddistributedprocessing,high-performancecomputingandnetworkinformationmining.

IncPR:AnIncrementalParallelPageRankAlgorithm

JiangShuangshuang,LiaoQun,YangYulu,andLiTao

(College of Computer and Control Engineering, Nankai University, Tianjin 300350)

PageRankalgorithmplaysanimportantroleinvariousareassuchasinformationretrievalandsocialnetworkanalysis.ThecontinuouslyincreasingsizeofnetworksandthetimelinessrequirementsmakeitbringenormouscomputationaloverheadtorepeatcalculatingPageRankforamassiveandevolvingnetwork.Therefore,IncPR,aPageRankalgorithmbasedontheideaofincrementalcomputationmodelisproposed.IncPRreusesexistingresultsfrompreviouscomputationandmodifiesPageRankvaluesaccordingtothechangedpartofdatasetsaccumulativelyviaanextendedMonteCarlomethod,whichcaneffectivelyavoidreduplicatedcomputationandimprovetheperformanceofPageRankcomputingwithnoadditionalstorageoverhead.TheoreticalanalysisshowsthatthecomputationalcomplexityofIncPRprocessinganevolvingnetworkwithmnodesandnedgeschangedisO((cm+n)Rc2),wherecistheresetprobabilityandRisthenumberofrandomwalksstartingfromeachnode.ThecomputationalcomplexityofIncPRislowerthanotherexistingrelatedalgorithms.Ourevaluationswithtypicalreal-worldgraphsuponaHamaclusteralsodemonstratethatIncPRobtainsPageRankvalueswithequal(orevenhigher)accuracyasthebaselineMonteCarloPageRankalgorithmandreducestheamountofcomputationsignificantly.Inexperimentswith0.01%datachanged,IncPRreducesover99.9%amountofcomputation.

PageRank;Webmining;incrementalcomputing;MonteCarloalgorithm;parallelanddistributedprocessing

2016-03-21；

2016-05-25

TP391