一種發(fā)現(xiàn)交疊社團(tuán)的快速層次化算法

彭佳揚(yáng)，楊路明，王建新，李敏，蔡娟

(中南大學(xué) 信息科學(xué)與工程學(xué)院，湖南 長沙，410083)

在現(xiàn)實(shí)世界中，很多自然、社會(huì)和科學(xué)系統(tǒng)都以網(wǎng)絡(luò)的形式存在，這些網(wǎng)絡(luò)很復(fù)雜，被稱為“復(fù)雜網(wǎng)絡(luò)”[1]。隨著人們對(duì)復(fù)雜網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)、物理意義和數(shù)學(xué)特性的深入研究，發(fā)現(xiàn)許多實(shí)際網(wǎng)絡(luò)不但具有小世界性、無標(biāo)度性等基本統(tǒng)計(jì)特性，還具有拓?fù)浣Y(jié)構(gòu)屬性——社團(tuán)結(jié)構(gòu)，具有同社團(tuán)節(jié)點(diǎn)相互連接緊密、異社團(tuán)節(jié)點(diǎn)相互連接稀疏的特點(diǎn)[2-6]。為了更好地分析復(fù)雜網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)、理解復(fù)雜網(wǎng)絡(luò)的功能以及預(yù)測(cè)復(fù)雜網(wǎng)絡(luò)的行為，必須對(duì)網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行社團(tuán)劃分。層次聚類算法作為社團(tuán)發(fā)現(xiàn)最主要的一類方法，能夠展現(xiàn)復(fù)雜網(wǎng)絡(luò)中社團(tuán)的層次化結(jié)構(gòu)組成[7-9]。Newman[10]提出了基于局部搜索的快速復(fù)雜網(wǎng)絡(luò)聚類算法FN，其目的是使網(wǎng)絡(luò)模塊性(modularity)評(píng)價(jià)函數(shù)即Q函數(shù)極大化[11]。Q越高，意味著劃分的社團(tuán)越有意義，很多社團(tuán)劃分方法[12-15]的目的就是將Q極大化。Guimera等[3]提出了基于模擬退火算法的復(fù)雜網(wǎng)絡(luò)聚類算法GA，此算法具有跳過局部最優(yōu)解、找到全局最優(yōu)解的能力，從而具有很高的聚類精度。然而，Q函數(shù)是有偏的，并不能完全準(zhǔn)確地刻畫最優(yōu)的(或者說是真實(shí)的)網(wǎng)絡(luò)簇結(jié)構(gòu)[1]。對(duì)于某些網(wǎng)絡(luò)，其真實(shí)的網(wǎng)絡(luò)簇結(jié)構(gòu)對(duì)應(yīng)的 Q是局部極大值，而非全局最大值。Guimera等[16]經(jīng)進(jìn)一步研究發(fā)現(xiàn)：對(duì)于某些隨機(jī)網(wǎng)絡(luò)，由于受到擾動(dòng)的影響，明顯不好的網(wǎng)絡(luò)簇結(jié)構(gòu)卻對(duì)應(yīng)較高的Q。為此，F(xiàn)ortunato[17]研究了Q函數(shù)對(duì)聚類精度的影響，指出：對(duì)于大規(guī)模復(fù)雜網(wǎng)絡(luò)，采用這類優(yōu)化方法傾向于找到粗糙的而不是精確的網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)。這意味著采用這類算法未必能找到大規(guī)模網(wǎng)絡(luò)中真正存在的全部社團(tuán)，僅僅適合于小規(guī)模網(wǎng)絡(luò)的社團(tuán)劃分。這種啟發(fā)式復(fù)雜網(wǎng)絡(luò)社團(tuán)發(fā)現(xiàn)算法包括 MFC算法[18]、GN算法[2]及其改進(jìn)算法[6,19]、WH算法[20]等。這些層次化社團(tuán)發(fā)現(xiàn)算法將網(wǎng)絡(luò)劃分為不同的社團(tuán)，每個(gè)點(diǎn)只屬于1個(gè)社團(tuán)。然而，在許多實(shí)際網(wǎng)絡(luò)中，有些點(diǎn)可能屬于多個(gè)社團(tuán)，所以，若能發(fā)現(xiàn)可交疊的社團(tuán)結(jié)構(gòu)，則更具有實(shí)際意義[1]。為了找到社團(tuán)間重復(fù)的點(diǎn)，Palla等[4]提出基于k-團(tuán)的算法CPM，能夠識(shí)別重疊網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)。其后提出k-dense[21]算法，也可以識(shí)別重疊的網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)，并且應(yīng)用于各種實(shí)際網(wǎng)絡(luò)中。但是，這些方法又不能顯示出社團(tuán)的層次化特性。Lancichinetti等[22]提出了 1種可以允許重疊的層次化社團(tuán)發(fā)現(xiàn)算法。他們?cè)噲D找到合適函數(shù)的局部最優(yōu)解來發(fā)現(xiàn)重疊的社團(tuán)結(jié)構(gòu)，圍繞1個(gè)種子節(jié)點(diǎn)來發(fā)現(xiàn)重疊社團(tuán)的層次化結(jié)構(gòu)。但是，由于種子節(jié)點(diǎn)是隨機(jī)選取的，不能保證所有重疊社團(tuán)都有層次結(jié)構(gòu)，為此，Shen等[23]提出了一種EAGLE算法[23]，用極大團(tuán)作為初始社團(tuán)，根據(jù)社團(tuán)的相似性，應(yīng)用凝聚法來合并社團(tuán)，以此找到重疊的層次化社團(tuán)結(jié)構(gòu)。但是，由于要重復(fù)計(jì)算社團(tuán)的相似度，算法復(fù)雜度極高，很難應(yīng)用于大規(guī)模的實(shí)際網(wǎng)絡(luò)[11]。為了提高算法的運(yùn)行效率，本文作者設(shè)計(jì)了一種發(fā)現(xiàn)層次化交疊社團(tuán)的快速算法F-HOC：用極大團(tuán)k-團(tuán)作為初始社團(tuán)，提出1個(gè)指標(biāo)——社團(tuán)連通性，以該指標(biāo)為依據(jù)，用凝聚法對(duì)k-團(tuán)進(jìn)行弱社團(tuán)檢測(cè)，將符合條件的社團(tuán)進(jìn)行遞歸合并，以達(dá)到網(wǎng)絡(luò)可交疊層次化快速聚類的目的。

