王　敏　王　蕾　馮曉兵　曹寶香

1(計算機體系結構國家重點實驗室(中國科學院計算技術研究所)　北京　100190)2　　　(曲阜師范大學信息科學與工程學院　山東日照　276800)

?

基于頂點加權的介度中心近似算法研究

王敏1,2王蕾1馮曉兵1曹寶香2

1(計算機體系結構國家重點實驗室(中國科學院計算技術研究所)北京100190)2(曲阜師范大學信息科學與工程學院山東日照276800)

(wangmin01@ict.ac.cn)

摘要介度中心(betweenness centrality, BC)是衡量網絡節(jié)點重要程度的一個廣泛使用的指標，最快的介度中心算法需要計算n次單源最短路徑，時間復雜度是O(V×E).介度中心算法的瓶頸就在于計算量太大，導致運行時間太長，無法在實際中應用，因此需要從近似算法的角度降低介度中心算法的計算量.目前介度中心近似算法在計算自然圖時對計算量的降低并不顯著.為了進一步降低介度中心算法的計算量，提出了一種基于頂點加權的介度中心近似算法，該算法采用頂點加權的方式將多次重復計算過程累加到一次計算過程上，結合選擇高影響力源點的方法可以大大降低介度中心算法的計算量，加速比平均達到了25倍，并且最大誤差百分比小于0.01%.

關鍵詞介度中心算法；計算量；影響力；頂點加權；近似

衡量網絡節(jié)點的重要程度是網絡分析的一個重要方面，在衡量網絡節(jié)點重要程度時，被廣泛使用的一個指標是介度中心(betweenness centrality, BC)[1].介度中心算法有著廣泛的使用范圍，例如社區(qū)劃分[2]、查找恐怖組織的領導者[3]、保護網絡節(jié)點中的關鍵服務器、分析疾病的傳播途徑[4]以及分析人體關鍵蛋白質的組成[5]等，這些應用中的圖都屬于自然圖.

介度中心[1]是基于最短路徑計算的全局性衡量指標，在圖G(V,E)中，對于任意的節(jié)點對(s,t)∈V，σs t表示節(jié)點s和t之間的最短路徑條數，σs t(u)表示s，t之間的最短路徑中經過節(jié)點u的條數，節(jié)點u的介度中心可以量化為

目前最快的介度中心算法是由Brandes[1]提出的，具體做法是以圖中的每個節(jié)點為源點做1次最短路徑計算，累加每次計算的依賴值δ，整個算法的時間復雜度是O(V×E).對于規(guī)模較大[6]的圖，該方法的計算時間仍然是無法接受的，如在Intel Xeon E5645的機器，Linux 2.6.32單核的運行環(huán)境上，對于一個社交網絡soc-LiveJournal1[7](4.8×106個頂點和6.8×107條邊)完成1次最短路徑和依賴值δs(u)計算(簡稱一次遍歷)的時間為7 s，完成n次遍歷的時間約13個月.

目前國內外有很多降低介度中心算法運行時間的研究，一類是將介度中心算法并行化縮短其計算時間；另一類是通過近似算法減少介度中心算法的計算量，從而減少計算時間.本文的工作屬于第2類方法范疇.介度中心近似算法中比較有代表性的有Brandes等人[8]提出的隨機近似算法，這些算法在一定程度上降低了介度中心算法的計算量.經測試發(fā)現，當選取源點數目大約為n×60%時，可以保證近似算法結果的誤差是可接受的，但是對計算量只降低了約40%.在實際應用中對自然圖的計算量的降低并沒有使其達到實用化的程度，所以需要進一步降低介度中心算法的計算量.

本文提出了一種基于頂點加權的介度中心近似算法，該近似算法核心思想是減少計算量.通過減少相似的重復計算并結合選取高度源點的方式，使得少數次的遍歷計算效果相當于多次的遍歷計算效果，從而達到降低計算量的目的.實驗結果顯示該算法的平均加速比為25，逆序對百分比(衡量誤差的1個指標，見4.2節(jié))也都小于0.01%.該算法降低的只是單源最短路徑的計算次數，所以這種方式并不會影響并行介度中心算法的并行性，與并行算法是正交的.

1相關工作

