摘 要：針對(duì)標(biāo)簽傳播算法中節(jié)點(diǎn)啟動(dòng)順序和更新標(biāo)簽的隨機(jī)性造成的結(jié)果不穩(wěn)定問(wèn)題，提出一種新標(biāo)簽傳播算法用于復(fù)雜網(wǎng)絡(luò)社區(qū)檢測(cè)（density peaks and node similarity，DPNS-LPA），包括社區(qū)中心的確定和外圍節(jié)點(diǎn)的標(biāo)簽傳播。首先利用大度節(jié)點(diǎn)不利指標(biāo)、Jaccard指標(biāo)和度為1節(jié)點(diǎn)的結(jié)構(gòu)特性刻畫(huà)節(jié)點(diǎn)局部相似性指標(biāo)，并用此指標(biāo)度量節(jié)點(diǎn)間距離和解決最大標(biāo)簽相同時(shí)的隨機(jī)選擇；然后引入改進(jìn)的密度峰值聚類(lèi)算法尋找社區(qū)中心，確定社區(qū)數(shù)量；最后基于社區(qū)中心和外圍節(jié)點(diǎn)的標(biāo)簽傳播，得到最終的社區(qū)劃分結(jié)果。通過(guò)人工網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)上的實(shí)驗(yàn)，結(jié)果表明標(biāo)準(zhǔn)化互信息、模塊度和D-score指標(biāo)值優(yōu)于對(duì)比算法，所提出的算法可以有效發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)，且魯棒性更高。

關(guān)鍵詞：密度峰值聚類(lèi)；局部相似度；標(biāo)簽傳播；社區(qū)發(fā)現(xiàn)

中圖分類(lèi)號(hào)：O157.5 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：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

研究復(fù)雜網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)和特征，有助于人們深入了解復(fù)雜系統(tǒng)的功能及演化過(guò)程［1］。一般來(lái)說(shuō)，網(wǎng)絡(luò)中的社區(qū)內(nèi)部節(jié)點(diǎn)之間聯(lián)系緊密，社區(qū)之間連接稀疏［2］。因此，借助社區(qū)結(jié)構(gòu)的特征研究網(wǎng)絡(luò)中成員之間的差異和聯(lián)系，對(duì)于復(fù)雜網(wǎng)絡(luò)分析和實(shí)際應(yīng)用的發(fā)展具有重要作用［3］。

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

1 相關(guān)工作

1.1 標(biāo)簽傳播算法

LPA算法不依賴(lài)自由參數(shù)和目標(biāo)函數(shù)，主要根據(jù)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)傳播節(jié)點(diǎn)信息。初始時(shí)為網(wǎng)絡(luò)中的所有節(jié)點(diǎn)分配一個(gè)唯一的標(biāo)簽，然后逐次迭代將一個(gè)節(jié)點(diǎn)的標(biāo)簽更新為其鄰居的標(biāo)簽。標(biāo)簽傳播算法具有簡(jiǎn)單、高效的優(yōu)點(diǎn)，但其節(jié)點(diǎn)啟動(dòng)順序和更新標(biāo)簽的隨機(jī)性易造成社區(qū)劃分結(jié)果不穩(wěn)定。針對(duì)LPA算法的不足，提出了多種算法。Xing等人［7］基于K-shell的概念，提出一種基于節(jié)點(diǎn)影響力的標(biāo)簽傳播算法（node influence based label propagation algorithm，NIBLPA）。該算法根據(jù)節(jié)點(diǎn)的影響力值確定節(jié)點(diǎn)的更新順序，當(dāng)存在多個(gè)最大標(biāo)簽時(shí)，引入標(biāo)簽影響力計(jì)算公式來(lái)計(jì)算各個(gè)最大標(biāo)簽的影響力，從而避免隨機(jī)選擇一個(gè)標(biāo)簽的問(wèn)題。LPA-intimacy（label propa-gation algorithm based on node intimacy）算法［8］通過(guò)親密度矩陣評(píng)估節(jié)點(diǎn)的重要性，根據(jù)節(jié)點(diǎn)的重要性降序更新節(jié)點(diǎn)以解決節(jié)點(diǎn)啟動(dòng)順序的隨機(jī)性問(wèn)題。對(duì)于每個(gè)待更新節(jié)點(diǎn)，根據(jù)其鄰居中最有影響力的標(biāo)簽作為其更新標(biāo)簽，以解決多個(gè)標(biāo)簽出現(xiàn)頻次相同時(shí)的隨機(jī)選擇問(wèn)題。

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