1 發(fā)現(xiàn)層次化交疊社團(tuán)的快速算法F-HOC

大多數(shù)層次化聚類算法在其凝聚過程中是對(duì)孤立的點(diǎn)進(jìn)行擴(kuò)展，本文提出的F-HOC算法則是從極大團(tuán)開始進(jìn)行擴(kuò)展。由于初始的極大團(tuán)中包含重復(fù)的點(diǎn)，所以，基于這些極大團(tuán)擴(kuò)展發(fā)現(xiàn)的社團(tuán)很可能彼此交疊。在計(jì)算極大團(tuán)時(shí)，有些極大團(tuán)中的點(diǎn)分別屬于其它不同的極大團(tuán)，這種極大團(tuán)稱為附屬極大團(tuán)(Subordinate maximal clique)[23]。附屬極大團(tuán)容易誤導(dǎo)算法，本文不予考慮。實(shí)驗(yàn)證明大多數(shù)附屬極大團(tuán)的規(guī)模比較小，因此，F(xiàn)-HOC先找出所有大于等于k的極大團(tuán)即k-團(tuán)，這樣可以有效地剔除附屬極大團(tuán)。但是，這樣可能會(huì)剔除一些比較小的非附屬極大團(tuán)，k越大，越可能刪除更多的非附屬極大團(tuán)，而k越小，則越可能保留附屬極大團(tuán)。在實(shí)際網(wǎng)絡(luò)中，k一般取3～6[4,23]。在剔除小于k的附屬極大團(tuán)后，有可能存在一些點(diǎn)不屬于任何極大團(tuán)，這些點(diǎn)成為附屬點(diǎn)(Subordinate vertices)，將這些點(diǎn)作為單獨(dú)的初始社團(tuán)參與合并過程。

