基于圈結構的LPANNI優化算法

收稿日期：2022-02-28；修回日期：2022-04-22" 基金項目：國家自然科學基金資助項目（72164034，71762028）；新疆維吾爾自治區高校科研計劃資助項目（XJEDU2019SI006）

作者簡介：劉繼（1974-），男，四川達州人，教授，碩導，博士，主要研究方向為數據智能分析、網絡社區發現（liuji5000@126.com）；賈芳弟（1995-），女，甘肅天水人，碩士研究生，主要研究方向為數據智能分析、網絡社區發現.

摘 要：針對重疊社區發現準確率提升問題，提出了一種基于圈結構的LPANNI優化算法CLPANNI（cycle label propagation algorithm with neighbor node influence）。該算法通過挖掘節點的最小圈信息，依據圈比指標衡量節點的重要性并按升序進行標簽更新，增加了標簽傳播過程的穩定性，按照鄰居節點影響力大小加權接收鄰居節點傳遞的標簽。與四種基準算法在NMI_LFK、NMI_MGH、MOV指標下進行測試比較，CLPANNI算法在社區發現準確率方面表現較好。實驗結果表明，該算法能夠有效探測網絡重疊社團結構，發現網絡的緊密子團，識別的社團分布與真實網絡結構更為接近。

關鍵詞：復雜網絡；圈結構；標簽傳播算法；重疊社區發現

中圖分類號：TP301.6"" 文獻標志碼：A

文章編號：1001-3695（2022）09-024-2717-06

doi：10.19734/j.issn.1001-3695.2022.02.0078

LPANNI optimization algorithm based on cycle structure

Liu Jia，b，Jia Fangdia

（a.School of Statistics amp; Data Science，b.Xinjiang Research Center of Social Economic Statistics amp; Big Data Application，Xinjiang University of Finance amp; Economics，Urumqi 830012，China）

Abstract：In order to improve the accuracy of overlapping community detection，this paper proposed an LPANNI optimization algorithm CLPANNI based on cycle structure by mining the minimum circle information of nodes，measuring the importance of nodes according to the circle ratio index and updating labels in ascending order.This algorithm increased the stability of label propagation process，and received the labels transmitted by neighbor nodes according to the influence of neighbor nodes.Compared with four benchmark algorithms in NMI_ LFK，NMI_ MGH and Mov indicators，CLPANNI algorithm performed well in the accuracy of community discovery.Experimental results show that the algorithm can effectively detect the overlapping community structure of the network，find the close sub clusters of the network，and the identified community distribution is closer to the real network structure.

Key words：complex network；cycle structure；label propagation algorithm；overlapping community detection

復雜網絡是人們用來理解現實世界復雜系統的一種抽象模型，它將復雜系統中的實體抽象成節點，將實體之間的關系抽象成連線。社團結構（community structure）是復雜網絡中最普遍也是最重要的拓撲特性之一，表現為社區內部結構緊密，社區之間連接稀松。社區發現（community detection）對探索復雜系統的運行機制及其功能特性具有重要意義，從是否考慮節點的多社區歸屬性這一角度可以將其分為兩類，非重疊社區發現算法（non-overlapping community detection）和重疊社區發現算法（overlapping community detection）。真實網絡中社區結構之間普遍具有重疊區域，往往存在重疊節點，即一個節點同時存在于兩個以上社團的現象［1］。而重疊節點對網絡結構的演變起到了十分重要的促進作用，在萬物互連的大數據時代，重疊節點在網絡動力學演化中的作用值得深入分析。

自2005年以來，研究人員試圖從不同角度［2～6］設計重疊社區發現探測算法提高重疊社團的識別率和計算效率。其中，標簽傳播算法［7］以線性時間復雜度的優勢被各國學者廣泛應用到真實網絡重疊社區結構探測研究中［8］，COPRA（community overlap propagation algorithm）［9］是第一個應用于重疊社區發現的標簽傳播算法，該算法依據節點在不同社團隸屬系數的變化識別社團；隨后提出了SLPA（speaker-listener label propagation algorithm）［10］、DEMON（democratic estimate of the modular organization of a network）［11］、ACSLPA（active semi-supervised SLPA）［12］等算法識別重疊社團；文獻［13］對五種表現較好的經典算法CPM（clique percorlation method）［1］、COPRA［9］、DEMON［11］、SLPA［10］、BigCLAM（cluster affiliation model for big networks）［14］進行了結構識別效果對比，發現算法識別的社團只是算法運行的結果，并不代表真實的社團，作者指出僅依據常見指標評價算法的優劣存在問題，建議在設計重疊社區發現算法時更多關注重疊區域的節點數量和節點的隸屬度等信息。

