基于密度峰值的標簽傳播社區發現算法

摘 要：針對標簽傳播算法中節點啟動順序和更新標簽的隨機性造成的結果不穩定問題，提出一種新標簽傳播算法用于復雜網絡社區檢測（density peaks and node similarity，DPNS-LPA），包括社區中心的確定和外圍節點的標簽傳播。首先利用大度節點不利指標、Jaccard指標和度為1節點的結構特性刻畫節點局部相似性指標，并用此指標度量節點間距離和解決最大標簽相同時的隨機選擇；然后引入改進的密度峰值聚類算法尋找社區中心，確定社區數量；最后基于社區中心和外圍節點的標簽傳播，得到最終的社區劃分結果。通過人工網絡和真實網絡上的實驗，結果表明標準化互信息、模塊度和D-score指標值優于對比算法，所提出的算法可以有效發現復雜網絡中的社區結構，且魯棒性更高。

關鍵詞：密度峰值聚類；局部相似度；標簽傳播；社區發現

中圖分類號：O157.5 文獻標志碼：A 文章編號：1001-3695（2023）08-012-2323-06

doi： 10.19734/j.issn.1001-3695.2022.12.0796

Label propagation community discovery algorithm based on density peak

Fu Lidong Liu Jiahui Wang Qiuhong

（1.College of Computer Science amp; Technology， Xi’an University of Science amp; Technology， Xi’an 710699， China; 2.The 20th Institute of China Electronics Technology Group Co.， Ltd.， Xi’an 710068， China）

Abstract：Aiming at the problem of instability caused by the randomness of node starting order and updating labels in the label propagation algorithm， this paper proposed a new label propagation algorithm for detection of complex network community （density peaks and node similarity，DPNS-LPA）. It included the determination of community center and label propagation of peripheral nodes. Firstly， the method defined the local similarity index of nodes which was characterized by the hub depressed index， Jaccard index and the structural characteristics of nodes with degree 1， and this index was used to measure the distance between nodes and solve the random selection of the same maximum label. Then it introduced the improved density peak clustering algorithm to find community centers and determined the number of communities. Finally， it obtained the final community division result based on the label propagation of the community center and peripheral nodes. Experimental results on artificial networks and real networks show that the standardized mutual information、modularity and D-score index values are superior to the comparison algorithms. The proposed algorithm can effectively discover community structure in complex networks， and has higher robustness.

Key words：density peak clustering; local similarity; label propagation; community discovery

研究復雜網絡的社區結構和特征，有助于人們深入了解復雜系統的功能及演化過程［1］。一般來說，網絡中的社區內部節點之間聯系緊密，社區之間連接稀疏［2］。因此，借助社區結構的特征研究網絡中成員之間的差異和聯系，對于復雜網絡分析和實際應用的發展具有重要作用［3］。

標簽傳播算法（label propagation algorithm，LPA）是由Raghavan等人［4］提出的，因具有接近線性的時間復雜度且無須任何先驗信息而被廣泛用于復雜網絡社區檢測。但由于節點啟動順序和更新標簽的隨機性，LPA算法的社區劃分結果存在不穩定性、易形成較大社區等缺點。密度峰值聚類算法［5］（density peaks clustering algorithm，DPC）具有較好的魯棒性，所選出的中心節點個數決定了最終數據集的聚類數量。這一思想適用于解決標簽傳播算法性能不穩定的問題。但由于密度峰值聚類算法的局部密度和相對距離是基于坐標進行計算的，所以DPC算法無法直接應用于復雜網絡社區檢測。因此，本文提出一種基于密度峰值的標簽傳播社區發現算法（DPNS-LPA）用于復雜網絡社區檢測。DPNS-LPA算法將標簽傳播過程分為社區中心節點的標簽傳播和外圍節點的標簽傳播。社區中心節點的標簽傳播關鍵在于社區中心的確定。本文通過改進DPC算法中聚類中心的選擇過程來自動選擇社區中心節點。外圍節點的標簽傳播是對網絡中未更新節點和已在社區中的節點進行標簽更新。為避免LPA算法中的節點啟動順序的隨機性，利用PageRank指標［6］對外圍節點進行重要性排序，從PageRank值最高的外圍節點進行標簽傳播。針對傳播過程中存在多個最大標簽的問題，提出一種新的節點局部相似度指標。該指標綜合考慮了節點之間有無共同鄰居的情況，在無共同鄰居時同時考慮了節點度為1時的節點相似性度量問題。通過社區中心的標簽傳播形成初始社區，外圍節點的標簽傳播得到最終的社區劃分結果。在真實網絡數據集和合成網絡數據集上與已有的算法進行實驗對比，證實了本文算法的有效性。

