基于Graphlab的網(wǎng)絡(luò)圖關(guān)鍵節(jié)點(diǎn)發(fā)現(xiàn)算法研究

高壯良，呂雁飛，張鴻

?

基于Graphlab的網(wǎng)絡(luò)圖關(guān)鍵節(jié)點(diǎn)發(fā)現(xiàn)算法研究

高壯良1，呂雁飛2，張鴻2

（1. 北京航空航天大學(xué)計(jì)算機(jī)學(xué)院，北京 100191；2. 國家計(jì)算機(jī)網(wǎng)絡(luò)應(yīng)急技術(shù)處理協(xié)調(diào)中心，北京 100029）

針對(duì)橋接中心度的計(jì)算特點(diǎn)設(shè)計(jì)了一種分布式的網(wǎng)絡(luò)圖關(guān)鍵節(jié)點(diǎn)發(fā)現(xiàn)算法（DABC），并基于Graphlab進(jìn)行了實(shí)現(xiàn)。算法具有良好的擴(kuò)展性，由于能夠利用集群的內(nèi)存資源，算法能處理的圖規(guī)模與集群的大小成正比，并且該算法利用并行處理大幅度提升了計(jì)算速度。實(shí)驗(yàn)表明，與傳統(tǒng)的基于單機(jī)實(shí)現(xiàn)的關(guān)鍵節(jié)點(diǎn)發(fā)現(xiàn)算法相比，算法可以獲得高達(dá)4倍的性能提升。

關(guān)鍵節(jié)點(diǎn)；橋接中心度；分布式算法；Graphlab

1 引言

網(wǎng)絡(luò)圖中的關(guān)鍵節(jié)點(diǎn)在圖的組織和信息傳播中起著樞紐作用，對(duì)圖中關(guān)鍵節(jié)點(diǎn)進(jìn)行標(biāo)識(shí)和發(fā)現(xiàn)是圖中的一個(gè)重要研究方向，有著豐富的應(yīng)用場(chǎng)景和重要的應(yīng)用價(jià)值。例如，社交網(wǎng)絡(luò)成員中的關(guān)鍵節(jié)點(diǎn)通常具有更大的影響力或者更強(qiáng)的信息傳播能力，找到社交網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)可以分析甚至影響社交網(wǎng)絡(luò)中的消息傳播。在計(jì)算機(jī)網(wǎng)絡(luò)拓?fù)渲袑?duì)關(guān)鍵節(jié)點(diǎn)進(jìn)行保護(hù)可以提升整個(gè)網(wǎng)絡(luò)的頑健性，反之對(duì)關(guān)鍵節(jié)點(diǎn)進(jìn)行攻擊會(huì)起到事半功倍的效果。此外，在反恐斗爭(zhēng)中，關(guān)鍵節(jié)點(diǎn)研究也對(duì)重要恐怖分子的發(fā)現(xiàn)等[1]有著輔助作用。

識(shí)別網(wǎng)絡(luò)圖中關(guān)鍵節(jié)點(diǎn)的一類重要方法是計(jì)算圖中節(jié)點(diǎn)的中心度，包括距離中心度、譜中心度和橋接中心度等。其中，橋接中心度是研究關(guān)鍵節(jié)點(diǎn)中常用的一種中心度度量，它可以用來衡量節(jié)點(diǎn)在網(wǎng)絡(luò)圖連通和信息傳播中的重要程度。具有較高橋接中心度的節(jié)點(diǎn)代表著該點(diǎn)對(duì)圖中的其他頂點(diǎn)的控制能力越大。近年來，橋接中心度在網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)重要節(jié)點(diǎn)度量、關(guān)系網(wǎng)絡(luò)研究等領(lǐng)域得到了廣泛的應(yīng)用。本文選用橋接中心度算法作為研究對(duì)象，下文如無特別說明，提到的中心度均為橋接中心度。

針對(duì)不同場(chǎng)景中的橋接中心度計(jì)算，相關(guān)工作已經(jīng)給出了多種計(jì)算方法[2~9]。但是傳統(tǒng)的計(jì)算橋接中心度的方法主要為集中式算法，即假設(shè)圖存儲(chǔ)在一臺(tái)物理機(jī)上，并基于單機(jī)實(shí)現(xiàn)圖的存儲(chǔ)和計(jì)算。由于中心度計(jì)算算法的時(shí)間空間復(fù)雜度較高，集中式算法能夠處理的圖規(guī)模受到單機(jī)內(nèi)存大小的限制，而且單機(jī)有限的處理能力也很大程度上影響了算法的執(zhí)行效率。隨著圖規(guī)模的不斷增加，算法的處理效率下降明顯，嚴(yán)重影響了算法的應(yīng)用范圍，急需研究集群環(huán)境下的分布式算法。

