基于三級(jí)鄰居影響力分析的重疊社區(qū)發(fā)現(xiàn)算法

林 穗，陳仕雙，姜文超,+，熊 夢，賀忠堂

(1.廣東工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，廣東 廣州 510006； 2.東莞中國科學(xué)院云計(jì)算產(chǎn)業(yè)技術(shù)創(chuàng)新與育成中心 技術(shù)預(yù)研部，廣東 東莞 523808)

0 引 言

復(fù)雜網(wǎng)絡(luò)[1,2]是對(duì)現(xiàn)實(shí)世界各類實(shí)體及其彼此之間關(guān)聯(lián)的抽象?，F(xiàn)實(shí)世界中復(fù)雜關(guān)聯(lián)實(shí)體構(gòu)成的社區(qū)實(shí)體之間往往存在著重疊和交集，由許多個(gè)社區(qū)網(wǎng)絡(luò)構(gòu)成一個(gè)復(fù)雜網(wǎng)絡(luò)。

重疊社區(qū)發(fā)現(xiàn)有多種方法，例如基于派系過濾CPM[3,4]的重疊社區(qū)發(fā)現(xiàn)算法，該算法將社區(qū)看作整個(gè)復(fù)雜網(wǎng)絡(luò)中的一個(gè)全連通子圖；Lancichinetti等[5]提出了基于拓展函數(shù)和局部優(yōu)化的重疊社區(qū)發(fā)現(xiàn)算法LFM，該算法給每個(gè)節(jié)點(diǎn)設(shè)定一個(gè)F值列表，并每次迭代刪除F值小于0的節(jié)點(diǎn)；王斌等[6]提出基于邊圖的重疊社區(qū)發(fā)現(xiàn)算法，該算法根據(jù)計(jì)算各邊的相似度實(shí)現(xiàn)社區(qū)劃分和發(fā)現(xiàn)重疊社區(qū)?；跇?biāo)簽傳播的社區(qū)發(fā)現(xiàn)算法有Gregory等[7]提出的COPRA，該算法分配給每個(gè)節(jié)點(diǎn)一個(gè)初始標(biāo)簽，不斷通過標(biāo)簽傳播迭代直至節(jié)點(diǎn)標(biāo)簽穩(wěn)定；Xie等[8]提出SLPA算法，該算法為每個(gè)節(jié)點(diǎn)每次迭代增加一個(gè)標(biāo)簽，再通過閾值r進(jìn)行篩選標(biāo)簽；Lu等[9]提出LPANNI算法，該算法在標(biāo)簽傳播基礎(chǔ)上根據(jù)鄰居節(jié)點(diǎn)影響力計(jì)算新的標(biāo)簽隸屬度。

然而，目前重疊社區(qū)發(fā)現(xiàn)算法仍然存在準(zhǔn)確度不高和效率低下等問題，例如CPM算法的時(shí)間復(fù)雜度較高；COPRA算法劃分的社區(qū)質(zhì)量不高且不穩(wěn)定；SLPA算法的空間復(fù)雜度較高。針對(duì)以上問題，本文提出一種基于三級(jí)鄰居節(jié)點(diǎn)影響力度量TIM[10]的重疊社區(qū)發(fā)現(xiàn)算法OCDITN(overlapping community discovery algorithm based on three-level neighbor node influence analysis)，并分別使用基于人工模擬生成的大規(guī)模網(wǎng)絡(luò)圖數(shù)據(jù)集和來自真實(shí)世界的網(wǎng)絡(luò)數(shù)據(jù)集對(duì)OCDITN算法進(jìn)行測試，與SLPA、LPANNI、COPRA算法相比，OCDITN算法劃分的社區(qū)更穩(wěn)定，質(zhì)量更好，效率也更高。

1 OCDITN算法

1.1 基于三級(jí)鄰居的影響力度量

