基于局部鄰域連通性的重疊社區發現算法

鄭文萍，喬艷超，楊貴

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

0 引言

現實世界中的復雜系統可以建模為復雜網絡如社交網絡、科研協作網絡、蛋白質相互作用網絡等，其中節點代表系統個體，邊代表個體間的聯系［1］。社區結構是復雜網絡的重要特征之一。發現真實網絡中的社區結構有助于了解實體之間的相互作用，深入理解和分析復雜系統的群體特征和結構特征。如發現社交網絡中有相似興趣愛好的用戶群體、科研協作網絡中具有相似研究興趣的學術團體、蛋白質相互作用網絡中行使生物功能的蛋白質復合體等。鑒于此，社區發現算法已被廣泛應用個性化興趣推薦、社會網絡分析、蛋白質功能預測等諸多領域［1-3］。

目前已經有許多成功的非重疊社區發現算法用來檢測網絡中社區間沒有共同節點的社區結構。然而在真實網絡中，有些節點可能有多個社區歸屬，如在線社交網絡中的用戶可能屬于不止一個興趣愛好團體、科研協作網絡中一個科學家可能歸屬于多個研究領域、蛋白質相互作用網絡中大部分蛋白質屬于多個蛋白質功能復合體，發現復雜網絡中的重疊社區得到了越來越多的關注。目前已有的重疊社區發現算法主要包括基于派系過濾的、基于標簽傳播的和基于局部擴展的重疊社區發現算法等。

最早的重疊社區檢測算法是2005年Palla等［4］提出的派系過濾算法CPM，通過發現相鄰τ派系檢測到重疊的稠密社區，然而發現網絡中所有的τ派系是NP困難問題，算法計算代價比較大。2008年Kumpula等［5］提出SCP算法對CPM算法中的派系發現過程進行改進，從一個空網絡開始，在插入邊的同時檢測τ-團，提高了社區檢測速度?；谂上颠^濾的算法通常用于檢測網絡中的內部連邊稠密的社區，對網絡中普遍存在的內部稀疏連接的社區發現能力不足。派系過濾算法的計算開銷依賴于網絡團的分布，無法適用于大規模網絡的社區發現問題。

2010年，Gregory等［6］提出了基于標簽傳播的重疊社區發現算法COPRA，計算標簽傳播過程中節點對社區的隸屬度，高于給定閾值的標簽被賦予節點。由于COPRA僅根據鄰域的當前標簽信息更新節點標簽，因此最終產生大量的小規模社區。針對這一問題，2011年Xie等［7］提出基于動態交互規則的標簽傳播算法SLPA，根據節點的所有歷史標簽信息更新標簽。2012年Coscia等［8］提出了基于局部結構的標簽傳播算法DEMON，利用標簽傳播算法檢測網絡中每個節點的直接鄰居節點所構成的局部子圖內的社區結構，對所發現的局部社區進行合并得到最終重疊社區檢測結果。由于節點更新順序和標簽更新過程中的一些隨機性，導致標簽傳播算法的社區發現結果不穩定；另一方面，由于僅利用節點的直接鄰居信息更新標簽，這類算法通常不能較好地發現網絡中大度節點周圍的社區［9］。

基于“種子擴展”策略的重疊社區發現算法首先選取一部分節點作為種子節點，將這些種子節點看作社區中心進行擴展，可以更好地發現網絡中內部連接密度各異的社區結構。種子節點選擇和社區擴展方式影響基于“種子擴展”策略的重疊社區發現質量。Lancichinetti等［10］提出的算法LFM隨機選取尚未分配社區的節點作為種子節點，可能導致社區結果不穩定，并且當種子節點屬于社區重疊部分時，無法準確發現網絡中的重疊社區。Lee等［11］提出的算法GCE選取網絡中τ派系作為初始種子進行擴展，在一定程度上提高了算法穩定性，然而由于尋找網絡τ派系計算代價大，不適用于大規模網絡的重疊社區發現算法，且無法對網絡節點完全聚類。Wang等［12］提出算法LOCD優先選擇與已有種子節點的相距較遠的大度節點作為種子擴展社區。Zhang等［13］提出算法CFCD，根據節點的k核中心性選擇種子節點。這些算法在選取種子節點時考慮了節點的局部鄰域結構，提高了社區檢測質量?；凇胺N子擴展”策略的社區發現算法往往通過定義社區適應度函數來判斷節點是否加入或者離開社區，如算法LFM和GCE以社區內部邊數占與社區關聯的所有邊數比例作為適應度函數，算法LOCD以社區內部節點間Salton相似性與社區關聯的所有度數之比作為適應度函數，算法CFCD根據社區內節點的k核中心性定義適應度函數。根據某一種適應度函數進行社區擴展，通常能夠發現網絡中內部連接比較稠密、適應度值較高的社區結構，無法發現大規模網絡中內部結構差異較大的不同社區結構。

