王本鈺，顧益軍，彭舒凡

中國人民公安大學(xué) 信息網(wǎng)絡(luò)安全學(xué)院，北京100032

現(xiàn)實(shí)生活中，許多復(fù)雜系統(tǒng)都被描述成復(fù)雜網(wǎng)絡(luò)的形式，例如生物網(wǎng)絡(luò)[1]、引文網(wǎng)絡(luò)[2]、社交網(wǎng)絡(luò)[3]。復(fù)雜網(wǎng)絡(luò)通常由多個社區(qū)組成，同一社區(qū)內(nèi)的節(jié)點(diǎn)聯(lián)系較為緊密，不同社區(qū)之間的節(jié)點(diǎn)聯(lián)系較為松散。社區(qū)發(fā)現(xiàn)便是一個根據(jù)復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)間的關(guān)系，將節(jié)點(diǎn)劃分到各個社區(qū)中的一個過程，有助于研究人員了解復(fù)雜網(wǎng)絡(luò)的組織架構(gòu)和功能。

社區(qū)發(fā)現(xiàn)由于研究方法的不同已經(jīng)總結(jié)形成了許多具有代表性的算法，例如基于網(wǎng)絡(luò)邊介數(shù)的GN（Girvan-Newman）算法[4]，基于標(biāo)簽傳播的社區(qū)發(fā)現(xiàn)算法（label propagation algorithm，LPA）[5]，基于粒子競爭機(jī)制的社區(qū)發(fā)現(xiàn)算法（stochastic competitive learning，SCL）[6]，基于距離動力學(xué)的Attractor 算法[7]，基于圖卷積神經(jīng)網(wǎng)絡(luò)（graph convolution networks，GCN）的社區(qū)深度圖信息極大化算法（community deep graph infomax，CommDGI）[8]，融合遷移學(xué)習(xí)和自編碼器的社區(qū)發(fā)現(xiàn)算法（community detection with deep transitive autoencoder，CDDTA）[9]，基于生成對抗網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)算法（community detection with generative adversarial network，CommunityGAN）[10]。然而這些算法都是無監(jiān)督社區(qū)發(fā)現(xiàn)算法，通常只利用了網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，常常會出現(xiàn)社區(qū)發(fā)現(xiàn)結(jié)果難以解釋、算法性能難以衡量的問題，尤其是當(dāng)網(wǎng)絡(luò)結(jié)構(gòu)不清晰時，無監(jiān)督社區(qū)發(fā)現(xiàn)算法的性能會大幅下降。

為了解決這樣的問題，研究人員通常會采取半監(jiān)督學(xué)習(xí)方式，通過引入一些復(fù)雜網(wǎng)絡(luò)中易于獲取的先驗信息，例如節(jié)點(diǎn)標(biāo)簽信息[11]和成對約束[12-13]等，提高社區(qū)發(fā)現(xiàn)算法的魯棒性和結(jié)果的準(zhǔn)確性。因此近年來標(biāo)簽傳播[14]、隨機(jī)游走[15]、距離動力學(xué)[16]、非負(fù)矩陣分解[17]、粒子競爭機(jī)制[18]等算法中紛紛引入網(wǎng)絡(luò)中的先驗信息，以半監(jiān)督學(xué)習(xí)的方式實(shí)現(xiàn)社區(qū)發(fā)現(xiàn)任務(wù)。Hua等[14]提出了一種基于節(jié)點(diǎn)影響力的半監(jiān)督標(biāo)簽傳播算法（node influence-based label propagation，NILP），通過節(jié)點(diǎn)的度值和局部密度來衡量節(jié)點(diǎn)的影響力，將先驗信息優(yōu)先傳播給影響力大的節(jié)點(diǎn)以控制傳播過程，解決了傳統(tǒng)的標(biāo)簽傳播算法將所有節(jié)點(diǎn)視為等價節(jié)點(diǎn)而忽略重要節(jié)點(diǎn)的問題。Liu等[15]提出了一種基于隨機(jī)游走的半監(jiān)督社區(qū)發(fā)現(xiàn)算法（semi-supervised DeepWalk，SSDW），通過先驗信息改善了傳統(tǒng)隨機(jī)游走過程中的節(jié)點(diǎn)轉(zhuǎn)移概率，實(shí)驗證明SSDW 算法能獲得較好的社區(qū)發(fā)現(xiàn)效果。Fan等[16]提出了一種基于距離動力學(xué)的半監(jiān)督社區(qū)發(fā)現(xiàn)方法Semi-Attractor，結(jié)合先驗信息和網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)來改變節(jié)點(diǎn)之間的距離，實(shí)驗結(jié)果表明該算法不僅提升了社區(qū)發(fā)現(xiàn)的準(zhǔn)確性，而且加快了算法收斂速度。Lu等[17]提出一種融合非負(fù)矩陣分解與奇異值分解的半監(jiān)督社區(qū)發(fā)現(xiàn)算法，通過奇異值分解方法來獲得社區(qū)數(shù)量，然后結(jié)合先驗信息和非負(fù)矩陣分解實(shí)現(xiàn)社區(qū)發(fā)現(xiàn)任務(wù)，實(shí)驗結(jié)果表明可以顯著提高社區(qū)發(fā)現(xiàn)效果。

基于粒子競爭機(jī)制的半監(jiān)督社區(qū)發(fā)現(xiàn)方法最初由Quiles等[19]提出。Quiles等定義了節(jié)點(diǎn)粒子競爭機(jī)制，粒子在網(wǎng)絡(luò)中隨機(jī)游走并且在節(jié)點(diǎn)上互相競爭，通過粒子占據(jù)更多節(jié)點(diǎn)的方式來達(dá)到社區(qū)發(fā)現(xiàn)的目的。Silva等[6]改進(jìn)了粒子競爭機(jī)制中粒子的游走方式，通過結(jié)合粒子隨機(jī)游走和優(yōu)先游走的方式來實(shí)現(xiàn)社區(qū)發(fā)現(xiàn)任務(wù)。Verri等[18]重新定義了粒子競爭機(jī)制，提出了基于邊粒子競爭機(jī)制標(biāo)簽組件展開算法（labeled component unfolding，LCU），通過粒子在網(wǎng)絡(luò)中執(zhí)行游走、吸收、生成步驟來爭奪各類粒子對網(wǎng)絡(luò)中邊的占據(jù)權(quán)以實(shí)現(xiàn)社區(qū)發(fā)現(xiàn)任務(wù)。王本鈺等[20]提出了融合粒子競爭機(jī)制與距離動力學(xué)模型的DDSCL（community detection algorithm based on dynamic distance and stochastic competitive learning）算法，改善了粒子游走初期隨機(jī)性大的問題，實(shí)驗中獲得了不錯的效果。此后，在錯誤標(biāo)簽檢測[21]、動態(tài)社區(qū)發(fā)現(xiàn)[22]、重疊社區(qū)發(fā)現(xiàn)[23]、異常節(jié)點(diǎn)檢測[24]、多層網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)[25]、分類數(shù)量預(yù)測[26]以及圖像分割[27]等各領(lǐng)域中紛紛引入了粒子競爭機(jī)制。粒子競爭機(jī)制的發(fā)展歷程證明了其應(yīng)用于復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)任務(wù)的可行性和有效性。

