種子節(jié)點(diǎn)貪婪擴(kuò)張的重疊社區(qū)發(fā)現(xiàn)方法

李 艷,賀 靜,武優(yōu)西

1(河北工業(yè)大學(xué) 經(jīng)濟(jì)管理學(xué)院,天津 300401)2(河北工業(yè)大學(xué) 人工智能與數(shù)據(jù)科學(xué)學(xué)院,天津 300401)3(河北省大數(shù)據(jù)計(jì)算重點(diǎn)實(shí)驗(yàn)室,天津 300401)

1 引 言

現(xiàn)實(shí)世界中存在許多復(fù)雜的系統(tǒng),如人際關(guān)系網(wǎng)、捕食者關(guān)系網(wǎng)、城市交通網(wǎng)、蛋白質(zhì)合作網(wǎng)等,這些復(fù)雜系統(tǒng)都可以抽象成復(fù)雜網(wǎng)絡(luò)進(jìn)行分析與研究.復(fù)雜系統(tǒng)中的實(shí)體用節(jié)點(diǎn)表示,而實(shí)體間的關(guān)系用邊表示.復(fù)雜網(wǎng)絡(luò)的一個(gè)重要特性是社區(qū)結(jié)構(gòu)(也被稱為“模塊”或“簇”等),它是指網(wǎng)絡(luò)由若干個(gè)社區(qū)組成,同一社區(qū)內(nèi)的節(jié)點(diǎn)彼此之間連接緊密,而不同社區(qū)之間的連接稀疏[1].社區(qū)發(fā)現(xiàn)研究的目的就是挖掘復(fù)雜網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu).社區(qū)發(fā)現(xiàn)能夠揭示復(fù)雜網(wǎng)絡(luò)中的群體共性,準(zhǔn)確理解網(wǎng)絡(luò)內(nèi)部的拓?fù)浣Y(jié)構(gòu),從而為利用和改造網(wǎng)絡(luò)提供指導(dǎo),推進(jìn)實(shí)際應(yīng)用研究,所以社區(qū)發(fā)現(xiàn)已經(jīng)成為復(fù)雜網(wǎng)絡(luò)研究的熱點(diǎn)之一.

社區(qū)發(fā)現(xiàn)的早期研究側(cè)重于非重疊社區(qū)發(fā)現(xiàn),方法假設(shè)每個(gè)節(jié)點(diǎn)有且僅屬于一個(gè)社區(qū),并且社區(qū)彼此不重疊.代表性算法包括基于圖分割方法[2]、基于標(biāo)簽傳播方法[3]、層次聚類方法[4]、模塊度優(yōu)化方法[5]等.對(duì)非重疊社區(qū)發(fā)現(xiàn)的研究取得了良好的成果,并提出了很多具有代表性的算法.但是現(xiàn)實(shí)世界中,通常一個(gè)事物具有多種屬性,因此一個(gè)事物可以歸屬于多個(gè)類別,若將這種現(xiàn)象推廣到社區(qū)發(fā)現(xiàn)中,就導(dǎo)致重疊社區(qū)現(xiàn)象.重疊社區(qū)發(fā)現(xiàn)是指網(wǎng)絡(luò)中存在屬于多個(gè)社區(qū)的節(jié)點(diǎn),具體可分為:a)派系過濾方法,此類方法認(rèn)為社區(qū)是由多個(gè)內(nèi)部連接緊密的全連通子圖組成,定義為k-派系,每個(gè)k-派系只屬于一個(gè)社區(qū),但一個(gè)節(jié)點(diǎn)可以屬于多個(gè)k-派系,因此能夠發(fā)現(xiàn)重疊節(jié)點(diǎn),代表方法包括CPM算法[6];b)基于標(biāo)簽傳播的方法,初始化時(shí)給每個(gè)節(jié)點(diǎn)分配唯一的標(biāo)簽,通過迭代更新節(jié)點(diǎn)的標(biāo)簽和對(duì)標(biāo)簽的隸屬度,直到標(biāo)簽不再變化,標(biāo)簽相同的節(jié)點(diǎn)劃分到同一社區(qū),具有多個(gè)標(biāo)簽的節(jié)點(diǎn)即為重疊節(jié)點(diǎn),代表方法包括COPRA算法[7];c)基于鏈接的方法,將聚類對(duì)象轉(zhuǎn)換為網(wǎng)絡(luò)中的邊(或稱為“鏈接”),對(duì)邊進(jìn)行非重疊的劃分,由于節(jié)點(diǎn)通常有多條邊以其為端點(diǎn),轉(zhuǎn)換成節(jié)點(diǎn)社區(qū)時(shí)便能發(fā)現(xiàn)重疊節(jié)點(diǎn),代表方法包括LINK算法[8];d)基于局部社區(qū)優(yōu)化和擴(kuò)張的方法,此類方法從局部社區(qū)出發(fā),基于優(yōu)化函數(shù)逐步擴(kuò)張,多個(gè)擴(kuò)張之間會(huì)形成交叉區(qū)域,由此發(fā)現(xiàn)重疊社區(qū)結(jié)構(gòu),代表方法包括LFM算法[9]和GCE算法[10].除上述方法外,還有一些比較經(jīng)典的方法,比如Gregory 等人[11]提出的CONGA算法,通過節(jié)點(diǎn)自身分裂出克隆節(jié)點(diǎn),在分裂節(jié)點(diǎn)間添加虛邊來發(fā)現(xiàn)重疊節(jié)點(diǎn).