2013年，Whang等［14］提出了基于個性化PageRank的社區擴展算法框架NISE，對已選好的種子節點進行擴展，以社區導電性作為社區評價指標，能夠更好地發現種子節點周圍的社區結構。2015年，Soundarajan等［15］提出了基于節點局部鄰域結構的重疊社區檢測算法框架Node_Perception，首先發現每個節點的直接鄰域導出子圖內的局部社區結構，最終合并各節點鄰域的局部社區結構得到社區發現結果。

根據節點的鄰域結構信息來選擇有效的種子節點，并采用合適方式對種子節點進行擴展，是重疊社區檢測算法的核心問題。本文提出了一種基于鄰域連通性的重疊社區發現算法LNCA，首先根據節點的度信息和k步鄰域連通信息計算節點鄰域中心性并選擇種子節點；采用帶重啟的隨機游走過程擴展種子節點；最后，根據兩社區之間的重疊度對相似性較大的社區進行處理。

在6個真實帶標簽網絡、9個真實無標簽網絡，將本文算法LNCA與6個經典重疊社區發現 算 法 SLPA［7］、DEMON［8］、CPM［4］、Node_Perception［15］、Ego_Networks［16］、Egonet_Splitter［16］進行比較，實驗結果表明LNCA算法社區發現結果表現出良好的穩定性，在重疊社區NMI、F1分數和重疊模塊度EQ等指標上都表現出較好的性能。

1 背景知識

一個復雜網絡可以建模成一個圖G=(V，E)，其 中 節 點 集 V={v1，v2，…，vn}，邊 集E={(vi，vj)|1 ≤ i≠ j≤ n}。除非特別指出，本文僅對無向無權圖進行研究。節點v和w的距離l(v，w)指這兩個節點間最短路徑的邊數。節點v的k步鄰域記作Nk(v)={w∈V|l(v，w)=k}，則 N1(v)為 v的直接鄰居節點集合，簡記為N(v)。因此，節點v的度d(v)=|N(v)|，簡記為 dv。頂點子集 S(? V)的體積為Vol(S)=∑v∈Sdv，表示S中所有節點的度 數 和 。 對 圖 G′=(V′，E′)，若 V′?V 且E′?E，則稱G′是G的子圖，記作G′?G。若V′? V 且 邊 E′={(vi，vj)|vi，vj∈ V′∧(vi，vj)∈ E}，則稱子圖G′是圖G的導出子圖，記為G[V′]，簡 記 為 [V′]；若 |V′|= τ且 |E′|= τ(τ-1)/2，則G′是圖G的一個包含τ個節點的完全子圖，也稱為圖G的一個τ派系。如果圖G的任意兩個節點v和w間至少存在一條路徑，則稱圖G是連通的。無向圖G中的一個極大連通子圖稱為G的一個連通分支。

社區結構是復雜網絡的重要特征之一，通常表現為社區內部的節點間連接比較緊密，社區之間的節點間連接相對稀疏。對一個圖G，社區發現是指將G中的節點分成若干子集，即V=C1∪C2…∪Ck，其中 k為社區的個數。若對任意的 1≤ i，j≤ k，有 Ci∩Cj= ?，則稱 Ω ={C1，C2，…，Ck}是圖 G 的一種非重疊社區發現結果；否則稱Ω為圖G的一種重疊社區發現結果［17］。