1 相關工作

1.1 標簽傳播算法

LPA算法不依賴自由參數和目標函數，主要根據網絡的拓撲結構傳播節點信息。初始時為網絡中的所有節點分配一個唯一的標簽，然后逐次迭代將一個節點的標簽更新為其鄰居的標簽。標簽傳播算法具有簡單、高效的優點，但其節點啟動順序和更新標簽的隨機性易造成社區劃分結果不穩定。針對LPA算法的不足，提出了多種算法。Xing等人［7］基于K-shell的概念，提出一種基于節點影響力的標簽傳播算法（node influence based label propagation algorithm，NIBLPA）。該算法根據節點的影響力值確定節點的更新順序，當存在多個最大標簽時，引入標簽影響力計算公式來計算各個最大標簽的影響力，從而避免隨機選擇一個標簽的問題。LPA-intimacy（label propa-gation algorithm based on node intimacy）算法［8］通過親密度矩陣評估節點的重要性，根據節點的重要性降序更新節點以解決節點啟動順序的隨機性問題。對于每個待更新節點，根據其鄰居中最有影響力的標簽作為其更新標簽，以解決多個標簽出現頻次相同時的隨機選擇問題。

Aghaalizadeh等人［9］為解決LPA算法的不穩定性，提出一種基于節點重要性和核心擴展的標簽傳播算法（label propagation algorithm based on node ranking and core expansion，CSLPR）。該算法在標簽傳播階段開始之前，先根據網絡的拓撲結構對節點的重要程度進行排序；然后從低重要性節點的標簽傳播到網絡的密集中心；對于多個標簽出現頻率相同的問題，作者分兩種情況來處理以消除隨機選擇的過程：在標簽傳播的第一次和第二次迭代中使用Adamic/Adar指標確定待更新節點的標簽；在其他迭代中，根據每個標簽的影響力來更新節點的標簽。LSDPC（node local similarity based on two-stage density peaks algorithm）算法是由段小虎等人［10］提出的，用于解決重疊社區檢測。該算法指出DPC算法尋找聚類中心點的思想適用于復雜網絡的社區發現，通過結合大度節點有利指標和連接貢獻度定義了一種新的節點局部相似性指標用于改進密度峰值聚類算法，使其能直接用于復雜網絡社區發現。

1.2 密度峰值聚類算法

綜上可知，密度峰值算法雖然可以識別任意形狀的簇，但存在一些不足，即截斷距離需要人為設置和中心點的選擇存在主觀性［11］。此外，基于坐標計算節點距離的指標無法直接應用于復雜網絡社區檢測。一些學者通過改進密度峰值聚類算法將其應用于社區發現。段小虎等人［10］結合大度節點有利指標與連接貢獻度來度量節點距離，為避免人工決策，利用切比雪夫不等式來選擇社區中心點，但標準差系數ε需人為給定且計算距離的時間復雜度較高。Ma等人［12］基于Salton指標定義節點間的相似度，節點間的距離通過相似度的倒數來衡量，該方法雖然減少了計算節點距離的時間復雜度，但設計節點相似度時局部信息利用不全面，只考慮了節點間有共同鄰居的情況。

2 基于密度峰值的標簽傳播社區發現算法

