毛國勇， 張 寧

（1.常州工學(xué)院 電子信息與電氣工程學(xué)院，常州 213002；2.上海理工大學(xué) 管理學(xué)院，上海 200093）

大規(guī)模網(wǎng)絡(luò)分析在許多重要領(lǐng)域，如社會(huì)網(wǎng)絡(luò)、信息傳播網(wǎng)絡(luò)和生物網(wǎng)絡(luò)等領(lǐng)域中有著廣泛的應(yīng)用［1］，而介數(shù)［2］（BC）是分析大規(guī)模復(fù)雜網(wǎng)絡(luò)時(shí)廣泛使用的一個(gè)指標(biāo).通過這個(gè)指標(biāo)，可以對圖中節(jié)點(diǎn)的重要程度進(jìn)行定量分析，可以衡量一個(gè)節(jié)點(diǎn)在網(wǎng)絡(luò)通信中的重要性，識別出網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn).較高的BC指標(biāo)表明，一個(gè)節(jié)點(diǎn)到其它節(jié)點(diǎn)有相對較多的最短路徑，或者這個(gè)節(jié)點(diǎn)位于其它兩個(gè)節(jié)點(diǎn)最短路徑上的可能性很大.BC反映了相應(yīng)的節(jié)點(diǎn)在整個(gè)網(wǎng)絡(luò)中的作用和影響力，是一個(gè)重要的全局幾何量，具有很強(qiáng)的現(xiàn)實(shí)意義.例如，在社會(huì)關(guān)系網(wǎng)或技術(shù)網(wǎng)絡(luò)中，介數(shù)的分布特征反映了不同人員、資源和技術(shù)在相應(yīng)生產(chǎn)關(guān)系中的地位，這對于發(fā)現(xiàn)和保護(hù)關(guān)鍵資源、技術(shù)和人才具有重要意義.BC的計(jì)算是網(wǎng)絡(luò)分析的重要內(nèi)容，它占了大部分的計(jì)算時(shí)間.所以，對這個(gè)算法進(jìn)行并行加速具有重要意義.

1 BC算法簡介

節(jié)點(diǎn)v的BC為

式中，σst為從節(jié)點(diǎn)s到節(jié)點(diǎn)t的最短路徑總數(shù)目；σst（v）為這些路徑中經(jīng)過頂點(diǎn)v的路徑條數(shù).計(jì)算一個(gè)圖中所有頂點(diǎn)的BC需要計(jì)算所有頂點(diǎn)間的最短路徑，所需時(shí)間為O（n3）.對于無權(quán)圖，用Brandes算法計(jì)算所需時(shí)間為O（n×m）［3］，其中，n為頂點(diǎn)的數(shù)目，m為邊的數(shù)目.

Brandes算法由寬度優(yōu)先搜索（breadth first search，BFS）、部分和累加、標(biāo)準(zhǔn)化等3個(gè)部分構(gòu)成.對于圖1所示的BC算法示例圖中的b點(diǎn)，其BC值為

式中，σac（b）為經(jīng)過b點(diǎn)從a到c的最短路徑條數(shù)，σac為從a到c的最短路徑條數(shù).假定0除0等于0.為了使最終的BC位于［0，1］之間，還需要對結(jié)果進(jìn)行標(biāo)準(zhǔn)化.所謂標(biāo)準(zhǔn)化對于無向圖而言，就是除以（n－1）× （n－2）／2.對于有向圖，就是除以（n－1）×（n－2）.圖1為無向圖，n＝5，（n－1）×（n－2）／2＝6.

圖1 BC算法示例圖Fig.1 Example graph of BCalgorithm

2 并行BC算法

2.1 算法的數(shù)據(jù)結(jié)構(gòu)