分布式處理技術(shù)是目前的熱點(diǎn)研究方向，以MapReduce[10]為代表的分布式計(jì)算框架目前已變得非常流行，其在處理大規(guī)模數(shù)據(jù)方面有著相當(dāng)多的應(yīng)用。與此同時(shí)，一些分布式圖計(jì)算框架也不斷被提出，如Pregel[11]、Graphlab[12,13]、PowerGraph[14]，GraphX[15]等。這些分布式計(jì)算框架為開發(fā)者提供了很多的API來設(shè)計(jì)和實(shí)現(xiàn)自己的算法。本文針對(duì)關(guān)鍵節(jié)點(diǎn)發(fā)現(xiàn)的分布式算法進(jìn)行了研究。

本文設(shè)計(jì)了計(jì)算橋接中心度的分布式算法(DABC, distributed algorithm for betweenness centrality)。在DABC算法中為圖頂點(diǎn)分布存儲(chǔ)在多臺(tái)物理機(jī)器上，DABC算法設(shè)計(jì)了算法所需的數(shù)據(jù)結(jié)構(gòu)，節(jié)點(diǎn)間數(shù)據(jù)通信機(jī)制，結(jié)果收集機(jī)制等。算法基于分布式圖計(jì)算框架Graphlab進(jìn)行了實(shí)現(xiàn)。由于可以使用分布式環(huán)境中多臺(tái)服務(wù)器的內(nèi)存資源，所以算法能夠處理的圖規(guī)模獲得了較大提升，并且可以隨集群規(guī)模擴(kuò)展。同時(shí)由于使用了并行處理技術(shù)，算法的計(jì)算效率也比集中式算法明顯增強(qiáng)。實(shí)驗(yàn)表明，在8臺(tái)服務(wù)器組建的集群中，分布式算法可以處理5倍于集中式算法所能處理的圖規(guī)模。由于支持并行處理，即使同在單機(jī)環(huán)境中，算法的處理速度也獲得了提升，最好情況下提升幅度達(dá)到4倍以上。

2 相關(guān)工作

有向圖中的橋接中心度是由Anthonisse等[2]在1971年首先提出。1977年，F(xiàn)reeman[3]將這一概念引入具有不連通節(jié)點(diǎn)的網(wǎng)絡(luò)中?，F(xiàn)在使用最廣泛的是Freeman提出的定義，即基于最短路徑的橋接中心度算法。在這種定義中首先計(jì)算所有節(jié)點(diǎn)對(duì)之間的最短路徑，在所有最短路徑中次數(shù)較多的節(jié)點(diǎn)擁有較高的橋接中心度。Carpenter等[4]在分析恐怖分子網(wǎng)絡(luò)時(shí)指出橋接中心度是需要解決的重要的問題。Brands[5]通過對(duì)橋接中心度算法的深入研究，在2001年提出了高效的橋接中心度算法。在Brands提出的算法基礎(chǔ)上，又產(chǎn)生了針對(duì)不同條件、不同類型圖結(jié)構(gòu)的變形算法[6]，包括proximal betweenness算法、bounded-distance betweenness算法、distance-scaled betweenness 算法、group betweenness算法等。2012年，Lee[7]第一次提出了針對(duì)無向圖的橋接中心度快速更新算法。同年，楊建祥[8]提出了社交網(wǎng)絡(luò)橋接中心度快速更新算法。Tan[9]等提出了一種新的適用于CREW PRAM 的并行橋接中心度算法，應(yīng)用于大規(guī)模網(wǎng)絡(luò)分析。這些算法的出現(xiàn)為分析圖結(jié)構(gòu)數(shù)據(jù)提供了方便，但是由于這些算法都未采用分布式處理技術(shù)，所以算法能夠處理的圖規(guī)模受到了較大限制，也影響了算法的應(yīng)用場(chǎng)景。