EAGLE算法以社團(tuán)的相似性作為合并兩社團(tuán)的條件，但重復(fù)計(jì)算社團(tuán)的相似性相當(dāng)耗時(shí)；在大多數(shù)層次化聚類算法中，使用邊數(shù)之類的全局變量來劃分社團(tuán)，而重復(fù)計(jì)算全局變量的算法時(shí)間復(fù)雜度非常高，很難應(yīng)用于大型復(fù)雜網(wǎng)絡(luò)?？紤]到連接兩社團(tuán)間的邊數(shù)越多，兩社團(tuán)聯(lián)系越緊密，越有可能屬于1個(gè)社團(tuán)，本文在F-HOC算法中采用1個(gè)新的指標(biāo)——社團(tuán)連通性，來評(píng)價(jià)2個(gè)社團(tuán)連接是否緊密。

定義1 社團(tuán)連通性CAB是評(píng)價(jià)2個(gè)社團(tuán)連接是否緊密的1個(gè)指標(biāo)：

式(1)中：分子 | EAB|+|EO′ |+2|EO|為連接兩社團(tuán)的邊數(shù)；分母 | EAB|+|EA|+|EB|為兩社團(tuán)的總邊數(shù)。CAB越大，則表示連接兩社團(tuán)的邊占兩社團(tuán)總邊數(shù)的比例越大，表明兩社團(tuán)連接越緊密，兩者越有可能屬于同一個(gè)社團(tuán)。

F-HOC以社團(tuán)連通性指標(biāo)為依據(jù)，用凝聚法對(duì)k-團(tuán)進(jìn)行合并判斷，最終目的是所發(fā)現(xiàn)的社團(tuán)都滿足弱社團(tuán)的定義。

定義 2 弱社團(tuán)(Weak community)[6]是指子圖 H中所有節(jié)點(diǎn)與H內(nèi)部節(jié)點(diǎn)的度之和大于H中所有節(jié)點(diǎn)與H外部節(jié)點(diǎn)連接的度之和。給定1個(gè)無向簡(jiǎn)單圖G和1個(gè)子圖H( H ? G )，H滿足弱社團(tuán)的定義，當(dāng)且僅當(dāng)：

其中：v為H中的節(jié)點(diǎn)；din(H,v)為v的內(nèi)度；dout(H,v)為v的外度。

基于社團(tuán)連通性和弱社團(tuán)的量化定義，提出一種基于連通性的發(fā)現(xiàn)交疊社團(tuán)的快速層次化算法F-HOC。

Input: 無向無權(quán)簡(jiǎn)單圖G=(V,E)，初始極大團(tuán)規(guī)模k；

Output: 可交疊的層次化社團(tuán)。

步驟1 找出所有規(guī)?！輐的極大團(tuán)，附屬點(diǎn)視為獨(dú)立初始社團(tuán)。

步驟 2 對(duì)兩兩相連的社團(tuán)采用 CAB進(jìn)行判斷；對(duì)CAB進(jìn)行降序排列，放入隊(duì)列CC中。

步驟3 依次判斷Cc中每2個(gè)社團(tuán)是否合并。

(1) 若2個(gè)社團(tuán)都不滿足弱社團(tuán)的定義，則合并2個(gè)社團(tuán)；

(2) 合并2個(gè)社團(tuán)后，將這個(gè)CAB從隊(duì)列CC中移除，且將與新合并社團(tuán)有連接的社團(tuán)的CAB進(jìn)行重新計(jì)算，將隊(duì)列CC重新排序；

步驟4 對(duì)不滿足合并條件的社團(tuán)不進(jìn)行處理。

步驟5 按CC的排序執(zhí)行步驟3和4，直到隊(duì)列CC為空為止。