基于局部社區(qū)優(yōu)化和擴(kuò)張的方法,利用網(wǎng)絡(luò)中局部拓?fù)浣Y(jié)構(gòu)信息優(yōu)化局部函數(shù)來發(fā)現(xiàn)社區(qū)結(jié)構(gòu),因?yàn)椴恍枰谰W(wǎng)絡(luò)的全局拓?fù)浣Y(jié)構(gòu),所以對(duì)當(dāng)下節(jié)點(diǎn)數(shù)越來越多的大型網(wǎng)絡(luò)表現(xiàn)出一定的優(yōu)勢.種子的選擇是基于局部社區(qū)優(yōu)化和擴(kuò)張方法挖掘社區(qū)結(jié)構(gòu)的基礎(chǔ),會(huì)影響挖掘質(zhì)量.Lancichinetti等人[9]提出的LFM算法與Coscia等人[12]提出的DEMON算法都是通過隨機(jī)選擇節(jié)點(diǎn)作為種子來擴(kuò)張社區(qū),不可避免的造成社區(qū)發(fā)現(xiàn)結(jié)果不穩(wěn)定的情況;而Lee等人[10]提出的GCE算法是在LFM算法上做了改進(jìn),通過經(jīng)典的Bron-Kerbosch算法[13]挖掘網(wǎng)絡(luò)中的k-派系作為種子,相對(duì)于節(jié)點(diǎn),派系的位置是固定的,避免了社區(qū)發(fā)現(xiàn)結(jié)果不穩(wěn)定的問題,但種子的選擇依賴于參數(shù)k的選擇;Shen等人[14]提出的EAGLE算法選擇網(wǎng)絡(luò)中的極大派系作為種子,忽略次要極大派系,但選擇派系作為種子的時(shí)間復(fù)雜度很高.

本文選擇基于點(diǎn)度中心性定義的局部最大度節(jié)點(diǎn)作為種子節(jié)點(diǎn)來擴(kuò)張社區(qū),得到的社區(qū)質(zhì)量高,避免了結(jié)果不穩(wěn)定的情況.

2 種子節(jié)點(diǎn)貪婪擴(kuò)張的重疊社區(qū)發(fā)現(xiàn)算法

本文針對(duì)當(dāng)前局部社區(qū)優(yōu)化和擴(kuò)張方法種子選擇復(fù)雜度高和社區(qū)發(fā)現(xiàn)結(jié)果不穩(wěn)定的問題,提出了一種種子節(jié)點(diǎn)貪婪擴(kuò)張的重疊社區(qū)發(fā)現(xiàn)算法(Seed Greedy Expansion,SGE),該算法分為兩個(gè)部分,第一部分利用網(wǎng)絡(luò)節(jié)點(diǎn)的拓?fù)涮卣鼽c(diǎn)度中心性尋找種子,第二部分通過基于適應(yīng)度函數(shù)的貪心策略擴(kuò)張種子為自然社區(qū).

