王　敏　王　蕾　馮曉兵　曹寶香

1(計(jì)算機(jī)體系結(jié)構(gòu)國家重點(diǎn)實(shí)驗(yàn)室(中國科學(xué)院計(jì)算技術(shù)研究所)　北京　100190)2　　　(曲阜師范大學(xué)信息科學(xué)與工程學(xué)院　山東日照　276800)

?

基于頂點(diǎn)加權(quán)的介度中心近似算法研究

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

1(計(jì)算機(jī)體系結(jié)構(gòu)國家重點(diǎn)實(shí)驗(yàn)室(中國科學(xué)院計(jì)算技術(shù)研究所)北京100190)2(曲阜師范大學(xué)信息科學(xué)與工程學(xué)院山東日照276800)

(wangmin01@ict.ac.cn)

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

關(guān)鍵詞介度中心算法；計(jì)算量；影響力；頂點(diǎn)加權(quán)；近似

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

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

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

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

本文提出了一種基于頂點(diǎn)加權(quán)的介度中心近似算法，該近似算法核心思想是減少計(jì)算量.通過減少相似的重復(fù)計(jì)算并結(jié)合選取高度源點(diǎn)的方式，使得少數(shù)次的遍歷計(jì)算效果相當(dāng)于多次的遍歷計(jì)算效果，從而達(dá)到降低計(jì)算量的目的.實(shí)驗(yàn)結(jié)果顯示該算法的平均加速比為25，逆序?qū)Π俜直?衡量誤差的1個(gè)指標(biāo)，見4.2節(jié))也都小于0.01%.該算法降低的只是單源最短路徑的計(jì)算次數(shù)，所以這種方式并不會(huì)影響并行介度中心算法的并行性，與并行算法是正交的.

1相關(guān)工作

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

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

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

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

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

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

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

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

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

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

2基于頂點(diǎn)加權(quán)的介度中心近似算法

2.1研究動(dòng)機(jī)

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

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

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

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

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

Fig. 2　Scale free network.圖2　無尺度網(wǎng)絡(luò)圖

Fig. 3　The traversal of source s .圖3　源點(diǎn)s的遍歷過程

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

通過頂點(diǎn)加權(quán)的方式可以使得1個(gè)源點(diǎn)的遍歷效果相當(dāng)于k+1個(gè)源點(diǎn)的遍歷效果，減少了計(jì)算量.例如使用相同源點(diǎn)進(jìn)行介度中心計(jì)算時(shí)，選取了5種不同類型的網(wǎng)絡(luò)圖，在選擇相同源點(diǎn)的情況下，分析了加權(quán)方式和不加權(quán)方式得出的近似結(jié)果的精確度，比較了這2種方式的結(jié)果中排名前10個(gè)點(diǎn)的逆序?qū)€(gè)數(shù)(具體介紹在3.2節(jié)中，值越小結(jié)果越精確)，如表1所示，頂點(diǎn)加權(quán)方式的近似結(jié)果比不加權(quán)方式近似結(jié)果的逆序?qū)?shù)減少22倍，提高了算法精確度.

Table 1　The Number of Inversions Between Vertex Weighted

Fig. 5　The comparsion of influence between high-degree and low-degree.圖5　高度點(diǎn)和低度點(diǎn)影響力對(duì)比

另一方面，利用自然圖的冪律分布特性來提高介度中心算法的計(jì)算質(zhì)量.自然圖的冪律分布特性使得少部分的節(jié)點(diǎn)成為網(wǎng)絡(luò)的“樞紐”[26]，這些高度點(diǎn)對(duì)其他點(diǎn)有著很高的影響力，在計(jì)算介度中心值時(shí)也不例外.這些高度點(diǎn)對(duì)介度中心值貢獻(xiàn)較大，并且排名誤差較小.例如本文選取了5個(gè)不同類型的網(wǎng)絡(luò)圖，測試其高度源點(diǎn)和低度源點(diǎn)對(duì)排名前10個(gè)點(diǎn)的介度中心值的貢獻(xiàn)，如圖5所示，高度點(diǎn)對(duì)重要點(diǎn)介度中心值的貢獻(xiàn)是低度點(diǎn)貢獻(xiàn)的2.15倍(柱狀圖的面積越大表明貢獻(xiàn)程度越大).說明選擇低度點(diǎn)遍歷2次的效果相當(dāng)于高度點(diǎn)遍歷1次的效果，可以將計(jì)算量減少2倍多.表2是分別選高度和低度的100個(gè)源點(diǎn)得到的前10的逆序?qū)?shù)，選擇高度源點(diǎn)的逆序?qū)Ρ鹊投仍袋c(diǎn)的逆序?qū)ι倭私?倍，精確度有很大提高.

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

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

2.2基于頂點(diǎn)加權(quán)的介度中心近似算法

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

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

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

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

3.1實(shí)驗(yàn)方法

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

Table 3　The Figure of Test Data Sets

