一種基于局部擴(kuò)展優(yōu)化的重疊社區(qū)發(fā)現(xiàn)算法*

李 慧，楊青泉，王慧慧

(首都師范大學(xué)教育技術(shù)系，北京100048)

1 引言

復(fù)雜網(wǎng)絡(luò)是現(xiàn)實(shí)世界中復(fù)雜系統(tǒng)的高度抽象，如生物系統(tǒng)中的新陳代謝網(wǎng)、蛋白質(zhì)相互作用網(wǎng)，科技系統(tǒng)中的因特網(wǎng)、萬維網(wǎng)，社會系統(tǒng)中的科學(xué)家協(xié)作網(wǎng)、電子郵件網(wǎng)等。除了小世界特性和無標(biāo)度特性外，社區(qū)結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)最重要的拓?fù)浣Y(jié)構(gòu)特征之一，已成為多學(xué)科交叉研究的熱點(diǎn)［15］。挖掘復(fù)雜網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)，對分析網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)、理解網(wǎng)絡(luò)的功能及預(yù)測網(wǎng)絡(luò)的行為等具有重要的理論意義和實(shí)用價(jià)值。

2002年，Girvan和Newman首次提出著名的社區(qū)發(fā)現(xiàn)算法GN，引起了國內(nèi)外研究者的廣泛關(guān)注，隨后在社區(qū)挖掘領(lǐng)域取得了一系列創(chuàng)新性研究成果［6，7］。經(jīng)典的社區(qū)發(fā)現(xiàn)算法包括圖分割、層次聚類、譜聚類、模塊度優(yōu)化及基于模型的方法等，主要圍繞非重疊社區(qū)探測問題展開，具有一定的局限性:(1)需要網(wǎng)絡(luò)的結(jié)構(gòu)信息、社區(qū)規(guī)模和社區(qū)劃分?jǐn)?shù)目等先驗(yàn)知識;(2)全局搜索和計(jì)算影響算法的運(yùn)行速度，計(jì)算復(fù)雜度高;(3)難以發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)中社區(qū)的重疊屬性。2005年，Palla等人［8］拓展了傳統(tǒng)社區(qū)模式，允許節(jié)點(diǎn)同時(shí)屬于多個(gè)社區(qū)，提出基于派系過濾的重疊社區(qū)發(fā)現(xiàn)算法，開啟了重疊社區(qū)結(jié)構(gòu)識別的研究熱潮，迅速成為社區(qū)挖掘的前沿研究熱點(diǎn)。派系過濾、標(biāo)簽傳播［9］、局部邊聚類優(yōu)化［10］、局部擴(kuò)展優(yōu)化［11，12］等重疊社區(qū)發(fā)現(xiàn)方法，無需完整的網(wǎng)絡(luò)結(jié)構(gòu)信息等先驗(yàn)知識，基于局部拓?fù)浣Y(jié)構(gòu)揭示網(wǎng)絡(luò)整體或局部的社區(qū)結(jié)構(gòu)，在計(jì)算代價(jià)、網(wǎng)絡(luò)局部社區(qū)特性挖掘等方面具有更多優(yōu)勢。