1.2 密度峰值聚類(lèi)算法

綜上可知，密度峰值算法雖然可以識(shí)別任意形狀的簇，但存在一些不足，即截?cái)嗑嚯x需要人為設(shè)置和中心點(diǎn)的選擇存在主觀性［11］。此外，基于坐標(biāo)計(jì)算節(jié)點(diǎn)距離的指標(biāo)無(wú)法直接應(yīng)用于復(fù)雜網(wǎng)絡(luò)社區(qū)檢測(cè)。一些學(xué)者通過(guò)改進(jìn)密度峰值聚類(lèi)算法將其應(yīng)用于社區(qū)發(fā)現(xiàn)。段小虎等人［10］結(jié)合大度節(jié)點(diǎn)有利指標(biāo)與連接貢獻(xiàn)度來(lái)度量節(jié)點(diǎn)距離，為避免人工決策，利用切比雪夫不等式來(lái)選擇社區(qū)中心點(diǎn)，但標(biāo)準(zhǔn)差系數(shù)ε需人為給定且計(jì)算距離的時(shí)間復(fù)雜度較高。Ma等人［12］基于Salton指標(biāo)定義節(jié)點(diǎn)間的相似度，節(jié)點(diǎn)間的距離通過(guò)相似度的倒數(shù)來(lái)衡量，該方法雖然減少了計(jì)算節(jié)點(diǎn)距離的時(shí)間復(fù)雜度，但設(shè)計(jì)節(jié)點(diǎn)相似度時(shí)局部信息利用不全面，只考慮了節(jié)點(diǎn)間有共同鄰居的情況。

2 基于密度峰值的標(biāo)簽傳播社區(qū)發(fā)現(xiàn)算法

針對(duì)靜態(tài)無(wú)向網(wǎng)絡(luò)，本文設(shè)計(jì)了一種基于密度峰值的標(biāo)簽傳播社區(qū)發(fā)現(xiàn)算法，該算法主要包括：

a）改進(jìn)密度峰值聚類(lèi)算法確定社區(qū)中心節(jié)點(diǎn)，作為標(biāo)簽傳播算法的輸入。包括結(jié)合改進(jìn)的Jaccard指標(biāo)、大度節(jié)點(diǎn)不利指標(biāo)和度為1的節(jié)點(diǎn)的結(jié)構(gòu)特性來(lái)定義節(jié)點(diǎn)相似度，用于度量節(jié)點(diǎn)間距離和解決多個(gè)標(biāo)簽出現(xiàn)頻次相同時(shí)的隨機(jī)選擇問(wèn)題。通過(guò)網(wǎng)格搜索確定切比雪夫不等式中的標(biāo)準(zhǔn)差系數(shù)ε，以解決系數(shù)ε人為給定的主觀性。

b）提出外圍節(jié)點(diǎn)的概念和外圍節(jié)點(diǎn)標(biāo)簽更新的兩種規(guī)則，并利用PageRank指標(biāo)度量外圍節(jié)點(diǎn)的重要性，以解決標(biāo)簽傳播中節(jié)點(diǎn)啟動(dòng)順序的隨機(jī)性。

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

2.1 社區(qū)中心節(jié)點(diǎn)的確定