盡管現(xiàn)有基于粒子競爭機(jī)制的算法在不同場景下展示了其有效性，但是本文在研究中發(fā)現(xiàn)，該類算法仍存在以下不足：

（1）粒子游走過程具有很大的隨機(jī)性，沒有建立粒子游走的傾向性，導(dǎo)致社區(qū)發(fā)現(xiàn)效果差、粒子收斂速度慢。

（2）粒子游走范圍沒有約束條件，粒子在游走過程中容易偏離已占據(jù)節(jié)點(diǎn)，隨著粒子游走次數(shù)增多，社區(qū)發(fā)現(xiàn)效果會越來越差。

（3）現(xiàn)有算法中粒子競爭機(jī)制僅單一存在節(jié)點(diǎn)或者邊上，沒有一種融合節(jié)點(diǎn)粒子競爭機(jī)制和邊粒子競爭機(jī)制的社區(qū)發(fā)現(xiàn)算法。

為了解決上述問題，本文提出了一種基于粒子競爭機(jī)制的半監(jiān)督社區(qū)發(fā)現(xiàn)算法（semi-supervised community detection algorithm based on particle competition，SSPC）。本文的主要貢獻(xiàn)有以下幾點(diǎn)：

（1）結(jié)合節(jié)點(diǎn)之間的交互影響，根據(jù)粒子在節(jié)點(diǎn)上的競爭情況提出轉(zhuǎn)移提出概率和轉(zhuǎn)移接收概率，重新定義粒子游走概率，降低粒子游走過程的隨機(jī)性，建立粒子游走的傾向性，加快粒子收斂速度。

（2）設(shè)置粒子在邊上的重啟機(jī)制，體現(xiàn)粒子在邊上的競爭情況并且有效限制粒子游走范圍，提升社區(qū)發(fā)現(xiàn)效果。

（3）提出了一種融合了節(jié)點(diǎn)粒子競爭機(jī)制和邊粒子競爭機(jī)制的半監(jiān)督社區(qū)發(fā)現(xiàn)算法，并給出關(guān)于SSPC 算法收斂性的數(shù)學(xué)證明。在真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集和LFR 人工基準(zhǔn)網(wǎng)絡(luò)上對SSPC 算法與近幾年具有代表性的社區(qū)發(fā)現(xiàn)算法進(jìn)行實(shí)驗測試比較，發(fā)現(xiàn)該算法可以獲得較好的社區(qū)發(fā)現(xiàn)結(jié)果，同時對主要參數(shù)進(jìn)行了討論。

1 相關(guān)工作

1.1 網(wǎng)絡(luò)基礎(chǔ)知識

給定復(fù)雜網(wǎng)絡(luò)G=(V,E)，其中V是網(wǎng)絡(luò)中節(jié)點(diǎn)的集合，E={e=(i,j)|1 ≤i,j≤n,i≠j}是網(wǎng)絡(luò)中邊的集合，用ij來表示邊e=(i,j)。

記網(wǎng)絡(luò)G的鄰接矩陣A∈RN×N，定義為：

令網(wǎng)絡(luò)G中社區(qū)類別的集合為y={1,2,…,C},其中C表示網(wǎng)絡(luò)中社區(qū)的數(shù)量,yi=c表示節(jié)點(diǎn)i歸屬于c類社區(qū)。令網(wǎng)絡(luò)G中已標(biāo)記的節(jié)點(diǎn)集合為L={v1,v2,…,vl}，其中l(wèi)表示網(wǎng)絡(luò)中已標(biāo)記節(jié)點(diǎn)的數(shù)量。令網(wǎng)絡(luò)G中無標(biāo)記的節(jié)點(diǎn)集合為U={vl+1,vl+2,…,vl+u}，其中u表示網(wǎng)絡(luò)中未標(biāo)記節(jié)點(diǎn)的數(shù)量。因此可得V(G)╞l+u，并且L∩U=?，L∪U=V。由于網(wǎng)絡(luò)中已標(biāo)記節(jié)點(diǎn)的數(shù)量遠(yuǎn)遠(yuǎn)小于無標(biāo)記節(jié)點(diǎn)的數(shù)量，本文假設(shè)l?u，并且每個社區(qū)中至少存在一個已標(biāo)記節(jié)點(diǎn)。

令h(i)={j|j∈V(i≠j)∧(i,j)∈E}，稱h(i)為節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)。

令di=|j|j∈V(i≠j)∧(i,j)∈E|，其中，集合內(nèi)元素的個數(shù)用|*|表示，稱di為節(jié)點(diǎn)i的度。

1.2 粒子競爭機(jī)制

近些年來，隨著粒子競爭機(jī)制的不斷完善，基于粒子競爭機(jī)制的社區(qū)發(fā)現(xiàn)算法在社區(qū)發(fā)現(xiàn)任務(wù)中具有良好的表現(xiàn)，其中以SCL[6]、LCU[19]、DPP（dynamic particle propagation）[22]算法較為顯著。

Silva 等提出了SCL 算法，SCL 算法通過無監(jiān)督的方式實(shí)現(xiàn)社區(qū)發(fā)現(xiàn)任務(wù)。SCL 算法中隨機(jī)放置多個粒子在網(wǎng)絡(luò)中，每個粒子在網(wǎng)絡(luò)中執(zhí)行隨機(jī)游走、優(yōu)先游走、生成等步驟。在隨機(jī)游走步驟中，粒子將以同等的概率向周邊節(jié)點(diǎn)進(jìn)行游走。在優(yōu)先游走步驟中，粒子將會以更高的概率訪問已被該類粒子占據(jù)的節(jié)點(diǎn)。在生成步驟中，粒子每游走到一個節(jié)點(diǎn)上時將會檢查自身的能量狀態(tài)。如果節(jié)點(diǎn)被同類粒子占據(jù)，粒子的能量會增加。如果節(jié)點(diǎn)被其他類粒子占據(jù)，粒子的能量會減少。當(dāng)粒子能量耗盡時，粒子將會執(zhí)行生成步驟。粒子將會在已占據(jù)節(jié)點(diǎn)上重新生成。SCL 算法中每個粒子對應(yīng)一個社區(qū)，以粒子達(dá)到收斂狀態(tài)時每個粒子占據(jù)的節(jié)點(diǎn)來揭示網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)。