近年來，利用分布式計(jì)算框架處理圖數(shù)據(jù)已經(jīng)越來越流行。分布式計(jì)算框架也在不斷發(fā)展。Pregel[11]借鑒了Leslie Valiant于20世紀(jì)80年代提出的BSP計(jì)算模型，采用“計(jì)算—通信—同步”的模式完成機(jī)器學(xué)習(xí)的數(shù)據(jù)同步和算法迭代，計(jì)算由主機(jī)（master）負(fù)責(zé)分配任務(wù)和收集結(jié)果。同時(shí)采用了基于檢查點(diǎn)（checkpoint）的系統(tǒng)容錯(cuò)方法。Giraph[16]是應(yīng)用較為廣泛的Pregel克隆版本，在Pregel基礎(chǔ)上，增加了主節(jié)點(diǎn)計(jì)算、面向邊的輸入和核外計(jì)算等功能。Graphlab[12, 13]是最近比較流行的圖處理框架，它是一個(gè)分布式異步內(nèi)存共享系統(tǒng)，節(jié)點(diǎn)程序可以直接訪問該節(jié)點(diǎn)、相鄰邊和相鄰節(jié)點(diǎn)的信息，并通過阻止相鄰的程序同時(shí)運(yùn)行來保證結(jié)果的正確性。在Pregel和GraphLab的基礎(chǔ)上，PowerGraph[14]特別針對(duì)社交網(wǎng)絡(luò)圖數(shù)據(jù)的冪律分布特性，借鑒了GraphLab的內(nèi)存共享技術(shù)和Pregel的協(xié)同收集技術(shù)，提出了Gather-Apply-Scatter計(jì)算模型，分解高度數(shù)的節(jié)點(diǎn)并提供更大的并行性。

3 分布式關(guān)鍵節(jié)點(diǎn)發(fā)現(xiàn)算法

3.1 橋接中心度概念與計(jì)算方法

橋接中心度可以簡(jiǎn)單描述為網(wǎng)絡(luò)圖中的頂點(diǎn)在連接其他任意節(jié)點(diǎn)的最短路徑中所占的比重。假設(shè)網(wǎng)絡(luò)圖表示為，其中，節(jié)點(diǎn)用來表示圖中的頂點(diǎn)集合，表示節(jié)點(diǎn)之間的邊集合。在本文中只考慮無權(quán)圖，即認(rèn)為每條邊的權(quán)值均為1。對(duì)節(jié)點(diǎn)表示點(diǎn)和點(diǎn)之間的最短路徑的長度，若，。

以圖1中的有向圖為例，圖中包含5個(gè)頂點(diǎn)及5條邊，頂點(diǎn)處在到，到，到的最短路徑上，且到及到的最短路徑只有一條，到的最短路徑有2條，并且頂點(diǎn)在2條最短路徑上都有出現(xiàn)，所以頂點(diǎn)的橋接中心度根據(jù)定義可計(jì)算得到。

圖1 節(jié)點(diǎn)中心度示意

由節(jié)點(diǎn)中心度的定義可知，節(jié)點(diǎn)中心度計(jì)算可由計(jì)算圖中兩兩節(jié)點(diǎn)的最短路徑得到。目前計(jì)算中心度的最好算法是由Brandes[5]在2001年提出的，本文中稱為FABC算法(faster algorithm for betweenness centrality)。FABC的計(jì)算過程可以簡(jiǎn)單描述如下。

定義點(diǎn)對(duì)之間的依賴為

(3)

而單點(diǎn)依賴滿足

在本文的實(shí)驗(yàn)環(huán)境中，對(duì)一個(gè)包含3 000個(gè)頂點(diǎn)的無向圖，算法的計(jì)算時(shí)間約為500 s，而且隨著頂點(diǎn)數(shù)的不斷增加，計(jì)算時(shí)間也隨之增加。當(dāng)頂點(diǎn)數(shù)達(dá)到萬級(jí)別的時(shí)候，算法的時(shí)間消耗已變的不可接受。針對(duì)這個(gè)問題，本文提出了分布式的節(jié)點(diǎn)中心度計(jì)算方法。

3.2 DABC算法概述