國內外對介度中心算法的工作主要集中在近似、并行、增量式計算等方面.本文的工作主要集中在近似算法的角度，目前國內外的介度中心近似算法主要分為2類：1)減少介度中心算法的整體計算量；2)減少單個頂點的介度中心值的計算量.減少介度中心算法整體計算量的近似算法主要有隨機近似算法[8]、隨機線性縮放近似算法[9]、隨機二分近似算法等人[9].隨機近似算法(Random)是由Brandes等人[10]提出的，方法是隨機選擇一些點作為源點進行最短路徑計算.通過這種方式可以在一定程度上降低介度中心算法的計算量.隨機近似算法的缺點在于隨機選擇源點的方式可能會選擇很多低度的源點，導致離源點近的點的介度中心值偏高；其次為保證近似結果的誤差可接受，在計算有向自然圖時需要選取源點數目大約為n×60%，計算量僅降低了40%，算法性能提升不到1倍.

隨機線性縮放算法是由Geisberger等人[9]提出的，該算法與隨機近似算法源點的不同點在于通過在介度中心值計算過程中添加距離函數的方式解決了隨機近似算法中有些點的介度中心值偏高的問題.隨機線性縮放算法也是通過隨機選擇一部分源點的方式來減少計算量.該算法解決了某些介度中心值偏高的問題，提高了算法近似結果的精確度.經測試發(fā)現，在計算有向自然圖時，選擇與隨機近似算法相同個數的源點，最重要10個點的誤差與隨機算法的結果相同，排名前100個點的精確度大約提高25%.在實際應用中所關注的往往是最重要的1個或者幾個點，所以需要選取與隨機近似算法相當的源點個數，這對計算量的降低并不明顯.為了保證計算結果的誤差可接受，需選取與隨機近似算法相當的計算量，計算量偏大.

隨機二分近似算法是由Geisberger等人[9]提出的另一種介度中心近似算法，該算法與隨機線性縮放算法的不同在于距離函數的選取，根據節(jié)點距離源點的距離將距離函數定義為1個確定的值0或者1.該算法取得了與隨機線性近似算法相當的精確度，但是也存在相同的問題就是對自然圖的計算量降低太少，需要選取約n×60%的計算量，計算量降低較少.

另一類介度中心近似算法中比較有代表性的是由David等人[10]提出的自適應采樣近似算法，該算法用來減少單個節(jié)點或者已知節(jié)點集合的介度中心值的計算量，具體做法是隨機選擇源點，當已知節(jié)點或者已知節(jié)點集合的介度中心值滿足一定條件時停止計算.該算法的核心思想是對節(jié)點介度中心值的估算，問題在于需要提前知道哪些節(jié)點是重要的，目前還無法確定哪些點是需要關注的.

并行方面的工作主要包括介度中心算法的粗粒度并行和細粒度并行.介度中心算法的計算過程是以每個節(jié)點為根節(jié)點進行最短路徑遍歷和依賴值計算的過程，粗粒度并行是指并行根節(jié)點進行最短路徑遍歷和依賴值計算的過程，細粒度并行是指在依賴值計算或者最短路徑遍歷時，對遍歷到同層的節(jié)點進行并行計算.

1) 在粗粒度并行方面，Jin等人[11]提出了通過并行的介度中心算法的方式來進行電網事故分析；Yang等人[12]通過并行優(yōu)化介度中心算法對蛋白質網絡進行了計算和分析.這些粗粒度并行的方式對小的圖數據具有良好的分析效果.

2) 在細粒度并行方面，Bader等人[13]首次提出了一種基于粗粒度和細粒度同時并行的介度中心算法；Madduri等人[14]在Bader的基礎上將Bader算法的細粒度并行方式中記錄前驅的方法改成了記錄后繼的方式，進一步優(yōu)化了算法的性能；Cong等人[15]通過重新布局圖的節(jié)點以及圖節(jié)點預取的方式對介度中心算法的細粒度并行進行了優(yōu)化；Tan等人[16-18]在Bader的基礎上改進了圖劃分方式，使得圖數據邏輯地被劃分在不同的處理器上，前驅節(jié)點的列表分布在每個分區(qū)上，并且在IBM Cyclops64處理器上對介度中心值計算性能進行了分析，取得了良好的性能.