2.1 種子選取

在實(shí)際的網(wǎng)絡(luò)中,通常有一些度很大的節(jié)點(diǎn),稱為“中心節(jié)點(diǎn)”.這類節(jié)點(diǎn)與其他節(jié)點(diǎn)聯(lián)系密切,信息傳播能力強(qiáng),通常位于網(wǎng)絡(luò)中節(jié)點(diǎn)連接較為緊密的區(qū)域,且比較分散的分布于整個(gè)網(wǎng)絡(luò)[15],這與社區(qū)的定義相符合,為此本文選擇這些節(jié)點(diǎn)作為種子.節(jié)點(diǎn)的中心性可以反映其在網(wǎng)絡(luò)中的重要性[16].研究人員給出度量中心性的指標(biāo)包括點(diǎn)度中心性、特征向量中心性、接近中心性和中介中心性等,其中只有點(diǎn)度中心性的計(jì)算只需要網(wǎng)絡(luò)的局部連接信息,其余方法都需要完整的網(wǎng)絡(luò)拓?fù)湫畔?

通常,一個(gè)網(wǎng)絡(luò)可以用無向圖G=(V,E)表示,其中V={v1,v2,…,vn}表示網(wǎng)絡(luò)中的n個(gè)節(jié)點(diǎn),E={e1,e2,…,em}表示網(wǎng)絡(luò)中的m條邊.

定義1.點(diǎn)度中心性:節(jié)點(diǎn)的度數(shù)即為其點(diǎn)度中心性,用Cd(vi)表示,即:

Cd(vi)=d(vi)

(1)

其中d(vi)是節(jié)點(diǎn)vi的度數(shù)

定義2.局部中心節(jié)點(diǎn):當(dāng)節(jié)點(diǎn)的中心性不小于其所有鄰居節(jié)點(diǎn)的中心性時(shí),該節(jié)點(diǎn)稱為網(wǎng)絡(luò)的局部中心節(jié)點(diǎn).

使用點(diǎn)度中心性來度量網(wǎng)絡(luò)中節(jié)點(diǎn)的中心性時(shí),局部中心節(jié)點(diǎn)是局部最大度節(jié)點(diǎn).給定圖G中的節(jié)點(diǎn)vi,如果節(jié)點(diǎn)vi的度大于或等于其所有鄰居節(jié)點(diǎn)的度,則節(jié)點(diǎn)vi是局部最大度節(jié)點(diǎn).局部最大度節(jié)點(diǎn)有以下性質(zhì):在圖G中,vi和vj是兩個(gè)局部最大度節(jié)點(diǎn),如果d(vi)≠d(vj),則vi和vj不相鄰[16].

局部最大度節(jié)點(diǎn)中心度大,大部分都分散在網(wǎng)絡(luò)中,只有當(dāng)兩個(gè)局部最大度節(jié)點(diǎn)具有相同度數(shù)時(shí)它們才相鄰,所以本文選擇局部最大度節(jié)點(diǎn)作為種子.具體算法如算法1所示.首先將所有節(jié)點(diǎn)標(biāo)記為0,找到節(jié)點(diǎn)集合中度最大的節(jié)點(diǎn)放入種子節(jié)點(diǎn)集合中,如算法1第2-8行所示;然后將局部最大度節(jié)點(diǎn)及其鄰居節(jié)點(diǎn)標(biāo)記為1并移出節(jié)點(diǎn)集合,如算法9-10行所示;迭代尋找下一個(gè)種子,直到所有節(jié)點(diǎn)都被標(biāo)記并移出節(jié)點(diǎn)集合.