Filipe 等提出了LCU 算法，LCU 算法是一個半監(jiān)督社區(qū)發(fā)現(xiàn)算法。LCU 算法中已知網(wǎng)絡(luò)中社區(qū)的類別，并且每個社區(qū)中都有少數(shù)已標(biāo)記的節(jié)點(diǎn)作為先驗信息。在算法初始化階段，會在每個社區(qū)的已標(biāo)記節(jié)點(diǎn)上產(chǎn)生一個粒子，該粒子攜帶的標(biāo)簽信息對應(yīng)所屬社區(qū)的類別。粒子通過既定的規(guī)則在網(wǎng)絡(luò)中執(zhí)行游走、吸收、生成步驟，不同類粒子之間會相互競爭，爭奪粒子對于邊的占據(jù)權(quán)。在游走步驟中，LCU 算法采用類似于SCL 算法中的隨機(jī)游走步驟，粒子將以相等的概率向周邊節(jié)點(diǎn)進(jìn)行游走。在吸收步驟中，粒子向周邊節(jié)點(diǎn)游走時會有一定的概率在邊上被吸收。如果粒子沒有被吸收，粒子將會成功轉(zhuǎn)移到下一個節(jié)點(diǎn)上。粒子被吸收的概率取決于當(dāng)前時刻粒子對于邊的占據(jù)程度，粒子對于邊的支配程度越大，粒子被吸收的可能性越小。在生成步驟中，如果粒子被吸收，粒子將會在該類粒子已標(biāo)記的節(jié)點(diǎn)上重新生成。最終當(dāng)算法達(dá)到收斂條件時，根據(jù)粒子對于邊的占據(jù)程度揭示網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)。

Li 等提出了DPP 算法，DPP 算法中通過粒子在網(wǎng)絡(luò)中執(zhí)行游走、分裂、跳躍步驟改變粒子對于節(jié)點(diǎn)的占據(jù)程度，粒子對于節(jié)點(diǎn)的占據(jù)程度的改變也會影響粒子的運(yùn)動。在游走步驟中，DPP 同樣采取向每個鄰居節(jié)點(diǎn)進(jìn)行同等概率游走的策略。在分裂步驟中，DPP 算法為了解決LCU 算法中粒子數(shù)量需要人為指定的問題，通過粒子在節(jié)點(diǎn)上進(jìn)行分裂的策略，根據(jù)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)自動確定每類粒子的數(shù)量。在跳躍步驟中，粒子向周邊節(jié)點(diǎn)游走時存在一定的概率進(jìn)行跳躍。同類粒子累計訪問邊的次數(shù)越多，粒子越不容易執(zhí)行跳躍步驟。相反，同類粒子訪問邊的次數(shù)越少，粒子越容易執(zhí)行跳躍步驟。經(jīng)過一系列相互作用，DPP 算法可以實(shí)現(xiàn)半監(jiān)督社區(qū)發(fā)現(xiàn)任務(wù)。

2 SSPC 算法

為了提高社區(qū)發(fā)現(xiàn)的準(zhǔn)確性，解決粒子競爭機(jī)制中粒子游走隨機(jī)性大、不能限制粒子游走范圍的問題，本文提出一種融合節(jié)點(diǎn)粒子競爭機(jī)制和邊粒子競爭機(jī)制的半監(jiān)督社區(qū)發(fā)現(xiàn)算法SSPC。SSPC 算法的時間復(fù)雜度和網(wǎng)絡(luò)中節(jié)點(diǎn)和邊的數(shù)量呈線性關(guān)系，因此該算法在提高社區(qū)發(fā)現(xiàn)準(zhǔn)確性的同時在應(yīng)用于大規(guī)模網(wǎng)絡(luò)時也具有很好的擴(kuò)展性，是一個兼顧準(zhǔn)確率和時間復(fù)雜度的算法。該算法主要分為4個階段：（1）初始化階段，SSPC 算法通過網(wǎng)絡(luò)中的先驗信息以半監(jiān)督學(xué)習(xí)的方式在已標(biāo)記的節(jié)點(diǎn)上產(chǎn)生粒子，粒子通過既定的規(guī)則在網(wǎng)絡(luò)中執(zhí)行游走和重啟步驟。（2）游走階段，SSPC 算法結(jié)合節(jié)點(diǎn)之間的交互影響，提出了轉(zhuǎn)移提出概率和轉(zhuǎn)移接收概率，重新定義粒子的游走概率，充分體現(xiàn)粒子在節(jié)點(diǎn)上的競爭關(guān)系，并且建立粒子游走的傾向性，降低粒子游走的隨機(jī)性，加快粒子的收斂速度。（3）重啟階段，為了體現(xiàn)粒子在邊上的競爭關(guān)系并且限制粒子游走范圍，該算法設(shè)置了重啟機(jī)制。當(dāng)粒子在邊上游走時會產(chǎn)生粒子間的競爭，粒子存在一定概率重啟。當(dāng)粒子重啟時，粒子將會基于粒子對于各節(jié)點(diǎn)的占據(jù)程度選擇節(jié)點(diǎn)進(jìn)行重啟。（4）收斂階段，當(dāng)粒子達(dá)到收斂狀態(tài)時，節(jié)點(diǎn)將被某一類粒子所占據(jù)。根據(jù)各類粒子占據(jù)的節(jié)點(diǎn)來揭示網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)。

2.1 初始化階段

初始化階段，SSPC 算法會通過網(wǎng)絡(luò)中的先驗信息在已標(biāo)記節(jié)點(diǎn)上產(chǎn)生一個粒子，同時確定每類粒子在初始化階段對于節(jié)點(diǎn)和邊的占據(jù)程度。

初始化階段，節(jié)點(diǎn)i上的c類粒子數(shù)量定義如下：

其中，L表示已標(biāo)記節(jié)點(diǎn)的集合。

初始化階段，c類粒子對于節(jié)點(diǎn)i的占據(jù)程度定義如下：

初始化階段，c類粒子對于邊ij的占據(jù)程度定義如下：

2.2 游走階段