基于局部擴(kuò)展優(yōu)化的重疊社區(qū)發(fā)現(xiàn)算法，通常從不同種子節(jié)點(diǎn)開始，根據(jù)給定的優(yōu)化函數(shù)，探索種子所在的局部社區(qū)結(jié)構(gòu)，由所有局部社區(qū)結(jié)構(gòu)融合成整個(gè)網(wǎng)絡(luò)的重疊社區(qū)結(jié)構(gòu)，代表性算法有LFM(Local Fitness Maximization)算法［11］和 GCE(Greedy Clique Expansion) 算法［12］。Lancichinetti等人提出的基于局部結(jié)構(gòu)適應(yīng)度的社區(qū)擴(kuò)展方法LFM是第一個(gè)能同時(shí)發(fā)現(xiàn)重疊社區(qū)及其層次結(jié)構(gòu)的算法。LFM隨機(jī)選取初始種子節(jié)點(diǎn)，基于適應(yīng)度函數(shù)的貪婪優(yōu)化，從種子節(jié)點(diǎn)開始逐步合并使節(jié)點(diǎn)適應(yīng)度增加的鄰居節(jié)點(diǎn)或刪除使其減小的節(jié)點(diǎn)，直至適應(yīng)度函數(shù)為負(fù)值，得到種子節(jié)點(diǎn)所在的局部社區(qū);搜索過程中，任意節(jié)點(diǎn)可以被多次訪問，使得節(jié)點(diǎn)能夠包含在多個(gè)社區(qū)，從而發(fā)現(xiàn)網(wǎng)絡(luò)的重疊社區(qū)結(jié)構(gòu);調(diào)節(jié)分辨率參數(shù)可以獲得社區(qū)的層次結(jié)構(gòu)。LFM算法對初始種子節(jié)點(diǎn)較敏感，隨機(jī)選取種子節(jié)點(diǎn)可能導(dǎo)致劃分結(jié)果的不穩(wěn)定，誤選種子節(jié)點(diǎn)將不能得到合理的社區(qū)結(jié)構(gòu);當(dāng)初始種子節(jié)點(diǎn)位于稀疏的重疊區(qū)域時(shí)，會出現(xiàn)左右搖擺的社區(qū)漂移問題，帶來大量的計(jì)算冗余;在局部擴(kuò)展過程中存在刪除節(jié)點(diǎn)操作，可能導(dǎo)致最初的種子節(jié)點(diǎn)被刪除，使得擴(kuò)展過程不再圍繞該種子進(jìn)行，違背社區(qū)的“局部性”［13，14］。GCE 算法首先選取所有節(jié)點(diǎn)規(guī)模不小于k的最大團(tuán)作為種子，然后采用貪心策略從種子開始逐步添加適應(yīng)度函數(shù)最大的節(jié)點(diǎn)，直至適應(yīng)度函數(shù)不再增大，得到種子所在的局部社區(qū)Ct;計(jì)算 Ct與已檢測到的社區(qū) C1，C2，…，Ct－1之間的距離，如小于給定的閾值則舍棄Ct，否則保留Ct。GCE算法選取的種子存在相似性，導(dǎo)致不同種子擴(kuò)展得到相似或者冗余的社區(qū)。在種子擴(kuò)展過程中存在社區(qū)刪除操作，使得最終獲得的重疊社區(qū)只能覆蓋整個(gè)網(wǎng)絡(luò)的一部分節(jié)點(diǎn)，即算法結(jié)束后存在一部分社區(qū)標(biāo)簽未知的節(jié)點(diǎn)。

針對上述問題，本文提出一種基于節(jié)點(diǎn)聚集系數(shù)和適應(yīng)度函數(shù)的局部擴(kuò)展式重疊社區(qū)識別算法CFLEM(Local Expansion Method based on Clustering-coefficient and Fitness)，主要步驟包括基于節(jié)點(diǎn)聚集系數(shù)的種子選取、基于適應(yīng)度函數(shù)最大化的自然社區(qū)識別以及社區(qū)結(jié)果的對比與合并。本文的主要貢獻(xiàn):

(1)基于節(jié)點(diǎn)聚集系數(shù)的種子過濾規(guī)則能夠得到局部性好、結(jié)構(gòu)穩(wěn)定的自然社區(qū)識別結(jié)果，避免了結(jié)果抖動(dòng)性問題。

(2)對社區(qū)識別結(jié)果的對比與合并，能夠在保證高社區(qū)覆蓋率的前提下盡量減少冗余社區(qū)。

本文分別在 LFR(Lancichinetti-Fortunato-Radicchi)人工網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上對CFLEM算法的性能進(jìn)行測試，并與具有代表性的基于局部擴(kuò)展優(yōu)化的重疊社區(qū)發(fā)現(xiàn)算法進(jìn)行對比分析，結(jié)果表明本文算法在稀疏程度不同的網(wǎng)絡(luò)上均能發(fā)現(xiàn)較高質(zhì)量的重疊社區(qū)結(jié)構(gòu)。

2 基本概念及定義

2．1 社區(qū)

復(fù)雜網(wǎng)絡(luò)可以建模為圖 G=(V，E)，其中V={v1，v2，…，vn} 為節(jié)點(diǎn)的非空有限集，n為節(jié)點(diǎn)數(shù);E={e1，e2，…，em} 為邊的非空有限集，m 為邊數(shù)。節(jié)點(diǎn)vi的度定義為該節(jié)點(diǎn)的鄰居數(shù)，表示為，其中A是圖G的鄰接矩陣。社區(qū)是圖G的節(jié)點(diǎn)內(nèi)聚子圖，其內(nèi)部節(jié)點(diǎn)連接緊密，不同社區(qū)間的節(jié)點(diǎn)連接稀疏，反映了網(wǎng)絡(luò)的模塊化與異質(zhì)性。

