一種基于節(jié)點(diǎn)穩(wěn)定性的社區(qū)發(fā)現(xiàn)算法

鄭文萍 ,劉美麟 ,穆俊芳 ,楊 貴

（1.山西大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院，太原，030006；2.計(jì)算智能與中文信息處理教育部重點(diǎn)實(shí)驗(yàn)室，山西大學(xué)，太原，030006；3.山西大學(xué)智能信息處理研究所，太原，030006）

現(xiàn)實(shí)世界中的許多復(fù)雜系統(tǒng)都可以抽象成網(wǎng)絡(luò)，如社交網(wǎng)絡(luò)、基因調(diào)控網(wǎng)絡(luò)、交通運(yùn)輸網(wǎng)絡(luò)、電力傳輸網(wǎng)絡(luò)、引文網(wǎng)絡(luò)等［1-4］.社區(qū)結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)的重要特征，即一個(gè)網(wǎng)絡(luò)中節(jié)點(diǎn)形成了若干個(gè)社區(qū)，社區(qū)內(nèi)部節(jié)點(diǎn)連接相對(duì)緊密，社區(qū)間節(jié)點(diǎn)連接相對(duì)稀疏.網(wǎng)絡(luò)中的社區(qū)通常對(duì)應(yīng)復(fù)雜系統(tǒng)中的一些特殊功能模塊，如社交網(wǎng)絡(luò)中具有某種特定關(guān)系的群體、基因調(diào)控網(wǎng)絡(luò)中特定生物功能的蛋白質(zhì)復(fù)合體、互聯(lián)網(wǎng)中具有相同主題的網(wǎng)站集合、引文網(wǎng)絡(luò)中相同興趣的研究群體等.在網(wǎng)絡(luò)上進(jìn)行圖聚類分析，可以挖掘網(wǎng)絡(luò)中的潛在社區(qū)，為分析和理解復(fù)雜系統(tǒng)的拓?fù)浣Y(jié)構(gòu)及動(dòng)力學(xué)特性提供指導(dǎo)［5］.

1 相關(guān)工作

研究者已提出許多社區(qū)檢測(cè)算法，主要分為基于模塊度優(yōu)化的算法、基于譜聚類的算法、基于信息傳播的算法等.也有許多用于評(píng)價(jià)社區(qū)劃分結(jié)果好壞的模塊度指標(biāo)，使用最廣泛的是2004 年Newman and Girvan［6］提出的模塊度.許多基于模塊度優(yōu)化的算法被提出，如BGLL［7］，Leiden［8］等，其基本思想是從對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)所有可能的劃分中尋找使得模塊度最大的社區(qū)劃分，通常可以找到滿足社區(qū)定義的較穩(wěn)定的社區(qū)劃分結(jié)果，但由于計(jì)算代價(jià)較高且受模塊度的精度限制［9］，此類算法通常不適用于大規(guī)模網(wǎng)絡(luò)中的社區(qū)發(fā)現(xiàn)，并且無法探測(cè)規(guī)模較小但結(jié)構(gòu)顯著的社區(qū).基于譜聚類的社區(qū)發(fā)現(xiàn)算法是利用網(wǎng)絡(luò)節(jié)點(diǎn)間的相似性構(gòu)造相似圖，根據(jù)相似矩陣或其拉普拉斯矩陣的前k個(gè)特征向量進(jìn)行節(jié)點(diǎn)表示，并利用傳統(tǒng)聚類方法對(duì)節(jié)點(diǎn)聚類.研究者根據(jù)不同的譜映射方法和準(zhǔn)則函數(shù)設(shè)計(jì)了多種譜聚類社區(qū)發(fā)現(xiàn)算法，以發(fā)現(xiàn)多種規(guī)模尺度的社區(qū)，如FCM（Fuzzy C -Means）［10］，SSCF［11］等.但由于譜聚類算法中需要進(jìn)行矩陣運(yùn)算，因此不適用于規(guī)模較大的復(fù)雜網(wǎng)絡(luò)上的社區(qū)發(fā)現(xiàn).