求解BC時(shí)，復(fù)雜網(wǎng)絡(luò)的規(guī)模也是計(jì)算中必需面對的問題.在空間復(fù)雜度方面，目前復(fù)雜網(wǎng)絡(luò)主要有鄰接表和鄰接矩陣兩種表示方法.如果用鄰接矩陣來表示復(fù)雜網(wǎng)絡(luò)，其空間復(fù)雜度為V2，其中V是頂點(diǎn)的數(shù)目；對于節(jié)點(diǎn)數(shù)為1 000 000的復(fù)雜網(wǎng)絡(luò)，計(jì)算機(jī)需要數(shù)T的內(nèi)存才能表示，這對于目前的計(jì)算機(jī)幾乎是不可能的.對于稀疏網(wǎng)絡(luò)而言，用鄰接表表示則占用較少的內(nèi)存空間，因?yàn)樗恍枰鎯?chǔ)不存在的邊.如果使用數(shù)組來表示鄰接表，對于無向圖需要8E字節(jié)的存儲(chǔ)容量，其中E是邊的數(shù)目，每條邊使用4字節(jié)，每一條邊在鄰接表中出現(xiàn)兩次；而對于有向圖，只需要4E字節(jié)的存儲(chǔ)容量，因?yàn)槊織l邊在鄰接表中只出現(xiàn)一次.由于復(fù)雜網(wǎng)絡(luò)往住是稀疏網(wǎng)絡(luò)，因此，采用鄰接表來存儲(chǔ)網(wǎng)絡(luò).

本算法的開發(fā)語言為 Python 2.7［4］，它是一種面向?qū)ο?、直譯式的計(jì)算機(jī)程序設(shè)計(jì)語言.其提供了Dict（字典）、Set（集合）、List（列表）及 Tuple（元組）等幾種數(shù)據(jù)結(jié)構(gòu)，其中，字典有時(shí)稱為關(guān)聯(lián)數(shù)組或者哈希表.它們通過鍵將一系列值聯(lián)系起來，這樣就可以使用鍵從字典中取出一項(xiàng).本算法中采用字典來表示鄰接表，將鍵值相同的值放在一個(gè)列表中，實(shí)現(xiàn)從鍵到值的多重映射.例如，對于以邊表形式表示的圖數(shù)據(jù)

其對應(yīng)的字典為｛1：（2，3，4）；2：（4，5）｝，頂點(diǎn)1和2為鍵，（2，3，4）及（4，5）分別為與鍵1和鍵2對應(yīng)的值.由于Python對內(nèi)存的使用非常節(jié)省，加上用整型的頂點(diǎn)編號來代替字符型的頂點(diǎn)名稱，因此，對于325 729個(gè)頂點(diǎn)及1 497 134條邊的網(wǎng)絡(luò)［5］，其內(nèi)存占用不到200M.對于2 508 811個(gè)頂點(diǎn)及25 278 346條邊的網(wǎng)絡(luò)［6］，其內(nèi)存占用不到2G，因此，采用這種數(shù)據(jù)結(jié)構(gòu)，能在目前流行的服務(wù)器上對上億條邊的復(fù)雜網(wǎng)絡(luò)進(jìn)行分析.

2.2 算法流程

本并行算法的開發(fā)環(huán)境為并行Python［7］，它是一個(gè)Python模塊，能夠在SMP及工作站機(jī)群 上并行運(yùn)行Python代碼.BC的并行算法從每個(gè)源節(jié)點(diǎn)開始做寬度優(yōu)先遍歷，然后回溯累加得到BC.采用并行Python來實(shí)現(xiàn)粗粒度并行，將每個(gè)從源節(jié)點(diǎn)開始的遍歷及回溯累加過程看作一個(gè)任務(wù)，算法需要n個(gè)任務(wù)，求得每個(gè)節(jié)點(diǎn)的部分BC值.最后，將每個(gè)任務(wù)的部分BC值累加，得到每個(gè)頂點(diǎn)的最終BC值，這n個(gè)任務(wù)可以并行處理，而且在并行計(jì)算過程中，各個(gè)節(jié)點(diǎn)間不需要通信，只需要一個(gè)并行規(guī)約操作得到最終的值.算法流程如圖2所示.

圖2 并行算法在管理節(jié)點(diǎn)及計(jì)算節(jié)點(diǎn)的執(zhí)行流程Fig.2 Execution workflow of parallel algorithm in management and computation of nodes

在每個(gè)計(jì)算節(jié)點(diǎn)，都需要以源點(diǎn)s表示圖的字典aDict，以及圖的頂點(diǎn)集合G作為參數(shù)調(diào)用寬度優(yōu)先遍歷子程序，返回該源點(diǎn)對應(yīng)的部分BC值，從該源點(diǎn)開始遍歷時(shí)可以訪問的頂點(diǎn)集合S，以及開始遍歷時(shí)，節(jié)點(diǎn)v的前驅(qū)集合Pred，則對應(yīng)的算法為