3) 在異構方面，Zhi等人[19]提出了一種在GPU上的同步并行方式，圖劃分方式是將圖中的邊在線程之間進行了劃分，這種并行方式也取得了較好的性能.

4) 在其他方面，Yang等人[20]提出了一種添加虛擬節(jié)點的方式來降低有權圖介度中心值計算的時間，通過加虛擬節(jié)點使得圖中所有邊的權值相等，進而降低了有權圖計算介度中心值的時間復雜度.

增量式算法的目的主要是為了計算動態(tài)變化的圖的介度中心值，一方面，Lee等人[21]提出了一種基于MUC的介度中心值計算方法，該算法的核心思想是使得圖的變化范圍僅在MUC內部，當圖數據發(fā)生變化的時候只需要計算MUC內部節(jié)點的介度中心值即可；另一方面，Miray等人[22]和Green等人[23]提出了通過記錄大量中間結果的方式來計算動態(tài)變化的圖，當圖數據發(fā)生變化時只需要更改中間結果便可以完成對新生成圖的介度中心值計算.

2基于頂點加權的介度中心近似算法

2.1研究動機

很多自然圖具有無尺度特性[24]，具體特征為大多數節(jié)點只與很少的節(jié)點相連，只有極少數的點與大量的節(jié)點相連，這些極少數的節(jié)點是網絡中的“樞紐”.無尺度特性表現為網絡中的節(jié)點的度符合冪律分布[25]特性，如圖1[24]所示，網絡中1%點的邊數占總邊數的50%.造成自然圖無尺度特征的原因是:1)網絡中不斷有新的節(jié)點加進來，即增長性;2)新加進來的節(jié)點總是優(yōu)先連接那些度數高的點，即擇優(yōu)連接性.我們主要利用了自然圖的擇優(yōu)連接性和冪律分布的特性來降低介度中心算法的計算量.

Fig. 1　Power-law degree distribution.圖1　冪律分布圖

為了降低介度中心算法的計算量，一方面我們利用自然圖的擇優(yōu)連接性來減少相似的重復計算.自然圖的擇優(yōu)連接性[24]使得新加入網絡的低度節(jié)點都連接到一些高度的節(jié)點上，如圖2[26]所示，以這些高度的點和其入邊的點分別為源點計算最短路徑時，會存在大量相似重復計算.圖3是以s為源點的計算過程，圖4是以s入邊點為源點的計算過程.從圖3和圖4可以看出從n1到nk對其他點依賴值δ累加的效果和s效果是相同的，可以將這k+1次的計算通過加權的方式轉變成1次的計算，累加介度中心值時只需乘以重復計算依賴值δ的次數k，具體實現為

if(u!=s)，thenBC(u)+=(1+k)×δ(u)；

if(u==s)，thenBC(s)+=k×δ(s).

Fig. 2　Scale free network.圖2　無尺度網絡圖

Fig. 3　The traversal of source s .圖3　源點s的遍歷過程

Fig. 4　The traversal of the neighbors of s.圖4　s鄰居的遍歷過程

通過頂點加權的方式可以使得1個源點的遍歷效果相當于k+1個源點的遍歷效果，減少了計算量.例如使用相同源點進行介度中心計算時，選取了5種不同類型的網絡圖，在選擇相同源點的情況下，分析了加權方式和不加權方式得出的近似結果的精確度，比較了這2種方式的結果中排名前10個點的逆序對個數(具體介紹在3.2節(jié)中，值越小結果越精確)，如表1所示，頂點加權方式的近似結果比不加權方式近似結果的逆序對數減少22倍，提高了算法精確度.

Table 1　The Number of Inversions Between Vertex Weighted

Fig. 5　The comparsion of influence between high-degree and low-degree.圖5　高度點和低度點影響力對比

另一方面，利用自然圖的冪律分布特性來提高介度中心算法的計算質量.自然圖的冪律分布特性使得少部分的節(jié)點成為網絡的“樞紐”[26]，這些高度點對其他點有著很高的影響力，在計算介度中心值時也不例外.這些高度點對介度中心值貢獻較大，并且排名誤差較小.例如本文選取了5個不同類型的網絡圖，測試其高度源點和低度源點對排名前10個點的介度中心值的貢獻，如圖5所示，高度點對重要點介度中心值的貢獻是低度點貢獻的2.15倍(柱狀圖的面積越大表明貢獻程度越大).說明選擇低度點遍歷2次的效果相當于高度點遍歷1次的效果，可以將計算量減少2倍多.表2是分別選高度和低度的100個源點得到的前10的逆序對數，選擇高度源點的逆序對比低度源點的逆序對少了近4倍，精確度有很大提高.