初始一個(gè)社區(qū)網(wǎng)絡(luò)G=(V,E,Pu,v)，V和E分別代表社區(qū)網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)據(jù)集與邊的數(shù)據(jù)集，Pu,v表示節(jié)點(diǎn)u對(duì)節(jié)點(diǎn)v的激活概率；M23表示在社區(qū)網(wǎng)絡(luò)中將一個(gè)節(jié)點(diǎn)的傳播影響力逐漸變小的2級(jí)、3級(jí)鄰居節(jié)點(diǎn)視為一個(gè)集合，當(dāng)節(jié)點(diǎn)的2級(jí)鄰居處于激活狀態(tài)，則M23中的3級(jí)鄰居的就可能被激活為激活狀態(tài)，此時(shí)M23被激活的概率如式(1)所示

(1)

對(duì)于隨意節(jié)點(diǎn)u，其1級(jí)鄰居節(jié)點(diǎn)數(shù)量與M23整體鄰居節(jié)點(diǎn)數(shù)量相比，很多情況下M23一個(gè)整體的節(jié)點(diǎn)數(shù)量可能是1級(jí)鄰居節(jié)點(diǎn)數(shù)量的若干倍。如圖1所示，對(duì)于節(jié)點(diǎn)u而言，1級(jí)、2級(jí)、3級(jí)鄰居節(jié)點(diǎn)，分別標(biāo)記為V、W、X，其中M23代表著標(biāo)記為W，X的節(jié)點(diǎn)為一個(gè)整體，并且可從圖1看出，M23的節(jié)點(diǎn)數(shù)量與標(biāo)記為V的節(jié)點(diǎn)數(shù)量之間的比值是3。

圖1 節(jié)點(diǎn)u的鄰居節(jié)點(diǎn)示例

由圖1可以看出，節(jié)點(diǎn)u對(duì)2級(jí)、3級(jí)鄰居節(jié)點(diǎn)的影響顯然大于其對(duì)1級(jí)鄰居的影響，這與節(jié)點(diǎn)隨著傳播層級(jí)的深入，其影響逐級(jí)衰減的特性相矛盾，因此需要通過加強(qiáng)1級(jí)鄰居節(jié)點(diǎn)的傳播影響力，來調(diào)整節(jié)點(diǎn)u對(duì)M23整體影響力與1級(jí)鄰居節(jié)點(diǎn)影響力之間的比重。根據(jù)指數(shù)函數(shù)y=ex具有當(dāng)x大于0，則y大于1的特性來加強(qiáng)1級(jí)鄰居節(jié)點(diǎn)的傳播影響力，引入?yún)?shù)θ調(diào)整影響差距，得到TIM節(jié)點(diǎn)影響力度量計(jì)算公式如式(2)所示

(2)

其中，Pu,v表示節(jié)點(diǎn)u對(duì)v的激活概率，參數(shù)θ可調(diào)整影響差距，本文實(shí)驗(yàn)參數(shù)θ取值為1000， |M23| 表示節(jié)點(diǎn)u的2級(jí)、3級(jí)鄰居節(jié)點(diǎn)數(shù)量。

1.2 OCDITN算法標(biāo)簽更新

COPRA算法是Gregory等提出的一種基于標(biāo)簽傳播的重疊社區(qū)發(fā)現(xiàn)算法，該算法主要步驟是：首先初始化每個(gè)節(jié)點(diǎn)的初始ID；然后節(jié)點(diǎn)再根據(jù)鄰居所在社區(qū)的分布來決定自己的社區(qū)，這個(gè)過程稱為節(jié)點(diǎn)的社區(qū)隸屬劃分過程，可用節(jié)點(diǎn)隸屬度來表示；最后依據(jù)社區(qū)內(nèi)部的節(jié)點(diǎn)數(shù)目或者標(biāo)簽數(shù)量經(jīng)過兩次迭代是否保持不變，來決定是否停止執(zhí)行。節(jié)點(diǎn)隸屬度計(jì)算方式如式(3)所示

(3)

其中，N(u) 代表節(jié)點(diǎn)u的鄰居節(jié)點(diǎn)集；bt(c,u) 為迭代次數(shù)t次時(shí)的節(jié)點(diǎn)u對(duì)于社區(qū)c的隸屬度。

在COPRA基礎(chǔ)上，OCDITN算法在節(jié)點(diǎn)標(biāo)簽更新階段重新優(yōu)化并定義了節(jié)點(diǎn)與其鄰居的相似度計(jì)算模型如式(4)所示