定義1(社區(qū)相似度) 給定圖G中的任意2個(gè)社區(qū)C1和C2，社區(qū)相似度定義為:

δ(C1，C2)表示社區(qū)C1和C2的相似程度，取值范圍為［0，1］，值越大社區(qū)相似性越高。

2．2 適應(yīng)度函數(shù)

其中，f(C+{v})和f(C－{v})分別表示在同分辨率情況下的節(jié)點(diǎn)v在社區(qū)C內(nèi)部和在社區(qū)C外部的結(jié)構(gòu)適應(yīng)度。隨著分辨率α的增加，網(wǎng)絡(luò)逐漸呈現(xiàn)細(xì)粒度化趨勢，直至每個(gè)節(jié)點(diǎn)自成一個(gè)獨(dú)立的社區(qū)。根據(jù)節(jié)點(diǎn)適應(yīng)度f(v)可以判定節(jié)點(diǎn)v是重疊節(jié)點(diǎn)還是離散點(diǎn)。

2．3 聚集系數(shù)

定義4(節(jié)點(diǎn)的聚集系數(shù)) 假設(shè)圖G=(V，E)中節(jié)點(diǎn)vi有ki個(gè)鄰居節(jié)點(diǎn)，則節(jié)點(diǎn)vi的聚集系數(shù)CCi定義為其所有鄰居節(jié)點(diǎn)之間實(shí)際存在的邊數(shù)Ei與可能存在的最大邊數(shù)ki(ki－1)/2的比值，表示為:

節(jié)點(diǎn)vi的聚集系數(shù)CCi是衡量網(wǎng)絡(luò)集團(tuán)化程度的重要參數(shù)，用于描述節(jié)點(diǎn)的聚集程度，即與節(jié)點(diǎn)vi相連的兩個(gè)節(jié)點(diǎn)也相連的可能性。節(jié)點(diǎn)的聚集系數(shù)越大，表明其局部聚集性較高，成為干擾點(diǎn)和離散點(diǎn)的概率相對越小。

3 算法思想與分析

本文綜合運(yùn)用網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)信息和節(jié)點(diǎn)的屬性，提出一種基于局部擴(kuò)展優(yōu)化的重疊社區(qū)發(fā)現(xiàn)算法，首先根據(jù)網(wǎng)絡(luò)中節(jié)點(diǎn)的拓?fù)涮卣?聚集系數(shù))選取種子節(jié)點(diǎn)作為初始社區(qū)，然后采用貪心策略將初始社區(qū)擴(kuò)展為局部自然社區(qū)，最后對比、合并不同的局部社區(qū)獲得重疊社區(qū)結(jié)構(gòu)。具體過程見算法1。

算法1CFLEM算法

輸入:網(wǎng)絡(luò)G=(V，E)，分辨率參數(shù)α。

輸出:重疊社區(qū)結(jié)構(gòu)C。

步驟1初始化，C=。

步驟2根據(jù)種子選取算法，得到種子集合S。

步驟3當(dāng)S≠時(shí)，選擇某個(gè)種子，執(zhí)行步驟4;否則執(zhí)行步驟6。

步驟4種子擴(kuò)展成局部自然社區(qū)D，調(diào)整種子集合S。

步驟5將D加入到C中，返回步驟3。

步驟6對比、合并局部社區(qū)。

步驟7返回重疊社區(qū)結(jié)構(gòu)C，結(jié)束。

3．1 種子選取

種子選取是基于局部擴(kuò)展優(yōu)化的重疊社區(qū)發(fā)現(xiàn)算法的關(guān)鍵步驟，對社區(qū)識別結(jié)果的影響不容小覷。LFM算法隨機(jī)選取種子節(jié)點(diǎn)，不可避免地導(dǎo)致社區(qū)發(fā)現(xiàn)結(jié)果不穩(wěn)定。GCE算法選取網(wǎng)絡(luò)中所有節(jié)點(diǎn)規(guī)模不小于k的最大團(tuán)作為種子，避免了社區(qū)發(fā)現(xiàn)結(jié)果不穩(wěn)定的問題。但是，較小的k容易導(dǎo)致種子規(guī)模過大、擴(kuò)展得到的局部自然社區(qū)數(shù)增多，形成冗余社區(qū);較大的k則容易導(dǎo)致局部自然社區(qū)數(shù)減少，社區(qū)發(fā)現(xiàn)結(jié)果的覆蓋率降低;由于不同最大團(tuán)之間存在相似性，導(dǎo)致不同種子擴(kuò)展得到的局部社區(qū)是相似的甚至冗余的。