本文通過(guò)改進(jìn)密度峰值聚類(lèi)算法中的局部密度和節(jié)點(diǎn)距離度量指標(biāo)，使其能直接用于復(fù)雜網(wǎng)絡(luò)社區(qū)檢測(cè)。在得到局部密度和節(jié)點(diǎn)最小距離的乘積后，通過(guò)網(wǎng)絡(luò)搜索來(lái)確定切比雪夫不等式中的標(biāo)準(zhǔn)差系數(shù)ε，從而自動(dòng)篩選出社區(qū)中心節(jié)點(diǎn)。以下是確定社區(qū)中心節(jié)點(diǎn)所涉及的相關(guān)定義。

1）節(jié)點(diǎn)局部密度

在復(fù)雜網(wǎng)絡(luò)中，節(jié)點(diǎn)的密度大小不僅與節(jié)點(diǎn)領(lǐng)導(dǎo)的鄰居數(shù)量有關(guān)，而且也與鄰居節(jié)點(diǎn)之間聯(lián)系的緊密性息息相關(guān)。節(jié)點(diǎn)領(lǐng)導(dǎo)的鄰居數(shù)量越多，其影響力就越強(qiáng)，鄰居節(jié)點(diǎn)之間的連邊越多，則該節(jié)點(diǎn)凝聚周?chē)?jié)點(diǎn)的能力就越強(qiáng)。因此，本文綜合考慮節(jié)點(diǎn)在網(wǎng)絡(luò)中的領(lǐng)導(dǎo)力和凝聚力來(lái)設(shè)計(jì)局部密度指標(biāo)，即

2.2 社區(qū)中心和外圍節(jié)點(diǎn)的標(biāo)簽傳播

2.2.1 初始社區(qū)的形成

由2.1節(jié)得到的復(fù)雜網(wǎng)絡(luò)社區(qū)中心節(jié)點(diǎn)形成初始社區(qū)。即將各社區(qū)中心節(jié)點(diǎn)標(biāo)簽傳播至其鄰居，由各個(gè)中心節(jié)點(diǎn)及鄰居構(gòu)成初始社區(qū)。

2.2.2 外圍節(jié)點(diǎn)的標(biāo)簽傳播

如果一個(gè)節(jié)點(diǎn)有70%的鄰居標(biāo)簽與該節(jié)點(diǎn)的標(biāo)簽不同，則將該節(jié)點(diǎn)定義為外圍節(jié)點(diǎn)。參數(shù)確定為70%（即0.7），將在3.3節(jié)給出詳細(xì)闡述。

由于2.2.1小節(jié)所形成的初始社區(qū)不能完全覆蓋網(wǎng)絡(luò)中的所有節(jié)點(diǎn)，且社區(qū)中心節(jié)點(diǎn)的鄰居標(biāo)簽更新過(guò)于簡(jiǎn)單，若不對(duì)其進(jìn)行檢查易造成累積效應(yīng)，導(dǎo)致最終社區(qū)劃分結(jié)果質(zhì)量偏低。因此，本文對(duì)網(wǎng)絡(luò)中的所有節(jié)點(diǎn)進(jìn)行檢查，將滿足外圍節(jié)點(diǎn)概念的節(jié)點(diǎn)加入集合D中，從而對(duì)未覆蓋的節(jié)點(diǎn)和已在社區(qū)中的節(jié)點(diǎn)進(jìn)行標(biāo)簽更新。

研究表明，節(jié)點(diǎn)的啟動(dòng)順序會(huì)影響算法的性能。為避免節(jié)點(diǎn)啟動(dòng)順序的隨機(jī)性，采用Python庫(kù)中的PageRank指標(biāo)來(lái)衡量節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要性，PageRank值越大，節(jié)點(diǎn)重要性越高。

2.2.3 標(biāo)簽更新規(guī)則