基于信息傳播的算法通過模擬信息流在網(wǎng)絡(luò)中的傳播過程進(jìn)行社區(qū)發(fā)現(xiàn)，主要有標(biāo)簽傳播算法（Label Propagation Algorithm，LPA）及其改進(jìn)［12-14］、基于信息編碼的算法Infomap［15］、基于隨機(jī)游走的算法Walktrap［16］等.標(biāo)簽傳播算法最早是Raghavan et al［12］于2007 年提出的，其基本思想是將節(jié)點(diǎn)鄰域中出現(xiàn)次數(shù)最多的社區(qū)標(biāo)簽作為該節(jié)點(diǎn)的標(biāo)簽.標(biāo)簽傳播算法具有接近線性的時(shí)間復(fù)雜度，已被廣泛應(yīng)用于大規(guī)模復(fù)雜網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)，但由于受到標(biāo)簽傳播過程中節(jié)點(diǎn)更新順序、節(jié)點(diǎn)標(biāo)簽選擇等多種隨機(jī)因素的影響，社區(qū)發(fā)現(xiàn)結(jié)果表現(xiàn)了較強(qiáng)的不穩(wěn)定性.也就是說，即使在同一個(gè)網(wǎng)絡(luò)上執(zhí)行多次，LPA 算法也可能會(huì)得到差異很大的社區(qū)發(fā)現(xiàn)結(jié)果.Zhao et al［17］根據(jù)節(jié)點(diǎn)鄰域中標(biāo)簽分布的香農(nóng)熵確定節(jié)點(diǎn)更新順序以提高算法結(jié)果的穩(wěn)定性.Li et al［14］提出一種分階段的標(biāo)簽傳播算法LPA-S，選擇最相似鄰居節(jié)點(diǎn)的標(biāo)簽更新當(dāng)前節(jié)點(diǎn)標(biāo)簽進(jìn)行社區(qū)發(fā)現(xiàn).Barber and Clark［18］和Liu and Murata［19］提出的LPAm 算法在標(biāo)簽傳播過程中通過優(yōu)化模塊度來發(fā)現(xiàn)社區(qū).鄭文萍等［20］提出一種改進(jìn)的標(biāo)簽傳播算法LPA-TS，定義節(jié)點(diǎn)的社區(qū)參與系數(shù)以確定節(jié)點(diǎn)更新順序，并依據(jù)節(jié)點(diǎn)間相似性更新節(jié)點(diǎn)標(biāo)簽，得到最終的社區(qū)劃分結(jié)果.這些改進(jìn)的標(biāo)簽傳播算法降低了節(jié)點(diǎn)更新順序和標(biāo)簽選擇過程的隨機(jī)性，在一定程度上提高了算法的穩(wěn)定性.

隨著要處理的網(wǎng)絡(luò)數(shù)據(jù)越來越復(fù)雜，節(jié)點(diǎn)間的關(guān)系也越來越復(fù)雜，算法結(jié)果的不穩(wěn)定性越來越強(qiáng).盡管這樣，多次運(yùn)行LPA 算法得到不同的社區(qū)劃分結(jié)果的同時(shí)，也為確定在社區(qū)形成過程的節(jié)點(diǎn)穩(wěn)定性提供了有效信息.比如一部分具有明確社區(qū)歸屬的節(jié)點(diǎn)通常會(huì)表現(xiàn)穩(wěn)定，而一些社區(qū)間的重疊節(jié)點(diǎn)或社區(qū)內(nèi)的邊緣節(jié)點(diǎn)在社區(qū)發(fā)現(xiàn)過程中表現(xiàn)出較高的不穩(wěn)定性.利用標(biāo)簽傳播算法所提供的節(jié)點(diǎn)穩(wěn)定性信息有望進(jìn)行更有效的社區(qū)發(fā)現(xiàn).

本文根據(jù)社區(qū)劃分結(jié)果定義節(jié)點(diǎn)在該社區(qū)劃分下的標(biāo)簽熵，度量節(jié)點(diǎn)在社區(qū)發(fā)現(xiàn)過程中的穩(wěn)定性，以此為基礎(chǔ)提出一種基于節(jié)點(diǎn)穩(wěn)定性的社區(qū)發(fā)現(xiàn)算法（Node Stability-based Algorithm，NSA）.首先運(yùn)行t次社區(qū)發(fā)現(xiàn)算法得到原網(wǎng)絡(luò)的t個(gè)社區(qū)劃分，計(jì)算各節(jié)點(diǎn)對(duì)應(yīng)社區(qū)劃分的標(biāo)簽熵，從而確定網(wǎng)絡(luò)的穩(wěn)定節(jié)點(diǎn)集S.然后，在原網(wǎng)絡(luò)上抽取包含穩(wěn)定節(jié)點(diǎn)集S的連通子網(wǎng)絡(luò)并在該子網(wǎng)絡(luò)上進(jìn)行初步社區(qū)發(fā)現(xiàn)，得到初始類簇.最后，計(jì)算其他不穩(wěn)定節(jié)點(diǎn)與初始類簇的距離，將尚無社區(qū)歸屬的節(jié)點(diǎn)根據(jù)歸屬度劃分至初始類簇中，得到最終聚類結(jié)果.在四個(gè)帶標(biāo)簽和八個(gè)無標(biāo)簽的網(wǎng)絡(luò)數(shù)據(jù)集上，本文的NSA 算法與五種經(jīng)典社區(qū)發(fā)現(xiàn)算法的比較實(shí)驗(yàn)表明，NSA 算法能得到更穩(wěn)定的社區(qū)劃分結(jié)果，且在NMI和模塊度等方面表現(xiàn)了良好的算法性能.