在分布式系統(tǒng)中，一個(gè)完整的圖通常被切分為數(shù)個(gè)部分，由不同的機(jī)器進(jìn)行存儲(chǔ)和處理。實(shí)際應(yīng)用的圖數(shù)據(jù)多數(shù)呈冪律分布[17]，所以現(xiàn)在使用最廣泛的切分方式是按點(diǎn)切分[18]。Powergraph已經(jīng)證明相比于邊切分，點(diǎn)切分能帶來存儲(chǔ)、通信和計(jì)算上的優(yōu)勢(shì)。在點(diǎn)切分方式中，一個(gè)點(diǎn)被復(fù)制成幾份分別存儲(chǔ)在幾臺(tái)機(jī)器上，而邊不做復(fù)制。本文把其中的一個(gè)頂點(diǎn)稱作master，而它的復(fù)制點(diǎn)統(tǒng)一稱為mirror。master知道它的所有mirror信息，但是mirror只知道它隸屬于master的信息。如圖2所示，一個(gè)數(shù)據(jù)圖被切分到2個(gè)機(jī)器上，頂點(diǎn)與頂點(diǎn)被切分，其中頂點(diǎn)、為master，它們的mirror分別為1、1。

本文設(shè)計(jì)了分布式計(jì)算橋接中心度的算法。算法執(zhí)行過程中，所有機(jī)器并行計(jì)算得到最終結(jié)果。以圖2中的切分方式為例，圖3介紹了算法的執(zhí)行過程。

假設(shè)當(dāng)前頂點(diǎn)為執(zhí)行頂點(diǎn)，頂點(diǎn)接收到的消息，將其到的最短路徑個(gè)數(shù)更新為1，最短距離更新為1（每條邊權(quán)重默認(rèn)1）。如圖3(a)所示。然后將消息發(fā)給它的鄰居和1，1根據(jù)消息更新自己的及，1將自己的數(shù)據(jù)發(fā)送給，頂點(diǎn)根據(jù)消息更新自己的及，同時(shí)頂點(diǎn)也將自己的數(shù)據(jù)同步到1。直到頂點(diǎn)收到來自1和的消息，更新自己的為2及為3，如圖3(b)所示。

最后根據(jù)式（1）可求得這一次消息傳遞中的各個(gè)頂點(diǎn)的橋接中心度。

3.3 基于Graphlab的DABC算法實(shí)現(xiàn)

下面將本節(jié)中用到的符號(hào)及其含義列出，如表1所示。

表1 符號(hào)及含義

本文使用了Graphlab框架來實(shí)現(xiàn)算法。Graphlab[12, 13]是基于BSP模型的圖并行框架，以高性能著稱。其不僅支持基于消息的編程模型，而且支持共享內(nèi)存風(fēng)格的“收集—更新—擴(kuò)散”（記做GAS）模型，除此之外Graphlab還支持異步計(jì)算，對(duì)自然圖的并行處理具有較高的性能。因此本文以Graphlab為基礎(chǔ)框架來實(shí)現(xiàn)。

Graphlab主要分為3個(gè)計(jì)算過程。首先是收集階段，工作頂點(diǎn)的邊從鄰接頂點(diǎn)和自身收集數(shù)據(jù)。然后是更新階段，從節(jié)點(diǎn)將收集的數(shù)據(jù)發(fā)送給主節(jié)點(diǎn)進(jìn)行匯總，主節(jié)點(diǎn)將匯總后的數(shù)據(jù)同步更新到從節(jié)點(diǎn)。最后是擴(kuò)散階段，工作頂點(diǎn)更新完成后，更新邊上的數(shù)據(jù)，并通知對(duì)其有依賴的鄰接頂點(diǎn)更新狀態(tài)。

DABC算法主要分為2個(gè)步驟。步驟1：首先計(jì)算任意2個(gè)節(jié)點(diǎn)之間的最短路徑及其數(shù)量，如圖4所示。

/* 表示接收本地消息的頂點(diǎn)集合*/1) for 所有的do2) 將本地消息求和保存在部分結(jié)果,中3) if then 將,發(fā)送到 master4) 同步以保證所有機(jī)器均完成通信5) for 所有的do6) 遍歷do7) if（<0） then8) 9) if（）10) 11) if u有mirror頂點(diǎn) then 將,發(fā)送到所有mirror頂點(diǎn)12)，if u收到, ,then 更新本地信息13) 同步以保證所有機(jī)器均完成通信14) for 所有的do15) 遍歷do16) if then17) 發(fā)送, 至18) 同步以保證所有機(jī)器均完成本輪迭代

在步驟1的一次迭代中，主要包括3個(gè)超級(jí)步。

第1個(gè)超級(jí)步。1) 本地計(jì)算：工作節(jié)點(diǎn)從接收到的來自本地鄰居的消息（消息包含經(jīng)過該鄰居到節(jié)點(diǎn)的當(dāng)前最短路徑及數(shù)量）中；2) 通信：如果是mirror，則將、發(fā)送給它的master；如果是master，則接收其所有mirror的消息。3) 同步屏障：確保所有mirror發(fā)送完消息并且master接收到發(fā)給它的消息。