(4)

其中，T(u) 表示為數(shù)組中節(jié)點(diǎn)u的TIM值，代表節(jié)點(diǎn)u的影響力；節(jié)點(diǎn)u與鄰居節(jié)點(diǎn)v之間共同節(jié)點(diǎn)的數(shù)量，記為NS(u,s)； 節(jié)點(diǎn)u的度，記為k(u)。 當(dāng)Ov(u) 值越小時(shí)，則表示節(jié)點(diǎn)u與鄰居節(jié)點(diǎn)v之間的關(guān)聯(lián)越微弱，鄰居節(jié)點(diǎn)對(duì)節(jié)點(diǎn)的影響越小。在選擇節(jié)點(diǎn)更新標(biāo)簽時(shí)按節(jié)點(diǎn)影響力進(jìn)行降序排序，將此序列記為SQ作為更新節(jié)點(diǎn)標(biāo)簽的序列，并依次更新節(jié)點(diǎn)，從而解決COPRA算法隨機(jī)選擇節(jié)點(diǎn)更新標(biāo)簽所帶來的社區(qū)低質(zhì)量性和不穩(wěn)定性。參考COPRA算法中的節(jié)點(diǎn)隸屬度bt(c,u)， 實(shí)現(xiàn)重疊社區(qū)的發(fā)現(xiàn)。在選擇節(jié)點(diǎn)更新之后的標(biāo)簽更新過程中，鄰居節(jié)點(diǎn)傳播給節(jié)點(diǎn)u的主標(biāo)簽序列，用LSN表示，如式(5)所示

LSN={ls(c1,b1),ls(c2,b2),…,ls(cv,bv)}

(5)

其中，鄰居節(jié)點(diǎn)v的主標(biāo)簽，記為ls(cv,bv)； 節(jié)點(diǎn)v從屬社區(qū)cv的隸屬度，記為bv；其中節(jié)點(diǎn)v屬于由節(jié)點(diǎn)u的鄰居節(jié)點(diǎn)所構(gòu)成的序列之中。

借鑒LPANNI算法中計(jì)算標(biāo)簽隸屬度的方法，計(jì)算更新節(jié)點(diǎn)標(biāo)簽的隸屬度模型如式(6)所示

(6)

通過式(6)計(jì)算得到節(jié)點(diǎn)新的標(biāo)簽隸屬度序列，記為LS′N， 刪除LS′N序列中標(biāo)簽隸屬度小于閾值p的標(biāo)簽，其中p=1/LN，LN(label number)表示節(jié)點(diǎn)u的標(biāo)簽集合的大小，從而重新得到標(biāo)簽序列LS″N。

采用LPANNI算法中標(biāo)簽序列歸一化模型如式(7)所示，整理過后的節(jié)點(diǎn)標(biāo)簽序列LS″N， 再次得到新的標(biāo)簽序列LSN

(7)

在經(jīng)過標(biāo)簽歸一化模型處理后的節(jié)點(diǎn)標(biāo)簽序列LSu中，節(jié)點(diǎn)u選擇最大標(biāo)簽隸屬度的標(biāo)簽作為主標(biāo)簽。

1.3 OCDITN算法

OCDITN算法首先初始化每個(gè)節(jié)點(diǎn)標(biāo)簽為自身ID，并基于3級(jí)鄰居計(jì)算每個(gè)節(jié)點(diǎn)影響力TIM值，根據(jù)節(jié)點(diǎn)影響力按降序進(jìn)行排序，進(jìn)而確定更新節(jié)點(diǎn)標(biāo)簽的順序；其次，標(biāo)簽更新策略中利用節(jié)點(diǎn)與其鄰居之間的相似度確定鄰居節(jié)點(diǎn)標(biāo)簽序列LSN；最后，通過計(jì)算節(jié)點(diǎn)標(biāo)簽的隸屬度來實(shí)現(xiàn)重疊社區(qū)的鑒別與發(fā)現(xiàn)，算法流程具體如下。

輸入：無向無權(quán)網(wǎng)絡(luò)G=(V,E,Pu,v)， 計(jì)算節(jié)點(diǎn)TIM值時(shí)的參數(shù)θ設(shè)為1000，Pu,v值設(shè)為0.5，標(biāo)簽傳播過程的最大迭代次數(shù)T。

