基于橋系數(shù)的分裂社區(qū)檢測(cè)算法研究

冀慶斌，康 茜，李德玉，王素格

(山西大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院, 山西 太原 030051)

基于橋系數(shù)的分裂社區(qū)檢測(cè)算法研究

冀慶斌，康 茜，李德玉，王素格

(山西大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院, 山西 太原 030051)

研究社區(qū)結(jié)構(gòu)有助于揭示網(wǎng)絡(luò)結(jié)構(gòu)和功能之間的關(guān)系，而社區(qū)檢測(cè)是社區(qū)結(jié)構(gòu)研究的基礎(chǔ)和核心。該文定義了一種聚集度橋系數(shù)，將其應(yīng)用到社區(qū)檢測(cè)中，設(shè)計(jì)出一種分裂社區(qū)檢測(cè)方法，包括分裂和合并兩個(gè)算法。分裂算法使用橋系數(shù)識(shí)別社區(qū)間邊，通過迭代刪除社區(qū)間邊分解網(wǎng)絡(luò)，從而發(fā)現(xiàn)網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)；合并算法根據(jù)社區(qū)連接強(qiáng)度合并社區(qū)，可以揭示社區(qū)結(jié)構(gòu)中的分層嵌套的現(xiàn)象。在六個(gè)社會(huì)網(wǎng)絡(luò)數(shù)據(jù)集上的實(shí)驗(yàn)表明，本文算法可以有效的將網(wǎng)絡(luò)分裂為有意義的社區(qū)，并且準(zhǔn)確性接近或超過經(jīng)典的社區(qū)檢測(cè)算法。

社區(qū)檢測(cè)；分裂算法；橋系數(shù)

1 引言

現(xiàn)實(shí)世界中的許多系統(tǒng)，如朋友網(wǎng)、協(xié)作網(wǎng)和Internet等都可以抽象成復(fù)雜網(wǎng)絡(luò)[1]，這些網(wǎng)絡(luò)都具有社區(qū)結(jié)構(gòu)的特征，即網(wǎng)絡(luò)中的節(jié)點(diǎn)可以自然形成節(jié)點(diǎn)組，同一個(gè)節(jié)點(diǎn)組內(nèi)的節(jié)點(diǎn)的連接具有稠密性，而不同節(jié)點(diǎn)組間的節(jié)點(diǎn)的連接具有稀疏性[2]。研究社區(qū)結(jié)構(gòu)有助于分析網(wǎng)絡(luò)的特性[3]，而社區(qū)檢測(cè)是社區(qū)結(jié)構(gòu)研究的基礎(chǔ)和核心[4]，通過網(wǎng)絡(luò)拓?fù)湫畔ⅲR(shí)別網(wǎng)絡(luò)中連接稠密的節(jié)點(diǎn)組[5]用于社區(qū)的發(fā)現(xiàn)。

為了獲得復(fù)雜網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)，學(xué)者們從不同的角度提出了許多社區(qū)檢測(cè)方法，主要有：相似度方法[6]、模塊度方法[7]、譜方法[8]、派系過濾方法[9]、塊模型方法[10]、標(biāo)簽傳播方法[11]和分裂方法[12]等。其中，分裂方法是較早開始研究的一類社區(qū)檢測(cè)方法，其核心問題是社區(qū)間邊的識(shí)別。通過迭代刪除社區(qū)間邊，分裂方法用于分解網(wǎng)絡(luò)，從而獲得網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)。

GN算法[13]使用邊介數(shù)識(shí)別社區(qū)間邊，是一種典型的分裂方法，其計(jì)算邊介數(shù)的時(shí)間復(fù)雜度為O(mn)[14]，而整個(gè)算法的時(shí)間復(fù)雜度為O(n3)。為了提高邊介數(shù)的計(jì)算效率，Tyler等[15]采用抽樣的方法降低邊介數(shù)的計(jì)算復(fù)雜度，Green等[16]使用并行技術(shù)提高邊介數(shù)的計(jì)算效率。然而抽樣需要網(wǎng)絡(luò)的統(tǒng)計(jì)信息，難以普遍推廣，而并行計(jì)算僅提高了計(jì)算速度，時(shí)間復(fù)雜度問題沒有得到很好的解決。文獻(xiàn)[17]利用節(jié)點(diǎn)相似度將無權(quán)網(wǎng)絡(luò)映射為加權(quán)網(wǎng)絡(luò)，通過邊的權(quán)重識(shí)別社區(qū)間邊，但映射過程需要鄰接矩陣的乘法運(yùn)算，使得整個(gè)算法的時(shí)間復(fù)雜度大于O(n3)。