2 基礎(chǔ)知識(shí)

通常用G=(V，E)表示一個(gè)復(fù)雜網(wǎng)絡(luò)，其中V={v1，v2，…，vn} 表示節(jié)點(diǎn)集，E表示邊集.除非特別聲明，以下僅對(duì)無向簡(jiǎn)單圖進(jìn)行研究.令Nv={u|(u，v)∈E∧u∈V} 表示節(jié)點(diǎn)v在G中的鄰接點(diǎn)集合，稱為v的直接鄰域.記節(jié)點(diǎn)v的度dv=|Nv|.對(duì)圖G的節(jié)點(diǎn)子集S，將圖G中與S中節(jié)點(diǎn)直接相鄰且不在S中的節(jié)點(diǎn)集合稱作S在G中的鄰域，記為

對(duì)圖G'=(V'，E')，若V'?V且E'?E，則稱G' 是G的一個(gè)子圖.對(duì)節(jié)點(diǎn)u，v∈V'，如果(u，v)∈E則(u，v)∈E'，那么稱G'為節(jié)點(diǎn)子集V'的導(dǎo)出子圖，記為G[V' ]，在不引起混淆的情況下簡(jiǎn)記為[V' ].

對(duì)圖G=(V，E)，稱Ω={C1，…，Ck} 為圖G的一種社區(qū)劃分，其中Ci?V，Ci≠?(1≤i≤k)且Ci∩Cj=?(i≠j).映射f：Ω→{1，…，k} 為Ω中的每個(gè)社區(qū)賦予唯一的標(biāo)簽.對(duì)節(jié)點(diǎn)v∈Ci，稱f(Ci)是節(jié)點(diǎn)v在劃分Ω下的社區(qū)標(biāo)簽，記作lΩ(v)=f(Ci).對(duì)節(jié)點(diǎn)子集S?V，稱lΩ(S)={lΩ(v)|v∈S} 為子集S對(duì)劃分Ω的社區(qū)標(biāo)簽集.

在信息論中，Shannon 熵［21］是度量信息不確定性程度的重要方法，若信息源有n個(gè)取值，概率分 別為{p1，p2，…，pn}，則 其 Shannon 熵 為利用Shannon 熵可以度量節(jié)點(diǎn)v鄰域的社區(qū)分布的不確定性，進(jìn)而度量節(jié)點(diǎn)v在社區(qū)劃分過程中的穩(wěn)定性.

3 基于節(jié)點(diǎn)穩(wěn)定性的社區(qū)發(fā)現(xiàn)算法

考慮節(jié)點(diǎn)v的穩(wěn)定性與社區(qū)劃分結(jié)果直接相關(guān)，為了更好地獲取網(wǎng)絡(luò)中的穩(wěn)定節(jié)點(diǎn)集合，可以參考多種社區(qū)劃分結(jié)果確定網(wǎng)絡(luò)的穩(wěn)定節(jié)點(diǎn)集.目前一些社區(qū)發(fā)現(xiàn)算法有近似線性時(shí)間復(fù)雜度，但運(yùn)行結(jié)果表現(xiàn)不穩(wěn)定，也就是說，多次運(yùn)行算法的社區(qū)發(fā)現(xiàn)結(jié)果差異很大.有效利用社區(qū)發(fā)現(xiàn)過程中的節(jié)點(diǎn)社區(qū)歸屬的不確定性對(duì)網(wǎng)絡(luò)中節(jié)點(diǎn)的穩(wěn)定性進(jìn)行度量，有望進(jìn)一步提高社區(qū)發(fā)現(xiàn)質(zhì)量.基于此，提出一種基于節(jié)點(diǎn)穩(wěn)定性的社區(qū)發(fā)現(xiàn)算法，首先根據(jù)快速社區(qū)發(fā)現(xiàn)算法對(duì)網(wǎng)絡(luò)進(jìn)行預(yù)處理得到網(wǎng)絡(luò)中的穩(wěn)定節(jié)點(diǎn)集，對(duì)穩(wěn)定節(jié)點(diǎn)集擴(kuò)展所得的連通子圖進(jìn)行聚類得到初始社區(qū)，根據(jù)未聚類節(jié)點(diǎn)對(duì)初始社區(qū)的歸屬度確定其最終社區(qū)歸屬.