Newman等［18］提出的模塊度是最常用的衡量社區劃分質量的標準，如公式（1）所示：

其中Cv和Cw分別表示節點v和w所屬的社區，若Cv=Cw，則 δ(Cv，Cw)=1，否 則 δ(Cv，Cw)=0；avw是鄰接矩陣元素。模塊度通常用來衡量一種社區發現結果的整體質量。

社區導電性常用來衡量單個社區內部節點與社區外其他部分的連接緊密程度［19］。假設C是圖G的一個社區，其導電性如公式（2）所示：

其中

E(C，VC)={(v，w)|v∈C，w∈VC，(v，w)∈E}，表示社區C的向外連邊集合。一個社區導電性越低，其社區結構越明顯。

2 基于局部鄰域連通熵的節點鄰域中心性度量

種子節點的選擇對于基于局部擴展策略的重疊社區發現算法至關重要，通常應該選擇能夠代表社區內的局部拓撲結構分布的節點作為一個社區的種子節點，找到合適的種子節點，可以提高社區發現的質量。早期用于重疊社區發現的LFM算法，通過隨機選取種子節點進行社區發現，導致算法結果不穩定；而GCE算法把網絡中的τ派系作為種子節點，不適用于大規模稀疏網絡中的社區發現；DEMON算法將所有節點看作初始種子節點進行擴展，往往將大度節點及其所有鄰居節點發現為一個社區，導致網絡中的小社區被大社區湮沒。2017年所提出的LOCD算法選擇大度節點作為種子節點，減少了初始種子節點的數目；而2019年所提的CFCD算法利用節點的k核中心性選擇種子節點，由于節點的k核中心性在一定程度上代表了該節點鄰域拓撲結構的連通信息，算法對不同社區的區分能力得到提高。

為了有效利用節點鄰域拓撲結構的連通信息進行種子節點選擇，本節首先給出一種基于節點局部鄰域連通熵的節點鄰域中心性度量指標。首先根據節點及其局部鄰域的導出子圖的連通信息計算網絡中每個節點的連通概率分布，再計算所得概率分布的熵，稱為該節點的局部鄰域連通熵。它反映了一個節點的局部鄰域拓撲結構的連通分布情況，熵越小代表連通情況越好，該節點對一個社區局部結構的代表性也越強。

2.1 節點的k步鄰域連通熵

令Hk(v)表示圖G中節點v的k步鄰域節點的導出子圖，即Hk(v)=[Nk(v)]。設Hk(v)中的連通分支為

連通熵SC(v)值越高，說明節點v局部鄰域內的節點越分散，可能歸屬的社區越多；SC(v)值越低，說明節點v的局部鄰域內的節點聚集性較好，屬于同一個社區的可能性越大。若網絡中的一個節點位于某社區的中心，則該節點的局部鄰域節點聚集性較好，因此也應具有較低的連通熵。

圖1給出了Dolphin網絡及網絡節點的k步連通熵（k=2）的分布情況。Dolphin網絡包含62個節點，159條邊，網絡中節點分成2個社區，分別用圖中的方形節點和圓形節點表示；圖中的黃色節點表示連通熵最小的24個節點?？梢钥闯?，有些度較大的節點具有較低的連通熵，這些節點的鄰域節點聚集性比較好，通常位于社區中心；然而，一些度較小的邊緣節點（如節點61和節點13），由于其鄰域中僅包含極少的節點，所得的連通熵也比較低，但這些節點并不位于社區中心。為了更好地選擇社區中心，本文提出了基于節點度信息和k步鄰域連通熵的節點鄰域中心性度量指標。

圖1 Dolphin網絡中連通熵較低的節點Fig.1 Nodes with low connectivity entropy in Dolphin network

2.2 基于度信息和k步鄰域連通熵的節點鄰域中心性度量指標

考慮到社區中心節點通常具有較多的連接，并且其鄰域中的節點聚集性比較高，因此給出如公式（5）所示的節點鄰域中心性度量。對網絡中的任意節點v∈V(G)，其鄰域中心性為：