在LCU、DPP 等基于粒子競爭機(jī)制的社區(qū)發(fā)現(xiàn)算法中，粒子向周邊節(jié)點(diǎn)游走的概率由當(dāng)前粒子所在節(jié)點(diǎn)的度值確定，即粒子向周邊各節(jié)點(diǎn)的游走概率相等，粒子的游走是一個完全隨機(jī)的過程。這樣的游走概率一方面沒有考慮節(jié)點(diǎn)間的交互影響，未能建立粒子游走的傾向性，另一方面完全隨機(jī)的游走概率會導(dǎo)致粒子收斂速度慢，社區(qū)發(fā)現(xiàn)的準(zhǔn)確性差。因此，本文結(jié)合粒子對于當(dāng)前節(jié)點(diǎn)的占據(jù)程度和粒子對于周邊節(jié)點(diǎn)的占據(jù)程度提出轉(zhuǎn)移提出概率Pforward(t)和轉(zhuǎn)移接受概率Paccept(t)，重新定義粒子的游走概率Ptransition(t)。

粒子對于節(jié)點(diǎn)的占據(jù)程度由t時刻該類粒子在節(jié)點(diǎn)上的數(shù)量和各類粒子在節(jié)點(diǎn)上的總數(shù)量的比值表示，因此c類粒子在t時刻對于節(jié)點(diǎn)i的占據(jù)程度定義如下：

其中，表示t時刻，c類粒子在節(jié)點(diǎn)i上的數(shù)量。C代表粒子的種類，即網(wǎng)絡(luò)中社區(qū)的數(shù)量。

各類粒子在t時刻對于節(jié)點(diǎn)i的占據(jù)程度定義如下：

粒子轉(zhuǎn)移概率Ptransition(t)由提出概率Pforward(t)和接收概率Paccept(t)組成，充分考慮了節(jié)點(diǎn)之間的交互影響，并且隨著時間變化而動態(tài)變化，最終收斂達(dá)到一個確定值，c類粒子從節(jié)點(diǎn)i向節(jié)點(diǎn)j進(jìn)行轉(zhuǎn)移的概率定義如下：

其中，ij表示邊e=(i,j)。

提出概率體現(xiàn)了當(dāng)前粒子向周邊節(jié)點(diǎn)提出轉(zhuǎn)移的概率，定義如下：

其中，表示c類粒子在節(jié)點(diǎn)j上的占據(jù)程度，d(i)表示節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)。c類粒子在節(jié)點(diǎn)j上的占據(jù)程度越大，粒子從節(jié)點(diǎn)i向節(jié)點(diǎn)j提出轉(zhuǎn)移的概率越大。

接收概率體現(xiàn)了粒子向周邊節(jié)點(diǎn)進(jìn)行轉(zhuǎn)移時被接收的概率，定義如下：

其中，表示c類粒子在節(jié)點(diǎn)i上的占據(jù)程度，d(j)表示節(jié)點(diǎn)j的鄰居節(jié)點(diǎn)。C類粒子在節(jié)點(diǎn)i上的占據(jù)程度越大，粒子從節(jié)點(diǎn)i向節(jié)點(diǎn)j轉(zhuǎn)移時被接收的概率越大。

最后，將粒子轉(zhuǎn)移概率進(jìn)行歸一化處理，定義如下：

其中，aij表示節(jié)點(diǎn)的連接情況，若節(jié)點(diǎn)之間存在連接，則該值為1，否則為0。

2.3 重啟階段

為體現(xiàn)粒子在邊上的競爭關(guān)系并且限制粒子游走范圍，SSPC 算法中設(shè)立重啟機(jī)制。重啟機(jī)制中，粒子重啟概率和粒子對于邊的占據(jù)程度有關(guān)，c類粒子在t時刻對于邊ij的占據(jù)程度定義如下：

各類粒子在t時刻對于邊ij的占據(jù)程度定義如下：

當(dāng)粒子對于邊的占據(jù)程度越大，該類粒子執(zhí)行重啟步驟的可能性越小，其他類粒子執(zhí)行重啟步驟的可能性越大。因此，在t時刻，c類粒子從節(jié)點(diǎn)i向節(jié)點(diǎn)j游走時重啟的概率定義如下：

其中，為c類粒子在t時刻對于邊ij的占據(jù)程度。λ為重啟執(zhí)行概率參數(shù)，λ∈[0,1]，用來調(diào)節(jié)粒子在邊上的競爭強(qiáng)度和重啟執(zhí)行概率，λ值越大則不同類粒子之間的競爭關(guān)系越強(qiáng)，粒子越容易執(zhí)行重啟步驟。若λ為0，則粒子不會執(zhí)行重啟步驟，粒子將一直執(zhí)行游走步驟。

粒子若執(zhí)行重啟步驟，則下一時刻將會根據(jù)粒子對于節(jié)點(diǎn)的占據(jù)程度選擇節(jié)點(diǎn)進(jìn)行重啟，當(dāng)c類粒子執(zhí)行重啟步驟時，在節(jié)點(diǎn)i上重啟的概率定義如下：

根據(jù)粒子占據(jù)程度選擇節(jié)點(diǎn)進(jìn)行重啟的策略，可以防止粒子在游走過程中陷入局部最優(yōu)，通過局部游走和全局游走相結(jié)合的方式，提高粒子的游走能力。

如果粒子不執(zhí)行重啟步驟，則粒子會成功轉(zhuǎn)移到周邊節(jié)點(diǎn)。粒子重啟機(jī)制保留了復(fù)雜網(wǎng)絡(luò)中產(chǎn)生的全部粒子，保證了粒子控制能力不會因游走失敗而降低。

2.4 收斂階段

經(jīng)過多次的粒子游走、重啟步驟，SSPC 算法將會得到社區(qū)發(fā)現(xiàn)情況。對于一個動力學(xué)算法，需要討論算法的收斂條件。LCU 算法為提高算法運(yùn)算速度，當(dāng)網(wǎng)絡(luò)中粒子游走的次數(shù)等于最大網(wǎng)絡(luò)子圖的直徑長度時算法則收斂。DPP 算法為進(jìn)一步提高算法的運(yùn)算速度，當(dāng)粒子遍歷完網(wǎng)絡(luò)中全部節(jié)點(diǎn)后便停止運(yùn)行算法，輸出社區(qū)發(fā)現(xiàn)結(jié)果。本文提出的SSPC 算法為了獲得準(zhǔn)確的社區(qū)發(fā)現(xiàn)結(jié)果，當(dāng)每條邊上都有一類粒子的占據(jù)程度趨于穩(wěn)定時，則認(rèn)為粒子已經(jīng)達(dá)到了收斂狀態(tài)，停止粒子的游走，輸出社區(qū)發(fā)現(xiàn)結(jié)果，粒子收斂狀態(tài)判定公式定義如下：

2.5 算法收斂性分析