根據(jù)PageRank值對(duì)外圍節(jié)點(diǎn)進(jìn)行排序，并進(jìn)行標(biāo)簽更新。外圍節(jié)點(diǎn)的標(biāo)簽更新有兩種更新規(guī)則：a）若出現(xiàn)頻次最高的鄰居標(biāo)簽唯一時(shí)，則將外圍節(jié)點(diǎn)的標(biāo)簽更新為最高頻次的鄰居標(biāo)簽；b）若出現(xiàn)頻次最高的鄰居標(biāo)簽不唯一時(shí)，需分別計(jì)算外圍節(jié)點(diǎn)與這些標(biāo)簽對(duì)應(yīng)節(jié)點(diǎn)之間的相似度，將外圍節(jié)點(diǎn)的標(biāo)簽更新為相似度高的鄰居標(biāo)簽。

以圖2為例來(lái)說(shuō)明外圍節(jié)點(diǎn)的標(biāo)簽更新過(guò)程。

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

為驗(yàn)證本文算法的有效性，將所提出的算法與改進(jìn)的標(biāo)簽傳播算法CSLPR［9］、NIBLPA［7］、LPA-intimacy［8］、基于密度峰值的社區(qū)發(fā)現(xiàn)算法 LSDPC［10］和經(jīng)典標(biāo)簽傳播算法LPA［4］在真實(shí)網(wǎng)絡(luò)和合成網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行對(duì)比。

3.1 評(píng)價(jià)指標(biāo)

3.2 數(shù)據(jù)集

本文選取了六個(gè)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集和六組LFR合成網(wǎng)絡(luò)數(shù)據(jù)集對(duì)所提算法進(jìn)行研究。

真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集分別為空手道俱樂(lè)部網(wǎng)絡(luò)（karate）、海豚社會(huì)網(wǎng)絡(luò)（dolphin）、政治書(shū)籍網(wǎng)絡(luò)（polbooks）、足球聯(lián)賽網(wǎng)絡(luò)（football）、美國(guó)電網(wǎng)網(wǎng)絡(luò)（power grid）和安然郵件網(wǎng)絡(luò)（Email Enron），具體如表1所示。

LFR基準(zhǔn)是由Lancichinetti等人［19］提出的，可以控制節(jié)點(diǎn)度分布和社區(qū)大小分布，生成與真實(shí)網(wǎng)絡(luò)結(jié)構(gòu)相似的網(wǎng)絡(luò)數(shù)據(jù)集。因此，常用于復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法的對(duì)比實(shí)驗(yàn)中。本文通過(guò)改變網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)、社區(qū)大小生成六組LFR基準(zhǔn)網(wǎng)絡(luò)，具體如表2所示。

參數(shù)K為節(jié)點(diǎn)的平均度，max（k）為節(jié)點(diǎn)的最大度；min（c）為社區(qū)的最小規(guī)模，max（c）為社區(qū)的最大規(guī)模；mu為混合參數(shù)，決定網(wǎng)絡(luò)的清晰度，其值越大，網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)越難以識(shí)別。

3.3 參數(shù)的確定

為確定外圍節(jié)點(diǎn)的數(shù)量，同時(shí)保證算法性能較優(yōu)，在LFR1和LFR2合成網(wǎng)絡(luò)上進(jìn)行實(shí)驗(yàn)，算法的性能使用標(biāo)準(zhǔn)化互信息NMI值進(jìn)行評(píng)價(jià)，結(jié)果如圖3所示。實(shí)驗(yàn)結(jié)果表明，在LFR1網(wǎng)絡(luò)中，參數(shù)0.1≤≤0.7時(shí)，NMI值均達(dá)到了1，當(dāng)參數(shù)增加至0.8時(shí)，算法性能出現(xiàn)下降。同時(shí)觀察外圍節(jié)點(diǎn)數(shù)量的變化，隨著參數(shù)的增加，待更新的外圍節(jié)點(diǎn)數(shù)量逐次下降，當(dāng)增加到0.7時(shí)，下降幅度出現(xiàn)緩和，即外圍節(jié)點(diǎn)的數(shù)量開(kāi)始穩(wěn)定。LFR2網(wǎng)絡(luò)中，當(dāng)增加至0.8時(shí)，NMI值也呈現(xiàn)了LFR1網(wǎng)絡(luò)中同樣的現(xiàn)象，即NMI值開(kāi)始出現(xiàn)下降。因此，為減少待更新外圍節(jié)點(diǎn)的數(shù)量，同時(shí)使NMI值最高，將參數(shù)設(shè)置為0.7較為合理，即NMI曲線的拐點(diǎn)對(duì)應(yīng)的參數(shù)值。