步驟6 輸出層次化合并的可交疊社團(tuán)。

F-HOC的輸入是1個(gè)無向無權(quán)簡(jiǎn)單圖G=(V,E)。首先用經(jīng)典的Bron-Kerbosch算法[24]找到所有極大團(tuán)，過濾圖中的規(guī)模小于k的極大團(tuán)，剩下規(guī)模大于等于k的每個(gè)極大團(tuán)視為1個(gè)初始社團(tuán)，附屬點(diǎn)也視為獨(dú)立的初始社團(tuán)。然后計(jì)算兩兩相連社團(tuán)的社團(tuán)連通性，其值越大，表明2個(gè)社團(tuán)越有可能屬于同一個(gè)社團(tuán)。根據(jù)計(jì)算所得的社團(tuán)連通性值進(jìn)行降序排列，放入隊(duì)列CC中，從大到小分別判斷兩社團(tuán)是否滿足弱社團(tuán)定義。只有在2個(gè)社團(tuán)都不滿足時(shí)才合并，直到隊(duì)列CC為空為止，整個(gè)層次化聚類過程結(jié)束，輸出得到的所有的社團(tuán)，包括合并過程和最終的社團(tuán)?？筛鶕?jù)合并過程畫出層次化社團(tuán)樹狀圖，以展示復(fù)雜網(wǎng)絡(luò)中社團(tuán)的層次化組織結(jié)構(gòu)。

因?yàn)镕-HOC算法是利用社團(tuán)連通性進(jìn)行判斷，只需計(jì)算局部變量，其時(shí)間復(fù)雜度比EAGLE用全局變量計(jì)算的低。EAGLE 的時(shí)間復(fù)雜度[23]為O(n2+(h+n)s+n2s) (不計(jì)計(jì)算極大團(tuán)的時(shí)間，其中，n為點(diǎn)的個(gè)數(shù)，s為初始社團(tuán)k-團(tuán)的個(gè)數(shù)，h為鄰居社團(tuán)對(duì)(兩兩相連社團(tuán)對(duì)或者是相似社團(tuán)對(duì))的個(gè)數(shù))。F-HOC中，計(jì)算所有鄰居社團(tuán)對(duì)社團(tuán)連通性的時(shí)間復(fù)雜度為 O(h)，重復(fù)合并的時(shí)間復(fù)雜度為 O(h2(s-1))，整個(gè)算法的時(shí)間復(fù)雜度為 O(h2s)(同樣不計(jì)計(jì)算極大團(tuán)的時(shí)間)。比較EAGLE的時(shí)間復(fù)雜度，h遠(yuǎn)小于n，所以，F(xiàn)-HOC更適用于大型的復(fù)雜網(wǎng)絡(luò)。

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

采用已知社團(tuán)結(jié)構(gòu)的隨機(jī)網(wǎng)絡(luò)進(jìn)行測(cè)試[1]，比較F-HOC和EAGLE的精度和速度。已知社團(tuán)結(jié)構(gòu)的隨機(jī)網(wǎng)絡(luò)定義為RN(C, b, d, pin)(其中：C為網(wǎng)絡(luò)社團(tuán)的個(gè)數(shù)；b為每個(gè)社團(tuán)包含節(jié)點(diǎn)的個(gè)數(shù)；d為網(wǎng)絡(luò)中節(jié)點(diǎn)的平均度；pin為社團(tuán)內(nèi)連接密度(即社團(tuán)內(nèi)連接總數(shù)與網(wǎng)絡(luò)連接總數(shù)的比值))。pin越大，隨機(jī)網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)越明顯，反之，社團(tuán)結(jié)構(gòu)越模糊。特別地，當(dāng)pin＜0.5時(shí)，認(rèn)為該隨機(jī)網(wǎng)絡(luò)不具有社團(tuán)結(jié)構(gòu)。實(shí)驗(yàn)采用被普遍接受的基準(zhǔn)隨機(jī)網(wǎng)絡(luò)RN(4, 32, 16, pin)作為標(biāo)準(zhǔn)數(shù)據(jù)，k取4，并設(shè)定了2個(gè)點(diǎn)為重疊點(diǎn)。

