毛國勇， 張 寧

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

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

1 BC算法簡介

節(jié)點v的BC為

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

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

式中，σac（b）為經(jīng)過b點從a到c的最短路徑條數(shù)，σac為從a到c的最短路徑條數(shù).假定0除0等于0.為了使最終的BC位于［0，1］之間，還需要對結(jié)果進行標準化.所謂標準化對于無向圖而言，就是除以（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時，復雜網(wǎng)絡(luò)的規(guī)模也是計算中必需面對的問題.在空間復雜度方面，目前復雜網(wǎng)絡(luò)主要有鄰接表和鄰接矩陣兩種表示方法.如果用鄰接矩陣來表示復雜網(wǎng)絡(luò)，其空間復雜度為V2，其中V是頂點的數(shù)目；對于節(jié)點數(shù)為1 000 000的復雜網(wǎng)絡(luò)，計算機需要數(shù)T的內(nèi)存才能表示，這對于目前的計算機幾乎是不可能的.對于稀疏網(wǎng)絡(luò)而言，用鄰接表表示則占用較少的內(nèi)存空間，因為它不需要存儲不存在的邊.如果使用數(shù)組來表示鄰接表，對于無向圖需要8E字節(jié)的存儲容量，其中E是邊的數(shù)目，每條邊使用4字節(jié)，每一條邊在鄰接表中出現(xiàn)兩次；而對于有向圖，只需要4E字節(jié)的存儲容量，因為每條邊在鄰接表中只出現(xiàn)一次.由于復雜網(wǎng)絡(luò)往住是稀疏網(wǎng)絡(luò)，因此，采用鄰接表來存儲網(wǎng)絡(luò).

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

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

2.2 算法流程

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

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

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

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

2.3 性能評價

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

3 實驗結(jié)果

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

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

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

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

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

4 結(jié)論及展望

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

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

［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］.復雜系統(tǒng)與復雜性科學，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］涂登彪，譚光明，孫凝暉.無鎖同步的細粒度并行介度中心算法［J］.軟件學報，2011，22（5）：986－995.