輸出：節(jié)點(diǎn)u的標(biāo)簽集合LSu。

(1)初始化每個(gè)節(jié)點(diǎn)的標(biāo)簽ID為自身編號(hào)，標(biāo)簽的隸屬度為1；

(2)通過式(2)計(jì)算每個(gè)節(jié)點(diǎn)影響力TIM值；并且依據(jù)TIM值降序?qū)λ械墓?jié)點(diǎn)進(jìn)行排序，得到節(jié)點(diǎn)更新序列SQ；

(3)通過式(4)計(jì)算每個(gè)節(jié)點(diǎn)與其鄰居節(jié)點(diǎn)之間的相似度；

當(dāng)?shù)螖?shù)t小于最大迭代次數(shù)T時(shí)，節(jié)點(diǎn)更新序列SQ中各節(jié)點(diǎn)的標(biāo)簽更新不斷循環(huán)第(4)步到第(8)步，直到達(dá)到最大迭代次數(shù)T終止；

(4)通過式(3)計(jì)算每個(gè)鄰居節(jié)點(diǎn)的節(jié)點(diǎn)隸屬度，并將其所有的主標(biāo)簽bt(c,u) 傳播給節(jié)點(diǎn)u，從而得到節(jié)點(diǎn)u標(biāo)簽集合LSN；

(5)通過式(6)重新計(jì)算節(jié)點(diǎn)的標(biāo)簽隸屬度，重新得到節(jié)點(diǎn)標(biāo)簽集合LS′N；

(6)通過丟棄LS′N集合中標(biāo)簽隸屬度小于閾值p的標(biāo)簽，重新得到標(biāo)簽集合LS″N；

(7)通過式(7)進(jìn)行節(jié)點(diǎn)歸一化得到新的節(jié)點(diǎn)標(biāo)簽集合LSu；

(8)在標(biāo)簽集合LSu中選擇最大隸屬度的標(biāo)簽作為節(jié)點(diǎn)u的最終主標(biāo)簽；

(9)輸出標(biāo)簽集合LSu，其中含有多個(gè)標(biāo)簽的節(jié)點(diǎn)為重疊節(jié)點(diǎn)，重疊節(jié)點(diǎn)構(gòu)成重疊社區(qū)。

2 實(shí)驗(yàn)分析

為驗(yàn)證OCDITN算法的有效性，本文基于人工模擬生成網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)兩類數(shù)據(jù)集進(jìn)行算法測試。對(duì)于人工合成網(wǎng)絡(luò)，采用標(biāo)準(zhǔn)化互信息NMI[11]指標(biāo)來衡量發(fā)現(xiàn)重疊社區(qū)與真實(shí)網(wǎng)絡(luò)的重疊社區(qū)之間的相似度，NMI指標(biāo)定義如式(8)所示

(8)

其中，在真實(shí)復(fù)雜網(wǎng)絡(luò)中，社區(qū)網(wǎng)絡(luò)結(jié)構(gòu)的集合，記為X；用于實(shí)驗(yàn)測試來發(fā)現(xiàn)重疊社區(qū)的人工合成網(wǎng)絡(luò)集合，記為Y；H(X|Y) 為社區(qū)X在社區(qū)Y上的條件熵，表示社區(qū)X與社區(qū)Y的差異程度。NMI指標(biāo)的取值范圍為[0,1]，NMI指標(biāo)越趨向于0，說明該算法發(fā)現(xiàn)的重疊社區(qū)與真實(shí)網(wǎng)絡(luò)的重疊社區(qū)差異越大。反之，NMI指標(biāo)越趨向于1，說明該算法發(fā)現(xiàn)的重疊社區(qū)與真實(shí)網(wǎng)絡(luò)的重疊社區(qū)差異越小，發(fā)現(xiàn)的重疊社區(qū)質(zhì)量越高。