Table 2　The Number of Inversions Between High-degree Sources and Low-degree Sources

基于以上的分析和測試，我們提出了一種基于頂點加權的介度中心近似算法，該近似算法把頂點加權方法與高度源點選擇方式相結合，大幅度削減計算量，從而提高計算效率.

2.2基于頂點加權的介度中心近似算法

基于頂點加權的介度中心近似算法的核心思想是：1)通過加權的方式，使得1次的遍歷效果等于k+1次的遍歷效果；2)選擇高影響力的源點，因為高影響力源點的一次遍歷效果相當于低影響力源點遍歷幾次的效果.這2種方式相結合選取少量的源點效果就相當于隨機近似算法中選取大量源點計算的效果.頂點加權近似算法主要包含3個階段：度數選擇源點階段、源點權值計算階段以及介度中心值計算階段.其中，源點選擇是選擇高影響力的源點(對頂點集合遍歷1遍，選擇度數最高的x%節(jié)點即可)；源點權值計算階段，引入k(s)記錄被選中的頂點s的重要性(頂點加權的權值)，如果頂點s某條入邊點不在選中的源點集合中，則k(s)的值加1(圖6(b)加括號中的行③～⑤)，這個值用于后續(xù)的介度中心值計算；在介度中心值計算階段，根據前一步得到的被選中頂點的權值來決定需要重復累加的次數(圖6(c)中的行⑤～⑧，其中行⑥之所以要加1，因為要考慮源點本身).

圖6(a)是該近似算法的具體實例.在源點選擇階段，將實例中的7個點按照度(在出入度中選擇較高的值，作為節(jié)點的度)的大小排序，選取度數高的n×x%的源點(x=3時已經達到了較高的精確度，如果需要更高精確度時可以增大x的值)；在源點權值計算階段，如圖6(b)所示，假設上圖頂點2和頂點4被選入源點集合，頂點2，4的權值分別為3和2；在介度中心值累加階段，如圖6(c)所示，累加介度中心值時需要將重復計算的效果累加到節(jié)點的介度中心值上，即以頂點2為源點遍歷時，所有點在累加介度中心值時需要依賴值乘以2的權值再累加到介度中心值上.由此可見，通過頂點加權的方式可以將經過頂點2的4次計算過程變成1次計算過程，將經過頂點4的3次計算過程變成了1次計算過程，整體計算量從7次變成了2次，計算量降低了3.5倍.

(a)Example of approximation algorithm

Thecomputingoftheweightedvaluekofsources: Input:GraphG(V,E),sources_set; Output:theweightedvaluekofsources. ①Functioncount_k() ② foreachsourcesinsource_setdo ③ foreachinsidevofsdo ④ if(visnotinsource_set)then ⑤ k[s]++; ⑥ endif ⑦ endfor ⑧ endfor ⑨returnk.ThecomputingofBC: Input:GraphG(V,E),sources_set,k Output:verticesBC ①FunctionBetweennessCentrality() ② foreachsourcesinsource_setdo ③ BFS(s); ④ delta→backward_accumulation(); ⑤ foreachvertexvinGraphGdo ⑥ ifv!=sthen ⑦ BC(v)+=(1+k[s])×delta[v]; ⑧ else ⑨ BC(s)+=k[s]×delta[s]; ⑩ endif endfor endfor returnBC.(b)Thephaseofcomputingsourcesvalueofk(c)ThephaseofcomputingBC

Fig. 6The approximation algorithm of betweenness centrality based on vertex-weighted and example.
圖6基于頂點加權的介度中心近似算法及示例

3實驗結果與分析

本節(jié)比較了2種近似算法(頂點加權近似算法和隨機近似算法)的精確度和性能，并進行深入分析.

3.1實驗方法