值得注意的是，以往大部分研究主要基于節點的鄰接關系研究網絡的功能與特性，但在實際交互場景中往往存在多個節點的復雜相互作用。不論是在自然界還是在虛擬的網絡社交圈中，單個個體的行為往往與群體有一定關聯。為了更好地協同整體，個體不僅需要考慮個體間的相互作用關系，還需要注意與群體的相互作用關系。考慮到反饋機制對現實網絡動態演變的影響，尤其是重要的重疊節點在不同社團的正負反饋作用，需要新的視角來分析節點的影響力。

1 相關知識

1.1 重疊社區發現

重疊節點是影響網絡拓撲結構演變的關鍵要素之一，對網絡動力學與網絡結構相互關系的探索十分重要，重疊社團檢測算法是研究網絡動力學有效的方法。本文關注的重疊社團探測算法主要基于團滲流思想和標簽傳播思想兩類，節點依據一定的傳播規則自底向上逐步集聚成團，此類算法不同于自頂向下的算法，對網絡社團結構的質量不作特別限制，因此更符合真實世界中自動生成的組織或者團簇。當前，網絡科學邁入新的研究階段，高階相互作用動力學將引起人們的極大興趣，重疊社團探測迎來了挑戰，在探測社團結構時需要考慮多節點間的交互特征與網絡中觀尺度的鄰域信息。

1.2 相關工作

文獻［15，16］借鑒龐加萊的剖分思想，將網絡分解為全齊性子網絡，開創了網絡科學研究的新框架——圈結構。由于圈結構建立了個體與群體的聯系，在一定程度上考慮了多個節點的相互作用，可以反映節點的局域影響力，能夠進一步指導網絡社區發現。文獻［17］基于網絡的一階圈結構設計了新的節點重要性指標——圈比，基于圈比指標找到的重要節點分布較為分散，這些重要節點傳播高效、不冗余、同步能力強。文獻［18］提出了LPANNI重疊社區發現算法，該算法融合了COPRA和DLPA（dominant label propagation algorithm）［19］的優點，巧妙地解決了COPRA在不同網絡中參數難以確定的問題；同時充分考慮了節點的局域信息，通過綜合節點重要性、鄰域節點相似性以及鄰居節點影響力的方式降低了標簽傳播算法的隨機性；引進歷史標簽偏好策略，確定節點每次迭代的主標簽，增加了重疊社區識別精度。

1.3 評價指標

在不知網絡重疊社團結構時，一般用質量函數衡量社團的緊密度，常見的有EQ［20］、Q［21］OV、MOV［22］。本文選用MOV指標，該指標依據每一個節點在不同社團的歸屬強度來進行計算該節點對社團的貢獻程度，是一種非常精確的重疊度衡量辦法，這與文獻［13］的建議十分吻合。根據節點在社團內連邊與社團外連邊數目的差值衡量節點對一社團的貢獻度，有效避開了其他重疊社區發現模塊度指標對高度重疊社團結構的低分辨問題。具體公式如下：

∑Kr=1ai，cr=1 ai，cr∈［0，1］

MOV=1ncr∑∑j∈cr，i≠jaij-∑jcraijdi×si×necrncr2 MOV∈［-1，1］ （1）

其中：ncr、necr分別代表第r個社團c的節點數和連邊數。由于第一個因子的取值在-1～1，第二個因子的取值在0～1，所以MOV的取值在-1～1變化。

在已知真實社團結構時，常用NMI指標進行社團劃分結果的衡量，本文選用CDlib庫（community discovery library）［23］中的兩種NMI指標。

2 LPANNI算法框架

LPANNI算法以固定順序更新節點的標簽，有效解決了標簽振蕩問題，降低了隨機性；同時合理運用節點的局部信息測度了不同鄰居節點的影響力大小；在標簽傳播過程中只傳播社區歸屬系數最大的主標簽，若具有多個相同的最大的主標簽則選擇歷史迭代中出現的主標簽，過濾了不重要的標簽信息；在算法收斂后，根據節點的標簽集信息確定重疊節點。

