饒東寧，林卓毅，魏 來

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

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

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

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

1 相關(guān)工作

對網(wǎng)絡(luò)的研究一方面在于提出全新的網(wǎng)絡(luò)中心度，或綜合已有的度量提出加權(quán)中心度。Singh等[5]提出綜合考慮頂點(diǎn)在圖中的全局和局部重要性的圖論傅里葉變換中心度(GFT Centrality)。Medeiros等[6]提出基于準(zhǔn)最短路徑的介數(shù)中心度(ρ-Geodesic Betweenness Centrality)，在計算介數(shù)中心度的時候不僅考慮最短路徑，還加入以ρ作為閾值的準(zhǔn)最短路徑。饒東寧等[7]提出針對BoardEx金融社交網(wǎng)絡(luò)的加權(quán)中心度，驗(yàn)證各公司的首席技術(shù)官和首席信息官的加權(quán)中心度與人員所在公司規(guī)模的相關(guān)性。王露等[8]基于網(wǎng)絡(luò)拓?fù)浣Y(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ò)，運(yùn)行時間及準(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算法實(shí)現(xiàn)并行化，相較傳統(tǒng)LPA效果更好速度更快。艾川等[11]借助Spark平臺，實(shí)現(xiàn)超大規(guī)模網(wǎng)絡(luò)傳播計算實(shí)驗(yàn)算法，可高效進(jìn)行大規(guī)模復(fù)雜網(wǎng)絡(luò)中的信息傳播仿真。

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

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

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

2.1.1 度中心度(Degree Centrality)

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

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

2.1.2 壓力中心度(Stress Centrality)

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

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

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

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

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

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

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

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

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

3.1 Pregel

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

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

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

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

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

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

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

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

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ù)到達(dá)n時迭代終止。統(tǒng)計各頂點(diǎn)屬性中可達(dá)頂點(diǎn)數(shù)量，即為n-度中心度。

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

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

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

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

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

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

初始化后，重復(fù)(2)(3)(4)，直到迭代次數(shù)到達(dá)k時迭代終止。所有最短路徑篩選出長度大于2的，并去除路徑兩端頂點(diǎn)，通過統(tǒng)計各頂點(diǎn)出現(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 并行算法的實(shí)現(xiàn)

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

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

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

4 性能測試

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

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

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

4.2 實(shí)驗(yàn)數(shù)據(jù)

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

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

4.3 實(shí)驗(yàn)設(shè)計

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

4.4 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

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

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

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

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

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

6 總結(jié)

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

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