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

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

1 引 言

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

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

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

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

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

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

2.1 種子選取

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

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

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

Cd(vi)=d(vi)

(1)

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

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

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

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

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

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

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

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

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

(2)

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

(3)

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

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

(4)

(5)

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

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

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

3 實 驗

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

3.1 實驗數(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é)點數(shù)目網(wǎng)絡(luò)的平均節(jié)點度網(wǎng)絡(luò)的最大節(jié)點度最小社區(qū)節(jié)點數(shù)目最大社區(qū)節(jié)點數(shù)目網(wǎng)絡(luò)中重疊節(jié)點數(shù)目重疊節(jié)點所屬社區(qū)數(shù)目混合參數(shù)度序列的負指數(shù)社區(qū)規(guī)模分布的負指數(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ò)的拓撲結(jié)構(gòu),性質(zhì)接近真實網(wǎng)絡(luò),并且在生成網(wǎng)絡(luò)時生成社區(qū),以便將算法的社區(qū)發(fā)現(xiàn)結(jié)果同生成的社區(qū)進行對比,驗證算法的準(zhǔn)確性和性能.LFR模型中參數(shù)設(shè)置如表1所示,其中混合參數(shù)μ取值范圍為(0,1],是網(wǎng)絡(luò)中社區(qū)內(nèi)部節(jié)點與外部節(jié)點連接的概率,μ越大,表示社區(qū)結(jié)構(gòu)越不明顯.實驗根據(jù)N∈{1000,5000},μ∈{0.1,0.3},Om∈[2,8]生成28個LFR基準(zhǔn)測試網(wǎng)絡(luò).

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

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

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

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

3.2 評價指標(biāo)

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

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

(6)

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

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

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

(7)

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

3.3 實驗結(jié)果

SGE有一個參數(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ù)集實驗結(jié)果

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

從圖1可以發(fā)現(xiàn),隨著重疊節(jié)點所屬社區(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算法,這是因為基于局部社區(qū)優(yōu)化和擴張的方法發(fā)現(xiàn)自然社區(qū)過程僅與網(wǎng)絡(luò)局部拓撲結(jié)構(gòu)有關(guān),與整個網(wǎng)絡(luò)的全局拓撲結(jié)構(gòu)無關(guān),具有一定的優(yōu)勢.對比SGE算法和LFM算法可以發(fā)現(xiàn),LFM算法與SGE算法的結(jié)果相差不多,并且有時高于SGE算法,這是因為LFM算法是隨機選擇種子然后擴張社區(qū),所以它的結(jié)果也是不穩(wěn)定的,通常在實際的網(wǎng)絡(luò)中,短時間內(nèi)社區(qū)的結(jié)構(gòu)是穩(wěn)定的,比如人際關(guān)系網(wǎng)絡(luò)中,在一段時間內(nèi)某個朋友圈的結(jié)構(gòu)是穩(wěn)定的,在這一點上SGE算法要優(yōu)于LFM算法.雖然LFM算法有時會優(yōu)于SGE算法,但SGE算法是穩(wěn)定的,所以更適合網(wǎng)絡(luò)的研究與應(yīng)用.

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

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

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

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

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

4 總 結(jié)

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