Radicchi等[18]認(rèn)為使用局部指標(biāo)識(shí)別社區(qū)間邊可降低分裂算法的時(shí)間復(fù)雜度。目前，這類局部指標(biāo)主要有邊聚類系數(shù)[18]和最大團(tuán)橋系數(shù)[19]，但當(dāng)邊聚類系數(shù)的階數(shù)較大時(shí)就不再是局部指標(biāo)[5]。文獻(xiàn)[20]利用文獻(xiàn)[19]的橋系數(shù)，認(rèn)為橋系數(shù)大的邊更可能是社區(qū)間邊，提出了一個(gè)凝聚算法。最大團(tuán)橋系數(shù)直接用于分裂社區(qū)檢測(cè)有兩點(diǎn)不足：(1)求解最大團(tuán)算法的時(shí)間復(fù)雜度大于O(n2)[21]，因此直接引入最大團(tuán)橋系數(shù)不能降低分裂算法的時(shí)間復(fù)雜度；(2)文獻(xiàn)[19]提出最大團(tuán)橋系數(shù)的目的是加速網(wǎng)絡(luò)分解，而網(wǎng)絡(luò)分解與社區(qū)檢測(cè)的要求并不相同[22]。本文從網(wǎng)絡(luò)中節(jié)點(diǎn)局部聚集的角度，定義了基于局部聚集度的橋系數(shù)，以有效識(shí)別社區(qū)間邊，進(jìn)而以橋系數(shù)為基礎(chǔ)設(shè)計(jì)了社區(qū)檢測(cè)算法，用于降低分裂算法的時(shí)間復(fù)雜度，提高分裂算法的效率。

BGLL算法[23]使用模塊度作為度量，采用逐步合并的方法合并社區(qū)，從而得到了社區(qū)的層次關(guān)系。但是已有研究[24,25]發(fā)現(xiàn)，模塊度方法存在分辨率限制，使用模塊度評(píng)價(jià)社區(qū)劃分質(zhì)量不一定能夠得到真實(shí)的社區(qū)結(jié)構(gòu)[2,26]，為此Chertkov等人[27]使用p-強(qiáng)社區(qū)來評(píng)價(jià)社區(qū)的質(zhì)量。本文借鑒BGLL算法[23]和p-強(qiáng)社區(qū)[27]的思想，設(shè)計(jì)了社區(qū)合并算法，可以揭示社區(qū)的層次結(jié)構(gòu)。

2 聚集度橋系數(shù)和社區(qū)強(qiáng)度的定義

2.1 最大團(tuán)橋系數(shù)

為了量化網(wǎng)絡(luò)中邊的連接強(qiáng)度，Cheng等[19]提出了最大團(tuán)橋系數(shù)的概念，定義如下：

其中，x和y是邊e的兩個(gè)端點(diǎn)，Sx、Sy和Se分別是包含節(jié)點(diǎn)x、y和邊e的最大團(tuán)的規(guī)模。

網(wǎng)絡(luò)中的團(tuán)可以刻畫節(jié)點(diǎn)的局部聚集特性[28]，因而最大團(tuán)橋系數(shù)本質(zhì)上是一種對(duì)節(jié)點(diǎn)局部聚集度的度量。

2.2 聚集度橋系數(shù)

在網(wǎng)絡(luò)分析中，一般使用聚類系數(shù)度量節(jié)點(diǎn)的局部聚集程度[29]；同時(shí)文獻(xiàn)[30]指出，偏好依賴是現(xiàn)實(shí)網(wǎng)絡(luò)的一大特點(diǎn)，因此節(jié)點(diǎn)的度也是度量節(jié)點(diǎn)聚集程度的重要指標(biāo)。由此，給出本文聚集度橋系數(shù)的定義。

給定無向網(wǎng)絡(luò)G=(V, E)，V={x}表示網(wǎng)絡(luò)中n個(gè)節(jié)點(diǎn)的集合，E={(x, y)}表示網(wǎng)絡(luò)中m條邊的集合。對(duì)于節(jié)點(diǎn)x，記N(x)為其近鄰，N[x]={x}∪N(x)為其閉合近鄰[31]，GV′為節(jié)點(diǎn)集V′對(duì)G的導(dǎo)出子圖。對(duì)于子網(wǎng)絡(luò)G′和其中的一個(gè)節(jié)點(diǎn)x，x在G′中的聚類系數(shù)記為Cx|G′，x在G′中的度記為dx|G′。

定義1對(duì)于邊(x,y)，聚集度橋系數(shù)定義為

其中，N[x]-{y}表示刪除邊(x, y)后節(jié)點(diǎn)x的閉合近鄰。

式(2)可以表示如下的意義：如果一條邊的兩個(gè)端點(diǎn)的共同鄰居較少，而且刪除邊后各自聚集鄰居的程度較強(qiáng)，則這條邊連接其端點(diǎn)的能力就較弱。

由于分子上的階數(shù)并不改變其單調(diào)性，因此，式(2)可以改寫為式(3)。

2.3 社區(qū)強(qiáng)度

為了評(píng)價(jià)社區(qū)的質(zhì)量，Chertkov等人[27]提出了p-強(qiáng)社區(qū)的概念，要求社區(qū)滿足以下條件：

將公式(4)改寫，給出社區(qū)強(qiáng)度的形式化定義。

定義2社區(qū)強(qiáng)度定義為