當(dāng)網(wǎng)絡(luò)中存在若干個(gè)同時(shí)滿足度最大的節(jié)點(diǎn),取其中一個(gè).假設(shè)一對(duì)節(jié)點(diǎn)vi和vj同時(shí)為度最大的節(jié)點(diǎn),因?yàn)槎葦?shù)相同所以vi是vj的鄰居,因?yàn)樯鐓^(qū)之間的連接是稀疏的,所以如果vi和vj都被選為種子,由它們擴(kuò)張形成的社區(qū)很可能近似重復(fù).所以在算法1中,當(dāng)vi被標(biāo)記為種子時(shí),vj作為vi的鄰居也會(huì)被標(biāo)記并從V中移除,所以只選擇節(jié)點(diǎn)vi作為種子加入到集合S中.

算法1能夠找出分布在網(wǎng)絡(luò)中的局部最大度節(jié)點(diǎn)并作為種子,這些種子節(jié)點(diǎn)的度未必是網(wǎng)絡(luò)中最大的,但它們很好的分布在各個(gè)社區(qū)中,通過擴(kuò)張這些局部最大度節(jié)點(diǎn)發(fā)現(xiàn)的自然社區(qū)不僅局部性良好,而且社區(qū)發(fā)現(xiàn)結(jié)果覆蓋率高.

2.2 局部擴(kuò)張發(fā)現(xiàn)自然社區(qū)

對(duì)于種子集合S中的每個(gè)種子,本文通過迭代添加其鄰居節(jié)點(diǎn)到社區(qū)來發(fā)現(xiàn)自然社區(qū).用于擴(kuò)張社區(qū)的方法有很多,包括R方法[16],適應(yīng)度函數(shù)方法[9,10]和標(biāo)簽傳播[7]等.Lancichiinetti等人[9]定義的適應(yīng)度函數(shù)方法在合成數(shù)據(jù)和真實(shí)數(shù)據(jù)集上都提供了良好的結(jié)果,所以本文采用適應(yīng)度函數(shù)方法.

定義3.對(duì)于網(wǎng)絡(luò)G=(V,E)中的某個(gè)社區(qū)C,其適應(yīng)度f(C)定義為:

(2)

定義4.節(jié)點(diǎn)v的適應(yīng)度f(v)可由公式(3)得到,具體表示為:

(3)

在第一部分找到種子集合后,對(duì)種子進(jìn)行基于適應(yīng)度函數(shù)的貪心策略擴(kuò)張,即通過對(duì)包含種子的臨時(shí)社區(qū)添加或者刪除節(jié)點(diǎn)達(dá)到社區(qū)適應(yīng)度函數(shù)的最大值.具體算法如算法2所示.將種子加入臨時(shí)社區(qū)C,首先計(jì)算其所有鄰居節(jié)點(diǎn)的適應(yīng)度,得到適應(yīng)度最大的鄰居節(jié)點(diǎn)vmax,把它加入到臨時(shí)社區(qū)C中,如算法2第2-10行所示;然后清洗社區(qū)中具有負(fù)適應(yīng)度的節(jié)點(diǎn),將其從社區(qū)中移除,如算法2第12-14行所示,雖然每次循環(huán)都會(huì)加入最大適應(yīng)度的鄰居節(jié)點(diǎn),但新節(jié)點(diǎn)的加入會(huì)改變整個(gè)社區(qū)的結(jié)構(gòu),此時(shí)每個(gè)節(jié)點(diǎn)對(duì)新臨時(shí)社區(qū)的適應(yīng)度將會(huì)更新,因此清洗社區(qū)就變得有意義;繼續(xù)迭代擴(kuò)張臨時(shí)社區(qū),直到添加任何節(jié)點(diǎn)進(jìn)去都會(huì)降低適應(yīng)度,由此得到最終社區(qū),將其放入社區(qū)集合中,然后繼續(xù)迭代擴(kuò)張下一個(gè)種子,直到所有種子都被擴(kuò)張.

