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

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

(山西大學 計算機與信息技術學院, 山西 太原 030051)

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

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

(山西大學 計算機與信息技術學院, 山西 太原 030051)

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

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

1 引言

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

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

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

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

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

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

2.1 最大團橋系數(shù)

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

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

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

2.2 聚集度橋系數(shù)

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

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

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

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

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

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

2.3 社區(qū)強度

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

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

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

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

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

定義3兩個社區(qū)的連接強度定義為

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

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

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

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

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

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

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

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

Begin

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

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

(3) while(True)

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

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

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

(7) 重新計算CC和Q；

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

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

(10) end；

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

End

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

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

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

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

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

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

Begin

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

(2) while(True)

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

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

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

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

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

(8) end；

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

End

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

3.3 BI算法時間復雜度分析

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

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

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

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

4 實驗結果及分析

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

4.1 實驗數(shù)據(jù)集

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

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

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

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

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

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

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

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

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

4.2 評價指標

本文使用以下三個指標評價社區(qū)劃分的質(zhì)量：

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

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

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

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

4.3 實驗結果及分析

實驗1使用BI算法檢測Karate網(wǎng)絡中的社區(qū)結構

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

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

圖2 Karate網(wǎng)絡上真實的社區(qū)結構

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

實驗2使用BI算法檢測Dolphins網(wǎng)絡中的社區(qū)結構

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

圖3 BI算法在Dolphins網(wǎng)絡得到的社區(qū)結構

圖4 Dolphins網(wǎng)絡上真實的社區(qū)結構

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

實驗3比較BI算法和GN算法對PolBooks網(wǎng)絡的劃分結果

本實驗在PolBooks網(wǎng)絡上同時運行BI算法和GN算法，實驗結果如表2所示。

表2 BI算法和GN算法對于PolBooks網(wǎng)絡的劃分結果分析

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

實驗4在四個已知社區(qū)結構網(wǎng)絡上，比較BI算法與其他算法的社區(qū)劃分質(zhì)量

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

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

實驗5測試BI算法分裂網(wǎng)絡的有效性

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

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

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

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

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

實驗6比較BI算法和BGLL算法對Jazz網(wǎng)絡的劃分結果

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

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

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

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

實驗7檢測BI算法能夠是否能夠克服分辨率限制

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

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

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

5 結束語

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

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

[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] 程學旗, 沈華偉. 復雜網(wǎng)絡的社區(qū)結構[J]. 復雜系統(tǒng)與復雜性科學, 2011, 08(1):57-70.

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

[6] 閔亮，邵良棚，趙永剛. 基于節(jié)點相似度的社團檢測[J]. 計算機工程與應用，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] 王玙, 高琳. 動態(tài)網(wǎng)絡橋系數(shù)增量聚類算法[J]. 西安電子科技大學學報(自然科學版), 2013, 40(1): 30-35.

[21] 胡新, 王麗珍, 何瓦特,等. 度數(shù)法求解最大團問題[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] 沈華偉, 程學旗, 陳海強, 等. 基于信息瓶頸的社區(qū)發(fā)現(xiàn)[J]. 計算機學報, 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—)，博士研究生，主要研究領域為社會計算。

康茜(1989—)，碩士研究生，主要研究領域為社會計算。

李德玉(1965—)，博士，教授，博士生導師，主要研究領域為智能計算與數(shù)據(jù)挖掘。

1003-0077(2017)03-0205-08

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

國家自然科學基金(61175067, 61272095, 61432011,61573231);山西省科技基礎條件平臺計劃項目(2015091001-0102);山西省回國留學人員科研項目(2013-014)

TP391

：A