可知，社區(qū)強(qiáng)度表示內(nèi)部度大于外部度的節(jié)點(diǎn)數(shù)在整個(gè)社區(qū)中所占的比例。對(duì)于式(5)，有p∈[0～1]，p越大，表示社區(qū)越強(qiáng)；當(dāng)p=1時(shí)，社區(qū)成為強(qiáng)社區(qū)。

社區(qū)合并的過程中，應(yīng)該首先合并連接最緊密的社區(qū)。為此，本文使用社區(qū)連接強(qiáng)度來度量社區(qū)連接的緊密程度。

定義3兩個(gè)社區(qū)的連接強(qiáng)度定義為

其中，Sc1表示社區(qū)c1內(nèi)部邊的數(shù)量，ωc1,c2表示社區(qū)c1和c2之間邊的數(shù)量。T越大，表示兩個(gè)社區(qū)之間的連接越強(qiáng)，越有可能合并為一個(gè)社區(qū)。

3 基于橋系數(shù)的分裂社區(qū)檢測(cè)算法

為了檢測(cè)出網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)，本節(jié)給出基于橋系數(shù)的分裂社區(qū)檢測(cè)方法(bridgeness index algorithm，BI算法)。首先使用橋系數(shù)將網(wǎng)絡(luò)分解為多個(gè)小社區(qū)，然后根據(jù)社區(qū)連接強(qiáng)度合并小社區(qū)。BI算法包括分裂網(wǎng)絡(luò)、合并社區(qū)兩個(gè)算法。

3.1 使用橋系數(shù)分裂網(wǎng)絡(luò)算法

基本思想：利用橋系數(shù)作為移除邊的標(biāo)準(zhǔn)，不斷重復(fù)刪除橋系數(shù)最大的邊，直到橋系數(shù)均為零或社區(qū)劃分的模塊度不再增加為止。

算法1Splitting(G)，使用橋系數(shù)分裂網(wǎng)絡(luò)算法。

輸入：網(wǎng)絡(luò)G (V, E)。

輸出：初始社區(qū)劃分P。

Begin

(1) 初始化模塊度Q=0，社區(qū)數(shù)C=1；

(2) 計(jì)算所有的橋系數(shù)bi；

(3) while(True)

(4) 找出最大橋系數(shù)bix,y；

(5) 如果 bix,y=0，跳到步驟(11)；

(6) 刪除邊(x,y)；

(7) 重新計(jì)算CC和Q；

(8) 如果CC增大而Q不再增大，跳到步驟(11)；

(9) 更新節(jié)點(diǎn)x和y的鄰接邊的橋系數(shù)；

(10) end；

(11) 返回社區(qū)劃分P。

End

利用算法1，可將橋系數(shù)最大的邊識(shí)別為社區(qū)間邊。在計(jì)算一條邊的橋系數(shù)時(shí)，需要遍歷兩個(gè)端點(diǎn)的鄰居和二步鄰居[32]一次即可，由此可以看出，聚集度橋系數(shù)是一個(gè)典型的局部指數(shù)。

3.2 使用社區(qū)連接強(qiáng)度合并社區(qū)算法

基本思想：根據(jù)社區(qū)連接強(qiáng)度逐層合并社區(qū)，直到合并后的社區(qū)強(qiáng)度不再增加為止。

算法2Merging (G, P)，使用社區(qū)連接強(qiáng)度合并網(wǎng)絡(luò)算法。

輸入：網(wǎng)絡(luò)G (V, E)，初始劃分P。

輸出：包含層次關(guān)系的社區(qū)劃分Pc。

Begin

(1) 初始化, 計(jì)算P包含的社區(qū)數(shù)CC；

(2) while(True)

(3) 計(jì)算所有社區(qū)間的連接強(qiáng)度Tc1,c2；

(4) 找出連接強(qiáng)度最大的兩個(gè)社區(qū)i和j；

(5) 計(jì)算合并前的社區(qū)強(qiáng)度pi和pj，以及合并后的社區(qū)強(qiáng)度p；

(6) 如果 p < sqrt(pi, pi)，跳到步驟(9)；

(7) 合并社區(qū)i和j，并更新P和T；

(8) end；

(9) 返回包含層次關(guān)系的社區(qū)劃分Pc。

End

算法2的合并過程可以看成是社區(qū)間逐漸吸引的過程，用于發(fā)現(xiàn)重疊的社區(qū)結(jié)構(gòu)。當(dāng)整個(gè)網(wǎng)絡(luò)作為一個(gè)社區(qū)時(shí)，社區(qū)連接強(qiáng)度不再有意義，由此算法2至少可以得到兩個(gè)社區(qū)。

3.3 BI算法時(shí)間復(fù)雜度分析

在BI算法中，計(jì)算最耗時(shí)的部分是算法1中對(duì)橋系數(shù)的計(jì)算。

(1) 計(jì)算整個(gè)網(wǎng)絡(luò)的橋系數(shù)的復(fù)雜度：計(jì)算一條邊的橋系數(shù)需要計(jì)算兩個(gè)點(diǎn)聚類系數(shù)和一條邊聚類系數(shù)，而計(jì)算一個(gè)節(jié)點(diǎn)和一條邊的聚類系數(shù)的復(fù)雜度均為O(k2)，因此，計(jì)算整個(gè)網(wǎng)絡(luò)的橋系數(shù)的復(fù)雜度為O(3mk2)。