針對上述問題，本文借鑒從中心節(jié)點(diǎn)出發(fā)進(jìn)行社區(qū)發(fā)現(xiàn)可以提高社區(qū)識別質(zhì)量的思想［15］，提出了選取網(wǎng)絡(luò)的核心節(jié)點(diǎn)作為社區(qū)劃分的種子節(jié)點(diǎn)。核心節(jié)點(diǎn)通常位于網(wǎng)絡(luò)中節(jié)點(diǎn)連接緊密的區(qū)域，對信息傳播的貢獻(xiàn)較大。網(wǎng)絡(luò)中的不同社區(qū)與核心節(jié)點(diǎn)之間往往存在對應(yīng)關(guān)系，因此本文采用節(jié)點(diǎn)的聚集系數(shù)作為拓?fù)涮卣髦笜?biāo)來選取種子節(jié)點(diǎn)，具體過程見算法2。

算法2種子選取算法

輸入:網(wǎng)絡(luò) G=(V，E)。

輸出:種子集合S。

步驟1初始化，S=。

步驟2將節(jié)點(diǎn)按聚集系數(shù)從大到小排序，形成候選種子列表L，所有節(jié)點(diǎn)初始化為無標(biāo)記。

步驟3取出L中第一個(gè)節(jié)點(diǎn)v，如果v未標(biāo)記，設(shè)置標(biāo)記并將其加入種子集合S。

步驟4標(biāo)記v的鄰居節(jié)點(diǎn)N(v)，從列表L中移除已標(biāo)記的節(jié)點(diǎn)集

步驟5當(dāng)L≠時(shí)，繼續(xù)執(zhí)行步驟3;否則，輸出種子集合S。

種子選取算法能夠在網(wǎng)絡(luò)中發(fā)掘彼此分散的、局部聚集系數(shù)大的節(jié)點(diǎn)，通過這些種子節(jié)點(diǎn)擴(kuò)展而成的自然社區(qū)的局部性好，社區(qū)發(fā)現(xiàn)結(jié)果對全網(wǎng)絡(luò)的覆蓋率高。

3．2 局部擴(kuò)展

在擴(kuò)展階段，CFLEM算法通過最大化局部社區(qū)適應(yīng)度函數(shù)的方法對種子節(jié)點(diǎn)進(jìn)行擴(kuò)展得到自然社區(qū)，主要包含兩個(gè)步驟:添加當(dāng)前社區(qū)C的鄰居中f(v)為正值的節(jié)點(diǎn)和刪除社區(qū)C中f(v)為負(fù)值的節(jié)點(diǎn)，使得社區(qū)C的適應(yīng)度函數(shù)f(C)達(dá)到最大。CFLEM算法采用批添加節(jié)點(diǎn)和批刪除節(jié)點(diǎn)的方法擴(kuò)展社區(qū)C，即首先遍歷C的每一個(gè)鄰居節(jié)點(diǎn)v并記錄其f(v)，在遍歷結(jié)束后將f(v)＞0的節(jié)點(diǎn)統(tǒng)一加入社區(qū);然后再遍歷社區(qū)C，記錄其每個(gè)節(jié)點(diǎn)v的f(v)，遍歷結(jié)束后將f(v)＜0的節(jié)點(diǎn)統(tǒng)一移出社區(qū)。具體過程見算法3。

算法3局部擴(kuò)展算法

輸入:網(wǎng)絡(luò)G=(V，E)，種子s，分辨率參數(shù)α。

輸出:社區(qū)C;

C←{s};

for each neighbor vertex v of C do

計(jì)算節(jié)點(diǎn)適應(yīng)度f(v)

end for

將節(jié)點(diǎn)適應(yīng)度值大于零的鄰居節(jié)點(diǎn)統(tǒng)一加入社區(qū)C;

for each vertex v of C

計(jì)算節(jié)點(diǎn)適應(yīng)度f(v)

end for

將所有適應(yīng)度值小于零的節(jié)點(diǎn)統(tǒng)一移出社區(qū)C;

返回C，結(jié)束。