2.1 符號說明

本文涉及到的關鍵符號及其含義如表1所示。表中符號主要基于本文提出的CLPANNI算法，部分符號為后續實驗中出現的參數。

2.2 參數初始化

設最大迭代次數為T，節點數量為V，迭代時刻為t，用一組有序數對bc（c，i）表示節點i在不同社區中的隸屬強度；節點i的鄰居節點為ng（i）；節點i標簽集的隸屬系數最大的標簽為主標簽Di，節點i的標簽集大小|L′|；節點i的標簽集合為Li。初始時刻，網絡G（V，E）中的節點各自為一個獨立社區，節點的隸屬系數為1，即社區i的隸屬系數bi為1，記做隸屬bi（i，1）。

2.3 更新策略

輸入：G=（V，E，w），最大迭代次數T。

輸出：社區識別結果。

階段1 固定標簽更新順序

for i in V：

依據節點重要性公式計算節點的重要性；

依據節點相似性公式衡量節點間的相似性；

依據鄰居節點影響力公式計算鄰居節點的重要性；

end for

按節點重要性的大小或者序列號的大小升序排列為VQ；

階段2 標簽傳播過程

t=0；

for i in V：

l［i］={i，1}；

主標簽Di = i；

end for

while tlt;T：

for i in VQ：

LNg={l（c1，b1），l（c2，b2），…，l（cv，bv）}，v∈Ng（i）；

L′=按照更新規則更新節點i的標簽集；

for ls in L′

if b′lt;1/|L′|

then delete ls from L′；

end if

end for

Li=歸一化的節點標簽L′；

確定節點i本次迭代后的主標簽Di；

end for

若所有節點的標簽集大小以及主標簽不再變化則停止迭代；

t=t+1；

end while

output Li of each node i（i∈V）。

LPANNI算法包含兩個階段的處理，即固定標簽更新順序和標簽傳播過程。階段1主要按照鄰居節點的影響力大小更新標簽信息。階段2在確定主標簽時，如果只有一個最大的隸屬度則傳播該社區標簽；如果存在多個相同的最大隸屬度社區標簽，則優先選擇上次迭代中的主標簽，否則隨機選擇一個作為主標簽。

LPANNI算法考慮了節點的局域信息，通過計算鄰居節點的影響力巧妙設計了標簽更新規則，在傳播規則上具有很大的借鑒意義；但其只關注節點對的相互作用，主要借助節點的度信息設計相關公式，對具有相同結構的節點區分度不大，需要借助節點ID順序較多，本文基于以上優點和不足對其進行改進。

3 CLPANNI算法設計

事物有從簡單到復雜的一個發展過程，錯綜復雜的交互關系使得組織得以延續壯大，組織間的交互帶來了連通與演化。以網絡科學視角可以看到一些特定的網絡結構，例如星結構、鏈結構以及圈結構。圈結構是構成網絡的基本結構之一，是形成網絡功能的最重要機制之一，是反饋效應的結構基礎，而反饋對事物的發展演化十分關鍵。

在網絡動力學同步的研究中，文獻［15，16］發現最容易同步的網絡是全齊性網絡。圈在結構上給網絡連通帶來了冗余路徑，在功能上表征了反饋機制，在網絡動力學中產生了強化效應，很容易增強社會協同效應，因此圈結構在保持網絡連通性和維護網絡的動態交互方面比較重要。在此基礎上，Fan等人［17］認為參與許多圈的節點很重要，這些節點對網絡的連通、同步以及控制方面有極大的影響，他們基于網絡最小圈設計了基于圈結構的節點重要性指標——圈比。

圖1（修改自文獻[17]）的（b）中計算了（a）中節點1的圈比，（c）是所有節點的度、H指數、核數、圈比值、中介中心性等信息。他們對網絡的一階圈結構的最小圈定義了一個新的矩陣，稱為圈數矩陣。圈數矩陣的階數與網絡中的節點數相同，矩陣的第i行（列）描述了節點i與其他節點的共圈情況，矩陣的元素表示網絡中任意兩個節點之間的共圈數量。這樣，節點i的圈比值就可以根據圈數矩陣中第i行非零元素與對角線元素的比值之和計算出來。