第2個(gè)超級(jí)步。1) 本地計(jì)算每個(gè)master節(jié)點(diǎn)從消息中遍歷，如果存在<0，那么令，如果，那么令。2) 如果master發(fā)生更新，則將更新后的、發(fā)送給其所有的mirror；mirror接收新的、，覆蓋自己的、。3) 同步屏障，確保所有通信正常結(jié)束。

第3個(gè)超級(jí)步。對(duì)于發(fā)生更新的master和mirror，將滿足條件的、發(fā)給各自的本地鄰居，最后，使用同步屏障，確保所有操作結(jié)束。

步驟1完成之后，任意2個(gè)頂點(diǎn)之間的最短路徑及其數(shù)量已經(jīng)求得，然后利用公式便可求得每個(gè)頂點(diǎn)的橋接中心度，這是算法的步驟2，如圖5所示。

/*表示接收本地消息的頂點(diǎn)集合*/1) for所有的do2) 將本地消息求和保存在部分結(jié)果中3) if then 將發(fā)送到master4)同步以保證所有機(jī)器均完成通信5) for 所有的do6) 遍歷do7) 8) 9) if u有mirror頂點(diǎn) then 將發(fā)送到所有mirror頂點(diǎn)10)，if u收到,then 更新本地信息11) 同步以保證所有機(jī)器均完成通信12) for 所有的do 13) 遍歷do14) if then15) 發(fā)送至16) 同步以保證所有機(jī)器均完成本輪迭代

步驟2的一次迭代過程也包含3個(gè)超級(jí)步。

第1個(gè)超級(jí)步。1) 本地計(jì)算：工作節(jié)點(diǎn)接收到來自本地鄰居的消息（消息包含經(jīng)過該鄰居到節(jié)點(diǎn)的點(diǎn)對(duì)依賴）。2) 通信：如果是mirror，則將發(fā)送給它的master；如果是master，則接收其所有mirror的消息。3) 同步屏障：確保所有mirror發(fā)送完消息并且master接收到發(fā)給它的消息。

第2個(gè)超級(jí)步。1) 本地計(jì)算：每個(gè)master節(jié)點(diǎn)從消息中遍歷，然后根據(jù)式（3）及式（4）計(jì)算節(jié)點(diǎn)的橋接中心度。2) 通信：如果master發(fā)生更新，則將更新后的發(fā)送給其所有的mirror；mirror接收新的，覆蓋自己的。3) 同步屏障：確保所有通信正常結(jié)束。

第3個(gè)超級(jí)步。對(duì)于發(fā)生更新的master和mirror，將滿足條件的發(fā)給各自的本地鄰居，最后，使用同步屏障，確保所有操作結(jié)束。

4 性能測(cè)試與分析

本節(jié)對(duì)分布式橋接中心度算法進(jìn)行了測(cè)試和分析。測(cè)試的性能指標(biāo)包括運(yùn)行時(shí)間、內(nèi)存消耗以及通信消耗。

4.1 實(shí)驗(yàn)環(huán)境

本實(shí)驗(yàn)共使用了8臺(tái)物理服務(wù)器，服務(wù)器在內(nèi)部局域網(wǎng)中通過吉比特交換機(jī)互連。服務(wù)器的硬件配置如下：CPU Intel Xeon E5-2650 2.0 GHz 8 Core，內(nèi)存8 GB，硬盤500 GB。

實(shí)驗(yàn)使用的軟件環(huán)境如下：操作系統(tǒng)64位Debian7，Graphlab2.2，OpenMPI1.6，編譯環(huán)境為GCC 4.8，編程語言為C++。

實(shí)驗(yàn)采用了真實(shí)數(shù)據(jù)集與模擬數(shù)據(jù)集2類數(shù)據(jù)進(jìn)行評(píng)估。真實(shí)數(shù)據(jù)集來自SNAP[19]，該數(shù)據(jù)集描述了維基百科中的查詢請(qǐng)求關(guān)系。模擬數(shù)據(jù)集則以固定冪律生成了隨機(jī)網(wǎng)絡(luò)圖數(shù)據(jù)。實(shí)驗(yàn)采用的數(shù)據(jù)集信息如表2所示。

表2 實(shí)驗(yàn)數(shù)據(jù)集