本節(jié)將對SSPC 算法的收斂性進(jìn)行討論。SSPC算法的收斂條件是網(wǎng)絡(luò)中的每條邊上都有一類粒子的占據(jù)程度趨于穩(wěn)定，因此SSPC 算法是一個全局收斂算法。在SSPC 算法中，當(dāng)t→∞時，網(wǎng)絡(luò)中的每條邊和節(jié)點(diǎn)都存在某一類粒子對其的占據(jù)程度達(dá)收斂狀態(tài)，同時粒子轉(zhuǎn)移概率也會趨向于一個確定值，達(dá)到收斂狀態(tài)。

假設(shè)網(wǎng)絡(luò)中存在C類不同的社區(qū)，每個社區(qū)中存在少數(shù)已標(biāo)記節(jié)點(diǎn)，在初始化階段，會在每個社區(qū)已標(biāo)記節(jié)點(diǎn)上產(chǎn)生1 個粒子，粒子種類對應(yīng)社區(qū)的類別。

根據(jù)式（11）可以定義某一類粒子對于某一條邊的占據(jù)程度，因此c類粒子在t時刻對于邊ij的占據(jù)程度定義如下：

根據(jù)式（16），可得c類粒子在t+1 時刻對于邊ij的占據(jù)程度如式（17）所示：

因此，根據(jù)式（17）、式（18）和式（19），可得c類粒子在t+1 時刻對于邊ij的占據(jù)程度如式（20）所示：

接下來討論粒子對于節(jié)點(diǎn)的占據(jù)程度和粒子轉(zhuǎn)移概率的收斂性問題。

在t時刻，節(jié)點(diǎn)i上的c類粒子數(shù)量等于節(jié)點(diǎn)i的周邊節(jié)點(diǎn)轉(zhuǎn)移到節(jié)點(diǎn)i上的c類粒子數(shù)量加上在節(jié)點(diǎn)i上重啟的粒子數(shù)量，因此可得式（24）：

根據(jù)式（5）、式（6）和式（24），可得在t時刻，c類粒子對于節(jié)點(diǎn)i的占據(jù)程度，定義如下：

因此當(dāng)t→∞，根據(jù)式（26），可得在t時刻，c類粒子對于節(jié)點(diǎn)i的占據(jù)程度如式（27）所示：

因此當(dāng)t→∞，粒子對于各節(jié)點(diǎn)的占據(jù)情況也將達(dá)到一個收斂狀態(tài)。

而粒子轉(zhuǎn)移概率Ptransition和粒子對于節(jié)點(diǎn)的占據(jù)程度相關(guān)，因此當(dāng)粒子對于各節(jié)點(diǎn)的占據(jù)程度達(dá)到一個收斂狀態(tài)時，粒子轉(zhuǎn)移概率Ptransition也會達(dá)到一個收斂值。

綜上所述，SSPC 算法是收斂的，具有有效性和可行性。

2.6 算法流程

基于粒子競爭機(jī)制的半監(jiān)督社區(qū)發(fā)現(xiàn)算法SSPC具體方法流程見算法1。

算法1SSPC 算法

2.7 時間復(fù)雜度

SSPC 算法在粒子游走階段計算粒子游走概率時，需要計算粒子對于當(dāng)前節(jié)點(diǎn)的占據(jù)程度和粒子對于當(dāng)前節(jié)點(diǎn)的鄰居節(jié)點(diǎn)的占據(jù)程度，因此時間復(fù)雜度為O(CV)，其中為網(wǎng)絡(luò)中節(jié)點(diǎn)的平均度數(shù)。因為復(fù)雜網(wǎng)絡(luò)中≈，所以計算粒子游走概率的時間復(fù)雜度為O(2CE)。計算粒子在邊上的重啟概率需要計算粒子對于邊的占據(jù)程度，因此時間復(fù)雜度為O(CE)。計算網(wǎng)絡(luò)中重啟的粒子數(shù)量時需要計算網(wǎng)絡(luò)各節(jié)點(diǎn)上粒子的數(shù)量和粒子源節(jié)點(diǎn)上粒子的占據(jù)程度，因此時間復(fù)雜度為O(l+V)。因為網(wǎng)絡(luò)中已標(biāo)記節(jié)點(diǎn)的數(shù)量遠(yuǎn)遠(yuǎn)小于網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)量，所以l?V，計算網(wǎng)絡(luò)中重啟的粒子數(shù)量的時間復(fù)雜度為O(V)。更新粒子對于節(jié)點(diǎn)的占據(jù)程度和粒子對于邊的占據(jù)程度的時間復(fù)雜度為O(E+V)。在判斷粒子是否達(dá)到收斂狀態(tài)并輸出算法結(jié)果時的時間復(fù)雜度為O(CE),因此該算法的總時間復(fù)雜度為O(2CE+CE+V+E+V+CE)≈O(K(V+E))，其中K為常數(shù)項。SSPC 算法的時間復(fù)雜度和網(wǎng)絡(luò)中節(jié)點(diǎn)和邊的數(shù)量呈線性關(guān)系，因此該算法在應(yīng)用于大規(guī)模網(wǎng)絡(luò)時具有很好的擴(kuò)展性。

3 實(shí)驗

為了驗證本文算法的可行性與有效性，將SSPC算法與近幾年具有代表性的社區(qū)發(fā)現(xiàn)算法在真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集和LFR 人工基準(zhǔn)網(wǎng)絡(luò)上進(jìn)行對比實(shí)驗。首先介紹實(shí)驗數(shù)據(jù)集、對比算法、實(shí)驗指標(biāo)和實(shí)驗環(huán)境，之后進(jìn)行參數(shù)設(shè)置實(shí)驗，最后分析社區(qū)發(fā)現(xiàn)實(shí)驗結(jié)果。

3.1 實(shí)驗數(shù)據(jù)集

3.1.1 真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集

實(shí)驗中使用的真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集是Dolphins[28]、Football[29]、Polbooks[30]、Youtube[31]、Dblp[31]這5 個數(shù)據(jù)集。真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集信息如表1 所示。

表1 真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集信息Table 1 Information of real network datasets

Dolphins 數(shù)據(jù)集源自1994 年至2001 年間對62只海豚之間的關(guān)系的調(diào)研觀察數(shù)據(jù)；Football 數(shù)據(jù)集源自美國某橄欖球聯(lián)盟比賽中12 支大學(xué)生參賽隊比賽情況網(wǎng)絡(luò)；Polbooks 數(shù)據(jù)集源自美國政治書籍網(wǎng)絡(luò)；Youtube 數(shù)據(jù)集源自美國社交平臺Youtube 上的用戶交友關(guān)系網(wǎng)絡(luò)；Dblp 數(shù)據(jù)集源自科學(xué)家合作關(guān)系網(wǎng)絡(luò)。