圖2給出了Dolphin網絡中各節點的節點鄰域中心性度量指標的分布情況，黃色節點表示中心性最高的24個節點?？梢钥闯觯行男暂^高的節點更有可能成為社區中心。

圖2 Dolphin網絡中節點鄰域中心性較高的節點Fig.2 Nodes with high neighborhood centrality in Dolphin network

3 基于局部鄰域連通性的重疊社區發現算法LNCA

基于上一節提出的節點鄰域中心性度量指標，本節給出基于節點鄰域連通性的重疊社區檢測算法（Overlapping Community Detection Algorithm Based on Node Loca Neighborhood Connectivity，LNCA），算法采用種子擴展策略，包括三個主要步驟：種子節點選擇，初始社區擴展，合并社區。

3.1 種子節點選擇

對圖G=（V，E），首先根據公式（5）計算每個節點的鄰域中心性，并將G中節點按照中心性從大到小的順序排列，即V={v1，v2，…，vn}，對 于 1≤i＜j≤n，有cc(vi)≥cc(vj)。假設ˉ表示網絡中節點的平均鄰域中心性，選擇中心性指標高于cˉcˉ的節點作為候選種子節點集CI。為了避免將兩個相鄰的中心性較高的節點同時標記為社區中心，依次從候選種子集合CI中選擇中心性最高的節點v加入種子節點集I，同時將v及其直接鄰居節點從CI中刪除，直到CI為空。種子節點的選擇過程如算法1所示。圖2給出了Dolphin網絡的種子節點集，用紅色邊框表示。

3.2 擴展階段

在社區擴展階段，將利用隨機游走過程將每個種子節點擴展成為一個社區，為了避免隨機游走過程偏離種子節點太遠，此處采用帶重啟的隨機游走過程進行社區擴展。

從種子節點s出發進行帶重啟的隨機游走，隨機游走粒子每走一步，都以概率1-r返回種子節點s，以概率r從它指出的邊中隨機選擇一條邊并沿這條邊到達另一個節點。令pt(v)表示經過t步隨機游走到達節點v的概率，則t+1步隨機游走到達節點v的概率如公式（6）所示：

圖3給出了Dolphin網絡中以節點46作為種子進行擴展，當r=0.6，0.8，0.9，0.99時所得的社區。本文取r=0.99。對每個種子節點進行擴展，可以得到網絡的初始社區發現結果。

圖3 Dolphin網絡中以節點46為種子擴展所得社區Fig.3 Extended communities with node 46 as seed in Dolphin network

圖4給出了Dolphin網絡以種子節點｛46，15，48，33，58｝擴展所得的社區，可以看出，由這些種子節點擴展所得的初始社區與網絡的真實社區情況比較相符，說明利用帶重啟的隨機游走過程對種子節點進行擴展，可以得到合理的社區結果。然而，如果這些社區包含的節點有很大的重疊，需要對這些重疊度偏高的社區進行合并，以得到最終的社區發現結果。

圖4 Dolphin網絡種子節點s擴展出的初始社區發現結果Fig.4 Initial communities discovered from seed node s in Dolphin network

3.3 合并重疊度高的社區

對圖

G=(V，E)，Ω={C1，…，Ci，…，Cj，…，Cm}是圖G的一種社區發現結果，則社區Ci和Cj的重疊度計算如公式（7）所示：

本文中設置當社區Ci和Cj的重疊度大于0.8時，則將Ci和Cj合并為一個社區，即Ω={C1，…，Ci∩Cj，…，Cm}。對初始社區劃分結果進行一次合并得到最終社區。

圖5給出了Dolphin網絡在合并重疊度較大社區之后的社區發現結果，其中分別用方形節點和圓形節點代表不同的社區，節點8和20是重疊節點。

圖5 Dolphin網絡最終社區劃分結果Fig.5 The final community partition result of Dolphin network

4 實驗結果

在6個帶標簽網絡和9個無標簽網絡上，將本文算法LNCA與6個經典重疊社區發現算法SLPA［7］、DEMON［8］、CPM［4］、Node_Perception［15］、Ego_Networks［16］、Egonet_Splitter［16］進行比較實驗。數據集基本情況如表1所示，其中未標注引用文獻的數據均可從http：//networkrepository.com/index.php 和 https：//snap.stanford.edu/data/獲取。