本文所采用的實驗環(huán)境為Intel Xeon E5645的機器，Linux 2.6.32，GCC版本4.1.2，編譯優(yōu)化選項為-O3,2種近似算法(頂點加權近似算法和隨機近似算法)和1個精確算法都是串行程序，單核執(zhí)行.表3所示為我們測試數據集，都來自于真實世界.

Table 3　The Figure of Test Data Sets

3.2誤差評價指標

為評測近似結果的精確性本文主要采用3個評價指標，分別是topk逆序對、topk逆序對百分比、topk集合覆蓋率.在實際應用中關注的只是少部分重要點的排名，所以本文所提到的誤差評價指標都是從排名前k的點的角度來分析的.每個指標的介紹如下：

1) topk逆序對.一個逆序對[8]的定義為

{(u,v)|rankexact(u)>rankexact(v) and

rankapprox(u)

表示近似結果排名前k個點的排名變化情況.

2) topk逆序對百分比.近似結果排名前k個點實際產生的逆序對占這k個點可能產生逆序對數的比例.

3) topk集合覆蓋率.表示近似結果中排名前k個點對精確結果中排名前k個點的覆蓋情況，假設近似結果前k個點中有y個點的精確結果也是前k，那么topk的集合覆蓋率就可以表示為(ky)×100%.集合覆蓋率可以反映出集合的精確程度.

3.3實驗結果

頂點加權介度中心近似算法在保證精確度的情況下降低介度中心算法計算量，減少算法運行時間.

3.3.1誤差測試結果

1) 逆序對以及逆序對百分比

表4的結果是基于頂點加權近似算法與隨機近似算法(選取60%的源點)結果的逆序對數對比，頂點加權近似算法的結果中前5個點幾乎是完全精確的，前10個點的平均逆序對數為1.8，隨機近似算法的平均逆序對數為0.4和8.隨著topk集合點數的增加，逆序對數不斷增加，可以看出頂點加權算法選取少量源點的方式的精確度與隨機近似算法選取60%的源點的精確度相當.表5是2種算法逆序對百分比的對比結果，從實驗結果看出，雖然2種算法中隨著k的增大逆序對也不斷增加，但是逆序對百分比都相對較小，最高不超過0.01%，二者的精確度都是比較高的.

2) 集合覆蓋率

基于頂點加權的介度中心近似算法在集合覆蓋率上有很高的精確度，平均覆蓋率達到95%以上.圖7是通過頂點加權近似算法(大部分圖約選取3%的源點)得到的近似結果的topk的集合覆蓋率，topk分別取5,10,15,20,…,100，頂點加權近似算法的得到近似結果的集合覆蓋率達到了平均95%以上，說明雖然集合內部存在排名變化的點，但是整個集合的精確度還是很高的.

Table 4　Random Approximation Algorithm and Vertex Weighted Approximation Algorithm for Comparing the Results of the Number of Inversions

Table 5　Random Approximation Algorithm and Vertex Weighted Approximation Algorithm for Comparing the Results of the Percentage of Inversions

Fig. 7　The set coverage of vertex weighted approximation algorithm results.圖7　頂點加權算法結果的覆蓋率

3.3.2性能測試結果

基于頂點加權的介度中心近似算法可以大大降低介度中心算法的運行時間，比精確算法的運行時間降低了24倍，比隨機近似算法的運行時間降低了15倍.如圖8和表6所示，圖8是隨機近似算法和頂點加權近似算法相對于介度中心算法的加速比，表示3種算法的運行時間對比，可以看出基于頂點加權的介度中心近似算法相對于介度中心算法的加速比為25，相對于隨機近似算法的加速比為16，通過頂點加權結合選擇高影響力源點的方式可以大大減少介度中心算法的運行時間.

Table 6　Random Approximation Algorithm and Vertex Weighted Approximation Algorithm for Comparing the Results of Performance

Notes: speedup of random is BC running timerandom running time; speedup of vertex weighted is BC running timevertex weighted running time.

Fig. 8　Approximation algorithm speedup.圖8　近似算法加速比

3.3.3實驗結果分析

1) 誤差分析

① 逆序對與覆蓋率分析