2.1 算法的敏感度

敏感度Sn是用來評(píng)估社團(tuán)識(shí)別精度的重要指標(biāo)[25]，是指已知社團(tuán)中被算法發(fā)現(xiàn)出來的部分所占比例：

其中：PT(True positive)表示算法識(shí)別出來的社團(tuán) Cp與已知社團(tuán)Ck匹配程度OS(Cp, Ck)超過匹配度閾值的數(shù)量；NF(False negative)表示已知社團(tuán)中沒有被識(shí)別出來的數(shù)量。

算法識(shí)別出來的社團(tuán)(Predicted community, Cp)與已知社團(tuán)(Known community, Ck)的匹配程度OS(Cp, Ck)的計(jì)算公式[25-26]為：

若 Cp和 Ck的匹配程度 OS(Cp, Ck)超過給定的閾值，則稱這2個(gè)社團(tuán)匹配。對(duì)于已知社團(tuán)Ck，若識(shí)別出的社團(tuán)Cp與之匹配程度OS(Cp, Ck)超過給定閾值，則稱該已知社團(tuán)被標(biāo)識(shí)；若OS(Cp, Ck)=1，則稱該社團(tuán)被完全標(biāo)識(shí)。

圖1所示表示pin取0.9，0.8和0.7時(shí)，F(xiàn)-HOC和EAGLE在不同匹配閾值OS下的匹配精度Sn，匹配精度用敏感度來表示，曲線上的每個(gè)數(shù)據(jù)點(diǎn)是兩算法識(shí)別 50個(gè)已知社團(tuán)結(jié)構(gòu)的隨機(jī)網(wǎng)絡(luò)得到的平均 Sn。從圖 1可以看出：在網(wǎng)絡(luò)社團(tuán)性很強(qiáng)的情況下，即 pin為0.9和0.8時(shí)，F(xiàn)-HOC算法的敏感度與EAGLE算法的敏感度相差不多，都比較高。這也說明 F-HOC算法與EAGLE算法在網(wǎng)絡(luò)社團(tuán)性較明顯的情況下，兩算法都能準(zhǔn)確地識(shí)別出已知社團(tuán)。當(dāng)pin為0.7時(shí)，F(xiàn)-HOC算法的敏感度隨著匹配閾值的增加開始下降，這與大多數(shù)復(fù)雜網(wǎng)絡(luò)聚類算法的結(jié)果類似[1]，在網(wǎng)絡(luò)社團(tuán)性不是很強(qiáng)的情況下，識(shí)別能力開始顯著降低。

圖1 不同匹配閾值下F-HOC與EAGLE的敏感度Sn的比較Fig.1 Comparison of Sn of F-HOC and EAGLE with respect to different overlapping score thresholds

2.2 算法的速度

算法的速度是評(píng)價(jià)聚類算法的重要指標(biāo)。本文比較分析了F-HOC和EAGLE 2種算法在相同規(guī)模、不同社團(tuán)性網(wǎng)絡(luò)下的運(yùn)行時(shí)間以及不同規(guī)模網(wǎng)絡(luò)下的運(yùn)行時(shí)間，如表1和圖2所示。表1所示表示pin取0.9～0.5時(shí)，F(xiàn)-HOC和EAGLE識(shí)別50個(gè)隨機(jī)網(wǎng)絡(luò)得到的平均時(shí)間；圖2所示為不同規(guī)模下算法的運(yùn)行時(shí)間。選用的測(cè)試網(wǎng)絡(luò)是隨機(jī)網(wǎng)絡(luò)RN(4, b,16,0.8)。該網(wǎng)絡(luò)由社團(tuán)結(jié)構(gòu)確定，但其規(guī)?？捎蒪來調(diào)節(jié)，共包含4b個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)，64b條網(wǎng)絡(luò)連接。當(dāng)b =1 024時(shí)，EAGLE的運(yùn)行時(shí)間超過了48 h還沒有得出結(jié)果，所以沒有被列出。