圈提供的冗余連通和反饋機制使得圈上節點無論在同步還是傳播中［24］都有更高的概率被接觸和同步，能更好地模擬社會增強效應。考慮到圈比指標在挖掘高傳播節點方面的突出表現，本文將圈比運用到標簽傳播算法中，先借助圈比找到網絡中傳播能力強的節點，并運用LPANNI［18］算法的標簽傳播策略來提高網絡社團的劃分精度。

3.1 相關定義

簡單無向網絡G（V，E），其中V和E分別表示節點集和連邊集，n表示節點的數量，m表示連邊的數量。

a）圈（cycle）。二維平面上具有相同起點和終點的閉合路徑，圈的大小等于它的連線數目，最小圈是指含該節點的最小環路。

b）周長（girth）。從該點出發再返回它的最短環路所含的連線數目，即經過該節點的最小圈長。

c）圈數（cycle number）。含有該節點的最小圈的數量。

d）圈比（cycle ratio，CR）。節點重要性衡量指標，圈數矩陣中第i個節點所在行的元素比對應行的對角元素之和，得到i節點的圈比，具體計算公式為

CRi=0.1cii=0

∑j，cijgt;0 cijcjjciigt;0

（2）

其中：cij是S中節點i和j（i≠j）的共圈數量。若i=j，則cii是S中包含節點i的圈數；CRi為節點i的圈比值，為了能夠精確衡量鄰居節點影響力的大小，故這里將第一種情況取為0.1。

e）節點相似性（similarity，SIM）。本文衡量節點相似性主要基于網絡結構，文獻［25］對局部相似性指標的相關研究進行了梳理，并分析了這些指標的設計原理，指出結構相似性指標可以分為基于局部信息、路徑及隨機游走三類；文獻［18］提出的相似性指標結合了節點的局部信息以及路徑長度，有效融合了兩者優勢，本文沿用該相似性指標，具體計算公式為

SIM（x，y）=s（x，y）∑u∈Ngxs（x，u）∑v∈Ngys（y，v） （3）

其中：s（i，j）=∑a|p|=1（A|p|）ij|p|；p表示直接或間接連接節點i和j的路徑，|p|表示p的長度，在1～a變化；|A||p|表示p的測度度量。路徑長度閾值a來控制計算復雜度，用來區分兩個節點因度值差異對節點相似度帶來的影響。

f）鄰居節點影響力（neighbor node influence，NNI）。考慮到鄰居節點由于具有不同的局部結構，對節點的影響力也不盡相同，在標簽傳遞時需要測度不同鄰居節點的差異。文獻［18］提出的NNI綜合考慮鄰居節點的重要性大小和鄰居節點與該節點的相似性程度，相對來說比較客觀，本文沿用此定義。具體公式為

NNIy（x）=CR（y）SIM（x，y）maxh∈Ng（x）SIM（h，x） （4）

3.2 LPANNI算法的改進

LPANNI算法僅僅通過節點的度和三角形信息設計節點重要性公式來衡量節點的重要性以及鄰居節點的影響力大小，沒有考慮更多的圈結構，因此看到的信息是十分有限的，不足以衡量具有相同局部結構節點的差異。而圈比指標通過衡量節點參與鄰居節點圈的程度識別重要節點，有利于標簽的動力學傳播，本文基于圈結構信息對無向無權網絡提出重疊社區發現算法CLPANNI，根據圈比的升序固定節點的標簽更新順序，提高社團識別的精度。

3.3 CLPANNI算法框架

CLPANNI算法分為兩個階段：第一個階段完成節點圈比和鄰居節點影響力的計算；第二個階段進行標簽傳播，找到全部節點的隸屬社團，輸出節點的標簽集。具體流程如圖2所示。

3.4 標簽傳播規則

文獻［9］提出的COPRA考慮了節點在不同社團的隸屬強度，節點在不同社團的隸屬強度類似于一個個體在不同層面中注意力或者精力的分散程度，總和加起來為1。文獻［18］以節點重要性的升序固定標簽傳播序列增加了算法的穩定性，通過鄰居節點影響的標簽更新策略和歷史標簽偏好策略提出的LPANNI算法解決了COPRA需要提前設置節點最多擁有v個標簽的缺陷。這里以節點的圈視角衡量節點的重要性程度，具體標簽傳播規則為：