針對靜態無向網絡，本文設計了一種基于密度峰值的標簽傳播社區發現算法，該算法主要包括：

a）改進密度峰值聚類算法確定社區中心節點，作為標簽傳播算法的輸入。包括結合改進的Jaccard指標、大度節點不利指標和度為1的節點的結構特性來定義節點相似度，用于度量節點間距離和解決多個標簽出現頻次相同時的隨機選擇問題。通過網格搜索確定切比雪夫不等式中的標準差系數ε，以解決系數ε人為給定的主觀性。

b）提出外圍節點的概念和外圍節點標簽更新的兩種規則，并利用PageRank指標度量外圍節點的重要性，以解決標簽傳播中節點啟動順序的隨機性。

本文算法的流程如圖1所示。

2.1 社區中心節點的確定

本文通過改進密度峰值聚類算法中的局部密度和節點距離度量指標，使其能直接用于復雜網絡社區檢測。在得到局部密度和節點最小距離的乘積后，通過網絡搜索來確定切比雪夫不等式中的標準差系數ε，從而自動篩選出社區中心節點。以下是確定社區中心節點所涉及的相關定義。

1）節點局部密度

在復雜網絡中，節點的密度大小不僅與節點領導的鄰居數量有關，而且也與鄰居節點之間聯系的緊密性息息相關。節點領導的鄰居數量越多，其影響力就越強，鄰居節點之間的連邊越多，則該節點凝聚周圍節點的能力就越強。因此，本文綜合考慮節點在網絡中的領導力和凝聚力來設計局部密度指標，即

2.2 社區中心和外圍節點的標簽傳播

2.2.1 初始社區的形成

由2.1節得到的復雜網絡社區中心節點形成初始社區。即將各社區中心節點標簽傳播至其鄰居，由各個中心節點及鄰居構成初始社區。

2.2.2 外圍節點的標簽傳播

如果一個節點有70%的鄰居標簽與該節點的標簽不同，則將該節點定義為外圍節點。參數確定為70%（即0.7），將在3.3節給出詳細闡述。

由于2.2.1小節所形成的初始社區不能完全覆蓋網絡中的所有節點，且社區中心節點的鄰居標簽更新過于簡單，若不對其進行檢查易造成累積效應，導致最終社區劃分結果質量偏低。因此，本文對網絡中的所有節點進行檢查，將滿足外圍節點概念的節點加入集合D中，從而對未覆蓋的節點和已在社區中的節點進行標簽更新。

研究表明，節點的啟動順序會影響算法的性能。為避免節點啟動順序的隨機性，采用Python庫中的PageRank指標來衡量節點在網絡中的重要性，PageRank值越大，節點重要性越高。

2.2.3 標簽更新規則

根據PageRank值對外圍節點進行排序，并進行標簽更新。外圍節點的標簽更新有兩種更新規則：a）若出現頻次最高的鄰居標簽唯一時，則將外圍節點的標簽更新為最高頻次的鄰居標簽；b）若出現頻次最高的鄰居標簽不唯一時，需分別計算外圍節點與這些標簽對應節點之間的相似度，將外圍節點的標簽更新為相似度高的鄰居標簽。

以圖2為例來說明外圍節點的標簽更新過程。

3 實驗結果與分析

為驗證本文算法的有效性，將所提出的算法與改進的標簽傳播算法CSLPR［9］、NIBLPA［7］、LPA-intimacy［8］、基于密度峰值的社區發現算法 LSDPC［10］和經典標簽傳播算法LPA［4］在真實網絡和合成網絡數據集上進行對比。

3.1 評價指標

3.2 數據集

本文選取了六個真實網絡數據集和六組LFR合成網絡數據集對所提算法進行研究。

真實網絡數據集分別為空手道俱樂部網絡（karate）、海豚社會網絡（dolphin）、政治書籍網絡（polbooks）、足球聯賽網絡（football）、美國電網網絡（power grid）和安然郵件網絡（Email Enron），具體如表1所示。