表1 數據集基本情況Table 1 Basic information of datasets

4.1 評價指標

假設 Ω={C1，C2，…，Cm}表示算法得到的社 區 發 現 結 果 ，O={O1，O2，…，Om′}表 示 帶 標簽數據集的真實社區劃分。對帶標簽網絡，采用重疊社區NMI和F1分數評價算法運行結果，對無標簽網絡，采用擴展模塊度（Extended modularity，EQ）評價社區發現質量。

重疊NMI和F1分數的取值范圍都是［0，1］，值越高表明算法所得社區發現結果越符合網絡真實社區劃分結果。

對于無標簽網絡，采用沈華偉等［22］提出的擴展模塊度EQ進行評價，其定義如公式（10）所示：

其中，v和w表示網絡節點；m是算法劃分得到的社區數目；Ov表示節點v所屬的社區數；avw是鄰接矩陣元素。EQ越接近1，說明所得到的社區發現結果模塊度越高。

4.2 帶標簽網絡的實驗比較結果

表2和表3分別給出了在空手道俱樂部（Karate）［23］、海豚社交網絡（Dolphin）［24］、大學生 足 球 網 絡（Football）［25］、美 國 政 治 書 網 絡（Polbooks）［26］、亞馬遜網絡（Amazon）［27］、引文網絡（DBLP）［27］等6個帶標簽的真實網絡上，不同算法所發現社區的重疊NMI值和F1分數實驗結果。

表2 在帶標簽網絡上的重疊NMI實驗結果Table 2 Experimental results of overlapping NMIon labeled networks

表3 在帶標簽網絡上的F1分數實驗結果Table 3 Experimental results ofF1Score on labeled networks

可以看出，在 Karate、Dolphin、Football、Polbooks等真實社區較少的網絡上，本文算法LNCA在重疊NMI和F1分數方面明顯優于對比算法。由于Amazon和DBLP等網絡規模較大，且有很多包含3至10個節點的小規模社區，這些小社區往往被其他規模更大的社區完全覆蓋，LNCA經過社區去重處理后忽略了這部分小社區，導致LNCA在Amazon和DBLP等網絡上具有較低的重疊NMI值。實際上，LNCA所發現的社區與真實社區匹配程度更高，因此在Karate、Dolphin、Polbooks、DBLP 等網絡上 LNCA所得社區發現結果F1分數明顯優于對比算法，在Football、DBLP網絡上F1分數略低于SLPA算法，優于其他對比算法。

4.3 無標簽網絡的實驗比較結果

表 4 給 出 了 在 Les、Jazz［28］、Usair、Net-Science、Email、Facebook、Power、PGP、Ca-AstroPh等9個無標簽網絡上，本文算法LNCA與其他6個對比算法結果的擴展模塊度EQ的比較情況。

表4 在無標簽網絡上的模塊度實驗結果Table 4 Experimental results of modularity on unlabeled networks

實驗結果表明，在無標簽網絡上，LNCA所發現社區的重疊模塊度優于DEMON、CPM、Node_Perception、Ego_Networks等算法。在一些網絡上LNCA的重疊模塊度略低于SLPA，但SLPA算法過程中存在較大隨機性，無法得到穩定的社區發現結果，而LNCA通過節點的鄰域中心性選擇種子節點并通過帶重啟的局部隨機游走擴展種子節點，因此所發現的社區模塊度較高且運行結果穩定。

5 結論

本文提出了一種基于鄰域連通性的重疊社區發現算法LNCA，用于發現網絡中的重疊社區結構。首先，計算每個節點的局部鄰域連通熵和鄰域中心性cc；選擇鄰域中心性高的節點作為種子節點，采用帶重啟的隨機游走過程對種子節點進行擴展得到初始社區；最后合并重疊度較大的社區。在6個帶真實社區標簽的網絡和9個無真實社區標簽的網絡上，對所提算法LNCA與其他6個經典的重疊社區檢測算法進行比較實驗，結果表明LNCA算法可以較好地發現網絡中的真實社區結構。