3.4 人工網(wǎng)絡(luò)分析

人工網(wǎng)絡(luò)數(shù)據(jù)集中選取LFR3～LFR6四組基準(zhǔn)網(wǎng)絡(luò)共32個(gè)網(wǎng)絡(luò)作為實(shí)驗(yàn)數(shù)據(jù)集，標(biāo)準(zhǔn)化互信息NMI作為評(píng)價(jià)指標(biāo)。實(shí)驗(yàn)結(jié)果如圖4所示，橫坐標(biāo)表示混合參數(shù)mu的各個(gè)取值，縱坐標(biāo)表示標(biāo)準(zhǔn)化互信息NMI值。LSDPC算法中的標(biāo)準(zhǔn)差系數(shù)ε設(shè)為0.6，最近鄰參數(shù)k設(shè)置為20。

分析圖4可以看出，隨著混合參數(shù)mu的增加，幾種算法在四組網(wǎng)絡(luò)中均出現(xiàn)了不同程度的下降。在mult;0.5時(shí)，各算法的NMI值較高；當(dāng)mugt;0.5時(shí)，準(zhǔn)確率均出現(xiàn)了下降，其中CSLPR和LPA對(duì)參數(shù)mu的變化最為明顯；在mu≥0.7時(shí)，四組網(wǎng)絡(luò)中的NMI值均為0。LSDPC算法在網(wǎng)絡(luò)結(jié)構(gòu)復(fù)雜時(shí)的性能優(yōu)于其他算法。對(duì)比合成網(wǎng)絡(luò)LFR3、LFR4或合成網(wǎng)絡(luò)LFR5、LFR6，社區(qū)尺寸增加后，幾種算法在mu＞0.4時(shí)，NMI值下降速度增快；隨著節(jié)點(diǎn)數(shù)的增加，幾種算法的NMI值均有所增加。

對(duì)比CSLPR算法在四組網(wǎng)絡(luò)中的表現(xiàn)可以發(fā)現(xiàn)，該算法在社區(qū)尺寸較大時(shí)的社區(qū)劃分結(jié)果較好，但不適用于網(wǎng)絡(luò)結(jié)構(gòu)模糊的網(wǎng)絡(luò)，在混合參數(shù)mugt;0.5時(shí)，NMI值基本為0。

LPA存在隨機(jī)性，在LFR3、LFR4和LFR6合成網(wǎng)絡(luò)上，出現(xiàn)了NMI值振蕩的現(xiàn)象，魯棒性低于本文算法。NIBLPA和LPA-intimacy算法在四組合成網(wǎng)絡(luò)上的NMI值低于本文算法，當(dāng)mu≥0.7時(shí)，其N(xiāo)MI值略大于本文算法。LSDPC算法計(jì)算節(jié)點(diǎn)距離的時(shí)間復(fù)雜度較高且受標(biāo)準(zhǔn)差系數(shù)ε影響較大，ε選取的合理性決定了最終社區(qū)劃分的質(zhì)量，如在LFR3、LFR4合成網(wǎng)絡(luò)上，其N(xiāo)MI值總體低于其他算法。

綜上所述，在不同參數(shù)生成的合成網(wǎng)絡(luò)數(shù)據(jù)集上，本文提出的DPNS-LPA算法的社區(qū)劃分結(jié)果更好。

3.5 真實(shí)網(wǎng)絡(luò)分析

真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上采用模塊度Q進(jìn)行算法對(duì)比，設(shè)置LSDPC算法中的標(biāo)準(zhǔn)差系數(shù)ε為1，k為各個(gè)網(wǎng)絡(luò)的平均度，實(shí)驗(yàn)結(jié)果如表3所示。