(2) 迭代過程的復(fù)雜度：當(dāng)刪除一條邊后，需要更新兩個(gè)端點(diǎn)的鄰接邊的橋系數(shù)，而更新過程的復(fù)雜度為O(2k·3k2)。在最差情況下，需要?jiǎng)h除m條邊，整個(gè)迭代過程的復(fù)雜度為O(2mk·3k2)。

綜上所述，整個(gè)算法的時(shí)間復(fù)雜度為O(3mk2+2mk·3k2)，即在稀疏網(wǎng)絡(luò)中的時(shí)間復(fù)雜度近似于O(nk3)。

4 實(shí)驗(yàn)結(jié)果及分析

本節(jié)將在六個(gè)真實(shí)的社會(huì)網(wǎng)絡(luò)數(shù)據(jù)集上測(cè)試BI算法的有效性。同時(shí)，與其他幾個(gè)具有代表性的社區(qū)發(fā)現(xiàn)算法GN算法[13]、CNM算法[7]、BGLL算法[13]和LPA算法[11]進(jìn)行比較。

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

本文使用的六個(gè)社會(huì)網(wǎng)絡(luò)數(shù)據(jù)集如下。

(1) Zachary’s Karate Club (簡(jiǎn)稱Karate)，是二十世紀(jì)七十年代一所美國大學(xué)的空手道俱樂部的34名成員間的朋友網(wǎng)[33]，真實(shí)網(wǎng)絡(luò)擁有兩個(gè)社區(qū)。

(2) Dolphin Social Network (簡(jiǎn)稱Dolphins)，是生活在新西蘭Doubtful Sound海灣的一群62只海豚間的接觸網(wǎng)[34]，真實(shí)網(wǎng)絡(luò)擁有兩個(gè)社區(qū)。

(3) Books about US Politics(簡(jiǎn)稱PolBooks)，是亞馬遜網(wǎng)上書店售賣的關(guān)于2004年美國總統(tǒng)選舉的政治圖書間的關(guān)系網(wǎng)，真實(shí)網(wǎng)絡(luò)擁有三個(gè)社區(qū)。

(4) American College Football(簡(jiǎn)稱Football)，是根據(jù)2000年美國高校美式足球秋季常規(guī)賽季的分組比賽情況形成的網(wǎng)絡(luò)，真實(shí)網(wǎng)絡(luò)擁有12個(gè)社區(qū)。

(5) Jazz Musicians Network (簡(jiǎn)稱Jazz)，是根據(jù)1912～1940年之間的198個(gè)爵士樂樂隊(duì)之間的合作關(guān)系形成的網(wǎng)絡(luò)。Gleiser等[35]最早研究了這個(gè)網(wǎng)絡(luò)，指出Jazz網(wǎng)絡(luò)大致包括兩個(gè)社區(qū)。

(6) General Relativity and Quantum Cosmology Network[36](簡(jiǎn)稱GR-QC)，是電子預(yù)印本文庫中1993年1月至2003年4月之間關(guān)于廣義相對(duì)論和量子宇宙論范疇論文作者之間的科學(xué)合作網(wǎng)。

這六個(gè)數(shù)據(jù)集的基本統(tǒng)計(jì)性質(zhì)如表1所示。

表1 本文使用數(shù)據(jù)集的基本統(tǒng)計(jì)性質(zhì)

4.2 評(píng)價(jià)指標(biāo)

本文使用以下三個(gè)指標(biāo)評(píng)價(jià)社區(qū)劃分的質(zhì)量：

(1) FVIC(fraction of vertices identified correctly)，正確劃分的節(jié)點(diǎn)總數(shù)占所有節(jié)點(diǎn)數(shù)的比率。對(duì)于已知社區(qū)結(jié)構(gòu)的網(wǎng)絡(luò)，給出社區(qū)劃分后，即可計(jì)算有多少比例節(jié)點(diǎn)的劃分是正確的。

(2) 歸一化互信息(NMI)[37]。算法發(fā)現(xiàn)的社區(qū)個(gè)數(shù)與真實(shí)社區(qū)個(gè)數(shù)并一定相等，這種情況下可以使用基于信息論的NMI對(duì)劃分結(jié)果進(jìn)行評(píng)價(jià)。NMI定義為

其中，N為混淆矩陣；Ni,j表示“真實(shí)”社區(qū)i和發(fā)現(xiàn)的社區(qū)j重合的節(jié)點(diǎn)個(gè)數(shù)；Ni.為矩陣第i行的元素之和；N.i為矩陣第j列的元素之和；CR表示“真實(shí)”社區(qū)的個(gè)數(shù)；CF表示發(fā)現(xiàn)的社區(qū)個(gè)數(shù)；R表示“真實(shí)”社區(qū)；F表示發(fā)現(xiàn)的社區(qū)。

