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

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

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

1 相關(guān)工作

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

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

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

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

2 基礎(chǔ)知識

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

表1 Karate 網(wǎng)絡節(jié)點的標簽熵Table 1 The label entropy of nodes on Karate networks

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

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

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

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

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

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

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

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

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

4 實驗結(jié)果與分析

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

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

4.1 評價標準

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

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

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

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

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

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

表3 本文算法和五個對比算法在帶標簽網(wǎng)絡上的實驗結(jié)果對比Table 3 Experimental results on labeled networks of our algorithm and other five algorithms

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

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

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

表4 本文算法和五個對比算法在無標簽網(wǎng)絡上的實驗結(jié)果對比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 算法在真實網(wǎng)絡上的算法穩(wěn)定性實驗結(jié)果，表中黑體字是最好的結(jié)果.可以看出，本文算法NSA 在大多數(shù)網(wǎng)絡中能得到更穩(wěn)定的實驗結(jié)果.

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

5 結(jié)論

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

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