階段1 根據節點的圈比值，從小到大對節點排序，若節點的圈比值相同，則以ID大小升序排列，得到固定的更新序列VQ。

階段2 依據VQ的順序進行標簽更新。初始時刻，每個節點都完全屬于自己，即有Ldi=（i，1）；接下來按VQ順序接收鄰居節點的主標簽后形成LNg標簽集，主標簽是指鄰居節點傳遞最大的隸屬系數及社團標簽。

LNg={l（c1，b1），l（c2，b2），…l（cv，bv）} v∈Ng（i）（5）

按照鄰居節點的影響力大小NNI對隸屬系數進行加權處理，得到大小為鄰居節點數的新標簽集L′，此時每個節點的總隸屬系數為1。加權處理傳遞的社團隸屬系數為

b″（c，i）=b′（c，i）∑l（c，b′）∈L″b′（c，i） ∑l（c，b″）∈L″b″（c，i）=1 （6）

加權處理后的標簽集為

L′={l（c1，b1′），l（c2，b2′），…，l（c|L′|，b|L′|′），}∑l（c，b′）∈L′b′（c，i）=1（7）

自適應刪除無用標簽b′（c，i）lt;1|L′|，歸一化后得到此次迭代的標簽集L″。如此迭代T次后輸出各節點的標簽集。

b′（c，i） = ∑l（cv，bv）∈LNg（i），v∈Ng（i），cv=cb（cv，v）NNIv（i）∑l（cv，bv）∈LNg（i），v∈Ng（i）b（cv，v）NNIv（i）（8）

識別具有最大隸屬系數的標簽為節點i的主標簽，若有多個主標簽，則選擇上一步迭代的主標簽，否則隨機選擇一個作為主標簽。當全部節點的標簽集和主標簽穩定時，停止迭代，輸出節點的標簽集。

4 實驗結果及分析

4.1 實驗數據

1）人工數據集

LFR人工數據集能夠合成接近真實情況的使得節點數和社團數均滿足冪律分布的網絡。本文使用LFR基準網絡生成數據，分別用混合參數μ為0.1或0.3的兩組數據進行實驗對照。每一組數據中分三個等級，節點數目分別為1 000、3 000、5 000，每一個等級中分了五組不同重疊程度的數據。其具體信息如表2所示。

2）合成網絡的最小圈

以往重疊社團發現算法很少關注網絡的圈結構分布情況，部分算法［18，26，27］考慮網絡的三角形信息。對LFR數據進行圈結構分布的可視化有助于進一步了解網絡中的圈結構信息。在運用CLPANNI算法檢測網絡的社團結構的同時可以清楚地看到網絡的最小圈分布情況，如圖3所示。

由圖3可知，本實驗的六個LFR網絡中含較多的圈結構數據，不同規模的數據具有不同的圈結構分布，最小圈的周長為3，最大圈的周長為8，且最小圈中三角形數量占比過半。在混合參數μ=0.1時，三角形在網絡最小圈數量占比至少達到90%；當混合參數μ=0.3時，隨著網絡結構清晰度的下降，最小圈數量明顯減少，三角形的占比有所下降，四邊形與五邊形的占比明顯上升，這在一定程度上印證了當網絡結構不明顯時社團識別效果不好的原因。當網絡規模不變時，隨著網絡拓撲結構復雜程度上升，最小圈的種類和分布多樣化特征更為突出，這就加大了社團識別的難度。

3）真實數據集

文獻［12］提供了已知社團信息的三個真實數據，分別是處理過的共同購買網絡Amazon、科學家合作網絡DBLP和友誼網絡YouTube，并列出了網絡的重疊節點信息。本文對這三個真實網絡數據進行了最小圈挖掘，發現Amazon數據和DBLP數據中的最小圈種類較少；但YouTube數據中的圈分布具有多樣性的特征，其中最小的圈周長為3～10，說明YouTube網絡結構特征相對比較復雜。具體相關信息如表3所示。

由于YouTube數據中的最小圈數量較大且種類較多，不便枚舉。這里將最小圈分布展開分析，如圖4所示。可以看到YouTube網絡中，周長為3的圈，三角形依然是最小圈的主體組成部分，數量級別最高；其次是周長為4～8的圈，在該網絡中最長的圈周長為10。