(3) 模塊度[2,7]。它是一個(gè)衡量社區(qū)劃分質(zhì)量的客觀的指標(biāo)。對(duì)于未知社區(qū)結(jié)構(gòu)的兩個(gè)網(wǎng)絡(luò)，可以使用模塊度檢測(cè)算法結(jié)果的有效性。

4.3 實(shí)驗(yàn)結(jié)果及分析

實(shí)驗(yàn)1使用BI算法檢測(cè)Karate網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)

在Karate網(wǎng)絡(luò)上運(yùn)行BI算法，其中算法1將Karate網(wǎng)絡(luò)劃分為四個(gè)社區(qū)，分別用三角形、菱形、正方形、圓形代表；算法2根據(jù)社區(qū)連接強(qiáng)度將四個(gè)社區(qū)合并為兩個(gè)社區(qū)，結(jié)果如圖1所示，兩個(gè)社區(qū)以虛線分隔。真實(shí)的社區(qū)結(jié)構(gòu)如圖2所示。

圖1 BI算法在Karate網(wǎng)絡(luò)上發(fā)現(xiàn)的社區(qū)結(jié)構(gòu)

圖2 Karate網(wǎng)絡(luò)上真實(shí)的社區(qū)結(jié)構(gòu)

由圖1和圖2可以看出，BI算法得到的社區(qū)結(jié)構(gòu)與真實(shí)的社區(qū)結(jié)構(gòu)幾乎一致，除了一個(gè)節(jié)點(diǎn)10被錯(cuò)誤劃分。事實(shí)上，節(jié)點(diǎn)10與兩個(gè)社區(qū)聯(lián)系的緊密程度差不多。因此，BI算法可以發(fā)現(xiàn)Karate網(wǎng)絡(luò)中真實(shí)的社區(qū)結(jié)構(gòu)，并能檢測(cè)到網(wǎng)絡(luò)中的重疊社區(qū)。

實(shí)驗(yàn)2使用BI算法檢測(cè)Dolphins網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)

在Dolphins網(wǎng)絡(luò)上運(yùn)行BI算法。算法1在Dolphins網(wǎng)絡(luò)中發(fā)現(xiàn)了六個(gè)小社區(qū)(分別使用不同顏色和形狀代表)，并且得到了最大的模塊度值Q=0.433 7；算法2根據(jù)社區(qū)間的連接強(qiáng)度將六個(gè)社區(qū)合并為兩個(gè)社區(qū)，如圖3所示，兩個(gè)社區(qū)之間以虛線分隔。真實(shí)的社區(qū)結(jié)構(gòu)如圖4所示。

圖3 BI算法在Dolphins網(wǎng)絡(luò)得到的社區(qū)結(jié)構(gòu)

圖4 Dolphins網(wǎng)絡(luò)上真實(shí)的社區(qū)結(jié)構(gòu)

由圖3和圖4可以看出，BI算法的結(jié)果與真實(shí)的社區(qū)結(jié)構(gòu)幾乎一致，僅有一個(gè)節(jié)點(diǎn)31劃分錯(cuò)誤。這說明BI算法能夠有效的發(fā)現(xiàn)Dolphins網(wǎng)中的社區(qū)結(jié)構(gòu)。

實(shí)驗(yàn)3比較BI算法和GN算法對(duì)PolBooks網(wǎng)絡(luò)的劃分結(jié)果

本實(shí)驗(yàn)在PolBooks網(wǎng)絡(luò)上同時(shí)運(yùn)行BI算法和GN算法，實(shí)驗(yàn)結(jié)果如表2所示。

表2 BI算法和GN算法對(duì)于PolBooks網(wǎng)絡(luò)的劃分結(jié)果分析

由表2可以看出，雖然BI算法僅得到兩個(gè)社區(qū)，但基本分開了“共和黨”和“民主黨”兩個(gè)社區(qū)，正確率為82.86%，略低于GN算法的83.81%；雖然GN算法可以識(shí)別出“中立”社區(qū)，但正確率只有15.38%。這個(gè)結(jié)果是可以接受的，有以下原因：由于美國兩黨之間的政治主張明顯對(duì)立，中立政客在所有議題上也不可能都中立，因此僅使用拓?fù)浣Y(jié)構(gòu)很難識(shí)別出“中立”社區(qū)。這說明，BI算法能夠在PolBooks網(wǎng)絡(luò)上以很高的準(zhǔn)確率發(fā)現(xiàn)真實(shí)的社區(qū)結(jié)構(gòu)。

實(shí)驗(yàn)4在四個(gè)已知社區(qū)結(jié)構(gòu)網(wǎng)絡(luò)上，比較BI算法與其他算法的社區(qū)劃分質(zhì)量