LFR基準是由Lancichinetti等人［19］提出的，可以控制節點度分布和社區大小分布，生成與真實網絡結構相似的網絡數據集。因此，常用于復雜網絡社區發現算法的對比實驗中。本文通過改變網絡節點數、社區大小生成六組LFR基準網絡，具體如表2所示。

參數K為節點的平均度，max（k）為節點的最大度；min（c）為社區的最小規模，max（c）為社區的最大規模；mu為混合參數，決定網絡的清晰度，其值越大，網絡中的社區結構越難以識別。

3.3 參數的確定

為確定外圍節點的數量，同時保證算法性能較優，在LFR1和LFR2合成網絡上進行實驗，算法的性能使用標準化互信息NMI值進行評價，結果如圖3所示。實驗結果表明，在LFR1網絡中，參數0.1≤≤0.7時，NMI值均達到了1，當參數增加至0.8時，算法性能出現下降。同時觀察外圍節點數量的變化，隨著參數的增加，待更新的外圍節點數量逐次下降，當增加到0.7時，下降幅度出現緩和，即外圍節點的數量開始穩定。LFR2網絡中，當增加至0.8時，NMI值也呈現了LFR1網絡中同樣的現象，即NMI值開始出現下降。因此，為減少待更新外圍節點的數量，同時使NMI值最高，將參數設置為0.7較為合理，即NMI曲線的拐點對應的參數值。

3.4 人工網絡分析

人工網絡數據集中選取LFR3～LFR6四組基準網絡共32個網絡作為實驗數據集，標準化互信息NMI作為評價指標。實驗結果如圖4所示，橫坐標表示混合參數mu的各個取值，縱坐標表示標準化互信息NMI值。LSDPC算法中的標準差系數ε設為0.6，最近鄰參數k設置為20。

分析圖4可以看出，隨著混合參數mu的增加，幾種算法在四組網絡中均出現了不同程度的下降。在mult;0.5時，各算法的NMI值較高；當mugt;0.5時，準確率均出現了下降，其中CSLPR和LPA對參數mu的變化最為明顯；在mu≥0.7時，四組網絡中的NMI值均為0。LSDPC算法在網絡結構復雜時的性能優于其他算法。對比合成網絡LFR3、LFR4或合成網絡LFR5、LFR6，社區尺寸增加后，幾種算法在mu＞0.4時，NMI值下降速度增快；隨著節點數的增加，幾種算法的NMI值均有所增加。

對比CSLPR算法在四組網絡中的表現可以發現，該算法在社區尺寸較大時的社區劃分結果較好，但不適用于網絡結構模糊的網絡，在混合參數mugt;0.5時，NMI值基本為0。

LPA存在隨機性，在LFR3、LFR4和LFR6合成網絡上，出現了NMI值振蕩的現象，魯棒性低于本文算法。NIBLPA和LPA-intimacy算法在四組合成網絡上的NMI值低于本文算法，當mu≥0.7時，其NMI值略大于本文算法。LSDPC算法計算節點距離的時間復雜度較高且受標準差系數ε影響較大，ε選取的合理性決定了最終社區劃分的質量，如在LFR3、LFR4合成網絡上，其NMI值總體低于其他算法。

綜上所述，在不同參數生成的合成網絡數據集上，本文提出的DPNS-LPA算法的社區劃分結果更好。

3.5 真實網絡分析

真實網絡數據集上采用模塊度Q進行算法對比，設置LSDPC算法中的標準差系數ε為1，k為各個網絡的平均度，實驗結果如表3所示。

由表3可以看出，LSDPC算法在六個網絡數據集上的模塊度最低，原因是LSDPC算法尋找社區中心節點時依賴于標準差系數，而標準差系數又決定了最終選擇出的社區中心節點個數，若選擇出的社區中心個數與真實情況相差較大，則會導致社區劃分結果與真實網絡結構相差較大。比如在karate網絡上只識別出一個社區中心點，導致模塊度為0。本文算法在karate、dolphin、polbooks、football和Email Enron這五個真實網絡數據集上的模塊度Q均優于其他五種算法。在power grid數據集上，本文算法的Q值小于CSLPR算法，但都優于其他三種算法。整體來看，所提出的算法在許多真實網絡上的實驗結果最優，CSLPR算法次之。