4.2 實驗結果

以SLPA、DEMON、CPM和LPANNI為對比算法，經過多次實驗調參，相關算法的參數設置如表4所示。其中，由于SLPA算法不穩定，經過10次重復實驗取平均得到具體值，CPM算法中參數k一般取3～6，經過測試發現將k取為3得到的各項測試結果更好。其他算法中的參數按照CDlib庫［23］的默認值進行測試。

先對LFR數據進行測試，NMI_LFK［28］是常用的測試指標，該指標是標準互信息在重疊社區發現中的拓展，但有時候會高估兩個社團的相似性；NMI_MGH［29］（也稱NMImax）是McDaid等人對NMI_LFK做出的優化指標，本文選用該指標進行測試。五種算法的對比結果如圖5所示。

由圖5可知，CLPANNI與LPANNI算法相對其他基準算法表現較好，在網絡規模增大、網絡社團結構清晰度下降的情況下還能準確識別網絡的社團結構。當重疊節點數量增加時，CLPANNI算法的表現略強于LPANNI算法，說明本文的改進有效，圈比在挖掘節點重要性方面表現更好。

為進一步驗證CLPANNI算法的準確度，對三個社團結構已知的真實數據進行測試，結果如圖6所示。

在真實數據的實驗結果中，可以看到在三種指標的檢測下，除了YouTube數據，CLPANNI算法較LPANNI算法測試結果表現稍低外，在其他數據的表現比LPANNI算法好。在MOV指標下，CLPANNI算法表現較LPANNI算法好，尤其在Amazon數據集中優勢更為明顯。SLPA算法在DBLP數據上表現相對較好，說明該算法在社團結構明顯的網絡上表現較好。另一方面也說明本文的參數設置合理，但該算法存在極大的不穩定性和隨機性，需要多次重復實驗，不能保證每次都能得到較好的劃分，故并不能提供一個可靠的結果。DEMON算法在YouTube中，NMI_MGH得分較低，說明民主投票機制的標簽傳播策略不適用于此類網絡。總體來說，CLPANNI算法表現良好，在多項指標測試下都有不錯的表現。

5 分析討論

5.1 算法探測結果

由圖5的實驗結果可知，網絡社團結構越模糊，社團間重疊程度越大，CLPANNI算法相較其他算法表現越好；從圖6的重疊社團結構評價指標來看，本文所提算法CLPANNI在DBLP和Amazon網絡表現較原算法更優；另外，多個算法對YouTube數據的社團探測效果欠佳，因此有必要對該數據的探測結果做進一步分析，探尋其背后的原因。YouTube數據是社交網絡數據，故在該網絡上存在一定的社會網絡增強效應（注：由于SLPA算法具有隨機性，重復實驗15次。平均來說，能夠識別到社團477個，這里展示社團數量為中位數的實驗結果）。

真實情況下，YouTube網絡6 426個節點中有重疊節點865個、社團1 078個；主要的社團規模為5，共有307個。表5分別展示了各個算法在YouTube社交網絡上探測的社團重疊模塊度、主體社團規模及其探測數量、社團識別數量與總節點頻次信息。在本次實驗中，SLPA算法能發現社團455個；CPM算法能夠識別到緊密的社團結構，k=3，識別到的結構是以三角形為單元的團簇230個。在社團結構識別上，可以看到DEMON算法發現的社團數量最少，同時MOV得分最高，但在重疊節點探測上存在過擬合的問題；相對來說，CPM和SLPA算識別的社團數量較為相近，能夠探測出455個社團；LPANNI算法發現的社團數量最多但社團較小；在重疊節點發現方面，CLPANNI算法的識別效果不如LPANNI算法，但CLPANNI算法對主體社團規模的識別準確度較高，說明改進的CLPANNI算法較原始算法在社團規模探測方面擬合更好。YouTube具有多樣化的最小圈分布，說明本文算法對連邊冗余圈結構復雜的網絡效果更優，較原始算法能更好地模擬社會增強效應。

5.2 社團規模分布