結合逆序對和覆蓋率的結果可以看出，除了Wiki-Talk以外其他測試數據的近似結果top10集合中都存在逆序對，但是其集合覆蓋率平均達到了95%，對測試集中精確結果中介度中心值高的前10個點的近似排名進行了研究，這5個測試集近似結果產生逆序對的原因是這些點的近似排名相對于精確排名有小范圍內的變化，但近似結果也都排在了前10，所以集合覆蓋率平均在98%以上，這說明頂點加權近似算法的精確度比較高.

另外，top10逆序對的產生主要是因為精確結果排名相鄰的節(jié)點相互發(fā)生了變化，這些點的精確介度中心值本身相差都小于10%，說明它們的重要程度相當，排名發(fā)生了變化也是可以接受的.

② 不同類型圖的精確性分析

測試集中圖的誤差測試結果顯示，有些圖的誤差中top10能達到與隨機近似算法相當甚至更好的精確度，有些圖的精確度相對較低，按照近似結果top10的精確程度將測試集中的圖分成2類：1)精確程度高的圖，有Slashdot0811,Email-EuAll,Web-Google,Wiki-Talk;2)精確程度相對較低的圖，如p2p-Gnutella31.

基于頂點加權的介度中心近似算法比較適合于度服從冪律分布的圖，經測試可知，精確度相對高的一類圖的出度和入度都服從冪律分布的特征，而精確度相對較低的一類圖只有入度符合冪律分布，出度不符合冪律分布，在介度中心算法中對其他點的介度值有影響的圖主要是出度，所以這類圖應該主要從出度高的點進行選擇，而減少重復計算量主要靠入邊的多少，所以只按出度選擇源點的方式會使得減少重復計算量較少，所以結果相對不是特別精確.

2) 性能分析

① 計算量對比分析

為了使近似結果的誤差達到較低的誤差率，在隨機近似算法中選取了n×60%的源點數，基于頂點加權的介度中心近似算法選取了n×3%的源點數.本文統計顯示，通過頂點加權的方式n×3%源點數的計算效果相當于不加權方式的n×40%源點數的計算效果，在結合選擇高度源點的方式得到結果精確度可以達到與隨機近似算法選擇n×60%的源點數的結果精確度，計算量減少了約20倍，可以達到平均20多倍的加速比.

② 不同類別圖的加速比分析

從不同測試數據的基于頂點加權的介度中心近似算法相對于介度中心算法的加速比結果可以看出，出入度都符合冪律分布的圖的平均加速比為30，而只有入度符合冪律分布的p2p-Gnutella31加速比為3.25，這是因為p2p-Gnutella31的出度不符合冪律分布的特征，無法按照度的大小選擇源點，該圖進行源點選擇時是按照出度選擇，通過頂點加權的方式對該圖的計算量降低并不明顯，為了保證與隨機近似算法結果的精確度相當，需要選取n×15%的源點數，是出入度都符合冪律分布圖源點數的5倍左右，所以p2p-Gnutella31的加速比較低.

3.3.4與并行介度中心算法的關系分析

介度中心并行算法從粗細粒度2個方面來提高算法的并行性，粗粒度是通過并行介度中心算法的源點的圖遍歷和累加過程減少算法的運行時間，細粒度主要是對一次圖遍歷和累加過程的內部并行，例如TanGuangming等人[16]提出的無鎖細粒度介度中心并行算法等.頂點加權算法只是減少了介度中心算法外層的循環(huán)次數，與介度中心的粗細力度并行是正交的，并不會影響并行算法的并行性.

4結束語

介度中心算法的瓶頸在于計算量太大，本文提出一種基于頂點加權的介度中心近似算法，該算法采用頂點加權的方式將多次的重復計算過程累加到1次計算上，結合選擇高影響力源點的方法可以大大降低介度中心算法的計算量，加速比平均達到了25倍，并且最大誤差百分比小于0.01%.但是這種算法只對符合冪律分布的自然圖處理比較有效，因此下一步的工作就是要進一步降低其他非冪律分布圖的計算量.

參考文獻

[1]Brandes U. A faster algorithm for betweenness centrality[J]. Journal of Mathematical Sociology, 2001, 25(2): 163-177

[2]Girvan M, Newman M. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences, 2002, 99(12): 7821-7826

[3]Krebs V. Mapping networks of terrorist cells[J]. Connections, 2002, 24(3): 43-52

[4]Jeong H, Mason S P, Barabesi A, et al. Lethality and centrality in protein networks[J]. Nature, 2001, 411(6833): 41-42