對(duì)于真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集，因?yàn)槠渖鐓^(qū)分布真值是模糊的，可以使用模塊度函數(shù)作為評(píng)價(jià)標(biāo)準(zhǔn)。為了方便測試各算法的實(shí)驗(yàn)效果，分別采用擴(kuò)展模塊度函數(shù)EQ[12]和Nicosia等提出的重疊模塊度指標(biāo)Qov[13]兩種模塊度評(píng)價(jià)函數(shù)作為算法實(shí)驗(yàn)測試評(píng)價(jià)標(biāo)準(zhǔn)。

2.1 真實(shí)數(shù)據(jù)集實(shí)驗(yàn)結(jié)果與分析

真實(shí)社會(huì)網(wǎng)絡(luò)是對(duì)社會(huì)網(wǎng)絡(luò)的真實(shí)結(jié)構(gòu)截取的一部分子集，由于真實(shí)反映了實(shí)際網(wǎng)絡(luò)結(jié)構(gòu)和數(shù)據(jù)特性，因此真實(shí)網(wǎng)絡(luò)數(shù)據(jù)分析結(jié)果對(duì)于網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法有效性具有直接參考意義。本文在幾個(gè)真實(shí)復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)集上對(duì)OCDITN算法進(jìn)行測試并與SLPA、LPANNI、COPRA算法進(jìn)行對(duì)比。實(shí)驗(yàn)數(shù)據(jù)集包括海豚社會(huì)網(wǎng)絡(luò)(dolphin social network)、空手道俱樂部網(wǎng)絡(luò)(Karate network)、美國政治之書網(wǎng)絡(luò)(polbooks network)、博客網(wǎng)絡(luò)(blogs network)、悲慘世界關(guān)系網(wǎng)絡(luò)(lesmis network)、信任網(wǎng)絡(luò)(PGP network)、互聯(lián)網(wǎng)快照網(wǎng)絡(luò)(internet network)，真實(shí)社會(huì)網(wǎng)絡(luò)數(shù)據(jù)集見表1。

表1 真實(shí)社會(huì)網(wǎng)絡(luò)數(shù)據(jù)集

表2和表3分別為OCDITN、SLPA、LPANNI和COPRA算法在各個(gè)數(shù)據(jù)集上測試的EQ值和Qov值。由表2可知，在對(duì)Dolphins、Karate、Polbooks、Blogs、Lesmis、PGP、Internet這7種網(wǎng)絡(luò)數(shù)據(jù)集測試中，OCDITN算法的EQ值均高于SLPA、LPANNI、COPRA算法，說明具有較好的重疊社區(qū)劃分效果。

表2 各算法計(jì)算EQ值實(shí)驗(yàn)結(jié)果

由表3可知，OCDITN算法對(duì)Karate、Blogs、PGP這3種網(wǎng)絡(luò)數(shù)據(jù)的Qov值僅略低于COPRA算法外，其余數(shù)據(jù)集Qov值都優(yōu)于SLPA、LPANNI、COPRA算法。OCDITN算法對(duì)Lesmis網(wǎng)絡(luò)的EQ值最高，劃分效果最好，對(duì)Karate網(wǎng)絡(luò)數(shù)據(jù)的Qov值最低，劃分效果最差。

2.2 模擬數(shù)據(jù)集實(shí)驗(yàn)結(jié)果與分析

LFR基準(zhǔn)網(wǎng)絡(luò)[14]是目前復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法研究中經(jīng)典高效的人工模擬網(wǎng)絡(luò)數(shù)據(jù)集，常用于發(fā)現(xiàn)重疊社區(qū)實(shí)驗(yàn)測試，擁有真實(shí)世界網(wǎng)絡(luò)的重要屬性。LFR基準(zhǔn)網(wǎng)絡(luò)主要包括以下參數(shù)：社區(qū)結(jié)構(gòu)內(nèi)部節(jié)點(diǎn)的數(shù)量，記為N；社區(qū)結(jié)構(gòu)內(nèi)部節(jié)點(diǎn)的平均度數(shù)，記為K；社區(qū)結(jié)構(gòu)內(nèi)部節(jié)點(diǎn)中的最大度數(shù)，記為maxk；最小社區(qū)結(jié)構(gòu)中所包含節(jié)點(diǎn)的數(shù)目，記為minc；最大社區(qū)結(jié)構(gòu)所包含節(jié)點(diǎn)的數(shù)目，記為maxc；社區(qū)結(jié)構(gòu)之間所重疊節(jié)點(diǎn)的數(shù)目，記為on；重疊節(jié)點(diǎn)所隸屬社區(qū)的數(shù)目，記為om；社區(qū)結(jié)構(gòu)之間的混合程度，記為mu，表示著社區(qū)結(jié)構(gòu)內(nèi)部節(jié)點(diǎn)數(shù)目與社區(qū)結(jié)構(gòu)外部節(jié)點(diǎn)所連接的比值，mu值越大社區(qū)之間的混合程度越高，社區(qū)結(jié)構(gòu)劃分越模糊，LFR 基準(zhǔn)網(wǎng)絡(luò)參數(shù)見表4。