3．3 社區(qū)合并

重疊社區(qū)發(fā)現(xiàn)算法允許2個(gè)不同社區(qū)包含若干公共節(jié)點(diǎn)，因此種子擴(kuò)展得到的自然社區(qū)之間存在一定的相似性。當(dāng)相似性達(dá)到一定程度時(shí)，可能產(chǎn)生“過度重疊”現(xiàn)象，因此有必要對社區(qū)發(fā)現(xiàn)結(jié)果進(jìn)行后處理，發(fā)現(xiàn)其中的冗余社區(qū)，簡化社區(qū)結(jié)構(gòu)。

針對局部擴(kuò)展得到的自然社區(qū)，CFLEM算法采用公式(1)計(jì)算任意2個(gè)社區(qū)的相似度，即以它們之間共同節(jié)點(diǎn)在較小的社區(qū)中所占的比例來衡量社區(qū)是否需要合并。如果δ大于某個(gè)給定的閾值ε，則判定需要合并社區(qū)。具體過程見算法4。

算法4社區(qū)合并算法

輸入:社區(qū)集合{C}，閾值ε。

輸出:社區(qū)集合{C'}。

for each c in C do

if{C'}中存在社區(qū)c'和c的相似度大于ε

將c合并至社區(qū)c'

else

將c加入社區(qū)集合{C'}

end if

end for

返回{C'}，結(jié)束。

3．4 算法時(shí)間復(fù)雜度分析

CFLEM算法的實(shí)現(xiàn)過程可以概括為三個(gè)階段:(1)根據(jù)聚集系數(shù)調(diào)整種子節(jié)點(diǎn)并生成初始社區(qū);(2)將每個(gè)初始社區(qū)擴(kuò)展為局部社區(qū);(3)對比合并社區(qū)。階段(1)需要計(jì)算種子及其鄰居節(jié)點(diǎn)的聚集系數(shù)，最壞情況下計(jì)算給定網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的聚集系數(shù)時(shí)，時(shí)間復(fù)雜度為O(d2)，其中d為節(jié)點(diǎn)的平均度。階段(2)將每個(gè)初始社區(qū)擴(kuò)展為局部社區(qū)的時(shí)間復(fù)雜度為O(n2)，n表示社區(qū)的節(jié)點(diǎn)規(guī)模，若存在M個(gè)種子節(jié)點(diǎn)和初始社區(qū)，那么階段(2)的總時(shí)間開銷為 O(M珔n2)，珔n 表示平均社區(qū)節(jié)點(diǎn)規(guī)模。當(dāng)分辨率參數(shù)α較小時(shí)，新節(jié)點(diǎn)的加入導(dǎo)致f(C)增大的機(jī)會更大，使社區(qū)C能夠接納更多的節(jié)點(diǎn)，達(dá)到更大的社區(qū)規(guī)模(即珔n比較大)，時(shí)間復(fù)雜度隨之增大，最壞情況下時(shí)間復(fù)雜度為O(N2)，其中N為網(wǎng)絡(luò)中節(jié)點(diǎn)的規(guī)模。反之，當(dāng)α越來越大時(shí)，新節(jié)點(diǎn)的加入對增大f(C)值的貢獻(xiàn)越小，使新節(jié)點(diǎn)加入當(dāng)前社區(qū)的難度增大，從而形成較小規(guī)模的社區(qū)(即珔n比較小)，時(shí)間復(fù)雜度將逐漸趨于線性O(shè)(N)。階段(3)最壞情況下的時(shí)間復(fù)雜度為O(M2)。因此，CFLEM算法的時(shí)間復(fù)雜度在最壞情況下為O(d2+N2+M2)。在復(fù)雜網(wǎng)絡(luò)中，由于節(jié)點(diǎn)的平均度dN，種子的個(gè)數(shù)M ＜N，因此總的來說，CFLEM算法的時(shí)間復(fù)雜度為O(N2)。

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

本文采用不同規(guī)模、不同屬性的人工網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集測試算法性能，設(shè)置如下2類實(shí)驗(yàn):

(1)測試當(dāng)節(jié)點(diǎn)數(shù)及混雜系數(shù)變化時(shí)算法性能的變化規(guī)律，網(wǎng)絡(luò)數(shù)據(jù)為LFR網(wǎng)絡(luò)數(shù)據(jù)生成器［16］模擬生成的人工網(wǎng)絡(luò)。

(2)比較各算法發(fā)現(xiàn)不同網(wǎng)絡(luò)結(jié)構(gòu)的性能，網(wǎng)絡(luò)數(shù)據(jù)為6個(gè)不同規(guī)模、不同類型的真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集。

為了實(shí)現(xiàn)算法的對比分析，采用模塊度函數(shù)Qo作為度量指標(biāo)。Newman等人［17］最先提出的模塊度函數(shù)Q已成為評價(jià)不可重疊社區(qū)發(fā)現(xiàn)算法的重要指標(biāo)。針對重疊社區(qū)劃分的質(zhì)量評價(jià)，Shen等人［18］提出了擴(kuò)展模塊度函數(shù)Qo，其函數(shù)表達(dá)式為:

其中，v、w為節(jié)點(diǎn);K是網(wǎng)絡(luò)包含的社區(qū)數(shù);Ov是節(jié)點(diǎn)v所屬社區(qū)的數(shù)目;Avw為鄰接矩陣A中的元素，如果節(jié)點(diǎn)v、w相連，則Avw=1，否則Avw=0;m=為網(wǎng)絡(luò)中邊的數(shù)目;d是節(jié)點(diǎn)v的度值，v表示在隨機(jī)網(wǎng)絡(luò)中節(jié)點(diǎn)v和節(jié)點(diǎn)w之間存在連邊的可能性。

當(dāng)復(fù)雜網(wǎng)絡(luò)的社區(qū)內(nèi)部節(jié)點(diǎn)連接越緊密而不同社區(qū)間節(jié)點(diǎn)連接越稀疏時(shí)，Qo函數(shù)取值越大，算法社區(qū)劃分的準(zhǔn)確率越高，算法性能越好。

4．1 不同清晰度的人工網(wǎng)絡(luò)上算法性能的比較

為了比較具有不同清晰度網(wǎng)絡(luò)上的算法性能，采用不同規(guī)模的人工網(wǎng)絡(luò)測試CFLEM算法與LFM算法隨網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)及混雜系數(shù)變化的規(guī)律。4類人工網(wǎng)絡(luò)由LFR網(wǎng)絡(luò)數(shù)據(jù)生成器模擬獲得，分別為稀疏網(wǎng)絡(luò)小社區(qū)(SS)、稀疏網(wǎng)絡(luò)大社區(qū)(SL)、稠密網(wǎng)絡(luò)小社區(qū)(DS)和稠密網(wǎng)絡(luò)大社區(qū)(DL)，對應(yīng)的LFR參數(shù)(網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)N、節(jié)點(diǎn)平均度值珋k、節(jié)點(diǎn)最大度值kmax、社區(qū)最大規(guī)模Cmax、社區(qū)最小規(guī)模Cmin、節(jié)點(diǎn)度指數(shù)t1、社區(qū)規(guī)模指數(shù)t2、重疊節(jié)點(diǎn)數(shù)On、重疊節(jié)點(diǎn)屬于社區(qū)數(shù)Om和混雜系數(shù)μ)見表1。其中，混雜系數(shù)μ反映了網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的清晰程度，該值越小社區(qū)結(jié)構(gòu)越清晰，當(dāng)μ∈［0．7，0．9］時(shí)網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)通常不明顯，因此分別在4類網(wǎng)絡(luò)上生成μ∈［0．1，0．6］的測試網(wǎng)絡(luò)。

Table 1 Parameters setting of synthetic networks表1 人工網(wǎng)絡(luò)數(shù)據(jù)集的參數(shù)設(shè)置

實(shí)驗(yàn)針對不同算法設(shè)置不同的參數(shù)，并選取各參數(shù)下Qo值中的最大值作為最終結(jié)果進(jìn)行對比。具體地，LFM 算法中，設(shè)置參數(shù) α ∈［0．8，1．6］，取值間隔為0．1，運(yùn)行次數(shù)r=3;CFLEM算法中，設(shè)置參數(shù) α ∈［0．6，1．2］，ε ∈［0，0．9］，取值間隔均為0．1。隨著網(wǎng)絡(luò)規(guī)模(節(jié)點(diǎn)數(shù)、邊數(shù))的增加和混雜系數(shù)μ的增大，CFLEM算法與LFM算法在不同清晰度的4類人工網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果如圖1所示。

總體來看，隨著混雜系數(shù)μ的增加，網(wǎng)絡(luò)中社區(qū)的內(nèi)部節(jié)點(diǎn)連接社區(qū)外部節(jié)點(diǎn)的機(jī)會增大，導(dǎo)致社區(qū)結(jié)構(gòu)變得模糊，社區(qū)發(fā)現(xiàn)的難度變大，使得2種算法社區(qū)發(fā)現(xiàn)結(jié)果的質(zhì)量降低，因此在4類人工網(wǎng)絡(luò)上2種算法得到的Qo值均有不同程度的下降。其中，LFM算法相對于CFLEM算法的下降幅度更大，尤其在稀疏網(wǎng)絡(luò)小社區(qū)(SS)和稀疏網(wǎng)絡(luò)大社區(qū)(SL)中，當(dāng)社區(qū)結(jié)構(gòu)越來越不明顯時(shí)，CFLEM算法展現(xiàn)出一定的優(yōu)勢。

從圖1中可以看出，CFLEM算法在絕大多數(shù)網(wǎng)絡(luò)上的社區(qū)發(fā)現(xiàn)結(jié)果要好于LFM算法，原因在于CFLEM算法選取網(wǎng)絡(luò)中的核心節(jié)點(diǎn)作為種子，擴(kuò)展得到的社區(qū)具有更好的局部性;LFM算法則隨機(jī)選取種子，在局部擴(kuò)展時(shí)將節(jié)點(diǎn)適應(yīng)度函數(shù)為負(fù)的種子刪除，導(dǎo)致擴(kuò)展過程不再圍繞該種子進(jìn)行，從而得到局部性較差的社區(qū)。

對比CFLEM算法、LFM算法在稀疏網(wǎng)絡(luò)小社區(qū)(SS)、稀疏網(wǎng)絡(luò)大社區(qū)(SL)、稠密網(wǎng)絡(luò)小社區(qū)(DS)和稠密網(wǎng)絡(luò)大社區(qū)(DL)的社區(qū)識別結(jié)果，2種算法在稀疏網(wǎng)絡(luò)上的準(zhǔn)確度更好。原因在于:當(dāng)固定混雜系數(shù)μ時(shí)，稀疏網(wǎng)絡(luò)相對于稠密網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)更為明顯，能夠較準(zhǔn)確地發(fā)現(xiàn)其中的自然社區(qū)。