從算法中可以看出,在擴(kuò)張的每次迭代中,更新后的社區(qū)都需要重新計(jì)算社區(qū)內(nèi)節(jié)點(diǎn)及其鄰居節(jié)點(diǎn)的適應(yīng)度,這大大增加了計(jì)算復(fù)雜度,所以本文對(duì)算法2進(jìn)行了優(yōu)化.

(4)

(5)

如果vi和vj之間有邊,則dij為1,否則為0.

2.3 時(shí)間復(fù)雜度分析

假設(shè)網(wǎng)絡(luò)G=(V,E)包含n個(gè)節(jié)點(diǎn)m條邊,算法1根據(jù)節(jié)點(diǎn)的點(diǎn)度中心性尋找種子,最壞的情況下找到n個(gè)種子,時(shí)間復(fù)雜度為O(n);假設(shè)算法1找到k個(gè)種子,算法2依次擴(kuò)張每個(gè)種子,任意一個(gè)種子進(jìn)行社區(qū)擴(kuò)張時(shí),假設(shè)有s個(gè)節(jié)點(diǎn)加入該社區(qū),每一個(gè)節(jié)點(diǎn)加入社區(qū)后都要清洗社區(qū),所以算法2的時(shí)間復(fù)雜度為O(ks2),s表示平均社區(qū)節(jié)點(diǎn)規(guī)模,最壞的情況s等于n,此時(shí)所有的節(jié)點(diǎn)在一個(gè)社區(qū)內(nèi),k等于1,時(shí)間復(fù)雜度為O(n2);所以最壞的情況下SGE算法的時(shí)間復(fù)雜度為O(n2).

3 實(shí) 驗(yàn)

本文選取了人工模擬網(wǎng)絡(luò)數(shù)據(jù)集和真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集進(jìn)行了實(shí)驗(yàn),對(duì)比了當(dāng)前有代表性的重疊社區(qū)發(fā)現(xiàn)算法,用于發(fā)現(xiàn)重疊社區(qū)的分裂方法CONGA、基于標(biāo)簽傳播的方法COPRA、基于局部社區(qū)優(yōu)化和擴(kuò)張的方法LFM算法,驗(yàn)證SGE算法的性能有所提升.

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

3.1.1 人工模擬網(wǎng)絡(luò)數(shù)據(jù)集

表1 LFR基準(zhǔn)網(wǎng)絡(luò)參數(shù)說明
Table 1 Parameter description of LFR reference network

參數(shù)說明取值NkkmaxCminCmaxOnOmμτ1τ2網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)目網(wǎng)絡(luò)的平均節(jié)點(diǎn)度網(wǎng)絡(luò)的最大節(jié)點(diǎn)度最小社區(qū)節(jié)點(diǎn)數(shù)目最大社區(qū)節(jié)點(diǎn)數(shù)目網(wǎng)絡(luò)中重疊節(jié)點(diǎn)數(shù)目重疊節(jié)點(diǎn)所屬社區(qū)數(shù)目混合參數(shù)度序列的負(fù)指數(shù)社區(qū)規(guī)模分布的負(fù)指數(shù){1000,5000}155020500.1N[2,8]{0.1,0.3}-2-1

本文采用由Lancichinetti等人[17]提出的LFR模型,LFR基準(zhǔn)測試網(wǎng)絡(luò)通過調(diào)節(jié)參數(shù)來控制生成網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu),性質(zhì)接近真實(shí)網(wǎng)絡(luò),并且在生成網(wǎng)絡(luò)時(shí)生成社區(qū),以便將算法的社區(qū)發(fā)現(xiàn)結(jié)果同生成的社區(qū)進(jìn)行對(duì)比,驗(yàn)證算法的準(zhǔn)確性和性能.LFR模型中參數(shù)設(shè)置如表1所示,其中混合參數(shù)μ取值范圍為(0,1],是網(wǎng)絡(luò)中社區(qū)內(nèi)部節(jié)點(diǎn)與外部節(jié)點(diǎn)連接的概率,μ越大,表示社區(qū)結(jié)構(gòu)越不明顯.實(shí)驗(yàn)根據(jù)N∈{1000,5000},μ∈{0.1,0.3},Om∈[2,8]生成28個(gè)LFR基準(zhǔn)測試網(wǎng)絡(luò).