本實(shí)驗(yàn)將測(cè)試BI算法與其他四個(gè)常用算法的社區(qū)劃分質(zhì)量。為了客觀的比較不同算法，實(shí)驗(yàn)在四個(gè)已知社區(qū)結(jié)構(gòu)網(wǎng)絡(luò)上進(jìn)行，使用FVIC和NMI指標(biāo)比較社區(qū)劃分的準(zhǔn)確性。同時(shí)，實(shí)驗(yàn)做了以下設(shè)定：(1) 限定了GN、CNM算法得到的社區(qū)數(shù)；(2) 由于BGLL算法不能限定社區(qū)數(shù)，因此不比較BGLL算法的FVIC值；(3) LPA算法得到的結(jié)果很不穩(wěn)定，取五次結(jié)果的平均值。實(shí)驗(yàn)結(jié)果見表3。

從表3可以看出，在四個(gè)網(wǎng)絡(luò)中BI算法都能夠以接近最高的準(zhǔn)確度檢測(cè)出真實(shí)的社區(qū)結(jié)構(gòu)，算法的準(zhǔn)確性接近或超過其他算法，表明了BI算法能夠有效的發(fā)現(xiàn)真實(shí)的社區(qū)結(jié)構(gòu)。

實(shí)驗(yàn)5測(cè)試BI算法分裂網(wǎng)絡(luò)的有效性

本實(shí)驗(yàn)將在Jazz和GR-QC兩個(gè)未知社區(qū)結(jié)構(gòu)的網(wǎng)絡(luò)上運(yùn)行算法1，檢驗(yàn)算法1是否可以有效的分裂網(wǎng)絡(luò)。模塊度可以客觀的評(píng)價(jià)社區(qū)劃分質(zhì)量，因此通過考查網(wǎng)絡(luò)分裂過程中模塊度的變化趨勢(shì)，可以評(píng)價(jià)算法能否有效的分裂網(wǎng)絡(luò)。實(shí)驗(yàn)結(jié)果如圖5、圖6所示。

表3 BI算法與其他常用算法在已知社區(qū)結(jié)構(gòu)網(wǎng)絡(luò)上的比較

圖5 BI算法在分裂Jazz網(wǎng)絡(luò)時(shí)模塊度的變化

圖6 BI算法在分裂GR-QC網(wǎng)絡(luò)時(shí)模塊度的變化

從圖5、圖6可以看出，隨著網(wǎng)絡(luò)的分解，社區(qū)劃分的模塊度逐漸增加，從而得到局部最大值。這與GN算法、CNM算法中模塊度的變化趨勢(shì)一致。這個(gè)實(shí)驗(yàn)說明，BI算法分裂網(wǎng)絡(luò)的方向是正確的，算法可以將網(wǎng)絡(luò)分裂為有意義的社區(qū)。

實(shí)驗(yàn)6比較BI算法和BGLL算法對(duì)Jazz網(wǎng)絡(luò)的劃分結(jié)果

本實(shí)驗(yàn)將在未知社區(qū)結(jié)構(gòu)的Jazz網(wǎng)絡(luò)上同時(shí)運(yùn)行BI算法和BGLL算法。BI算法在Jazz網(wǎng)絡(luò)上得到兩個(gè)社區(qū)，模塊度為0.289，與最早研究Jazz網(wǎng)絡(luò)的文獻(xiàn)的研究結(jié)果一致。BGLL算法在Jazz網(wǎng)絡(luò)上得到四個(gè)社區(qū)，模塊度為0.445；在BGLL算法的結(jié)果上運(yùn)行算法2，能夠得到兩個(gè)社區(qū)。結(jié)果如圖7、圖8所示。

從圖7、圖8可以看出，盡管BGLL算法可以得到更大的模塊度和更多的社區(qū)，但圖8中的三角形、正方形和圓形代表的三個(gè)社區(qū)連接比較緊密，通過算法2可以合并為一個(gè)社區(qū)。執(zhí)行算法2后，BI和BGLL算法的劃分結(jié)果僅有兩個(gè)節(jié)點(diǎn)不同。這說明，BI算法與BGLL算法的結(jié)果具有一定的相似性，但BI算法的結(jié)果能夠更好的反映真實(shí)的社區(qū)結(jié)構(gòu)。

圖7 BI算法在Jazz網(wǎng)絡(luò)上的結(jié)果

圖8 BGLL算法在Jazz網(wǎng)絡(luò)上的結(jié)果

實(shí)驗(yàn)7檢測(cè)BI算法能夠是否能夠克服分辨率限制

本實(shí)驗(yàn)將在未知社區(qū)結(jié)構(gòu)的GR-QC網(wǎng)絡(luò)運(yùn)行BI算法和BGLL算法，并從BGLL算法的社區(qū)劃分中選擇最大的一個(gè)社區(qū)，來檢測(cè)BI算法是否能夠克服BGLL算法的分辨率限制。取BGLL算法在GR-QC網(wǎng)絡(luò)上發(fā)現(xiàn)的最大社區(qū)，以不同的顏色代表BI算法在其中檢測(cè)到的社區(qū)，結(jié)果如圖9所示。