綜上所述，與FLM算法相比，CFLEM算法在不同清晰度的4類人工網(wǎng)絡(luò)數(shù)據(jù)集上能夠取得較高質(zhì)量的社區(qū)發(fā)現(xiàn)結(jié)果。

4．2 不同結(jié)構(gòu)的真實(shí)網(wǎng)絡(luò)上算法性能的比較

為了對比分析算法CFLEM、LFM、GCE的結(jié)構(gòu)發(fā)現(xiàn)能力，測試網(wǎng)絡(luò)采用6個(gè)不同規(guī)模、不同類型的真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集:人物關(guān)系網(wǎng)絡(luò)(Karate、Football)、動(dòng)物關(guān)系網(wǎng)絡(luò)(Dolphins)、游戲網(wǎng)絡(luò)(Risk)、論文合作網(wǎng)絡(luò)(CA-GrQc)和產(chǎn)品銷售記錄網(wǎng)絡(luò)(Amazon)，其基本信息見表2，更多信息參見http://www-personal．umich．edu/～ mejn/netdata、http://snap．stanford．edu/data 和 http://en．wikipedia．org/wiki/Risk_(game)。

Table 2 Datasets of real-world networks表2 真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集表

由于絕大多數(shù)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集的社區(qū)結(jié)構(gòu)是未知的，因此除了重疊模塊度函數(shù)Qo外，本文還采用社區(qū)連接密度和網(wǎng)絡(luò)覆蓋率Ro來綜合評價(jià)算法性能。社區(qū)連接密度Do定義為:

其中，K為網(wǎng)絡(luò)中的社區(qū)數(shù)，Do可以看作當(dāng)α=1時(shí)網(wǎng)絡(luò)中所有K個(gè)社區(qū)的局部結(jié)構(gòu)適應(yīng)度的平均值。

網(wǎng)絡(luò)覆蓋率Ro定義為:

其中，N、K分別為網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)和社區(qū)數(shù)，Ci表示第i個(gè)社區(qū)。社區(qū)連接密度Do和網(wǎng)絡(luò)覆蓋率Ro的取值均為［0，1］，值越大表明社區(qū)發(fā)現(xiàn)結(jié)果的質(zhì)量越好。

對于 GCE 算法，設(shè)置其參數(shù) α∈［0．8，1．6］，取值間隔為0．1，參數(shù) k∈{3，4}，ε =0．6;CFLEM算法和LFM算法的參數(shù)設(shè)置與4．1節(jié)相同，并選取各參數(shù)下的最優(yōu)結(jié)果進(jìn)行對比。各算法在6個(gè)真實(shí)網(wǎng)絡(luò)下的社區(qū)發(fā)現(xiàn)結(jié)果質(zhì)量的Qo、Do、Ro值分別如圖2a、圖2b、圖2c所示，其中橫坐標(biāo)軸表示真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集的編號，縱坐標(biāo)軸分別表示3種算法在對應(yīng)數(shù)據(jù)集上的社區(qū)發(fā)現(xiàn)結(jié)果的Qo、Do、Ro值。