3.1.2 真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集

本文選取了5個(gè)不同類型、不同規(guī)模的真實(shí)網(wǎng)絡(luò),網(wǎng)絡(luò)說明如表2所示.

表2 真實(shí)網(wǎng)絡(luò)說明
Table 2 Description of real network

數(shù)據(jù)集節(jié)點(diǎn)數(shù)邊數(shù)說明KarateDolphinFootballEmailPower3462115113349417815961654516594空手道俱樂部網(wǎng)絡(luò)海豚社會(huì)網(wǎng)絡(luò)美國大學(xué)生足球網(wǎng)絡(luò)電子郵件網(wǎng)絡(luò)美國電網(wǎng)

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

3.2.1 人工模擬網(wǎng)絡(luò)數(shù)據(jù)集評(píng)價(jià)指標(biāo)

對(duì)于人工模擬網(wǎng)絡(luò),社區(qū)結(jié)構(gòu)是已知的,通常采用規(guī)范互信息指標(biāo)NMI(normal mutual information)[18]來比較社區(qū)發(fā)現(xiàn)結(jié)果與真實(shí)網(wǎng)絡(luò)社區(qū)劃分結(jié)果的相似度,其計(jì)算方式如公式(6)所示:

(6)

其中,N是網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)目,CA是標(biāo)準(zhǔn)社區(qū)劃分結(jié)果,CB是算法社區(qū)劃分結(jié)果,C是混合矩陣,行對(duì)應(yīng)A的社區(qū)發(fā)現(xiàn)結(jié)果,列對(duì)應(yīng)B的社區(qū)發(fā)現(xiàn)結(jié)果,Cij表示節(jié)點(diǎn)既屬于A劃分的第i個(gè)社區(qū)又屬于B劃分的第j個(gè)社區(qū),Ci·和C·j分別是矩陣C第i行和第j列的和.

3.2.2 真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集評(píng)價(jià)指標(biāo)

對(duì)于真實(shí)網(wǎng)絡(luò),由于實(shí)際社區(qū)結(jié)構(gòu)未知,通常采用模塊度函數(shù)Qov(overlapping modularity)[19]來作為評(píng)價(jià)指標(biāo),如公式(7)所示:

(7)

NMI和Qov的取值范圍均為[0,1],值越大,說明社區(qū)發(fā)現(xiàn)結(jié)果越好.

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

SGE有一個(gè)參數(shù)α,取值為0.9到1.5,步長為0.1.其他算法的參數(shù)設(shè)置如下:CONGA的參數(shù)是社區(qū)的數(shù)量c,需要根據(jù)模塊度函數(shù)值確定;COPRA的參數(shù)為標(biāo)簽長度v,取值為2到8,步長為1;LFM的參數(shù)為α,取值為0.9到1.5,步長為0.1.分別選取各參數(shù)下最大的NMI值和Qov值作為最終結(jié)果.

3.3.1 人工模擬網(wǎng)絡(luò)數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

本文在生成的28個(gè)LFR基準(zhǔn)測試網(wǎng)絡(luò)上進(jìn)行實(shí)驗(yàn),選取各參數(shù)下NMI值最大的情況作為最終結(jié)果,實(shí)驗(yàn)結(jié)果如圖1所示,縱坐標(biāo)是NMI值,橫坐標(biāo)是重疊節(jié)點(diǎn)所屬社區(qū)的數(shù)目Om值.