[5]Liljeros F, Edling C R, Amaral L A, et al. The web of human sexual contacts[J]. Nature, 2001, 411(6840): 907-908

[6]Meng Xiaofeng, Li Yong, Zhu Jianhua. Social computing in the era of big data: Opportunities and challenges[J]. Journal of Computer Research and Development, 2013, 50(12): 2483-2491 (in Chinese) (孟小峰, 李勇, 祝建華. 社會計算: 大數據時代的機遇與挑戰(zhàn)[J]. 計算機研究與發(fā)展, 2013, 50(12): 2483-2491)

[7]Leskovec J, Huttenlocher D, Kleinberg J. Signed networks in social media[C]Proc of the 28th CHI. New York: ACM, 2010: 1361-1370

[8]Brandes U, Pich C. Centrality estimation in large networks[J]. International Journal of Bifurcation & Chaos, 2007, 17(7): 2303-2318

[9]Geisberger R, Sanders P, Schultes D. Better approximation of betweenness centrality[J]. Alenex, 2008, 11(19): 90-100

[10]Bader D, Kintali S, Madduri K, et al. Approximating betweenness centrality[G]LNCS 4863: Proc of the WAW. Berlin: Computer Science, 2007: 124-137

[11]Jin S, Huang Z, Chen Y, et al. A novel application of parallel betweenness centrality to power grid contingency analysis[C]Proc of IEEE Int Symp on Parallel & Distributed Processing. Piscataway, NJ: IEEE, 2010: 1-7

[12]Yang Q, Lonardi S. A parallel algorithm for clustering protein-protein interaction networks[C]Proc of IEEE Computational Systems Bioinformatics. Los Alamitos, CA: IEEE Computer Society, 2005: 174-177

[13]Bader D A, Madduri K. Parallel algorithms for evaluating centrality indices in real-world networks[C]Proc of the 2006 Int Conf on Parallel Processing. New York: ACM, 2006: 539-550

[14]Madduri K, Ediger D, Jiang K, et al. A faster parallel algorithm and efficient multithreaded implementations for evaluating betweenness centrality on massive datasets[C]Proc of the 23rd IEEE Int Symp on Parallel & Distributed Processing. Los Alamitos, CA: IEEE Computer Society, 2009: 537-546

[15]Cong G, Makarychev K. Optimizing large-scale graph analysis on a multi-threaded, multi-core platform[C]Proc of the 26th Int Symp on Parallel & Distributed Processing. Los Alamitos, CA: IEEE Computer Society, 2011: 414-425

[16]Tan G, Tu D, Sun N. A parallel algorithm for computing betweenness centrality[C]Proc of the 42nd Int Conf on Parallel Processing. Los Alamitos, CA: IEEE Computer Society, 2009: 340-347

[17]Tan G, Sreedhar V C, Gao G R. Analysis and performance results of computing betweenness centrality on IBM Cyclops64[J]. Journal of Supercomputing, 2011, 56(1): 1-24

[18]Tu Dengbiao, Tan Guangming, Sun Ninghui. Fine-grained parallel betweenness centrality algorithm without lock synchronization[J]. Journal of Software, 2011, 22(5): 986-995 (in Chinese)(涂登彪, 譚光明, 孫凝暉. 無鎖同步的細粒度并行介度中心算法[J]. 軟件學報, 2011, 22(5): 986-995)

[19]Shi Z, Zhang B. Fast network centrality analysis using GPUs[J]. BMC Bioinformatics, 2011, 12(10): 149-156

[20]Yang J, Chen Y. Fast computing betweenness centrality with virtual nodes on large sparse networks[J]. Plos One, 2011, 6(7): 1-5

[21]Lee M J, Lee J, Park J Y, et al. Qube a quick algorithm for updating betweenness centrality[C]Proc of the 21st Int Conf on World Wide Web. New York: ACM, 2012: 351-360

[22]Kas M, Wachs M, Carley K M, et al. Incremental algorithm for updating betweenness centrality in dynamically growing networks[C]Proc of Int Conf on Advances in Social Networks Analysis & Mining. Piscataway, NJ: IEEE, 2013: 33-40