表1 不同網(wǎng)絡(luò)社團(tuán)性下F-HOC與EAGLE算法的運(yùn)行時(shí)間比較Table 1 Comparison of time of F-HOC and EAGLE with respect to different network connections s

從表 1可以看出：不管網(wǎng)絡(luò)社團(tuán)性是否明顯，F(xiàn)-HOC的運(yùn)行效率都比 EAGLE的高很多。因?yàn)镕-HOC算法是利用社團(tuán)連通性進(jìn)行判斷，只需計(jì)算局部變量，計(jì)算復(fù)雜度較低，所以，不論網(wǎng)絡(luò)社團(tuán)性如何，F(xiàn)-HOC的速度都比EAGLE的速度快。如圖2所示，不管網(wǎng)絡(luò)規(guī)模如何，F(xiàn)-HOC比EAGLE的速度快很多，且隨著網(wǎng)絡(luò)規(guī)模的增加，EAGLE的運(yùn)行時(shí)間提升幅度比F-HOC的時(shí)間提升幅度快很多，而F-HOC時(shí)間變化幅度不大。網(wǎng)絡(luò)的規(guī)模越大，F(xiàn)-HOC的優(yōu)勢(shì)越明顯。而在實(shí)際網(wǎng)絡(luò)中，網(wǎng)絡(luò)節(jié)點(diǎn)一般都在 1 000以上，且隨著大規(guī)模網(wǎng)絡(luò)數(shù)據(jù)的不斷增加，F(xiàn)-HOC更適用于大規(guī)模的復(fù)雜網(wǎng)絡(luò)。

圖2 不同網(wǎng)絡(luò)規(guī)模下F-HOC與EAGEL的運(yùn)行時(shí)間比較Fig.2 Comparison of time of F-HOC and EAGLE with respect to different sizes of networks

2.3 交疊點(diǎn)的識(shí)別度

因?yàn)樗惴梢杂糜谧R(shí)別交疊的模塊，在生成已知社團(tuán)結(jié)構(gòu)的隨機(jī)網(wǎng)絡(luò)時(shí)，加入了1個(gè)重疊參數(shù)，即在生成隨機(jī)網(wǎng)絡(luò)時(shí)保證社團(tuán)之間有重疊點(diǎn)。為了驗(yàn)證算法識(shí)別社團(tuán)的交疊性能力，檢查了設(shè)定的重疊點(diǎn)是否出現(xiàn)在多個(gè)輸出社團(tuán)內(nèi)，若都找到，則令Ol=1；若有1個(gè)沒有找到，則令Ol=0，得出對(duì)已知交疊點(diǎn)的識(shí)別度Ov：

其中：n表示隨機(jī)網(wǎng)絡(luò)的個(gè)數(shù)。表2所示為pin取0.9～0.5時(shí)，F(xiàn)-HOC和EAGLE對(duì)已知交疊點(diǎn)的識(shí)別度。從表2可以看出：在網(wǎng)絡(luò)社團(tuán)性很強(qiáng)的情況下即pin為0.9和0.8時(shí)，F(xiàn)-HOC和EAGLE都能準(zhǔn)確地識(shí)別出已知的重疊點(diǎn)，也就是說算法確實(shí)找到了這些重疊的點(diǎn)，并且這些點(diǎn)都存在于多個(gè)社團(tuán)內(nèi)。但隨著網(wǎng)絡(luò)社團(tuán)性的減弱，識(shí)別重疊點(diǎn)的能力也明顯降低，這與識(shí)別社團(tuán)的能力呈正比。

表2 不同網(wǎng)絡(luò)社團(tuán)性下F-HOC與EAGLE算法對(duì)已知交疊點(diǎn)的識(shí)別度OvTable 2 Comparison of Ov of F-HOC and EAGLE with respect to different network connections