由于每個(gè)節(jié)點(diǎn)部分BC累加，規(guī)范化以及并行規(guī)約的算法比較簡單，限于篇幅，這里不再表述.

2.3 性能評價(jià)

算法中，第15行用來從字典中查找頂點(diǎn)v是否存在于字典的鍵中，第16行用來在鍵中查找v，并返回與v對應(yīng)的值，第17行用來判斷w是否在字典D中，這3步是while循環(huán)中最耗時(shí)的部分.但由于Python字典采用哈希表實(shí)現(xiàn)，因此，能快速地檢查一個(gè)鍵在字典中是否存在，查找效率可以達(dá)到O（1）.需要指出的是，本算法只是實(shí)現(xiàn)了粗粒度的并行，因此并行效率不如考慮了圖的鄰接信息的中粒度及細(xì)粒度并行［8］，但正因?yàn)椴挥每紤]圖的細(xì)節(jié)，因此實(shí)現(xiàn)起來相對簡單，能夠方便地應(yīng)用到更多核心、更多工作站的機(jī)群.

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

測試用的服務(wù)器包括一臺用作管理節(jié)點(diǎn)的Dell PowerEdge R910工作站，它有32個(gè)至強(qiáng)L7555物理核心，128G內(nèi)存，另有10臺用作計(jì)算節(jié)點(diǎn)的Dell PowerEdge R810工作站，它們都有12個(gè)至強(qiáng)X5660物理核心，24G內(nèi)存.測試的軟件環(huán)境為CentOS5、intel icc編譯器 11.1、Python2.7 以 及parallel python1.6.1，Python使用icc編譯器編譯以提高Python程序的執(zhí)行速度.

本文測試了文獻(xiàn)［5］的數(shù)據(jù)，它含有325 729個(gè)點(diǎn)，1 497 134條邊.不同處理器數(shù)目k的所需計(jì)算時(shí)間t及加速比r如表1所示（見下頁），相應(yīng)的加速比曲線如圖3所示（見下頁）.

表1 處理器數(shù)目與計(jì)算時(shí)間及加速比對應(yīng)關(guān)系表Tab.1 Relationship between number of processors，computing time and speedup

圖3 加速比曲線Fig.3 Curve of speedup

從表1可以看出，串行算法計(jì)算BC需1 263 720s，約14d，如果在10臺工作站共120個(gè)處理器中進(jìn)行計(jì)算，所需時(shí)間只有17 798s，不到5h.從圖3可以看出，隨著處理器數(shù)目的增加，加速比也有線性上升的趨勢.

4 結(jié)論及展望

在多核心工作站機(jī)群實(shí)現(xiàn)了計(jì)算介數(shù)的并行算法，為解決介數(shù)計(jì)算的時(shí)間與空間復(fù)雜度問題提供了易操作的方案，為分析更大規(guī)模復(fù)雜網(wǎng)絡(luò)的特性打下了良好的基礎(chǔ).

未來的工作將探討并行計(jì)算時(shí)的負(fù)載平衡問題，減少并行規(guī)約前的等待時(shí)間，提高計(jì)算速度.

［1］Wang X F，Chen G R.Complex networks：smallworld，scale－free and beyond ［J］.IEEE Circuits and Systems Magazine，2003，3（1）：6－20.

［2］Freeman L C.A set of measures of centrality based on betweenness［J］.Sociomtry，1977，40（1）：35－41.

［3］Brandes U.A faster algorithm for betweenness centrality［J］.Journal of Mathematical Socialogy，2001，25（2）：163－177.

［4］Official website for pathon.python2.7.python［EB／OL］.［2012－09－29］.http：∥www.python.offical website for python.org／index.html.

［5］Albert R，Jeong H，Barabási A L.Internet：diameter of theworld wide web［J］.Nature，1999，401（6749）：130－131.

［6］蘇磊，張寧，馬良.一種新的大規(guī)模網(wǎng)絡(luò)最短路徑的近似算法［J］.復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)，2008，5（2）：51－54.

［7］Offical website for parallel python.Parallel python1.6.1.parallel python［EB／OL］.［2012－09－30］.http：∥www.parallelpython.com／index.html.

［8］涂登彪，譚光明，孫凝暉.無鎖同步的細(xì)粒度并行介度中心算法［J］.軟件學(xué)報(bào)，2011，22（5）：986－995.