為測試算法在評估社區數量方面的性能，對已知真實社區個數的數據集采用D-score指標來對比各個算法的社區劃分結果，實驗結果如表4所示。

DPNS-LPA在四組已知真實社區劃分的網絡中，D-score值基本低于對比算法，說明本文算法發現的社區個數與真實情況更為接近。

為進一步驗證本文算法的魯棒性，在真實網絡數據集karate、dolphin、football和polbooks網絡上進行了100次獨立實驗與LPA對比，實驗結果如圖5所示。四個網絡中，LPA均出現了不同程度的波動，特別在karate網絡中LPA算法的模塊度出現了零值。相比之下，本文算法在100次實驗中保持了相同的群落劃分結果，且模塊化程度基本都高于LPA。

悲慘世界人物關系網絡由77個節點、254條邊構成，節點表示小說中的人物角色，邊表示兩個角色同時出現在同一章節。使用DPNS-LPA算法對悲慘世界人物關系網絡的劃分結果如圖6所示，DPNS-LPA將人物關系網絡劃分為3個社區，對應主人公人生路上的三個重要階段。3個社區的核心節點0、11和48分別對應小說中的主要人物Myriel、 Jean valjean和Gavroche。節點11位于整個網絡的核心，代表小說中的主人公冉阿讓；節點0是主人公人生路上的指路人，對應小說中的主教米里哀；加夫羅契對應節點48，以節點48為核心形成的社區主要描述主人公冉阿讓與德納第夫婦一家之間發生的人物關系。通過與小說人物關系的對應可以發現，使用DPNS-LPA算法的劃分結果可以真實反映小說中的主要人物關系，展示的人物層次結構更加清晰。

4 結束語

本文提出一種基于密度峰值的標簽傳播社區發現算法用于復雜網絡社區發現，算法包括社區中心的確定和外圍節點的標簽傳播兩個過程。社區中心的確定引入了密度峰值聚類算法，所提出的節點局部相似度指標綜合考慮了大度節點不利指標、Jaccard指標和度為1節點的結構特性，可以更好地度量節點之間的局部聯系。外圍節點的標簽傳播過程主要針對尚未達到穩定狀態的節點進行二次更新，為避免節點啟動順序的隨機性，采用PageRank指標評估節點的重要性；更新過程中根據所提出的兩種更新規則對網絡中的所有不穩定節點的標簽進行更新，從而獲得最終的社區劃分結果。在多組人工網絡和合成網絡數據集上的實驗結果表明，本文算法發現的社區質量優于對比算法，可以得到更加合理的社區結構。未來將進一步優化該算法使其可以發現復雜網絡中的重疊社區結構。

參考文獻：

［1］Amelio A，Pizzuti C. Overlapping community discovery methods： a survey ［M］//Social Networks： Analysis and Case Studies. Vienna： Springer，2014： 105-125.

［2］李輝，陳福才，張建朋，等. 復雜網絡中的社團發現算法綜述 ［J］. 計算機應用研究，2021，38（6）： 1611-1618. （Li Hui，Chen Fucai，Zhang Jianpeng，et al. Survey of community detection algorithm in complex network ［J］. Application Research of Computers，2021，38（6）： 1611-1618.）

［3］黃春林，劉興武，鄧明華，等. 復雜網絡上疾病傳播溯源算法綜述 ［J］. 計算機學報，2018，41（6）： 1156-1179. （Huang Chunlin，Liu Xingwu，Deng Minghua，et al. A survey on algorithm for epidemic source identification on complex networks ［J］. Chinese Journal Computers，2018，41（6）： 1156-1179.）