表3 F-HOC與EAGLE算法應(yīng)用于足球網(wǎng)絡(luò)的匹配度對(duì)照結(jié)果Table 3 Comparison of overlapping scores which applying F-HOC and EAGLE in football network

3 應(yīng)用

將F-HOC算法應(yīng)用于社團(tuán)性較強(qiáng)的足球網(wǎng)絡(luò)[2]，并與EAGLE的結(jié)果進(jìn)行比較，結(jié)果如表3所示。表3中列出了所有OS(Cp, Ck)≥0.2的社團(tuán)對(duì)和其社團(tuán)匹配值，足球網(wǎng)絡(luò)有12個(gè)社團(tuán)。從表3可以看出：F-HOC找到了 10個(gè)社團(tuán)，其中與已知社團(tuán)完全匹配的有 6個(gè)，占已知社團(tuán)的50%；匹配值高于0.500 000的有7個(gè)，占已知社團(tuán)的58%。EAGLE找到了8個(gè)社團(tuán)，其中與已知社團(tuán)完全匹配的只有2個(gè)，僅占已知社團(tuán)的17%；匹配值高于0.500 000的有6個(gè)，占已知社團(tuán)的 50%。這也說明在社團(tuán)性明顯的實(shí)際網(wǎng)絡(luò)中，F(xiàn)-HOC的精度比EAGLE的精度高。

F-HOC算法的運(yùn)行時(shí)間為3.547 s，EAGLE算法的運(yùn)行時(shí)間為9 490 s，可見，F(xiàn)-HOC的運(yùn)行速度明顯增大。

4 結(jié)論

(1) 設(shè)計(jì)了一種發(fā)現(xiàn)交疊社團(tuán)的快速層次化算法F-HOC。以提出的度量社團(tuán)間連通性的指標(biāo)為依據(jù)，采用凝聚法對(duì)k-團(tuán)進(jìn)行弱社團(tuán)檢測(cè)，對(duì)符合條件的社團(tuán)進(jìn)行合并，遞歸合并以達(dá)到網(wǎng)絡(luò)可交疊層次化快速聚類的目的。

(2) F-HOC以極大團(tuán)為初始社團(tuán)，在此基礎(chǔ)上進(jìn)行合并，所以，社團(tuán)都存在交疊性。

(3) F-HOC利用社團(tuán)連通性這一指標(biāo)進(jìn)行判斷，計(jì)算復(fù)雜度比EAGLE采用的社團(tuán)相似度這一全局變量低，所以，不論網(wǎng)絡(luò)社團(tuán)性如何，速度都比EAGLE的運(yùn)行速度快，有明顯的優(yōu)勢(shì)；且隨著網(wǎng)絡(luò)規(guī)模的增大，F(xiàn)-HOC運(yùn)行時(shí)間的增幅比EAGLE運(yùn)行時(shí)間的增幅小很多。

(4) 在網(wǎng)絡(luò)社團(tuán)性強(qiáng)的情況下，F(xiàn)-HOC能準(zhǔn)確識(shí)別出已知的社團(tuán)結(jié)構(gòu)和重疊點(diǎn)，精度與EAGLE的精度相當(dāng)；但是，在社團(tuán)性較弱的情況下，雖然速度比EAGLE的快，但是，識(shí)別能力比EAGLE的弱。由于EAGLE是利用Q函數(shù)來劃分社團(tuán)性的，對(duì)于明顯不好的網(wǎng)絡(luò)簇結(jié)構(gòu)，EAGLE也有可能得出較高的Q，所以，F(xiàn)-HOC在社團(tuán)性不是很強(qiáng)的情況下，識(shí)別能力比EAGLE的弱并不能說明F-HOC的識(shí)別能力差。

(5) 總體來說，對(duì)于大規(guī)模的社團(tuán)結(jié)構(gòu)明顯的復(fù)雜網(wǎng)絡(luò)，用F-HOC算法發(fā)現(xiàn)可交疊的層次化社團(tuán)結(jié)構(gòu)具有很高的精度和運(yùn)行效率。