3.1 基于標(biāo)簽熵的節(jié)點(diǎn)穩(wěn)定性度量 可以用某種社區(qū)發(fā)現(xiàn)算法所得到的社區(qū)劃分結(jié)果來衡量網(wǎng)絡(luò)節(jié)點(diǎn)在社區(qū)發(fā)現(xiàn)過程中的穩(wěn)定性.對(duì)圖G中的一個(gè)節(jié)點(diǎn)v，如果其鄰域Nv中節(jié)點(diǎn)的社區(qū)分布比較集中，則v具有相對(duì)穩(wěn)定的社區(qū)歸屬；反過來，如果其鄰域Nv中節(jié)點(diǎn)的社區(qū)分布比較分散，則v在社區(qū)發(fā)現(xiàn)過程中表現(xiàn)不穩(wěn)定.為了利用信息熵對(duì)社區(qū)發(fā)現(xiàn)過程中節(jié)點(diǎn)的穩(wěn)定性進(jìn)行度量，首先根據(jù)其鄰居節(jié)點(diǎn)的社區(qū)歸屬分布定義節(jié)點(diǎn)v在社區(qū)劃分Ω下的標(biāo)簽熵.

定義1 標(biāo)簽熵假設(shè)Ω={C1，…，Ck} 為圖G的一種社區(qū)劃分，標(biāo)簽映射為f：Ω→{1，…，k}，節(jié)點(diǎn)v的鄰域節(jié)點(diǎn)標(biāo)簽集合記作lΩ(Nv)={l1，…，lkv}，其中kv代表v鄰域內(nèi)的標(biāo)簽類別數(shù).令Sv(li)={u|lΩ(u)=li，u∈Nv} 為v鄰域中標(biāo)簽為li的節(jié)點(diǎn)集，sv(li)=|Sv(li)|.定義節(jié)點(diǎn)v在劃分Ω下的標(biāo)簽分布為：

節(jié)點(diǎn)v的標(biāo)簽熵HΩ(v)可以對(duì)v在劃分Ω下社區(qū)歸屬的穩(wěn)定程度進(jìn)行度量，HΩ(v)越小，節(jié)點(diǎn)v在社區(qū)發(fā)現(xiàn)過程中具有較穩(wěn)定的社區(qū)歸屬.圖1給出了Karate［23］網(wǎng)絡(luò)的真實(shí)社區(qū)劃分結(jié)果，包括34 個(gè)節(jié)點(diǎn)，78 條邊，2 個(gè)社區(qū).其中節(jié)點(diǎn)2 的度d2=10，其鄰域中的節(jié)點(diǎn)分散到兩個(gè)社區(qū)C1和C2中，標(biāo)簽分別為l1和l2，即lΩ(N2)={l1，l2} 且s2(l1)=5，s2(l2)=5，則節(jié)點(diǎn)2 在該劃分下的標(biāo)簽分布PΩ(2)={0.5，0.5}，對(duì)應(yīng)的標(biāo)簽熵HΩ(2)=1.而對(duì)節(jié)點(diǎn)23，其鄰居節(jié)點(diǎn)都屬于社區(qū)C2，因此在該劃分下的標(biāo)簽熵HΩ(23)=0.可以看出，節(jié)點(diǎn)2 比節(jié)點(diǎn)23 具有更高的不穩(wěn)定性.

圖1 Karate 網(wǎng)絡(luò)的真實(shí)社區(qū)劃分結(jié)果Fig.1 A community detection result of of Karate network

3.2 確定穩(wěn)定節(jié)點(diǎn)集隨著網(wǎng)絡(luò)數(shù)據(jù)越來越復(fù)雜，不同的社區(qū)發(fā)現(xiàn)算法得到的社區(qū)劃分差異越來越大，即使是同一個(gè)算法多次運(yùn)行也可能得到差異較大的社區(qū)劃分結(jié)果.這些不同的社區(qū)劃分結(jié)果為確定在社區(qū)形成過程的節(jié)點(diǎn)穩(wěn)定性提供了有效信息，通常具有明確社區(qū)歸屬的節(jié)點(diǎn)會(huì)表現(xiàn)穩(wěn)定，而一些社區(qū)間的重疊節(jié)點(diǎn)或社區(qū)內(nèi)的邊緣節(jié)點(diǎn)在社區(qū)發(fā)現(xiàn)過程中表現(xiàn)出較高的不穩(wěn)定性.