從圖9中可以看到，對(duì)于箭頭所指的3個(gè)節(jié)點(diǎn)組①②③來說，內(nèi)部連接非常緊密，而與外界僅有一條或兩條邊相連，因此可以認(rèn)為這三個(gè)節(jié)點(diǎn)組是社區(qū)。BI算法能夠識(shí)別這些規(guī)模很小的社區(qū)，而BGLL算法不能識(shí)別這些小社區(qū)。這說明，BI算法能夠在大網(wǎng)絡(luò)上識(shí)別出小的社區(qū)，在社區(qū)分辨率上優(yōu)于基于模塊度優(yōu)化的方法。

圖9 BGLL算法在GR-QC網(wǎng)絡(luò)上發(fā)現(xiàn)的最大社區(qū)，但BI算法能夠在其中發(fā)現(xiàn)更小的社區(qū)

5 結(jié)束語

為了降低分裂社區(qū)發(fā)現(xiàn)算法的計(jì)算復(fù)雜度，本文定義了一種基于聚集度的橋系數(shù)，能夠量化網(wǎng)絡(luò)中邊的連接強(qiáng)度。在此基礎(chǔ)上，提出了“分裂—合并”兩步實(shí)現(xiàn)的BI算法，計(jì)算的時(shí)間復(fù)雜度為O(nk3)，優(yōu)于已有的社區(qū)分裂算法。在六個(gè)真實(shí)社會(huì)網(wǎng)絡(luò)上的實(shí)驗(yàn)表明，BI算法可有效的識(shí)別真實(shí)網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)。

隨著網(wǎng)絡(luò)的規(guī)模不斷增大，往往只能得到網(wǎng)絡(luò)的部分結(jié)構(gòu)，而橋系數(shù)是局部指數(shù)，可以在部分網(wǎng)絡(luò)中發(fā)現(xiàn)有意義的社區(qū)結(jié)構(gòu)。同時(shí)，現(xiàn)實(shí)中的網(wǎng)絡(luò)結(jié)構(gòu)是不斷變化的，節(jié)點(diǎn)之間聯(lián)系會(huì)中斷或產(chǎn)生，節(jié)點(diǎn)也會(huì)產(chǎn)生或消失，橋系數(shù)也可用于這類動(dòng)態(tài)網(wǎng)絡(luò)的社區(qū)檢測(cè)。

[1] Strogatz S H. Exploring complex networks[J]. Nature, 2001, (410): 268-276.

[2] Newman M E J, Girvan M. Finding and evaluating community structure in networks[J]. Physical Review E, 2004, 69(2): 026113.

[3] Cheng X Q, Shen H W. Uncovering the community structure associated with the diffusion dynamics on networks[J]. Journal of Statistical Mechanics Theory & Experiment, 2010, 33(2):147-167.

[4] 程學(xué)旗, 沈華偉. 復(fù)雜網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)[J]. 復(fù)雜系統(tǒng)與復(fù)雜性科學(xué), 2011, 08(1):57-70.

[5] Fortunato S. Community detection in graphs[J]. Physics Reports, 2010, 486(3-5):75-174.

[6] 閔亮，邵良棚，趙永剛. 基于節(jié)點(diǎn)相似度的社團(tuán)檢測(cè)[J]. 計(jì)算機(jī)工程與應(yīng)用，2015，51(9),77-81.

[7] Clauset A, Newman M E J, Moore C. Finding community structure in very large networks[J]. Physical Review E, 2004, 70(6)： 264-277.

[8] Nascimento M C V. Community detection in networks via a spectral heuristic based on the clustering coefficient[J]. Discrete Applied Mathematics, 2014, 176(3):89-99.

[9] Palla G, Derényi I, Farkas I, et al. Uncovering the overlapping community structure of complex networks in nature and society[J]. Nature, 2005, (435): 814-818.