由表3可以看出，LSDPC算法在六個(gè)網(wǎng)絡(luò)數(shù)據(jù)集上的模塊度最低，原因是LSDPC算法尋找社區(qū)中心節(jié)點(diǎn)時(shí)依賴(lài)于標(biāo)準(zhǔn)差系數(shù)，而標(biāo)準(zhǔn)差系數(shù)又決定了最終選擇出的社區(qū)中心節(jié)點(diǎn)個(gè)數(shù)，若選擇出的社區(qū)中心個(gè)數(shù)與真實(shí)情況相差較大，則會(huì)導(dǎo)致社區(qū)劃分結(jié)果與真實(shí)網(wǎng)絡(luò)結(jié)構(gòu)相差較大。比如在karate網(wǎng)絡(luò)上只識(shí)別出一個(gè)社區(qū)中心點(diǎn)，導(dǎo)致模塊度為0。本文算法在karate、dolphin、polbooks、football和Email Enron這五個(gè)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上的模塊度Q均優(yōu)于其他五種算法。在power grid數(shù)據(jù)集上，本文算法的Q值小于CSLPR算法，但都優(yōu)于其他三種算法。整體來(lái)看，所提出的算法在許多真實(shí)網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果最優(yōu)，CSLPR算法次之。

為測(cè)試算法在評(píng)估社區(qū)數(shù)量方面的性能，對(duì)已知真實(shí)社區(qū)個(gè)數(shù)的數(shù)據(jù)集采用D-score指標(biāo)來(lái)對(duì)比各個(gè)算法的社區(qū)劃分結(jié)果，實(shí)驗(yàn)結(jié)果如表4所示。

DPNS-LPA在四組已知真實(shí)社區(qū)劃分的網(wǎng)絡(luò)中，D-score值基本低于對(duì)比算法，說(shuō)明本文算法發(fā)現(xiàn)的社區(qū)個(gè)數(shù)與真實(shí)情況更為接近。

為進(jìn)一步驗(yàn)證本文算法的魯棒性，在真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集karate、dolphin、football和polbooks網(wǎng)絡(luò)上進(jìn)行了100次獨(dú)立實(shí)驗(yàn)與LPA對(duì)比，實(shí)驗(yàn)結(jié)果如圖5所示。四個(gè)網(wǎng)絡(luò)中，LPA均出現(xiàn)了不同程度的波動(dòng)，特別在karate網(wǎng)絡(luò)中LPA算法的模塊度出現(xiàn)了零值。相比之下，本文算法在100次實(shí)驗(yàn)中保持了相同的群落劃分結(jié)果，且模塊化程度基本都高于LPA。

悲慘世界人物關(guān)系網(wǎng)絡(luò)由77個(gè)節(jié)點(diǎn)、254條邊構(gòu)成，節(jié)點(diǎn)表示小說(shuō)中的人物角色，邊表示兩個(gè)角色同時(shí)出現(xiàn)在同一章節(jié)。使用DPNS-LPA算法對(duì)悲慘世界人物關(guān)系網(wǎng)絡(luò)的劃分結(jié)果如圖6所示，DPNS-LPA將人物關(guān)系網(wǎng)絡(luò)劃分為3個(gè)社區(qū)，對(duì)應(yīng)主人公人生路上的三個(gè)重要階段。3個(gè)社區(qū)的核心節(jié)點(diǎn)0、11和48分別對(duì)應(yīng)小說(shuō)中的主要人物Myriel、 Jean valjean和Gavroche。節(jié)點(diǎn)11位于整個(gè)網(wǎng)絡(luò)的核心，代表小說(shuō)中的主人公冉阿讓?zhuān)还?jié)點(diǎn)0是主人公人生路上的指路人，對(duì)應(yīng)小說(shuō)中的主教米里哀；加夫羅契對(duì)應(yīng)節(jié)點(diǎn)48，以節(jié)點(diǎn)48為核心形成的社區(qū)主要描述主人公冉阿讓與德納第夫婦一家之間發(fā)生的人物關(guān)系。通過(guò)與小說(shuō)人物關(guān)系的對(duì)應(yīng)可以發(fā)現(xiàn)，使用DPNS-LPA算法的劃分結(jié)果可以真實(shí)反映小說(shuō)中的主要人物關(guān)系，展示的人物層次結(jié)構(gòu)更加清晰。