一些快速社區(qū)發(fā)現(xiàn)算法如標(biāo)簽傳播算法具有近似線性時(shí)間復(fù)雜度，能在很短的時(shí)間內(nèi)得到網(wǎng)絡(luò)的一種社區(qū)發(fā)現(xiàn)結(jié)果，然而算法的多次運(yùn)行通常會(huì)得到差異較大的一些社區(qū)發(fā)現(xiàn)結(jié)果，這種算法結(jié)果的不穩(wěn)定性影響了其在實(shí)際社區(qū)發(fā)現(xiàn)問題中的應(yīng)用.實(shí)際上，社區(qū)發(fā)現(xiàn)結(jié)果的不穩(wěn)定通常是由一些社區(qū)邊緣節(jié)點(diǎn)對(duì)社區(qū)歸屬度低而引起的，社區(qū)歸屬相對(duì)確定的節(jié)點(diǎn)在算法多次運(yùn)行過程中表現(xiàn)也相對(duì)穩(wěn)定.針對(duì)這一特點(diǎn)，算法NSA首先在網(wǎng)絡(luò)上運(yùn)行t次標(biāo)簽傳播算法得到t種社區(qū)劃分Ω1，…，Ωt，計(jì)算每個(gè)節(jié)點(diǎn)v在不同劃分下的標(biāo)簽熵HΩi(v)，則網(wǎng)絡(luò)穩(wěn)定節(jié)點(diǎn)集定義為：

其中，ε稱作穩(wěn)定性閾值，不穩(wěn)定節(jié)點(diǎn)集合為V-S.

3.3 穩(wěn)定節(jié)點(diǎn)子圖聚類由于穩(wěn)定節(jié)點(diǎn)的社區(qū)歸屬相對(duì)確定，對(duì)網(wǎng)絡(luò)中穩(wěn)定節(jié)點(diǎn)進(jìn)行聚類可以得到比較確定的初始社區(qū)，對(duì)初始社區(qū)進(jìn)行擴(kuò)展有助于得到更穩(wěn)定的社區(qū)劃分結(jié)果.同時(shí)，由于網(wǎng)絡(luò)中穩(wěn)定節(jié)點(diǎn)所占比例通常較小，在時(shí)間允許的范圍內(nèi)，可以利用基于模塊度優(yōu)化或譜聚類等比較精確的算法對(duì)穩(wěn)定節(jié)點(diǎn)進(jìn)行聚類，得到盡可能準(zhǔn)確的初始社區(qū).

由穩(wěn)定節(jié)點(diǎn)子集S導(dǎo)出的子圖G[S]通常不連通，無法在G[S]上運(yùn)行圖聚類算法得到初始社區(qū)劃分.因此?，需要從原網(wǎng)絡(luò)G中抽取一個(gè)包含穩(wěn)定節(jié)點(diǎn)集S的連通子圖GS，使得S?V(GS)且V(GS)-S中的節(jié)點(diǎn)不穩(wěn)定性盡可能低.

由穩(wěn)定節(jié)點(diǎn)集S所構(gòu)造的連通子圖GS包含原網(wǎng)絡(luò)G中社區(qū)劃分相對(duì)穩(wěn)定的節(jié)點(diǎn)，因此在GS上進(jìn)行社區(qū)發(fā)現(xiàn)，會(huì)得到比較穩(wěn)定的劃分結(jié)果.此外，GS中的節(jié)點(diǎn)在原網(wǎng)絡(luò)G中所占比例比較低，這就允許選擇在較小規(guī)模網(wǎng)絡(luò)上具有較好性能的社區(qū)發(fā)現(xiàn)算法得到初始社區(qū).

本文采用LPA 算法對(duì)GS中節(jié)點(diǎn)進(jìn)行聚類，得到初始社區(qū)為其中k為初始社區(qū)個(gè)數(shù).

3.4 未聚類節(jié)點(diǎn)處理集合V(G-GS)中的節(jié)點(diǎn)還沒有社區(qū)歸屬，需要對(duì)這部分節(jié)點(diǎn)進(jìn)行處理.節(jié)點(diǎn)u∈V(G-GS)對(duì)社區(qū)的歸屬度定義為：

其中，1≤i≤k.sim()u，vj表示節(jié)點(diǎn)u與中節(jié)點(diǎn)vj的相似性；φ是一個(gè)聚合函數(shù)，將節(jié)點(diǎn)u與中各節(jié)點(diǎn)的相似性聚合為u對(duì)初始社區(qū)的歸屬度.本文中，

3.5 NSA 算法算法1 給出了本文所提的基于節(jié)點(diǎn)穩(wěn)定性的社區(qū)發(fā)現(xiàn)算法的框架 .

