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

高壯良，呂雁飛，張鴻

?

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

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

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

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

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

1 引言

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

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

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

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

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

2 相關工作

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

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

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

3.1 橋接中心度概念與計算方法

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

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

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

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

定義點對之間的依賴為

(3)

而單點依賴滿足

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

3.2 DABC算法概述

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

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

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

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

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

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

表1 符號及含義

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

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

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

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

在步驟1的一次迭代中，主要包括3個超級步。

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

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

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

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

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

步驟2的一次迭代過程也包含3個超級步。

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

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

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

4 性能測試與分析

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

4.1 實驗環(huán)境

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

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

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

表2 實驗數(shù)據(jù)集

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

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

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

4.2 實驗結(jié)果分析

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

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

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

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

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

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

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

5 結(jié)束語

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

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

[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

國家重點基礎研究發(fā)展計劃（“973”計劃）基金資助項目（No.2011CB302605）

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

高壯良（1990-），男，山東菏澤人，北京航空航天大學碩士生，主要研究方向為分布式圖計算。

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

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