3.1.2 LFR 人工基準(zhǔn)網(wǎng)絡(luò)

LFR 人工基準(zhǔn)網(wǎng)絡(luò)由Lancichinetti 等人[32]提出，可用于驗證各類社區(qū)發(fā)現(xiàn)算法的性能。LFR 人工基準(zhǔn)網(wǎng)絡(luò)可以通過設(shè)定參數(shù)的方式調(diào)節(jié)網(wǎng)絡(luò)結(jié)構(gòu)。N表示網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)量；k表示網(wǎng)絡(luò)平均節(jié)點(diǎn)度；kmax表示網(wǎng)絡(luò)最大節(jié)點(diǎn)度；Cmin表示網(wǎng)絡(luò)中最小社區(qū)規(guī)模；Cmax表示網(wǎng)絡(luò)中最大社區(qū)規(guī)模；τ1表示網(wǎng)絡(luò)的節(jié)點(diǎn)度冪率分布指數(shù);τ2表示網(wǎng)絡(luò)社區(qū)規(guī)模冪率分布指數(shù)；μ表示網(wǎng)絡(luò)混合度參數(shù)，反映了網(wǎng)絡(luò)中社區(qū)清晰程度，是衡量社區(qū)發(fā)現(xiàn)算法性能的一個重要參數(shù)。μ∈(0,1)，μ值越小網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)越清晰，μ值越大網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)越不明顯，被發(fā)現(xiàn)的難度也越大。

通過調(diào)節(jié)LFR 人工基準(zhǔn)網(wǎng)絡(luò)的參數(shù),可以獲得不同拓?fù)浣Y(jié)構(gòu)性質(zhì)的網(wǎng)絡(luò)，LFR 人工基準(zhǔn)網(wǎng)絡(luò)基本信息如表2 所示。

表2 LFR 人工基準(zhǔn)網(wǎng)絡(luò)信息Table 2 Information of LFR artificial benchmark networks

3.2 對比算法

將SSPC 算法與近幾年具有代表性的算法進(jìn)行對比實(shí)驗。其中SELP（semi-supervised label propagation）[33]、SDPT（semi-supervised discrete potential theory）[34]、LCU[19]、DPP[22]是半監(jiān)督社區(qū)發(fā)現(xiàn)算法，Infomap[35]、GN[4]、CNM（finding local community structure in networks）[36]、Walktrap[37]是無監(jiān)督社區(qū)發(fā)現(xiàn)算法。

SELP：是一種基于半監(jiān)督標(biāo)簽傳播的社區(qū)發(fā)現(xiàn)算法。通過兩個信度函數(shù)表示已標(biāo)記節(jié)點(diǎn)和未標(biāo)記節(jié)點(diǎn)，在標(biāo)簽傳播過程中，將標(biāo)簽從已標(biāo)記節(jié)點(diǎn)上傳播到未標(biāo)記節(jié)點(diǎn)上。當(dāng)傳播過程達(dá)到收斂狀態(tài)時揭示網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)。

SDPT：是一種基于半監(jiān)督離散勢理論的社區(qū)發(fā)現(xiàn)算法。該算法將復(fù)雜網(wǎng)絡(luò)視為電阻網(wǎng)絡(luò)，每一個已標(biāo)記節(jié)點(diǎn)看成一個單位電荷，不同標(biāo)記節(jié)點(diǎn)的單位電荷產(chǎn)生的靜電場不同。通過Dirichlet 定理計算未標(biāo)記節(jié)點(diǎn)的最大電壓值來揭示網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)。

LCU：是一種基于半監(jiān)督粒子競爭機(jī)制的社區(qū)發(fā)現(xiàn)算法。通過粒子在網(wǎng)絡(luò)中執(zhí)行游走、吸收、生成步驟來爭奪各類粒子對網(wǎng)絡(luò)中邊的占據(jù)權(quán)以實(shí)現(xiàn)社區(qū)發(fā)現(xiàn)任務(wù)。

DPP：是一種基于半監(jiān)督粒子競爭機(jī)制的社區(qū)發(fā)現(xiàn)算法。通過粒子在網(wǎng)絡(luò)中執(zhí)行游走、分裂、跳躍步驟來爭奪各類粒子對節(jié)點(diǎn)的占據(jù)權(quán)以實(shí)現(xiàn)社區(qū)發(fā)現(xiàn)任務(wù)。

Infomap：是一種基于隨機(jī)游走和信息編碼的社區(qū)發(fā)現(xiàn)算法。通過優(yōu)化目標(biāo)函數(shù)的方式將相似度較大的節(jié)點(diǎn)分配到同一個社區(qū)之中。

GN：是一種基于網(wǎng)絡(luò)邊介數(shù)的社區(qū)發(fā)現(xiàn)算法?；趶?fù)雜網(wǎng)絡(luò)社區(qū)內(nèi)部聯(lián)系緊密、社區(qū)外部聯(lián)系松散的特點(diǎn)，GN 算法通過不斷刪除社區(qū)之間的邊獲得緊密的社區(qū)結(jié)構(gòu)來實(shí)現(xiàn)社區(qū)發(fā)現(xiàn)任務(wù)。

CNM：是一種基于模塊度函數(shù)的社區(qū)發(fā)現(xiàn)算法。通過不斷合并兩個社區(qū)來獲得最大模塊度函數(shù)值增益以實(shí)現(xiàn)社區(qū)發(fā)現(xiàn)任務(wù)。

Walktrap：是一種基于隨機(jī)游走理論的社區(qū)發(fā)現(xiàn)算法。Walktrap 算法認(rèn)為節(jié)點(diǎn)在隨機(jī)游走過程中會陷于社區(qū)內(nèi)部，因此基于節(jié)點(diǎn)間的距離定義兩個節(jié)點(diǎn)的相似性來實(shí)現(xiàn)社區(qū)劃分。

3.3 實(shí)驗指標(biāo)和實(shí)驗環(huán)境介紹

本文實(shí)驗中使用的數(shù)據(jù)集源自具有真實(shí)社區(qū)劃分的網(wǎng)絡(luò)，因此本文采用標(biāo)準(zhǔn)化互信息指標(biāo)（normalized mutual information，NMI）[38]作為實(shí)驗評價指標(biāo)。NMI 指標(biāo)用于比較真實(shí)社區(qū)結(jié)構(gòu)與算法計算得到的社區(qū)結(jié)構(gòu)之間的相似性，NMI 指標(biāo)的計算公式定義如下：

