基于Graphlab的網絡圖關鍵節點發現算法研究

高壯良，呂雁飛，張鴻

?

基于Graphlab的網絡圖關鍵節點發現算法研究

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

（1. 北京航空航天大學計算機學院，北京 100191；2. 國家計算機網絡應急技術處理協調中心，北京 100029）

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

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

1 引言

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

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

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

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

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

2 相關工作

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

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

3 分布式關鍵節點發現算法

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

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

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

圖1 節點中心度示意

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

定義點對之間的依賴為

(3)

而單點依賴滿足

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

3.2 DABC算法概述

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

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

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

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

3.3 基于Graphlab的DABC算法實現

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

表1 符號及含義

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 性能測試與分析

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

4.1 實驗環境

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

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

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

表2 實驗數據集

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

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

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

4.2 實驗結果分析

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

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

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

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

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

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

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

5 結束語

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

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

[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

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

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

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

呂雁飛（1984-），男，遼寧朝陽人，博士，國家計算機網絡應急技術處理協調中心工程師，主要研究方向為大數據技術。

張鴻（1976-），男，陜西西安人，博士，國家計算機網絡應急技術處理協調中心高級工程師，主要研究方向為云計算、大數據、網絡安全。