[10] Karrer B, Newman M E J. Stochastic block models and community structure in networks[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2011, 83(1 Pt 2):211-222.

[11] Nandini R Usha, Réka A, Soundar K. Near linear time algorithm to detect community structures in large-scale networks[J]. Physical Review E, 2007, 76(3):036106.

[12] Sun P G, Yang Y. Methods to find community based on edge centrality[J]. Physical A Statistical Mechanics & Its Applications, 2013, 392(9):1977-1988.

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

[14] Sun P G, Yang Y. Methods to find community based on edge centrality[J]. Physical A Statistical Mechanics & Its Applications, 2013, 392(9):1977-1988.

[15] Tyler J R, Wilkinson D M, Huberman B A. Email as spectroscopy: Automated discovery of community structure within organizations[J]. The Information Society, 2003, 21(2): 143-153.

[16] Green O, Bader D A. Faster betweenness centrality based on data structure experimentation[J]. Procedia Computer Science, 2013, 18(1):399-408.

[17] Li L, Li S H, Li H J, et al. A community divisive algorithm based on local weak edges[J]. Journal of Information & Computational Science, 2014, 11(11):3727-3737.

[18] Radicchi F, Castellano C, Cecconi F, et al. Defining and identifying communities in networks[J]. Proceedings of the National Academy of Sciences, 2004, (101): 2658-2663.

[19] Cheng X Q, Ren F X, Shen H W, et al. Bridgeness: a local index on edge significance in maintaining global connectivity[J]. Journal of Statistical Mechanics: Theory and Experiment, 2010, 2010(10): P10011.

[20] 王玙, 高琳. 動(dòng)態(tài)網(wǎng)絡(luò)橋系數(shù)增量聚類算法[J]. 西安電子科技大學(xué)學(xué)報(bào)(自然科學(xué)版), 2013, 40(1): 30-35.

[21] 胡新, 王麗珍, 何瓦特,等. 度數(shù)法求解最大團(tuán)問題[J]. Journal of Frontiers of Computer Science & Technology, 2013, 7(3):262-271.

[22] Ding Z, Zhang X, Sun D, et al. Overlapping community detection based on network decomposition[J]. Scientific Reports, 2016, (6)：24115.

[23] Blondel V D, Guillaume J L, Lambiotte R, et al. Fast unfolding of communities in large networks[J]. Journal of Statistical Mechanics Theory and Experiment. 2008, 30(2): 155-168.

[24] Fortunato S, Barthélemy M. Resolution limit in community detection[J]. Proceedings of the National Academy of Sciences, 2007, 104(1): 36-41.

[25] Lancichinetti A, Fortunato S. Limits of modularity maximization in community detection[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2011, 84(84):2184-2188.

[26] 沈華偉, 程學(xué)旗, 陳海強(qiáng), 等. 基于信息瓶頸的社區(qū)發(fā)現(xiàn)[J]. 計(jì)算機(jī)學(xué)報(bào), 2008, 31(4): 677-686.

[27] Chertkov M，Chernyak V Y， Teodorescu R. Evaluating local community methods in networks[J]. Journal of Statistical Mechanics: Theory and Experiment, 2008, 49(5): P05001.

[28] Cheng X, Ren F, Zhou S, et al. Triangular clustering in document networks[J]. New Journal of Physics, 2009, 11(3):033019.

[29] Watts D J, Strogatz S H. Collective dynamics of “small-world” networks[J]. Nature, 1998, 393:440-442.

[30] Amaral L A N, Scala A, Barthélémy M, et al. Classes of small-world networks[J]. Proceedings of the National Academy of Sciences, 2000, (97): 11149-11152.

[31] Kulli V R, Warad N S. On the total closed neighbourhood graph of a graph[J]. Journal of Discrete Mathematical Sciences & Cryptography, 2001, 4(2):109-114.

[32] Newman M E J. Networks: an introduction[M]. OUP Oxford, 2010.

[33] Zachary W W. An information flow model for conflict and fission in small groups[J]. Journal of Anthropological Research. 1977, (33): 452-473.

[34] Lusseau D, Schneider K, Boisseau O J, et al. The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations: Can geographic isolation explain this unique trait[J]. Behavioral Ecology and Sociobiology. 2003, 54(4): 396-405.

[35] Gleiser P M, Danon L. Community structure in jazz[J]. Advances in Complex Systems, 2003, 6(4):565-573.

[36] Leskovec J, Lang K J, Dasgupta A, et al. Community structure in large networks: natural cluster sizes and the absence of large well-defined clusters[J]. Internet Mathematics, 2009, 6(1):29-123.

[37] L Danon, A Díaz-Guilera , J Duch , et al. Comparing community structure identification[J]. Journal of Statistical Mechanics: Theory and Experiment, 2005, 2005(09):09008.

ACommunityDetectionAlgorithmBasedonBridgeness

JI Qingbin, KANG Qian, LI Deyu, WANG Suge

(School of Computer & Information Technology, Shanxi University, Taiyuan, Shanxi 030051, China)

Study of community structure is of help to reveal the relationship between network structure and function, and community detection is essential to the community structure research. A bridgeness index based on clustering degree is defined in this paper, and applied to the community detection. The proposed algorithm includes two parts splitting and merging. The splitting algorithm identifies inter-community by bridgeness, and decomposes network by iterative removing inter-community edges until the community structure is discovered; The merging algorithm merges communities according to the community connection strength, so that the hierarchical nesting in community is revealed. Experiments on six social networks show that the proposed algorithm can effectively detect interesting communities for the whole network, and the accuracy is close to or even better than the classical algorithms.

community detection; divisive algorithm; bridgeness index

冀慶斌(1980—)，博士研究生，主要研究領(lǐng)域?yàn)樯鐣?huì)計(jì)算。

康茜(1989—)，碩士研究生，主要研究領(lǐng)域?yàn)樯鐣?huì)計(jì)算。

李德玉(1965—)，博士，教授，博士生導(dǎo)師，主要研究領(lǐng)域?yàn)橹悄苡?jì)算與數(shù)據(jù)挖掘。

1003-0077(2017)03-0205-08

2015-09-20定稿日期： 2015-12-20

國家自然科學(xué)基金(61175067, 61272095, 61432011,61573231);山西省科技基礎(chǔ)條件平臺(tái)計(jì)劃項(xiàng)目(2015091001-0102);山西省回國留學(xué)人員科研項(xiàng)目(2013-014)

TP391

：A