其中，N表示節(jié)點(diǎn)數(shù)量；A表示真實(shí)社區(qū)結(jié)構(gòu)；B表示算法計算得到社區(qū)結(jié)構(gòu)；M表示混淆矩陣；CA表示真實(shí)社區(qū)數(shù)量；CB表示算法計算得到社區(qū)數(shù)量；Mi·表示A中第i個社區(qū)的節(jié)點(diǎn)數(shù)，即矩陣M的第i行元素之和；同理，M·j表示B中第j個社區(qū)的節(jié)點(diǎn)數(shù)，即矩陣M中第j列元素之和；Mij表示A中屬于第i個社區(qū)的節(jié)點(diǎn)屬于B中屬于第j個社區(qū)的節(jié)點(diǎn)數(shù)。NMI(A,B)∈[0,1]，NMI 值越接近1 代表算法計算得到的社區(qū)結(jié)構(gòu)B和真實(shí)社區(qū)結(jié)構(gòu)A越接近。當(dāng)NMI(A,B)=1 時，表示真實(shí)社區(qū)結(jié)構(gòu)A和算法計算得到的社區(qū)結(jié)構(gòu)B完全相同。

本文的實(shí)驗環(huán)境為：處理器為Intel?CoreTMi7-8750H CPU@2.20 GHz，內(nèi)存為32 GB，操作系統(tǒng)為Windows 10 64 bit。

3.4 參數(shù)設(shè)置

SSPC 算法中需要討論的參數(shù)是重啟執(zhí)行概率參數(shù)λ和各社區(qū)中已標(biāo)記節(jié)點(diǎn)數(shù)量。重啟執(zhí)行概率參數(shù)λ可以決定粒子在邊上游走時執(zhí)行重啟步驟的概率，當(dāng)λ非常低時，粒子執(zhí)行重啟步驟的概率就會非常低，粒子在游走過程中會遠(yuǎn)離已被該類粒子占據(jù)的節(jié)點(diǎn)，導(dǎo)致社區(qū)發(fā)現(xiàn)效果偏差。雖然SSPC 算法中結(jié)合節(jié)點(diǎn)之間的交互影響重新定義了粒子游走概率，減小了粒子游走的隨機(jī)性，即使λ為0 時粒子在游走初期也會建立一定的傾向性，但是誤差會隨著游走次數(shù)增加而逐步增大。當(dāng)參數(shù)λ∈(0,1)時，粒子向其他類粒子控制的節(jié)點(diǎn)游走時受限制程度小，粒子游走的隨機(jī)性較大，盡管每類粒子游走范圍會擴(kuò)大，但是社區(qū)發(fā)現(xiàn)的準(zhǔn)確性會更差。當(dāng)λ為1 時，粒子游走的范圍會受到限制，重啟步驟會得到充分的應(yīng)用，社區(qū)發(fā)現(xiàn)的準(zhǔn)確性越好。實(shí)驗中，λ取值0至1，步長為0.1，各社區(qū)中已標(biāo)記節(jié)點(diǎn)數(shù)量設(shè)置為3，采用Football、Youtube 兩個真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集進(jìn)行社區(qū)發(fā)現(xiàn)任務(wù)，實(shí)驗評價指標(biāo)是NMI指標(biāo)，實(shí)驗結(jié)果如圖1 所示。

圖1 重啟執(zhí)行概率參數(shù)λ 的影響Fig.1 Influence of parameter λ on algorithm

實(shí)驗結(jié)果表明，在Football 和Youtube 兩個真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上，當(dāng)λ為0 時，NMI 值最低，社區(qū)發(fā)現(xiàn)效果最差。NMI值隨著λ的增大而增加，當(dāng)λ為1.0 時，NMI 值最大，社區(qū)發(fā)現(xiàn)效果最好，可以證明重啟機(jī)制可以有效限制粒子游走范圍，防止粒子在游走過程中遠(yuǎn)離已占據(jù)的節(jié)點(diǎn)。因此，在后續(xù)的實(shí)驗中λ取值為1.0。

SSPC 算法中各社區(qū)中已標(biāo)記節(jié)點(diǎn)數(shù)量需要人為指定。因為已標(biāo)記節(jié)點(diǎn)數(shù)量越多，算法可利用的先驗信息就越多，所以在半監(jiān)督社區(qū)發(fā)現(xiàn)算法中當(dāng)各社區(qū)中已標(biāo)記節(jié)點(diǎn)數(shù)量越多時，社區(qū)發(fā)現(xiàn)的效果越好。本文將在接下來的真實(shí)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)實(shí)驗中進(jìn)行驗證。

3.5 真實(shí)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)實(shí)驗結(jié)果分析

將SSPC 算法與4 種半監(jiān)督算法SELP、SDPT、LCU、DPP 在Dolphins、Football、Polbooks、Youtube、Dblp 這5 個真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行對比實(shí)驗。同時在實(shí)驗中，討論各社區(qū)中已標(biāo)記節(jié)點(diǎn)數(shù)量對于社區(qū)發(fā)現(xiàn)效果的影響，各社區(qū)中已標(biāo)記節(jié)點(diǎn)數(shù)量取值1 至5，步長為1，實(shí)驗中重啟執(zhí)行概率參數(shù)λ設(shè)置為1.0，實(shí)驗評價指標(biāo)是NMI指標(biāo)，實(shí)驗結(jié)果如圖2 所示。

圖2 真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集下算法的NMI值比較Fig.2 Comparison of NMI values of algorithms with real network datasets

實(shí)驗結(jié)果表明，各社區(qū)中已標(biāo)記節(jié)點(diǎn)數(shù)量取最大值時，NMI 值最高，社區(qū)發(fā)現(xiàn)效果最好，可以證明各社區(qū)中已標(biāo)記節(jié)點(diǎn)數(shù)量和社區(qū)發(fā)現(xiàn)效果呈正相關(guān)。LCU、DPP、SSPC 這三種基于粒子競爭機(jī)制的半監(jiān)督社區(qū)發(fā)現(xiàn)算法相比其他半監(jiān)督社區(qū)發(fā)現(xiàn)算法都取得了更好的社區(qū)發(fā)現(xiàn)效果。當(dāng)各社區(qū)中標(biāo)記節(jié)點(diǎn)數(shù)量為3 時，在Polbooks 數(shù)據(jù)集上，LCU 算法相比SELP算法NMI 值提高16.5%，相比SDPT 算法NMI 值提高6.3%，可以證明基于粒子競爭機(jī)制的半監(jiān)督社區(qū)發(fā)現(xiàn)算法性能優(yōu)于其他的半監(jiān)督社區(qū)算法，具有一定的優(yōu)越性。而SSPC 算法社區(qū)發(fā)現(xiàn)效果相較于LCU、DPP 在各個數(shù)據(jù)集上都有較大幅度的提升。當(dāng)各社區(qū)中標(biāo)記節(jié)點(diǎn)數(shù)量為5時，在Youtube數(shù)據(jù)集上，SSPC算法相比LCU 算法NMI 值提高4.8%，相比DPP 算法NMI 值提高6.5%，可以證明SSPC 算法改進(jìn)了原有粒子競爭機(jī)制中存在的問題，提高了社區(qū)發(fā)現(xiàn)效果。在大規(guī)模網(wǎng)絡(luò)Dblp 數(shù)據(jù)集上，SSPC 算法相比其他半監(jiān)督社區(qū)發(fā)現(xiàn)算法在不同標(biāo)記節(jié)點(diǎn)數(shù)量上都取得了更好的社區(qū)發(fā)現(xiàn)結(jié)果，可以證明SSPC 可以運(yùn)用于大規(guī)模網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)，具有較好的可擴(kuò)展性。