為進一步分析各個算法在該網絡社團結構探測方面的表現，對各個算法探測到的社團數量分布進行對比，結果如圖7所示。LPANNI、CLPANNI、DEMON、SLPA算法都含有標簽傳播算法的思想，因此會存在標簽傳播算法特定的缺點，存在標簽過度傳播和大團吃小團的現象，去除奇異值得到圖7 的社團探測結果。CPM算法主要通過完全子圖的滲流識別社團結構，得到的社團大小與網絡局域結構的緊密性有很大的關聯。在真實的YouTube數據中，最大的社團含31個節點，但五種算法識別到的最大社團大小均超過31，說明該網絡存在緊密的連通塊。如果精心篩選節點隸屬度閾值，檢測效果還會有提升，但會消耗較多時間。

5.3 可視化分析

圖8為Gephi自帶的Louvain算法社團識別結果，顏色相同的為同一社團，帶有標簽的節點為至少跨八個社團的重疊節點。經過可視化發現，YouTube數據的網絡社團結構不清晰，確實存在巨大連通片，且高重疊節點分布比較集中，這可能是幾個典型算法在該數據集中社團識別效果不佳的部分原因。YouTube社交網絡由于重疊節點分布集中，使得該網絡在輿情傳播中較容易形成規模性的網絡意見，在實際應用中應該更關注重疊節點的意見情況，為網絡輿情預警與引導提供智力支持。

6 結束語

本文對LPANNI算法進行了優化，提出了一種基于網絡圈結構信息的檢測重疊社團結構的標簽傳播算法CLPANNI，該算法提高了具有緊密網絡結構的社團識別精度。CLPANNI不僅具有良好的穩定性，還能在檢測重疊社團結構的同時得到網絡中每一個節點的最小圈信息以及網絡中不同周長的最小圈分布，這有助于進一步了解網絡的結構特點，提供中觀尺度信息指導重疊社團結構的探測。

經過對比YouTube網絡的社團輸出信息可以發現，CLPANNI算法在對真實網絡中的重疊節點挖掘、社團結構識別效率方面還有待提升，未來將結合圈結構對具有緊密結構的網絡進行深入分析。真實網絡往往會隨外界環境動態演變，而拓撲結構又影響信息的傳輸，如何利用探測到的重疊節點及其社團結構分析網絡的動態演化特性值得深入研究。考慮到網絡的連接往往是在信息不完全條件下作出的有限選擇，未來在研究中還需要融合先驗知識，整合網絡高階信息進一步量化網絡，合理嵌套節點屬性信息挖掘網絡的重疊社團結構，發掘關鍵重疊節點協助預判網絡的動態演化方向。

參考文獻：

［1］Palla G，Derényi I，Farkas I，et al.Uncovering the overlapping community structure of complex networks in nature and society［J］.Nature，2005，435（7043）：814-818.

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

［3］許英.利用改進蟻群算法的重疊社團檢測分析方法［J］.計算機應用研究，2020，37（5）：1375-1379.（Xu Ying.Novel algorithm of overlapping community detection and analysis with improved ant colony algorithm［J］.Application Research of Computers，2020，37（5）：1375-1379.）

［4］付饒，孟凡榮，邢艷.基于節點重要性與相似性的重疊社區發現算法［J］.計算機工程，2018，44（9）：192-198.（Fu Rao，Meng Fanrong，Xing Yan.Overlapping community discovery algorithm based on node importance and similarity［J］.Computer Engineering，2018，44（9）：192-198.）

［5］楚楊杰，楊忠保，洪葉.局部擴展的遺傳優化重疊社區發現方法［J］.計算機應用研究，2019，36（4）：1106-1109.（Chu Yangjie，Yang Zhongbao，Hong Ye.Local extension approach through genetic algorithm for overlapping community detection［J］.Application Research of Computers，2019，36（4）：1106-1109.）

［6］Shchur O，Günnemann S.Overlapping community detection with graph neural networks［EB/OL］.（2019-09-26）.https：//arxiv.org/pdf/1909.12201.pdf.

［7］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 Pt 2）：036106.

［8］張應龍，夏學文，徐星，等.面向標簽傳播算法的社團檢測研究現狀及展望［J］.小型微型計算機系統，2021，42（5）：1093-1102.（Zhang Yinglong，Xia Xuewen，Xu Xing，et al.Review on label propagation algorithms for community detection［J］.Journal of Chinese Computer Systems，2021，42（5）：1093-1102.）

［9］Gregory S.Finding overlapping communities in networks by label propagation［J］.New Journal of Physics，2009，12（10）：2011-2024.

