饒東寧，林卓毅，魏 來

（1. 廣東工業(yè)大學(xué) 計算機學(xué)院，廣東 廣州 510006；2. 香港大學(xué) 經(jīng)濟與金融學(xué)院，中國 香港 999077）

網(wǎng)絡(luò)中心度及其并行算法設(shè)計實現(xiàn)是網(wǎng)絡(luò)研究的熱點。頂點的網(wǎng)絡(luò)中心度[1]是對頂點在網(wǎng)絡(luò)中的重要性的量化。數(shù)據(jù)隨科技發(fā)展呈指數(shù)增長[2]，網(wǎng)絡(luò)的規(guī)模也日漸龐大。單機已難以實現(xiàn)大規(guī)模網(wǎng)絡(luò)的存儲和計算，多機分布式存儲[3]與并行計算[4]逐漸成為發(fā)展趨勢。因此，對網(wǎng)絡(luò)的研究重點不僅在于網(wǎng)絡(luò)中心度的研究，還在于網(wǎng)絡(luò)計算的并行算法設(shè)計實現(xiàn)。

目前網(wǎng)絡(luò)中心度并行算法的設(shè)計和實現(xiàn)尚未完善。在提出新的網(wǎng)絡(luò)中心度時，研究者通常只實驗于小型網(wǎng)絡(luò)，沒有考慮在大型網(wǎng)絡(luò)的應(yīng)用及并行算法的設(shè)計實現(xiàn)。此外，現(xiàn)有的并行算法實現(xiàn)較為分散，只有部分實現(xiàn)方法由Spark框架(https://spark.apache.org/)的GraphX模塊提供。使用中心度進行網(wǎng)絡(luò)分析研究時，需要額外開銷來尋找其他中心度的并行算法實現(xiàn)。

本文設(shè)計基于Spark的網(wǎng)絡(luò)中心度并行工具包，并提出n-度中心度和k-壓力中心度及其并行算法。在設(shè)計并行工具包時，對度中心度和壓力中心度進行補充拓展，提出n-度中心度和k-壓力中心度。設(shè)計其并行算法并借助Spark框架的Pregel方法實現(xiàn)。通過BoardEx(https://corp.boardex.com/)社交網(wǎng)絡(luò)進行實驗測試性能，結(jié)果顯示設(shè)計實現(xiàn)的并行算法有明顯的并行加速效果。最后，把并行算法的實現(xiàn)方法與現(xiàn)有的11種網(wǎng)絡(luò)中心度計算方法，整合成一個基于Spark框架的并行工具包。

1 相關(guān)工作

對網(wǎng)絡(luò)的研究一方面在于提出全新的網(wǎng)絡(luò)中心度，或綜合已有的度量提出加權(quán)中心度。Singh等[5]提出綜合考慮頂點在圖中的全局和局部重要性的圖論傅里葉變換中心度(GFT Centrality)。Medeiros等[6]提出基于準(zhǔn)最短路徑的介數(shù)中心度(ρ-Geodesic Betweenness Centrality)，在計算介數(shù)中心度的時候不僅考慮最短路徑，還加入以ρ作為閾值的準(zhǔn)最短路徑。饒東寧等[7]提出針對BoardEx金融社交網(wǎng)絡(luò)的加權(quán)中心度，驗證各公司的首席技術(shù)官和首席信息官的加權(quán)中心度與人員所在公司規(guī)模的相關(guān)性。王露等[8]基于網(wǎng)絡(luò)拓撲結(jié)構(gòu)綜合全局信息和局部信息，提出加權(quán)的網(wǎng)絡(luò)中心度。

另一方面，對網(wǎng)絡(luò)的研究還在于網(wǎng)絡(luò)計算的并行算法研究。喬少杰等[9]提出基于Spark的大規(guī)模網(wǎng)絡(luò)社區(qū)并行發(fā)現(xiàn)算法，能處理更大規(guī)模更復(fù)雜的網(wǎng)絡(luò)，運行時間及準(zhǔn)確率比Hadoop平臺有所提高。Ma等[10]在標(biāo)簽傳播算法(Label propagation algorithm，LPA)的基礎(chǔ)上提出基于概率和相似性的并行標(biāo)簽傳播算法(Probability and similarity based parallel label propagation algorithm，PSPLPA)，借助Spark的Pregel算法實現(xiàn)并行化，相較傳統(tǒng)LPA效果更好速度更快。艾川等[11]借助Spark平臺，實現(xiàn)超大規(guī)模網(wǎng)絡(luò)傳播計算實驗算法，可高效進行大規(guī)模復(fù)雜網(wǎng)絡(luò)中的信息傳播仿真。

2 網(wǎng)絡(luò)中心度定義

網(wǎng)絡(luò)可用圖G = (V, E)表示，其中V和E表示頂點集和邊集。頂點的網(wǎng)絡(luò)中心度衡量頂點在網(wǎng)絡(luò)中的重要性。對度中心度進行補充拓展，提出n-度中心度；受介數(shù)中心度(Betweenness Centrality)[1]與k-介數(shù)中心度(k-Betweenness Centrality)[12]的啟發(fā)，對壓力中心度進行補充拓展，提出k-壓力中心度。

2.1 傳統(tǒng)網(wǎng)絡(luò)中心度

2.1.1 度中心度(Degree Centrality)

度中心度[1]是以頂點的度作為網(wǎng)絡(luò)中心度。度(Degree)是一個頂點在網(wǎng)絡(luò)中鄰居頂點的數(shù)量，在有向圖中可分為入度(In-Degree)和出度(Out-Degree)。度中心度用式(1)表示。

式(1)中，CD(i)表示頂點i的度中心度，x(i,j)表示頂點i和頂點j(i≠j)的連接關(guān)系，如有連接為1否則為0。

2.1.2 壓力中心度(Stress Centrality)

頂點的壓力中心度[13]是其他頂點兩兩之間最短路徑通過該頂點的路徑數(shù)。壓力中心度反映信息在網(wǎng)絡(luò)中傳遞時頂點承受的壓力大小，表示為

式(2)中，CS(i)表示頂點i的壓力中心度，ρst(i)表示頂點s到頂點t經(jīng)過頂點i的最短路徑數(shù)。

2.2 n-度中心度和k-壓力中心度

2.2.1 n-度中心度(n-Degree Centrality)

n-度中心度是頂點在n度內(nèi)可以連接的頂點數(shù)量，也是與頂點距離不超過n的頂點數(shù)。在有向圖中也可分為n-入度(n-In-Degree)和n-出度(n-Out-Degree)。相比度中心度只考慮頂點的鄰居頂點數(shù)量，n-度中心度還考慮到鄰居頂點以外n度以內(nèi)的拓撲結(jié)構(gòu)，通過更大的區(qū)域判斷頂點的重要性，消除度中心度的局限性。n-度中心度用式(3)表示。

2.2.2 k-壓力中心度(k-Stress Centrality)

k-壓力中心度是其他頂點兩兩之間長度不超過k的最短路徑通過該頂點的路徑數(shù)。k-壓力中心度反映信息在網(wǎng)絡(luò)中傳遞時(傳遞距離不超過k)，頂點承受的壓力大小。在社交網(wǎng)絡(luò)中，有效的人際關(guān)系距離不遠。加入信息傳遞距離的限制，k-壓力中心度比壓力中心度更適用于社交網(wǎng)絡(luò)，更好地反映個人在人際網(wǎng)絡(luò)中傳遞信息的能力。k-壓力中心度為

3 并行算法設(shè)計與實現(xiàn)

基于Pregel的計算機制分別設(shè)計n-度中心度和k-壓力中心度的并行算法，并通過Spark框架的Pregel API完成算法實現(xiàn)。

3.1 Pregel

Pregel[14]是一種用于圖的迭代計算的并行計算模型。計算面向頂點，頂點有活躍或非活躍兩種狀態(tài)。每輪迭代稱為一個超步，包括頂點處理(vprog)，消息發(fā)送(sendMsg)和消息合并(mergeMsg) 3個過程。在一個超步中，(1) 頂點接收到上一超步鄰居頂點發(fā)送來的不同消息，把所有消息通過mergeMsg合并為一條消息；(2) 頂點的屬性與合并后消息由vprog處理，可能會更新屬性；(3) 更新了屬性的頂點處于活躍狀態(tài)，只有活躍的頂點才會通過sengMsg向所有鄰居頂點發(fā)送消息。

每次迭代重復(fù)步驟(1)～(3)，直到所有頂點都處于非活躍狀態(tài)即沒有新消息產(chǎn)生，或迭代達到設(shè)定的最大迭代次數(shù)，迭代終止。

3.2 n-度中心度的并行算法

基于Pregel的計算機制，n-度中心度的并行算法設(shè)計見算法 1。算法流程解釋如下：

(1) 初始化，把頂點集合(點集)作為頂點屬性，用以存放可達頂點；

(2) 發(fā)送消息，把源點可達但終點不可達的頂點集合，從源點發(fā)送到終點；

(3) 合并消息，所有接收到的點集合并、去重，形成一個點集；

(4) 頂點處理，消息的點集與屬性的點集合并，更新屬性，加入的頂點是距離增加1后新增的可達頂點。

Algorithm 1. n-Degree Centrality algorithm Input: Original graph, n.Output: Computed graph.1. // Initialization 2. for all vertex v∈vertices do 3. create a vertex set S with v in it； 4. end for 5. // Pregel 6. while new messages are produced or iteration do not reach n times do 7. // Send message 8. for all edge e∈edges do 9. send the difference-set between S of source vertex and S of destination vertex to destination vertex；10. end for 11. // Merge message 12. for all vertex v∈vertices do 13. merge messages into a unique-set as msg；14. end for 15. // Vertex program 16. for all vertex v∈vertices do 17. add all vertices of msg to S；18. end for 19. end while 20. // Centrality computation 21. for all vertex v∈vertices do 22. count the vertices number in S；23. end for 24. return computed graph.

初始化后，重復(fù)(2)(3)(4)，直到迭代次數(shù)到達n時迭代終止。統(tǒng)計各頂點屬性中可達頂點數(shù)量，即為n-度中心度。

3.3 k-壓力中心度的并行算法

基于Pregel的計算機制，k-壓力中心度的并行算法設(shè)計見算法 2。算法流程解釋如下：

(1) 初始化，頂點的屬性設(shè)置為映射關(guān)系(Map)，其中key為頂點，value為key頂點到本頂點的最短路徑(用頂點序列表示)集合；

(2) 發(fā)送消息，把源點已記錄但終點未記錄的頂點及最短路徑集合，從源點發(fā)送至終點；

(3) 合并消息，所有消息中，對于同一頂點只保留路徑長度最短的集合，如果有多個則合并成一個集合；

(4) 頂點處理，消息中的所有路徑在尾部附上當(dāng)前頂點，再把頂點和路徑集合合并至本頂點屬性的Map中。

初始化后，重復(fù)(2)(3)(4)，直到迭代次數(shù)到達k時迭代終止。所有最短路徑篩選出長度大于2的，并去除路徑兩端頂點，通過統(tǒng)計各頂點出現(xiàn)次數(shù)，得出k-壓力中心度。

Algorithm 2. k-Stress Centrality algorithm Input: Original graph, k.Output: Computed graph.1. // Initialization 2. for all vertex v∈vertices do 3. create a map with v as key, S(P(v)) as value； 4. // P is shortest-path represented by a vertex list, // S is a set of shortest-paths. 5. end for 6. // Pregel 7. while new messages are produced or iteration do not reach k times do 8. // Send message 9. for all edge e∈edges do 10. send sub-map of source vertex that the keys are not in the map of destination vertex to destination vertex；11. end for 12. // Merge message 13. for all vertex v∈vertices do 14. if path lengths of a key are different then 15. keep the shortest paths and remove others；16. else 17. merge paths into S of the key；18. end if 19. end for 20. // Vertex program

?

3.4 并行算法的實現(xiàn)

n-度中心度和k-壓力中心度的并行算法通過分布式框架Spark[15]的Pregel API實現(xiàn)。Pregel API調(diào)用方法如下。

Pregel. apply(graph, initialMsg, maxIterations,activeDirection) (vprog, sendMsg, mergeMsg)

其中，initialMsg是初始消息以供初始化；maxIterations是用戶設(shè)置的最大迭代次數(shù)；activeDirection是消息發(fā)送方向；vprog，sendMsg，mergeMsg分別是用戶自定義的頂點處理，消息發(fā)送，消息合并3個函數(shù)。將并行算法的頂點處理，消息發(fā)送，消息合并3個過程，以及自定義的初始消息和最大迭代次數(shù)傳入Pregel API，即可完成并行算法的實現(xiàn)。

4 性能測試

對n-度中心度和k-壓力中心度的并行算法實現(xiàn)進行實驗，測試算法并行加速效果。

4.1 實驗環(huán)境

使用Spark集群進行實驗。集群環(huán)境包括各機器的CPU、內(nèi)核數(shù)、分配內(nèi)存及硬盤等配置，如表1所示。

4.2 實驗數(shù)據(jù)

實驗數(shù)據(jù)源自金融社交網(wǎng)絡(luò)數(shù)據(jù)庫BoardEx。BoardEx記錄商業(yè)人士間的聯(lián)系及各自的個人信息，企業(yè)間的聯(lián)系及企業(yè)的詳細信息。按美國、英國、歐洲和其他國家各地區(qū)劃分，每個地區(qū)分別有個人網(wǎng)絡(luò)和企業(yè)網(wǎng)絡(luò)。BoardEx數(shù)據(jù)庫中均是大規(guī)模社交網(wǎng)絡(luò)，其中企業(yè)網(wǎng)絡(luò)相比個人網(wǎng)絡(luò)規(guī)模較小。實驗選用英國地區(qū)的企業(yè)網(wǎng)絡(luò)，測試n-度中心度和k-壓力中心度的并行算法性能。該網(wǎng)絡(luò)有45 185個頂點，80 418條邊。

表 1 Spark集群配置Table 1 Spark cluster configuration

4.3 實驗設(shè)計

使用算法加速比[16]測試兩種算法的并行加速效果。算法加速比由式(5)表示。

4.4 實驗結(jié)果

實驗一使用英國企業(yè)網(wǎng)絡(luò)測試n-度中心度并行算法的加速效果。實驗結(jié)果如圖 1所示，展示在不同規(guī)模的集群下n-度中心度并行算法的加速比。結(jié)果表明n-度中心度并行算法通過拓展集群具有良好的加速效果，在6機集群下加速比均超過3。而隨著迭代次數(shù)增加(增加n)，加速效果下降。主要原因是消息隨迭代次數(shù)的增加而變長，導(dǎo)致合并消息和頂點處理的時間開銷更大。

圖 1 n-度中心度并行算法加速效果Fig.1 Speedup of n-degree centrality parallel algorithm

實驗二使用英國企業(yè)網(wǎng)絡(luò)測試k-壓力中心度并行算法的加速效果。實驗結(jié)果如圖 2所示，展示在不同規(guī)模的集群下k-壓力中心度并行算法的加速比。結(jié)果表明k-壓力中心度并行算法通過拓展集群也有一定的加速效果，但效果不如n-度中心度并行算法。推測原因是算法使用更復(fù)雜的消息類型，機器內(nèi)存受限導(dǎo)致頻繁進行垃圾清理，而清理的時間無法通過并行加速。同樣的，隨迭代次數(shù)增加算法的加速效果下降，但不及n-度中心度并行算法加速效果下降得明顯。

圖 2 k-壓力中心度并行算法加速效果Fig.2 Speedup of k-stress centrality parallel algorithm

5 網(wǎng)絡(luò)中心度并行工具包設(shè)計

把各種網(wǎng)絡(luò)中心度的并行算法實現(xiàn)整合成一個網(wǎng)絡(luò)中心度并行工具包。除了本文設(shè)計實現(xiàn)的n-度中心度和k-壓力中心度的并行算法，工具包內(nèi)還包含以下中心度算法的實現(xiàn)：

(1) 改良的接近中心度(Closeness Centrality)與介數(shù)中心度(Betweenness Centrality)的并行算法實現(xiàn)；

(2) 饒東寧[17]等提出的并行最小割(Minimal Cut)算法；

(3) 廖志軍[18]提出的分布式K-Core算法；

(4) Spark框架的GraphX模塊提供的度、PageRank和三角計數(shù)(Triangle Count)的方法。

方法(1)也按第4節(jié)的步驟進行了性能測試，也表現(xiàn)出一定的并行加速效果；(2)(3)(4)的方法經(jīng)驗證在工具包中可運行。工具包的可行性與拓展性得以驗證。網(wǎng)絡(luò)中心度并行工具包中各方法，包括方法名與方法描述，詳見表2。

6 總結(jié)

本文將現(xiàn)有的網(wǎng)絡(luò)中心度并行算法的實現(xiàn)整合成一個并行工具包。在工具包的設(shè)計過程中，對度中心度和壓力中心度進行補充拓展，提出n-度中心度和k-壓力中心度。對兩種新度量分別基于Pregel的計算機制設(shè)計并行算法，并通過Spark框架的Pregel方法實現(xiàn)。通過BoardEx數(shù)據(jù)庫的社交網(wǎng)絡(luò)測試并行算法的性能，結(jié)果顯示均有較好的加速效果。并行工具包提供便捷可拓展的中心度并行計算，工具包內(nèi)的網(wǎng)絡(luò)中心度計算方法可通過拓展集群提高計算效率。并行工具包能為網(wǎng)絡(luò)中心度的研究提供選擇，未來的工作將加入更多網(wǎng)絡(luò)中心度的并行算法，或?qū)ぞ甙鼉?nèi)算法加以改進。

表 2 網(wǎng)絡(luò)中心度并行工具包的方法Table 2 Functions in the network centrality parallel toolkit