3.6 實(shí) 例以圖1 的空手道俱樂部網(wǎng)絡(luò)（Zachary's Karate Club）［22］為例解釋算法的具體步驟.

首先，在Karate 網(wǎng)絡(luò)上運(yùn)行三次標(biāo)簽傳播算法，得到三種社區(qū)劃分結(jié)果，分別為Ω1，Ω2，Ω3.計(jì)算Karate 網(wǎng)絡(luò)各節(jié)點(diǎn)在每種社區(qū)劃分結(jié)果上的標(biāo)簽熵，如表1 所示.

表1 Karate 網(wǎng)絡(luò)節(jié)點(diǎn)的標(biāo)簽熵Table 1 The label entropy of nodes on Karate networks

取ε=0，根據(jù)式（3）確定網(wǎng)絡(luò)穩(wěn)定節(jié)點(diǎn)集S={11，16，14，15，18，20，22，23，25，29，24，26} .圖2 給出了利用S所構(gòu)造的連通子圖GS，其中藍(lán)色表示S中的節(jié)點(diǎn)，擴(kuò)展的節(jié)點(diǎn)用綠色表示.可以看出，穩(wěn)定節(jié)點(diǎn)通常分布在一個(gè)大度節(jié)點(diǎn)的周圍，并且節(jié)點(diǎn)度不會(huì)太大.這也符合實(shí)際情況，如在社會(huì)網(wǎng)絡(luò)中，一個(gè)朋友圈較小的成員通常有比較穩(wěn)定的興趣社區(qū).

圖2 Karate 網(wǎng)絡(luò)上得到的穩(wěn)定節(jié)點(diǎn)集S 及包含S 的連通子圖GSFig.2 A set of stable nodes on the Karate network and a connected subgraph GS

圖3 展示了在連通子圖GS上運(yùn)行標(biāo)簽傳播算法所得到的初始社區(qū)劃分；圖4 給出了對(duì)未聚類節(jié)點(diǎn)進(jìn)行處理后所得到的社區(qū)劃分結(jié)果，其中包括三個(gè)社區(qū)，與真實(shí)劃分比較接近.圖3 和圖4中，每種顏色代表一個(gè)初始社區(qū).

圖3 由GS所得的初始社區(qū)劃分Fig.3 Initial communities of GS

圖4 算法NSA 所得的最終社區(qū)劃分結(jié)果Fig.4 Final communities detected by NSA

3.7 時(shí)間復(fù)雜度分析對(duì)一個(gè)包含n個(gè)節(jié)點(diǎn)，m條邊的網(wǎng)絡(luò)G，算法NSA 首先利用t次標(biāo)簽傳播算法計(jì)算節(jié)點(diǎn)的標(biāo)簽熵獲取節(jié)點(diǎn)的標(biāo)簽分布及標(biāo)簽熵，選擇網(wǎng)絡(luò)的穩(wěn)定節(jié)點(diǎn)集.由于標(biāo)簽傳播算法有近似線性的時(shí)間復(fù)雜度O(m)［12］，獲取節(jié)點(diǎn)標(biāo)簽熵的總時(shí)間代價(jià)為O(tm)；為進(jìn)一步獲取網(wǎng)絡(luò)中的穩(wěn)定節(jié)點(diǎn)集，要按標(biāo)簽熵從小到大的順序?qū)?jié)點(diǎn)進(jìn)行排序，時(shí)間代價(jià)為O(nlgn).因此選擇網(wǎng)絡(luò)穩(wěn)定節(jié)點(diǎn)集的總時(shí)間代價(jià)為O(tm+nlgn).

接下來，算法從原網(wǎng)絡(luò)中抽取一個(gè)包含穩(wěn)定節(jié)點(diǎn)集的連通子圖，并對(duì)該連通子圖進(jìn)行聚類，得到初始社區(qū).抽取連通子圖的時(shí)間代價(jià)為O(m)，若利用標(biāo)簽傳播算法進(jìn)行聚類，時(shí)間代價(jià)近似為O(m).

最后，計(jì)算未聚類節(jié)點(diǎn)與已有社區(qū)的連邊數(shù)得到節(jié)點(diǎn)對(duì)社區(qū)的歸屬度，將未聚類的節(jié)點(diǎn)分配到已有社區(qū)，得到最終的聚類結(jié)果，時(shí)間代價(jià)為O（m）.