3.2誤差評(píng)價(jià)指標(biāo)

為評(píng)測近似結(jié)果的精確性本文主要采用3個(gè)評(píng)價(jià)指標(biāo)，分別是topk逆序?qū)?、topk逆序?qū)Π俜直取opk集合覆蓋率.在實(shí)際應(yīng)用中關(guān)注的只是少部分重要點(diǎn)的排名，所以本文所提到的誤差評(píng)價(jià)指標(biāo)都是從排名前k的點(diǎn)的角度來分析的.每個(gè)指標(biāo)的介紹如下：

1) topk逆序?qū)?一個(gè)逆序?qū)8]的定義為

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

rankapprox(u)

表示近似結(jié)果排名前k個(gè)點(diǎn)的排名變化情況.

2) topk逆序?qū)Π俜直?近似結(jié)果排名前k個(gè)點(diǎn)實(shí)際產(chǎn)生的逆序?qū)φ歼@k個(gè)點(diǎn)可能產(chǎn)生逆序?qū)?shù)的比例.

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

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

頂點(diǎn)加權(quán)介度中心近似算法在保證精確度的情況下降低介度中心算法計(jì)算量，減少算法運(yùn)行時(shí)間.

3.3.1誤差測試結(jié)果

1) 逆序?qū)σ约澳嫘驅(qū)Π俜直?/p>

表4的結(jié)果是基于頂點(diǎn)加權(quán)近似算法與隨機(jī)近似算法(選取60%的源點(diǎn))結(jié)果的逆序?qū)?shù)對(duì)比，頂點(diǎn)加權(quán)近似算法的結(jié)果中前5個(gè)點(diǎn)幾乎是完全精確的，前10個(gè)點(diǎn)的平均逆序?qū)?shù)為1.8，隨機(jī)近似算法的平均逆序?qū)?shù)為0.4和8.隨著topk集合點(diǎn)數(shù)的增加，逆序?qū)?shù)不斷增加，可以看出頂點(diǎn)加權(quán)算法選取少量源點(diǎn)的方式的精確度與隨機(jī)近似算法選取60%的源點(diǎn)的精確度相當(dāng).表5是2種算法逆序?qū)Π俜直鹊膶?duì)比結(jié)果，從實(shí)驗(yàn)結(jié)果看出，雖然2種算法中隨著k的增大逆序?qū)σ膊粩嘣黾樱悄嫘驅(qū)Π俜直榷枷鄬?duì)較小，最高不超過0.01%，二者的精確度都是比較高的.

2) 集合覆蓋率

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

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　頂點(diǎn)加權(quán)算法結(jié)果的覆蓋率

3.3.2性能測試結(jié)果

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

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實(shí)驗(yàn)結(jié)果分析

1) 誤差分析

① 逆序?qū)εc覆蓋率分析

結(jié)合逆序?qū)透采w率的結(jié)果可以看出，除了Wiki-Talk以外其他測試數(shù)據(jù)的近似結(jié)果top10集合中都存在逆序?qū)?，但是其集合覆蓋率平均達(dá)到了95%，對(duì)測試集中精確結(jié)果中介度中心值高的前10個(gè)點(diǎn)的近似排名進(jìn)行了研究，這5個(gè)測試集近似結(jié)果產(chǎn)生逆序?qū)Φ脑蚴沁@些點(diǎn)的近似排名相對(duì)于精確排名有小范圍內(nèi)的變化，但近似結(jié)果也都排在了前10，所以集合覆蓋率平均在98%以上，這說明頂點(diǎn)加權(quán)近似算法的精確度比較高.

另外，top10逆序?qū)Φ漠a(chǎn)生主要是因?yàn)榫_結(jié)果排名相鄰的節(jié)點(diǎn)相互發(fā)生了變化，這些點(diǎn)的精確介度中心值本身相差都小于10%，說明它們的重要程度相當(dāng)，排名發(fā)生了變化也是可以接受的.

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

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

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

2) 性能分析

① 計(jì)算量對(duì)比分析

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

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

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

3.3.4與并行介度中心算法的關(guān)系分析

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

4結(jié)束語

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

參考文獻(xiàn)

[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) (孟小峰, 李勇, 祝建華. 社會(huì)計(jì)算: 大數(shù)據(jù)時(shí)代的機(jī)遇與挑戰(zhàn)[J]. 計(jì)算機(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)(涂登彪, 譚光明, 孫凝暉. 無鎖同步的細(xì)粒度并行介度中心算法[J]. 軟件學(xué)報(bào), 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)(湯大權(quán), 賀明科, 孟慶崧, 基于冪律分布和小世界特性的無結(jié)構(gòu)P2P網(wǎng)絡(luò)中搜索方法研究[J]. 計(jì)算機(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

基金項(xiàng)目：國家“八六三”高技術(shù)研究發(fā)展計(jì)劃基金項(xiàng)目(2015AA011505)；國家自然科學(xué)基金項(xiàng)目(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)

中圖法分類號(hào)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