一種基于節點穩定性的社區發現算法

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

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

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

1 相關工作

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

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

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

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

2 基礎知識

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

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

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

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

3 基于節點穩定性的社區發現算法

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

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

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

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

圖1 Karate 網絡的真實社區劃分結果Fig.1 A community detection result of of Karate network

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

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

其中，ε稱作穩定性閾值，不穩定節點集合為V-S.

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

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

由穩定節點集S所構造的連通子圖GS包含原網絡G中社區劃分相對穩定的節點，因此在GS上進行社區發現，會得到比較穩定的劃分結果.此外，GS中的節點在原網絡G中所占比例比較低，這就允許選擇在較小規模網絡上具有較好性能的社區發現算法得到初始社區.

本文采用LPA 算法對GS中節點進行聚類，得到初始社區為其中k為初始社區個數.

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

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

3.5 NSA 算法算法1 給出了本文所提的基于節點穩定性的社區發現算法的框架 .

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

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

表1 Karate 網絡節點的標簽熵Table 1 The label entropy of nodes on Karate networks

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

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

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

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

圖4 算法NSA 所得的最終社區劃分結果Fig.4 Final communities detected by NSA

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

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

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

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

4 實驗結果與分析

在四個帶標簽的真實網絡和八個無標簽真實網絡上，將本文所提算法NSA 與經典的社區發現算法LPA，Infomap，Walktrap，BGLL 和LPA-S 進行比較實驗.數據基本情況如表2 所示.

表2 實驗數據集的基本情況Table 2 Datasets used in experiments

4.1 評價標準

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

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

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

其中，m是網絡中邊的總數，nc是社團的數量，lv是社團v內部所包含的邊數，dv是社團v中所有節點的度值之和.模塊度越高代表聚類結果越好.

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

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

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

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

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

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

表4 本文算法和五個對比算法在無標簽網絡上的實驗結果對比Table 4 Experimental results on unlabeled networks of our algorithm and other five algorithms

其中，σ2為總體方差，X為變量，μ為總體均值，N為樣本總數.方差越低表明結果的穩定性越好.

表5 給出了NSA 算法與LPA 和LPA-S 算法在真實網絡上的算法穩定性實驗結果，表中黑體字是最好的結果.可以看出，本文算法NSA 在大多數網絡中能得到更穩定的實驗結果.

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

5 結論

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

隨著數據復雜性的增加，網絡中節點間的關系呈現多樣化，還需進一步研究在更復雜情況下網絡中節點穩定性的變化，如何更有效地區分穩定節點和不穩定節點是一個值得關注的研究問題.重疊社區在大規模網絡中普遍存在，在重疊社區背景下如何度量節點的穩定性也是未來的研究課題之一.