綜上所述，若利用標(biāo)簽傳播算法對(duì)連通子圖進(jìn)行聚類，則本文提出的NSA 算法的總時(shí)間代價(jià)為O(tm+nlgn).實(shí)際上，由穩(wěn)定節(jié)點(diǎn)構(gòu)成的連通子圖規(guī)模較小，可以利用準(zhǔn)確度高的一些算法（如BGLL，CNM 等）對(duì)其進(jìn)行聚類.

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

在四個(gè)帶標(biāo)簽的真實(shí)網(wǎng)絡(luò)和八個(gè)無標(biāo)簽真實(shí)網(wǎng)絡(luò)上，將本文所提算法NSA 與經(jīng)典的社區(qū)發(fā)現(xiàn)算法LPA，Infomap，Walktrap，BGLL 和LPA-S 進(jìn)行比較實(shí)驗(yàn).數(shù)據(jù)基本情況如表2 所示.

表2 實(shí)驗(yàn)數(shù)據(jù)集的基本情況Table 2 Datasets used in experiments

4.1 評(píng)價(jià)標(biāo)準(zhǔn)

4.1.1 標(biāo)準(zhǔn)互信息(NMI)若算法的社區(qū)發(fā)現(xiàn)結(jié)果為Ω={V1，V2，…，Vk}，帶標(biāo)簽的數(shù)據(jù)集上的原始劃分結(jié)果為O={O1，O2，…，Ok'}.對(duì)集合Vi和Oj(1≤i≤k，1≤j≤k')，令Ti，j=|Vi∩Oj|，對(duì)有標(biāo)簽數(shù)據(jù)集，選用標(biāo)準(zhǔn)互信息（NMI）［23］對(duì)聚類結(jié)果進(jìn)行評(píng)價(jià)，如式（5）所示：

劃分結(jié)果與原始劃分的吻合程度越高，NMI的值越高.

4.1.2 模塊度(Q)對(duì)于沒有標(biāo)簽的數(shù)據(jù)集，選用Newman and Girvan［6］提出的模塊度對(duì)聚類結(jié)果進(jìn)行評(píng)價(jià)，定義如式（6）所示：

其中，m是網(wǎng)絡(luò)中邊的總數(shù)，nc是社團(tuán)的數(shù)量，lv是社團(tuán)v內(nèi)部所包含的邊數(shù)，dv是社團(tuán)v中所有節(jié)點(diǎn)的度值之和.模塊度越高代表聚類結(jié)果越好.

4.2 實(shí)驗(yàn)結(jié)果在帶標(biāo)簽網(wǎng)絡(luò)上，通過最終社區(qū)劃分結(jié)果與真實(shí)社區(qū)的NMI指標(biāo)的對(duì)比進(jìn)行算法性能的比較.在無標(biāo)簽網(wǎng)絡(luò)上，由于沒有真實(shí)社區(qū)劃分，因此采用模塊度對(duì)算法性能進(jìn)行比較.為了評(píng)估算法的穩(wěn)定性，通過計(jì)算20 次實(shí)驗(yàn)結(jié)果所得的社區(qū)劃分方差進(jìn)行比較.

4.2.1 帶標(biāo)簽網(wǎng)絡(luò)的實(shí)驗(yàn)比較結(jié)果表3 給出了在空手道俱樂部（Karate）［22］、海豚社交網(wǎng)絡(luò)（Dolphins）［24］、美國(guó)政治書網(wǎng)絡(luò)（Polbooks）、政治博客網(wǎng)絡(luò)（Polblogs）四個(gè)帶標(biāo)簽的真實(shí)網(wǎng)絡(luò)上，算法所得到社區(qū)的NMI值比較情況，可以看出，本文的NSA 算法得到的社區(qū)劃分結(jié)果與真實(shí)社區(qū)更符合，表中黑體字是最好的結(jié)果.

表3 本文算法和五個(gè)對(duì)比算法在帶標(biāo)簽網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果對(duì)比Table 3 Experimental results on labeled networks of our algorithm and other five algorithms

4.2.2 無標(biāo)簽網(wǎng)絡(luò)的實(shí)驗(yàn)比較結(jié)果表4 給出了在Les，NetScience，Celegan，Email，Polblogs，F(xiàn)acebook，Power，PGP，Douban 等無標(biāo)簽網(wǎng)絡(luò)上的模塊度比較結(jié)果（此處將去除標(biāo)簽的Polblogs網(wǎng)絡(luò)看作一個(gè)無標(biāo)簽網(wǎng)絡(luò)進(jìn)行對(duì)比實(shí)驗(yàn)），最后一行給出了算法在所有網(wǎng)絡(luò)下所得社區(qū)劃分模塊度的平均值，表中黑體字是最好的結(jié)果.