3.6 LFR 人工基準(zhǔn)網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)實(shí)驗結(jié)果分析

將SSPC 算法和Infomap、GN、CNM、Walktrap 等無監(jiān)督社區(qū)發(fā)現(xiàn)算法在LFR 人工基準(zhǔn)網(wǎng)絡(luò)（表2）上進(jìn)行實(shí)驗，分別檢測算法對于混合度參數(shù)、網(wǎng)絡(luò)規(guī)模的適應(yīng)性，同時驗證半監(jiān)督社區(qū)發(fā)現(xiàn)算法相比無監(jiān)督社區(qū)發(fā)現(xiàn)算法的優(yōu)越性。

3.6.1 不同μ 值網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)實(shí)驗結(jié)果分析

在不同μ值的人工基準(zhǔn)網(wǎng)絡(luò)（N1 網(wǎng)絡(luò)）上的實(shí)驗結(jié)果如圖3 所示。

圖3 不同μ 值網(wǎng)絡(luò)下的各算法的NMI值比較Fig.3 Comparison of NMI values of algorithms in different μ values networks

實(shí)驗結(jié)果表明，當(dāng)μ取值在0.1 至0.3 時，社區(qū)結(jié)構(gòu)較清晰，除了CNM，各算法都取得了不錯的社區(qū)效果，NMI 值幾乎都為1。隨著μ值增大，各算法得到的NMI 值都呈下降趨勢。其中，SSPC 算法在不同μ值網(wǎng)絡(luò)上的NMI 值都高于對比算法，當(dāng)μ值為0.8時，GN、CNM 算法得到NMI 值為0，算法已無法獲得社區(qū)發(fā)現(xiàn)結(jié)果，而SSPC 算法仍可以把大多數(shù)節(jié)點(diǎn)劃分到正確的社區(qū)中，可以證明半監(jiān)督社區(qū)算法準(zhǔn)確性優(yōu)于無監(jiān)督社區(qū)發(fā)現(xiàn)算法，并且SSPC 算法運(yùn)用于社區(qū)發(fā)現(xiàn)任務(wù)中具有可行性和有效性。

3.6.2 不同規(guī)模網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)實(shí)驗結(jié)果分析

在不同規(guī)模的LFR 人工基準(zhǔn)網(wǎng)絡(luò)上的實(shí)驗結(jié)果如圖4 所示。

圖4 不同規(guī)模網(wǎng)絡(luò)下的各算法NMI值比較Fig.4 Comparison of NMI values of different algorithms in different scale networks

實(shí)驗結(jié)果表明，除了Infomap，SSPC 算法在各規(guī)模的網(wǎng)絡(luò)上相較于其他算法的社區(qū)發(fā)現(xiàn)效果都有大幅度的提升，可以證明SSPC 算法對于各規(guī)模的網(wǎng)絡(luò)都有一定的適應(yīng)性。Infomap 算法在不同規(guī)模上的LFR 人工基準(zhǔn)網(wǎng)絡(luò)上社區(qū)發(fā)現(xiàn)效果與SSPC 算法持平，分析原因是LFR 人工基準(zhǔn)網(wǎng)絡(luò)生成過程中，其社區(qū)內(nèi)部連邊和社區(qū)之間連邊分別采用隨機(jī)連接方式產(chǎn)生。這導(dǎo)致網(wǎng)絡(luò)中各社區(qū)內(nèi)部連邊分布比較均勻，兩節(jié)點(diǎn)之間的連邊概率與其度數(shù)成正相關(guān)關(guān)系，因此在網(wǎng)絡(luò)μ值相對不高、網(wǎng)絡(luò)結(jié)構(gòu)相對清晰時，LFR人工基準(zhǔn)網(wǎng)絡(luò)中社區(qū)分布比較平衡，網(wǎng)絡(luò)結(jié)構(gòu)也相對穩(wěn)定，因此基于隨機(jī)游走理論的社區(qū)發(fā)現(xiàn)算法Infomap 可以獲得較好的社區(qū)發(fā)現(xiàn)效果。

4 結(jié)束語

本文提出了一種基于粒子競爭機(jī)制的半監(jiān)督社區(qū)發(fā)現(xiàn)算法SSPC。該算法融合了節(jié)點(diǎn)粒子競爭機(jī)制和邊粒子競爭機(jī)制，每個類別的已標(biāo)記節(jié)點(diǎn)會產(chǎn)生粒子在網(wǎng)絡(luò)中執(zhí)行游走、重啟步驟，且粒子每次執(zhí)行游走和重啟步驟都會影響粒子對于節(jié)點(diǎn)和邊的占據(jù)程度。經(jīng)過多次游走后，當(dāng)網(wǎng)絡(luò)中的每條邊上都有一類粒子的占據(jù)程度趨于穩(wěn)定時，根據(jù)粒子占據(jù)程度可以獲得社區(qū)發(fā)現(xiàn)結(jié)果。實(shí)驗結(jié)果表明，該算法具有可行性和有效性，同時本文也給出了關(guān)于SSPC算法的收斂性證明。但是本文仍有幾個方面不足：首先，本文研究的網(wǎng)絡(luò)是簡單無向網(wǎng)絡(luò)，并沒有研究有向、屬性等更加復(fù)雜的網(wǎng)絡(luò)；其次，沒有解決復(fù)雜網(wǎng)絡(luò)重疊社區(qū)發(fā)現(xiàn)問題。在下一步的研究中，嘗試將本文算法擴(kuò)展到更加復(fù)雜的網(wǎng)絡(luò)上執(zhí)行社區(qū)發(fā)現(xiàn)任務(wù)，并致力于解決重疊社區(qū)發(fā)現(xiàn)問題。