從圖1可以發(fā)現(xiàn),隨著重疊節(jié)點(diǎn)所屬社區(qū)數(shù)量Om的增加,發(fā)現(xiàn)社區(qū)結(jié)構(gòu)變得越來越困難,4種算法的NMI值都呈現(xiàn)下降趨勢,但是SGE算法下降的幅度小于其他算法.從圖中還可以發(fā)現(xiàn),SGE算法和LFM算法的社區(qū)發(fā)現(xiàn)結(jié)果優(yōu)于COPRA算法和CONGA算法,這是因?yàn)榛诰植可鐓^(qū)優(yōu)化和擴(kuò)張的方法發(fā)現(xiàn)自然社區(qū)過程僅與網(wǎng)絡(luò)局部拓?fù)浣Y(jié)構(gòu)有關(guān),與整個(gè)網(wǎng)絡(luò)的全局拓?fù)浣Y(jié)構(gòu)無關(guān),具有一定的優(yōu)勢.對(duì)比SGE算法和LFM算法可以發(fā)現(xiàn),LFM算法與SGE算法的結(jié)果相差不多,并且有時(shí)高于SGE算法,這是因?yàn)長FM算法是隨機(jī)選擇種子然后擴(kuò)張社區(qū),所以它的結(jié)果也是不穩(wěn)定的,通常在實(shí)際的網(wǎng)絡(luò)中,短時(shí)間內(nèi)社區(qū)的結(jié)構(gòu)是穩(wěn)定的,比如人際關(guān)系網(wǎng)絡(luò)中,在一段時(shí)間內(nèi)某個(gè)朋友圈的結(jié)構(gòu)是穩(wěn)定的,在這一點(diǎn)上SGE算法要優(yōu)于LFM算法.雖然LFM算法有時(shí)會(huì)優(yōu)于SGE算法,但SGE算法是穩(wěn)定的,所以更適合網(wǎng)絡(luò)的研究與應(yīng)用.

圖1 人工模擬網(wǎng)絡(luò)對(duì)比實(shí)驗(yàn)結(jié)果Fig.1 Comparison experiment results of artificial simulation network

綜上所述,SGE算法相對(duì)于CONGA算法、COPRA算法和LFM算法能夠在人工模擬網(wǎng)絡(luò)上得到穩(wěn)定且較高質(zhì)量的社區(qū)發(fā)現(xiàn)結(jié)果.

3.3.2 真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

在5個(gè)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn),分別選取各參數(shù)下最大的Qov值作為最終結(jié)果,實(shí)驗(yàn)結(jié)果如表3所示.

表3 真實(shí)網(wǎng)絡(luò)對(duì)比實(shí)驗(yàn)結(jié)果
Table 3 Comparison experiment results of real network

算法CONGACOPRALFMSGEKarateDolphinFootballEmailPower0.4140.5010.4730.2250.4590.4220.6110.5420.4590.5460.6610.6360.5980.4620.5550.6420.6870.6100.4840.596

從表3中可以看出,SGE算法在大部分?jǐn)?shù)據(jù)集上得到的Qov值都是最好的,其次是LFM算法、COPRA算法、CONGA算法,這與4種算法在模擬數(shù)據(jù)集上的表現(xiàn)基本一致.雖然5個(gè)真實(shí)網(wǎng)絡(luò)大小不同、稀疏程度不同,但是SGE算法都能夠得到質(zhì)量較高的重疊社區(qū)結(jié)構(gòu),表現(xiàn)出一定的優(yōu)勢.例如在Dolphin數(shù)據(jù)集上,SGE算法Qov值取得了0.678,而其他三種算法均不能達(dá)到該性能.

4 總 結(jié)

本文提出了一種種子節(jié)點(diǎn)貪婪擴(kuò)張的重疊社區(qū)發(fā)現(xiàn)方法SGE,該方法分為兩個(gè)部分,第一部分根據(jù)網(wǎng)絡(luò)的局部連接信息尋找網(wǎng)絡(luò)中的局部最大度節(jié)點(diǎn)作為種子,第二部分基于適應(yīng)度函數(shù)貪婪擴(kuò)張每一個(gè)種子,并在每次加入一個(gè)新節(jié)點(diǎn)到社區(qū)中時(shí)清洗社區(qū).本文選取了人工模擬網(wǎng)絡(luò)數(shù)據(jù)集和真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集,并在這些數(shù)據(jù)集上與CONGA算法、COPRA算法、LFM算法等具有代表性的重疊社區(qū)發(fā)現(xiàn)方法進(jìn)行對(duì)比性實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果驗(yàn)證SGE算法的性能有所提升.