［10］Xie Jierui，Szymanski B K，Liu Xiaoming.SLPA：uncovering overlapping communities in social networks via a speaker-listener interaction dynamic process［C］//Proc of the 11th IEEE International Conference on Data Mining.Piscataway，NJ：IEEE Press，2011：344-349.

［11］Coscia M，Rossetti G，Giannotti F，et al.DEMON：a local-first disco-very method for overlapping communities［C］//Proc of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York：ACM Press，2012：615-623.

［12］Alghamdi E，Greene D.Active semi-supervised overlapping community finding with pairwise constraints［J］.Applied Network Science，2019，4（8）：article No. 63.

［13］Vieira V F，Xavier C R，Evsukoff A G.A comparative study of overlapping community detection methods from the perspective of the structural properties［J］.Applied Network Science，2020，5（1）：1-42.

［14］Yang J，Leskovec J.Structure and overlaps of ground-truth communities in networks［J］.ACM Trans on Intelligent Systems and Technology，2014，5（2）：article No. 26.

［15］Shi Dinghua，Chen Guanrong，Thong W W K，et al.Searching for optimal network topology with best possible synchronizability［J］.Circuits and Systems Magazine，2013，13（1）：66-75.

［16］Shi Dinghua，Lyu Linyuan，Chen Guanrong.Totally homogeneous networks［J］.National Science Review，2019，6（5）：962-969.

［17］Fan Tianlong，Lyu Linyuan，Shi Dinghua，et al.Characterizing cycle structure in complex networks［J］.Communications Physics，2021，4（12）：article No. 272.

［18］Lu Meilian，Zhang Zhenglin，Qu Zhihe，et al.LPANNI：overlapping community detection using label propagation in large-scale complex networks［J］.IEEE Trans on Knowledge and Data Engineering，2019，31（9）：1736-1749.

［19］Sun Heli，Huang Jianbin，Tian Yongqiang， et al.Detecting overlapping communities in networks via dominant label propagation［J］.Chinese Physics B，2015，24（1）：018703.

［20］Shen Huawei.Detecting the overlapping and hierarchical community structure in networks［M］//Community Structure of Complex Networks.Berlin：Springer，2013：19-44.

［21］Nicosia V，Mangioni G，Carchiolo V，et al.Extending the definition of modularity to directed graphs with overlapping communities［J］.Journal of Statistical Mechanics Theory amp; Experiment，2009（3）：3166-3168.

［22］Lázár A，ábel D，Vicsek T.Modularity measure of networks with overlapping communities［J］.EPL（Europhysics Letters），2010，90（1）：983-995.

［23］Rossetti G，Milli L，Cazabet R.CDLIB：a python library to extract，compare and evaluate communities from complex networks［J］.Applied Network Science，2019，4（7）：article No.52.

［24］范天龍.網絡中的圈結構［EB/OL］.（2022-01-04）.https：//swarma.org/？p=31541.2021-8-10/2022-4-4.（Fan Tianlong.Cycle structure in a network［EB/OL］.（2022-01-04）.https：//swarma.org/？p=31541.2021-8-10/2022-4-4.）

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

［26］鄭文萍，畢欣琦，楊貴.一種基于非對稱三角形割的重疊社區發現算法［J］.南京師范大學學報：工程技術版，2022，22（1）：1-8.（Zheng Wenping，Bi Xinqi，Yang Gui.An overlapping community detection algorithm based on asymmetric triangle cuts［J］.Journal of Nanjing Normal University：Engineering and Technology Edition，2022，22（1）：1-8.）

［27］潘劍飛，董一鴻，陳華輝，等.基于結構緊密性的重疊社區發現算法［J］.電子學報，2019，47（1）：145-152.（Pan Jianfei，Dong Yihong，Chen Huahui，et al.Overlapping community discovery algorithm based on compact structure［J］.Acta Electronica Sinica，2019，47（1）：145-152.）

［28］Lancichinetti A，Fortunato S，Kertész J.Detecting the overlapping and hierarchical community structure of complex networks［J］.New Journal of Physics，2009，11（3）：033015.

［29］McDaid A F，Greene D，Hurley N.Normalized mutual information to evaluate overlapping community finding algorithms［EB/OL］.（2013-08-02）.https：//arxiv.org/pdf/1110.2515.pdf.