數(shù)據(jù)集1中圖的頂點(diǎn)數(shù)從1 000~4 000，本文使用數(shù)據(jù)集1的邊數(shù)1這組數(shù)據(jù)來測(cè)試本文提出的算法和原有算法在運(yùn)行時(shí)間上的差別。同時(shí)本文也使用數(shù)據(jù)集1測(cè)試在固定頂點(diǎn)數(shù)量，變化邊數(shù)量的情況下，算法的運(yùn)行時(shí)間。

數(shù)據(jù)集2包含真實(shí)數(shù)據(jù)集SNAP和另一組模擬數(shù)據(jù)。數(shù)據(jù)集2比數(shù)據(jù)集1具有更大的數(shù)據(jù)規(guī)模，用來測(cè)試在多臺(tái)機(jī)器上算法的運(yùn)行指標(biāo)。

實(shí)驗(yàn)比較了集中式的中心度計(jì)算算法和本文提出的分布式中心度計(jì)算方法DABC的性能，并測(cè)試了在多臺(tái)服務(wù)器組成的集群環(huán)境下，DABC算法的運(yùn)行時(shí)間、內(nèi)存消耗、通信量等指標(biāo)。集中式的中心度算法采用了經(jīng)典的FABC算法，在前文中已經(jīng)有所介紹。

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

圖6給出了FABC算法與DABC算法的對(duì)比結(jié)果。測(cè)試使用了數(shù)據(jù)集1中的第1組數(shù)據(jù)。該實(shí)驗(yàn)在1臺(tái)機(jī)器上進(jìn)行，主要比較了算法在運(yùn)行時(shí)間上的差別。如圖6所示，本文提出的DABC算法比原有算法在時(shí)間上有了很大的提升，當(dāng)頂點(diǎn)規(guī)模較小的時(shí)候，新算法的運(yùn)行時(shí)間僅為原有算法的25%以下，當(dāng)頂點(diǎn)數(shù)達(dá)到3 000時(shí)，算法的加速比有所下降，但加速效果同樣明顯。進(jìn)一步計(jì)算可知，在本實(shí)驗(yàn)中，新算法的平均加速達(dá)到70%以上。

圖7對(duì)比了在相同頂點(diǎn)數(shù)，邊數(shù)不同的情況下DABC算法的運(yùn)行時(shí)間。實(shí)驗(yàn)同樣使用了數(shù)據(jù)集1中的數(shù)據(jù)。在數(shù)據(jù)集1中，本文固定圖中頂點(diǎn)數(shù)，生成了不同邊數(shù)的2組圖。本實(shí)驗(yàn)中將邊數(shù)較少的一組圖稱為稀疏圖，邊數(shù)較多的稱為稠密圖。

如圖7所示，在相同頂點(diǎn)數(shù)的情況下，稠密圖的耗時(shí)高于稀疏圖。這是由于算法在運(yùn)行過程中會(huì)搜索所有的邊，所以邊數(shù)的增加必然會(huì)導(dǎo)致運(yùn)行時(shí)間的增長。

在集群環(huán)境中，數(shù)據(jù)圖會(huì)被切分到每臺(tái)機(jī)器上存儲(chǔ)。機(jī)器間通過通信協(xié)作完成統(tǒng)一的計(jì)算任務(wù)。切分方式在某種程度上決定了數(shù)據(jù)的分布方式和機(jī)器間的協(xié)作方式，所以一個(gè)好的切分方法將會(huì)使算法的性能得到很大提升。

在本實(shí)驗(yàn)中，對(duì)比了3種切分方式，分別為random切分方式、oblivious切分方式、grid切分方式。其中，random切分方式將邊隨機(jī)的分配到每臺(tái)機(jī)器上，切分速度較快，但是這種方式?jīng)]有充分利用圖的連通特征。而oblivious切分方式采取貪心算法策略進(jìn)行數(shù)據(jù)圖的切分，該切分方式解決的問題為在采用盡可能少的切分點(diǎn)的情況下達(dá)到負(fù)載均衡，該切分方式由于以貪心算法為基礎(chǔ)，所以容易造成局部最優(yōu)。grid切分方式基于散列分配邊，該方法切分速度快、切分均衡、并且切分點(diǎn)較少。