表3 各算法計(jì)算Qov值的實(shí)驗(yàn)結(jié)果

表4 4種不同的LFR 基準(zhǔn)網(wǎng)絡(luò)參數(shù)

OCDITN、SLPA、LPANNI和COPRA算法在4組LFR網(wǎng)絡(luò)數(shù)據(jù)中的實(shí)驗(yàn)結(jié)果如圖2～圖5所示。其中橫坐標(biāo)為混雜系數(shù)mu，縱坐標(biāo)為社區(qū)發(fā)現(xiàn)質(zhì)量NMI。由圖2～圖5可知，隨著混雜系數(shù)的增大，OCDITN、SLPA、LPANNI和COPRA算法的NMI值降低，社區(qū)發(fā)現(xiàn)的質(zhì)量也降低。

圖2 N1網(wǎng)絡(luò)的NMI值

如圖2所示，N1網(wǎng)絡(luò)的NMI值除了在mu=0.4時(shí)LPANNI算法的NMI值比OCDITN算法大以外，其余mu值參數(shù)下OCDITN算法的NMI值最大，說明OCDITN比其它算法更有效。

由N2網(wǎng)絡(luò)測試結(jié)果可知，OCDITN算法比SLPA算法僅僅略好一點(diǎn)，兩個(gè)算法之間效果很接近，如圖3所示。

圖3 N2網(wǎng)絡(luò)的NMI值

如圖4所示，以從N3網(wǎng)絡(luò)的測試結(jié)果可知，OCDITN算法優(yōu)于SLPA、LPANNI、COPRA算法，特別是在mu=0.4時(shí)，OCDITN算法效果優(yōu)于SLPA、LPANNI、COPRA算法。

圖4 N3網(wǎng)絡(luò)的NMI值

從N4網(wǎng)絡(luò)測試結(jié)果可以看出，4個(gè)算法效果都很接近，OCDITN算法依然略優(yōu)于SLPA、LPANNI、COPRA算法，如圖5所示。

圖5 N4網(wǎng)絡(luò)的NMI值

3 結(jié)束語

本文提出一種基于三級(jí)鄰居節(jié)點(diǎn)影響力的重疊社區(qū)發(fā)現(xiàn)算法OCDITN。該算法結(jié)合最新的節(jié)點(diǎn)影響力度量算法對(duì)節(jié)點(diǎn)重要性進(jìn)行排序。實(shí)驗(yàn)測試分別基于人工網(wǎng)絡(luò)和真實(shí)世界網(wǎng)絡(luò)進(jìn)行測試，結(jié)果表明OCDITN算法能夠有效檢測出重疊社區(qū)，且其重疊社區(qū)發(fā)現(xiàn)質(zhì)量更高。

復(fù)雜網(wǎng)絡(luò)重疊社區(qū)發(fā)現(xiàn)問題相當(dāng)復(fù)雜，尤其是在動(dòng)態(tài)實(shí)時(shí)環(huán)境下，社區(qū)演變會(huì)對(duì)社區(qū)發(fā)現(xiàn)質(zhì)量形成較大影響。針對(duì)復(fù)雜網(wǎng)絡(luò)動(dòng)態(tài)特性，挖掘發(fā)現(xiàn)其本質(zhì)特征，并在動(dòng)態(tài)環(huán)境下實(shí)時(shí)確定社區(qū)及其演變規(guī)律，這將是未來研究的重點(diǎn)。