由圖2a可以看出，針對大部分真實(shí)網(wǎng)絡(luò)，CFLEM算法得到的Qo值最優(yōu)，二者較GCE算法具有較為明顯的優(yōu)勢，表明CFLEM算法能夠得到質(zhì)量較高的重疊社區(qū)結(jié)構(gòu)。

圖2b表明，CFLEM算法在所有真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上都取得了最高的社區(qū)連接密度Do，LFM算法得到的社區(qū)連接密度相對較低，原因在于CFLEM算法的種子節(jié)點(diǎn)選取方法優(yōu)于LFM算法隨機(jī)選取種子的方法，社區(qū)擴(kuò)展過程圍繞所選種子進(jìn)行，得到了局部性較好的社區(qū)。

如圖2c所示，CFLEM算法和LFM算法在不同網(wǎng)絡(luò)上均具有較高且較穩(wěn)定的網(wǎng)絡(luò)覆蓋率Ro，而GCE算法的Ro值較差且波動(dòng)較大。LFM算法從無社區(qū)標(biāo)簽的節(jié)點(diǎn)中隨機(jī)選取種子，在算法結(jié)束時(shí)僅剩余極少數(shù)標(biāo)簽不明確的節(jié)點(diǎn)，因此其社區(qū)覆蓋率很高。與GCE算法相比，CFLEM算法所選種子之間的相似性更低，擴(kuò)展得到的自然社區(qū)能夠覆蓋更多的網(wǎng)絡(luò)節(jié)點(diǎn);而且CFLEM算法對社區(qū)發(fā)現(xiàn)結(jié)果進(jìn)行了后處理，合并冗余社區(qū)，保證了網(wǎng)絡(luò)的高覆蓋率，更符合社區(qū)的真實(shí)情況。GCE算法將冗余的社區(qū)直接舍棄，導(dǎo)致算法結(jié)束時(shí)存在一部分社區(qū)標(biāo)簽未知的節(jié)點(diǎn)，社區(qū)發(fā)現(xiàn)結(jié)果的質(zhì)量較低。

綜合來看，在6個(gè)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上，CFLEM算法社區(qū)發(fā)現(xiàn)結(jié)果的質(zhì)量最高，LFM算法的結(jié)果質(zhì)量次之，GCE算法的結(jié)果質(zhì)量相對較低。3種算法的結(jié)果均存在不同程度的波動(dòng)，但CFLEM算法的波動(dòng)相對較小。

5 結(jié)束語

本文提出一種基于節(jié)點(diǎn)聚集系數(shù)和適應(yīng)度函數(shù)的局部擴(kuò)展式重疊社區(qū)發(fā)現(xiàn)算法——CFLEM。該算法選取網(wǎng)絡(luò)的核心節(jié)點(diǎn)作為社區(qū)劃分的種子節(jié)點(diǎn)，采用貪心策略將種子擴(kuò)展為局部自然社區(qū)，然后對社區(qū)發(fā)現(xiàn)結(jié)果進(jìn)行后處理，合并冗余社區(qū)從而保持社區(qū)的高覆蓋率。在LFR人工網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明:與LFM、GCE算法相比，CFLEM算法能夠在稀疏程度不同的網(wǎng)絡(luò)上獲得更優(yōu)的社區(qū)發(fā)現(xiàn)結(jié)果。下一步的工作將拓展CFLEM算法至加權(quán)網(wǎng)絡(luò)中，致力于加權(quán)網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)問題研究。