本實(shí)驗(yàn)使用了數(shù)據(jù)集2中的數(shù)據(jù)。如圖8所示，本文分別在2臺(tái)機(jī)器和4臺(tái)機(jī)器上進(jìn)行了測(cè)試。在2臺(tái)機(jī)器的情況下，3種切分方式的算法執(zhí)行效率差不多，但是，隨著機(jī)器數(shù)的增多，顯然在grid切分方式下算法具有更好的效率。這是由于grid切分方式切分均衡、切分點(diǎn)少，使機(jī)器間通信減少，并且每臺(tái)機(jī)器的計(jì)算負(fù)載也比較均衡。而另外2種切分方式，切分的點(diǎn)較多導(dǎo)致過多頂點(diǎn)被復(fù)制，使機(jī)器間通信頻繁，而且切分不均衡也會(huì)導(dǎo)致集群的機(jī)器負(fù)載不勻，降低整體運(yùn)行效率。

圖9給出了算法在數(shù)據(jù)集2上的運(yùn)行時(shí)間、內(nèi)存消耗、通信量的統(tǒng)計(jì)情況。圖9（a）給出了算法在運(yùn)行過程中的運(yùn)行時(shí)間與機(jī)器數(shù)量的關(guān)系。隨著機(jī)器數(shù)的增加，DABC算法的運(yùn)行時(shí)間不斷降低，但是可以看到，加速率隨著機(jī)器數(shù)的增加其有所下降。主要原因是由于機(jī)器數(shù)增加后，各機(jī)器間需要協(xié)作的工作也相應(yīng)增加，導(dǎo)致整體通信量有所增加。另外，機(jī)器數(shù)量增加后，各機(jī)器間的工作負(fù)載也可能會(huì)不均衡，導(dǎo)致等待時(shí)間增多。圖9（b）給出了參與計(jì)算的所有機(jī)器的內(nèi)存消耗總量和與機(jī)器數(shù)量的關(guān)系。隨著機(jī)器數(shù)的增加，算法消耗的內(nèi)存整體上升，但是平均每臺(tái)機(jī)器的消耗量有所下降?？偭可仙闹饕蚴怯捎诠?jié)點(diǎn)切分生成了多個(gè)mirror，并且為mirror生成了一些附加數(shù)據(jù)結(jié)構(gòu)，占用了大量?jī)?nèi)存空間。圖9（c）給出了算法在運(yùn)行過程中每臺(tái)機(jī)器平均通信量與機(jī)器數(shù)量的關(guān)系?？梢钥闯銮€呈現(xiàn)下降趨勢(shì)，這是因?yàn)殡S著機(jī)器增多，分配到每臺(tái)機(jī)器中的頂點(diǎn)數(shù)目會(huì)相應(yīng)減少，任意2臺(tái)機(jī)器之間的通信量也會(huì)隨著分區(qū)中頂點(diǎn)數(shù)目的減少而降低，所以平均通信量會(huì)減少。但集群的整體通信量有所增長，這是因?yàn)殡S著機(jī)器數(shù)的增加，圖分區(qū)數(shù)量也相應(yīng)增多，所以需要通信的節(jié)點(diǎn)數(shù)量也增加，導(dǎo)致通信總量的增加。

5 結(jié)束語

本文基于傳統(tǒng)的集中式橋接中心度計(jì)算方法設(shè)計(jì)和實(shí)現(xiàn)了分布式橋接中心度計(jì)算算法DABC。算法包含最短路徑計(jì)算和點(diǎn)中心度計(jì)算2個(gè)主要的分布式過程。實(shí)驗(yàn)結(jié)果表明該算法比原有算法在性能上有了大幅度的提升，同時(shí)由于采用了分布式架構(gòu)，該算法具備了良好的擴(kuò)展性，可以支持更大規(guī)模的圖數(shù)據(jù)處理。

在未來工作中，將進(jìn)一步優(yōu)化和完善該算法。1）設(shè)計(jì)更好的切分方法以進(jìn)一步降低算法的運(yùn)行時(shí)間。2）采用優(yōu)化的通信方法，以降低機(jī)器間的通信開銷。

[1] BADER D A, KINTALI S, MADDURI K, et al. Approximating betweenness centrality[C]//Workshop on Algorithms and Models for the Web-Graph. San Diego, CA, c2007: 124-137.

[2] ANTHONISSE J. The rush in a directed graph[M]. Amsterdam: Stichting Mathematisch Contrum, 1971. 1-10.

[3] FREEMAN L. A set of measure of centrality based on betweenness[J]. Sociomtry, 1977, 40 (1): 35-41.

[4] CARPENTER T, KARAKOSTAS G, SHALLCROSS D. Practical issues and algorithms for analyzing terrorist networks[C]// International Workshop on Mobile Commerce. San Antonio, c2012.