[23]Green O, McColl R, Bader D A. A fast algorithm for streaming betweenness centrality[C]Proc of Int Conf on Privacy, Security, Risk & Trust. Piscataway, NJ: IEEE, 2012: 11-20

[24]Pastor-Satorras R, Vespignani A. Epidemic spreading in scalevfree networks.[J]. Physical Review Letters, 2001, 86(1): 3200-3203

[25]Tang Daquan, He Mingke, Meng Qingsong. Research on searching in unstructured P2P network based on power-law distribution and small world character[J]. Journal of Computer Research and Development, 2007, 44(9): 1566-1571 (in Chinese)(湯大權, 賀明科, 孟慶崧, 基于冪律分布和小世界特性的無結構P2P網絡中搜索方法研究[J]. 計算機研究與發(fā)展, 2007, 44(9): 1566-1571)

[26]Costa L F, Rodrigues F A, Travieso G, et al. Charac-terization of complex networks: A survey of measurements[J]. Advances in Physics, 2007, 56(1): 167-242

[27]Ripeanu M, Foster I, Iamnitchi A. Mapping the gnutella network: Properties of large-scale peer-to-peer systems and implications for system design[J]. IEEE Internet Computing Journal, 2002, 6(1): 85-93

[28]Leskovec J, Kleinberg J, Faloutsos C. Graph evolution: Densification and shrinking diameters[J]. ACM Trans on Knowledge Discovery from Data, 2006, 1(1): 1-42

[29]Leskovec J, Lang K J, Mahoney A D M W. Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters[J]. Internet Mathematics, 2008, 6(1): 29-123

[30]Laura L, Donato D, Leonardi S, et al. Large scale properties of the Webgraph[J]. European Physical Journal, 2004, 38(2): 239-243

Wang Min, born in 1990. Master. Her main research interests include parallel computing and graph algorithm.

Wang Lei, born in 1976. PhD, assistant professor. Her main research interests include parallel computing and compiler optimization.

Feng Xiaobing, born in 1969. Professor and PhD supervisor. His main research interests include compiler optimization and binary translation.

Cao Baoxiang, born in 1955. Professor and master supervisor. Senior member of China Computer Federation. His main research interests include database and enterprise informationization.

收稿日期：2014-12-10；修回日期：2015-05-13

基金項目：國家“八六三”高技術研究發(fā)展計劃基金項目(2015AA011505)；國家自然科學基金項目(61402445，61303053，61202055，61221062)This work was supported by the National High Technology Research and Development Program of China (863 Program) (2015AA011505) and the National Natural Science Foundation of China (61402445，61303053，61202055，61221062).

通信作者：王蕾(wlei@ict.ac.cn)

中圖法分類號TP311

An Approximation Algorithm of Betweenness Centrality Based on Vertex Weighted

Wang Min1,2, Wang Lei1, Feng Xiaobing1, and Cao Baoxiang2

1(StateKeyLaboratoryofComputerArchitecture(InstituteofComputingTechnology,ChineseAcademyofSciences),Beijing100190)2(CollegeofInformationScienceandEngineering,QufuNormalUniversity,Rizhao,Shandong276800)

AbstractBetweenness centrality (BC) is a widely used indicator to measure the importance of network vertices. Currently the fastest time complexity of the algorithm is O(V×E). When computing the BC of vertices in networks, we need to do n times searches of single source shortest path. In big data era, networks have more nodes and edges, and the amount of calculation of BC algorithm is large. The huge amount of calculation makes the algorithm need a long time to compute each vertices’ BC value, and the algorithm cannot be applied in practice. The related work focuses on approximation to reduce the running time of BC algorithm, but they also can not reduce the amount of calculation of BC algorithm significantly. In order to further reduce the amount of the calculation of BC algorithm, we propose a vertex weighted approximation algorithm to reduce the amount of calculation of BC algorithm, and the algorithm can make the calculation process be repeated many times to accumulate on a calculation by vertex weighted and select high-impact vertex as source to compute BC. We can reduce the amount of calculation significantly in this way, and meet the requirement of lower error rate and high performance. The approximation algorithm of BC based on vertex weighted can achieve 25 times speedup, and the error rate is lower than percentage of 0.01.

Key wordsbetweenness centrality (BC) algorithm; calculation; influence; vertex weighted; approximation