可以看出，本文算法在大多數(shù)情況下得到了較好的社區(qū)劃分結(jié)果.由于BGLL 是基于模塊度優(yōu)化的算法，在網(wǎng)絡(luò)規(guī)模較小的時(shí)候能夠得到模塊度更優(yōu)的算法.然而，由于計(jì)算代價(jià)較高且受模塊度的精度限制，BGLL 算法不適合在更大規(guī)模網(wǎng)絡(luò)中進(jìn)行社區(qū)發(fā)現(xiàn).本文算法性能優(yōu)于其他基于信息傳播的算法，如LPA，Walktrap，LPA-S等.Infomap 算法與本文算法NSA 性能比較接近，而算法NSA 的平均值略高于Infomap 算法.

4.2.3 穩(wěn)定性比較結(jié)果在統(tǒng)計(jì)描述中，方差［25］可以用來計(jì)算每個(gè)變量與總體均值之間的差異.為了對(duì)算法劃分結(jié)果的穩(wěn)定性進(jìn)行評(píng)估，本文通過計(jì)算20 次實(shí)驗(yàn)結(jié)果模塊度值的方差來進(jìn)行比較，如式（7）所示：

表4 本文算法和五個(gè)對(duì)比算法在無標(biāo)簽網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果對(duì)比Table 4 Experimental results on unlabeled networks of our algorithm and other five algorithms

其中，σ2為總體方差，X為變量，μ為總體均值，N為樣本總數(shù).方差越低表明結(jié)果的穩(wěn)定性越好.

表5 給出了NSA 算法與LPA 和LPA-S 算法在真實(shí)網(wǎng)絡(luò)上的算法穩(wěn)定性實(shí)驗(yàn)結(jié)果，表中黑體字是最好的結(jié)果.可以看出，本文算法NSA 在大多數(shù)網(wǎng)絡(luò)中能得到更穩(wěn)定的實(shí)驗(yàn)結(jié)果.

表5 本文算法與LPA 和LPA-S 算法的算法穩(wěn)定性對(duì)比Table 5 The stability of our algorithm with LPA and LPA-S

5 結(jié)論

本文根據(jù)社區(qū)劃分結(jié)果定義節(jié)點(diǎn)在該社區(qū)劃分下的標(biāo)簽熵來衡量網(wǎng)絡(luò)中節(jié)點(diǎn)在社區(qū)劃分中的穩(wěn)定性；以此為基礎(chǔ)提出一種基于節(jié)點(diǎn)穩(wěn)定性的社區(qū)發(fā)現(xiàn)算法NSA.首先運(yùn)行t次快速社區(qū)發(fā)現(xiàn)算法得到原網(wǎng)絡(luò)的t個(gè)社區(qū)劃分，計(jì)算各節(jié)點(diǎn)對(duì)應(yīng)社區(qū)劃分的標(biāo)簽熵，從而確定網(wǎng)絡(luò)的穩(wěn)定節(jié)點(diǎn)集S.然后，在原網(wǎng)絡(luò)上抽取包含穩(wěn)定節(jié)點(diǎn)集S的連通子網(wǎng)絡(luò)GS并在其上進(jìn)行初始社區(qū)發(fā)現(xiàn)，得到初始類簇.最后，計(jì)算其他不穩(wěn)定節(jié)點(diǎn)與初始類簇的距離，將尚無社區(qū)歸屬的節(jié)點(diǎn)根據(jù)相似性劃分至與其最相似的類簇中，得到最終聚類結(jié)果.在四個(gè)帶標(biāo)簽和八個(gè)無標(biāo)簽的網(wǎng)絡(luò)數(shù)據(jù)集上，與五類經(jīng)典社區(qū)發(fā)現(xiàn)算法的比較實(shí)驗(yàn)表明，本文的NSA 算法能夠得到更穩(wěn)定的社區(qū)劃分結(jié)果，且在NMI和模塊度等方面表現(xiàn)了良好的算法性能.

隨著數(shù)據(jù)復(fù)雜性的增加，網(wǎng)絡(luò)中節(jié)點(diǎn)間的關(guān)系呈現(xiàn)多樣化，還需進(jìn)一步研究在更復(fù)雜情況下網(wǎng)絡(luò)中節(jié)點(diǎn)穩(wěn)定性的變化，如何更有效地區(qū)分穩(wěn)定節(jié)點(diǎn)和不穩(wěn)定節(jié)點(diǎn)是一個(gè)值得關(guān)注的研究問題.重疊社區(qū)在大規(guī)模網(wǎng)絡(luò)中普遍存在，在重疊社區(qū)背景下如何度量節(jié)點(diǎn)的穩(wěn)定性也是未來的研究課題之一.