[5] BRANDS U. A faster algorithm for betweenness centrality[J]. Journal of Mathematical Sociology, 2001, 25 (2):163-177.

[6] BRANDS U. On variants of shortest-path betweenness centrality and their generic computation[J]. Social Networks, 2008, 30(2):136-145.

[7] LEE M, LEE J, PARK J Y, et al. QUBE: a quick algorithm for updating betweenness centrality[C]//WWW. Lyon, France, c2012: 351-360.

[8] YANG J X, WANG C K, BAI Y Y. A fast algorithm for updating betweenness centrality in social networks[J]. Journal of Computer Research and Development, 2012, 49(l): 243-249.

[9] TAN G, TU D, SUN N. A parallel algorithm for computing betweenness centrality[C]//Washington ICPP. c2009: 340-347.

[10] JEREY D, SANJAY G. MapReduce: simplied data processing on large clusters[C]//6th USENIX Symp on Operating Syst Design and Impl. c2004: 137-150.

[11] GRZEGORZ M, MATTHEW H. Austern pregel: a system for large-scale graph processing[C]//The ACM SIGMOD Conference (SIGMOD). Indianapolis, Indiana, c2010: 135-146.

[12] LOW Y, GONZALEZ J, KYROLA A, et al. GraphLab: a new parallel framework for machine learning[C]//Uncertainty in Artificial Intelligence. c2010: 340-349.

[13] LOW Y, BICKSON D, GONZALEZ J, et al. Distributed GraphLab: a framework for machine learning and data mining in the cloud[J]. Proceedings of the VLDB Endowment, 2012, 5(8): 716-727.

[14] GONZALEZ J E, LOW Y, GU H, et al. PowerGraph: distributed graphparallel computation on natural graphs[C]//USENIX Conf Operating Systems Design and Implementation. c2012: 17-30.

[15] XIN R S, GONZALEZ J E, FRANKLIN M J, et al. GraphX: a resilient distributed graph system on Spark[C]//First International Workshop on Graph Data Management Experiences and Systems (GRADES 2013). c2013: 2-16.

[16] https://giraph.apache.org[EB/OL].2011.

[17] UGANDER J, KARRER B, BACKSTROM L, et al. The anatomy of the facebook social graph[J]. arXiv preprint arXiv:1111.4503. 2011.

[18] http://graphlab.org/projects/source.html[EB/OL]. 2014.

[19] JURE L, ANDREJ K. SNAP Datasets: large network dataset collection [EB/OL]. http://snap.stanford.edu/data/ 2014.

Key nodes discovery in network graph based on Graphlab

GAO Zhuang-liang1, LYU Yan-fei2, ZHANG Hong2

(1. School of Computer Science and Engineering, Beihang University, Beijing 100191, China; 2. National Computer Network Emergency Response Technical Team/Coordination Center of China, Beijing 100029, China)

A distributed key nodes discovery algorithm was proposed(DABC) which was implemented on Graphlab. Due to the good scalability, the scale of graph supported by the algorithm was enlarged significantly. The parallel processing also enhances the speed of calculation. Experiment results show that proposed algorithm can achieve up to 4 times performance improvement compared with the traditional centralized key node discovery algorithm.

key node, betweenness centrality, distributed algorithm, Graphlab

TP316.4

A

10.11959/j.issn.1000-436x.2016066

2015-04-03；

2015-11-11

呂雁飛，lyf@cert.org.cn

國家重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃（“973”計(jì)劃）基金資助項(xiàng)目（No.2011CB302605）

The National Basic Research Program of China (973 Program) (No.2011CB302605 )

高壯良（1990-），男，山東菏澤人，北京航空航天大學(xué)碩士生，主要研究方向?yàn)榉植际綀D計(jì)算。

呂雁飛（1984-），男，遼寧朝陽人，博士，國家計(jì)算機(jī)網(wǎng)絡(luò)應(yīng)急技術(shù)處理協(xié)調(diào)中心工程師，主要研究方向?yàn)榇髷?shù)據(jù)技術(shù)。

張鴻（1976-），男，陜西西安人，博士，國家計(jì)算機(jī)網(wǎng)絡(luò)應(yīng)急技術(shù)處理協(xié)調(diào)中心高級(jí)工程師，主要研究方向?yàn)樵朴?jì)算、大數(shù)據(jù)、網(wǎng)絡(luò)安全。