[1] 楊博, 劉大有, LIU Ji-ming, 等. 復(fù)雜網(wǎng)絡(luò)聚類方法[J]. 軟件學(xué)報(bào), 2009, 20(1): 54-66.YANG Bo, LIU Da-you, LIU Ji-ming, et al. Complex network clustering algorithms[J]. Journal of Software, 2009, 20(1):54-66.

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

[3] Guimera R, Amaral L A N. Functional cartography of complex metabolic networks[J]. Nature, 2005, 433(2): 895-900.

[4] Palla G, Derenyi I, Farkas I, et al. Uncovering the overlapping community structures of complex networks in nature and society[J]. Nature, 2005, 435(6): 814-818.

[5] Wilkinson D M, Huberman B A. A method for finding communities of related genes[J]. Proc of the National Academy of Science, 2004, 101(Suppl 1): 5241-5248.

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

[7] Sales-Pardo M, Guimerà R, Moreira A A, et al. Extracting the hierarchical organization of complex systems[J]. Proc of the National Academy of Science, 2007, 104(39): 15224-15229.

[8] Ravasz E, Somera A L, Mongru D A, et al. Hierarchical organization of modularity in metabolic networks[J]. Science,2002, 297(8): 1551-1555.

[9] Pons P. Post-processing hierarchical community structures:Quality improvements and multi-scale view[EB/OL].[2006-08-09]. http://arxiv.org/ps_cache/cs/pdf/0608/0608050 v1.pdf.

[10] Newman M E J. Fast algorithm for detecting community structure in networks[J]. The European Physical Journal B, 2004,38(6): 321-330.

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

[12] Wang Z, Zhang J. In serach of the biological significance of modular structures in protein networks[J]. PLOS Computational Biology, 2007, 3(6): 1011-1021.

[13] Newman M E J. Modularity and communities structure in networks[J]. Proc of the National Academy of Science, 2006,103(23): 8577-8582.

[14] Pujol J M, Béjar J, Delgado J. Clustering algorithm for determining community structure in large networks[J]. Physical Review E, 2006, 74(1): 016107-1-016107-9.

[15] Duch J, Arenas A. Community detection in complex networks using extreme optimization[J]. Physical Review E, 2005, 72(2):027104-1-027104-4.

[16] Guimera R, Sales M, Amaral L A N. Modularity from fluctuations in random graphs and complex networks[J].Physical Review E, 2004, 70(2): 025101-1-025101-8.

[17] Fortunato S, Barthelemy M. Resolution limit in community detection[J]. Proc of the National Academy of Science, 2007,104(1): 36-41.

[18] Flake G W, Lawrence S, Giles C L, et al. Self-Organization and identification of Web communities[J]. IEEE Computer, 2002,35(3): 66-71.

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

[20] Wu F, Huberman B A. Finding communities in linear time: A physics approach[J]. European Physical Journal B, 2004, 38(2):331-338.

[21] Saito K, Yamada T, Kazama K. Extracting communities from complex networks by the k-dense method[J]. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2008, E91-A(11): 3304-3311.

[22] Lancichinetti A, Fortunato S, Kertesz J. Detecting the overlapping and hierarchical community structure of complex networks[EB/OL]. [2009-05-11]. http://arxiv.org/ps_cache/arxiv/pdf/0802/0802.1218 v2.pdf.

[23] SHEN Hua, CHENG Xue, CAI Kai, et al. Detect overlapping and hierarchical community structure in networks[J]. Physica A,2009, 388: 1706-1712

[24] Bron C, Kerbosch J. Finding all cliques in an undirected graph[J].Communications of the ACM, 1973, 16(9): 575-577.

[25] Bader G D, Hogue C W. An automated method for finding molecular complexes in large protein interaction networks[J].BMC Bioinformatics, 2003, 4(2): 1-27.

[26] King A D, Przulj N, Jurisica I. Protein complex prediction via cost-based clustering[J]. Bioinformatics, 2004, 20(17):3013-3020.