［4］Raghavan U N，Albert R，Kumara S. Near linear time algorithm to detect community structures in large-scale networks ［J］. Physical Review E，2007，76（3）： article ID 036106.

［5］Rodriguez A，Laio A. Machine learning. Clustering by fast search and find of density peaks ［J］. Science，2014，344（6191）： 1492-1496.

［6］馬健，劉峰，李紅輝，等. 采用PageRank和節點聚類系數的標簽傳播重疊社區發現算法 ［J］. 國防科技大學學報，2019，41（1）： 183-190. （Ma Jian，Liu Feng，Li Honghui，et al. Overlapping community detection algorithm by label propagation using PageRenk and node clustering coefficients ［J］. Journal of National University of Defense，2019，41（1）： 183-190.）

［7］Xing Yan，Meng Fangrong，Zhou Yong，et al. A node influence based label propagation algorithm for community detection in networks ［J］. The Scientific World Journal，2014，2014： article ID 627581.

［8］Kong Hanzhang，Kang Qinma，Liu Chao，et al. An improved label propagation algorithm based on node intimacy for community detection in networks ［J］. International Journal of Modern Physics B，2018，32（25）： article ID 1850279.

［9］Aghaalizadeh S，Afshord S T，Bouyer A，et al. Improving the stability of label propagation algorithm by propagating from low-significance nodes for community detection in social networks ［J］. Computing，2021，104（1）： 21-42.

［10］段小虎，曹付元. 基于節點局部相似性的兩階段密度峰值重疊社區發現方法 ［J］. 計算機科學，2022，49（12）： 170-177. （Duan Xiaohu，Cao Fuyuan. Node local similarity based on two-stage density peaks algorithm for overlapping community detection ［J］. Computer Science，2022，49（12）： 170-177.）

［11］陳葉旺，申蓮蓮，鐘才明，等. 密度峰值聚類算法綜述 ［J］. 計算機研究與發展，2020，57（2）： 378-394. （Chen Yewang，Shen Lianlian，Zhong Caiming，et al.Survey on density peak clustering algorithm ［J］. Journal of Computer Research and Development，2020，57（2）： 378-394.）

［12］Ma Haiping，Yang Haiping，Zhou Kefei，et al. A local-to-global scheme-based multi-objective evolutionary algorithm for overlapping community detection on large-scale complex networks ［J］. Neural Computing and Applications，2020，33（10）： 5135-5149.

［13］FIndIk O，zkaynak E. Link prediction based on node weighting in complex networks ［J］. Soft Computing，2021，25（3）： 2467-2482.

［14］李艷麗，周濤. 鏈路預測中的局部相似性指標 ［J］. 電子科技大學學報，2021，50（3）： 422-427. （Li Yanli，Zhou Tao. Local similarity indices in link prediction ［J］. Journal of University of Electronic Science and Technology of China，2021，50（3）： 422-427.）

［15］Li Chuanwei，Chen Hongmei，Li Tianrui，et al. A stable community detection approach for complex network based on density peak clustering and label propagation ［J］. Applied Intelligence，2021，52（2）： 1188-1208.

［16］Chakraborty T，Dalmia A，Mukherjee A，et al. Metrics for community analysis：a survey［J］.ACM Computing Surveys，2017，50（4）：1-37.

［17］喬少杰，郭俊，韓楠，等. 大規模復雜網絡社區并行發現算法 ［J］. 計算機學報，2017，40（3）： 687-700. （Qiao Shaojie，Guo Jun，Han Nan，et al. Parallel algorithm for discovering communities in large-scale complex networks ［J］. Chinese Journal Computers，2017，40（3）： 687-700.）

［18］Ding Xiaoyu，Yang Hailu，Zhang Jianpei，et al. CEO： identifying overlapping communities via construction，expansion and optimization ［J］. Information Sciences，2022，596： 93-118.

［19］Lancichinetti A，Fortunato S，Radicchi F. Benchmark graphs for testing community detection algorithms ［J］. Physical Review E，2008，78（4）： article ID 046110.