4 結(jié)束語(yǔ)

本文提出一種基于密度峰值的標(biāo)簽傳播社區(qū)發(fā)現(xiàn)算法用于復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)，算法包括社區(qū)中心的確定和外圍節(jié)點(diǎn)的標(biāo)簽傳播兩個(gè)過(guò)程。社區(qū)中心的確定引入了密度峰值聚類(lèi)算法，所提出的節(jié)點(diǎn)局部相似度指標(biāo)綜合考慮了大度節(jié)點(diǎn)不利指標(biāo)、Jaccard指標(biāo)和度為1節(jié)點(diǎn)的結(jié)構(gòu)特性，可以更好地度量節(jié)點(diǎn)之間的局部聯(lián)系。外圍節(jié)點(diǎn)的標(biāo)簽傳播過(guò)程主要針對(duì)尚未達(dá)到穩(wěn)定狀態(tài)的節(jié)點(diǎn)進(jìn)行二次更新，為避免節(jié)點(diǎn)啟動(dòng)順序的隨機(jī)性，采用PageRank指標(biāo)評(píng)估節(jié)點(diǎn)的重要性；更新過(guò)程中根據(jù)所提出的兩種更新規(guī)則對(duì)網(wǎng)絡(luò)中的所有不穩(wěn)定節(jié)點(diǎn)的標(biāo)簽進(jìn)行更新，從而獲得最終的社區(qū)劃分結(jié)果。在多組人工網(wǎng)絡(luò)和合成網(wǎng)絡(luò)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，本文算法發(fā)現(xiàn)的社區(qū)質(zhì)量?jī)?yōu)于對(duì)比算法，可以得到更加合理的社區(qū)結(jié)構(gòu)。未來(lái)將進(jìn)一步優(yōu)化該算法使其可以發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)中的重疊社區(qū)結(jié)構(gòu)。

參考文獻(xiàn)：

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

［2］李輝，陳福才，張建朋，等. 復(fù)雜網(wǎng)絡(luò)中的社團(tuán)發(fā)現(xiàn)算法綜述 ［J］. 計(jì)算機(jī)應(yīng)用研究，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］黃春林，劉興武，鄧明華，等. 復(fù)雜網(wǎng)絡(luò)上疾病傳播溯源算法綜述 ［J］. 計(jì)算機(jī)學(xué)報(bào)，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和節(jié)點(diǎn)聚類(lèi)系數(shù)的標(biāo)簽傳播重疊社區(qū)發(fā)現(xiàn)算法 ［J］. 國(guó)防科技大學(xué)學(xué)報(bào)，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］段小虎，曹付元. 基于節(jié)點(diǎn)局部相似性的兩階段密度峰值重疊社區(qū)發(fā)現(xiàn)方法 ［J］. 計(jì)算機(jī)科學(xué)，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］陳葉旺，申蓮蓮，鐘才明，等. 密度峰值聚類(lèi)算法綜述 ［J］. 計(jì)算機(jī)研究與發(fā)展，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］李艷麗，周濤. 鏈路預(yù)測(cè)中的局部相似性指標(biāo) ［J］. 電子科技大學(xué)學(xué)報(bào)，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］喬少杰，郭俊，韓楠，等. 大規(guī)模復(fù)雜網(wǎng)絡(luò)社區(qū)并行發(fā)現(xiàn)算法 ［J］. 計(jì)算機(jī)學(xué)報(bào)，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，F(xiàn)ortunato S，Radicchi F. Benchmark graphs for testing community detection algorithms ［J］. Physical Review E，2008，78（4）： article ID 046110.