改進(jìn)局部擴(kuò)展的復(fù)雜網(wǎng)絡(luò)重疊社區(qū)檢測算法

付立東 劉佳會 王秋紅

摘 要：為有效度量種子質(zhì)量和確定節(jié)點的社區(qū)歸屬，通過考慮節(jié)點與社區(qū)內(nèi)外的鄰域信息，提出一種改進(jìn)的局部擴(kuò)展算法來檢測復(fù)雜網(wǎng)絡(luò)中的重疊社區(qū)。利用節(jié)點凝聚度指標(biāo)度量節(jié)點對周圍鄰居的凝聚力，得到候選種子集；采用社區(qū)歸屬度和歸屬阻力指標(biāo)對種子及鄰居形成的核心區(qū)域進(jìn)行擴(kuò)展；通過社區(qū)邊界節(jié)點的移動來修正節(jié)點與社區(qū)之間不準(zhǔn)確的隸屬關(guān)系。結(jié)果表明：改進(jìn)的局部擴(kuò)展算法在合成網(wǎng)絡(luò)上的標(biāo)準(zhǔn)化互信息和真實網(wǎng)絡(luò)上的擴(kuò)展模塊度值優(yōu)于對比算法，可以有效發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)中的重疊社區(qū)，重疊社區(qū)檢測準(zhǔn)確率更高；算法所選擇的種子質(zhì)量較高，D-Score值低于對比算法，發(fā)現(xiàn)的社區(qū)個數(shù)與真實分區(qū)更為接近，社區(qū)發(fā)現(xiàn)結(jié)果更符合真實情況。研究結(jié)果便于理解復(fù)雜系統(tǒng)的性質(zhì)、特征和結(jié)構(gòu)，揭示社區(qū)的演化趨勢。

關(guān)鍵詞：局部擴(kuò)展；重疊社區(qū)；節(jié)點凝聚度；社區(qū)歸屬度；邊界節(jié)點

中圖分類號：O 157.5 文獻(xiàn)標(biāo)志碼：A

文章編號：1672-9315（2023）03-0603-10

DOI：10.13800/j.cnki.xakjdxxb.2023.0318開放科學(xué)（資源服務(wù)）標(biāo)識碼（OSID）：

An improved local extended overlapping community detection algorithm for complex networks

FU Lidong¹，LIU J_iahui¹，WANG Qiuhong²

（1.College of Computer Science and Engineering，Xian University of Science and Technology，Xian 710054，China;2.The 20th Institute of China Electronics Technology Group Co.，Ltd.，Xian 710068，China）

Abstract：In order to measure seed quality effectively and determine community attribution of nodes， an improved local extension algorithm is proposed to detect overlapping communities in complex networks by considering both node and neighborhood information inside and outside the community. Using node cohesion index to measure the cohesion of nodes to neighbors， the candidate seed set was obtained; The core area formed by seeds and neighbors was expanded by the index of community attribution degree and belongingness resistance; The inaccurate membership relationship between the node and the community is corrected by moving the boundary node of the community. The experimental results show that： The improved local extension algorithm is superior to the comparison algorithm in standardized mutual information on synthetic networks and extended modularity on real networks. It can effectively detect overlapping communities in complex networks， and the detection accuracy of overlapping communities is higher. The seed quality selected by the algorithm is higher， the D-Score value is lower than that of the comparison algorithm， the number of communities found is closer to the real area， and the community discovery results are more consistent with the real situation.The results are convenient to understand the nature， characteristics and structures of complex systems， and reveal the evolution trend of communities.

Key words：local expansion；overlapping community；node cohesion degree；community attribution degree；boundary node

0 引 言

重疊社區(qū)廣泛存在于現(xiàn)實世界復(fù)雜系統(tǒng)中^[1]，研究重疊社區(qū)對揭示網(wǎng)絡(luò)的真實結(jié)構(gòu)、發(fā)現(xiàn)網(wǎng)絡(luò)中所隱藏的復(fù)雜信息具有重要作用^[2-3]。

目前，已提出多種不同類型的重疊社區(qū)發(fā)現(xiàn)算法，包括模塊度優(yōu)化方法、標(biāo)簽傳播方法和局部擴(kuò)展方法等。模塊度優(yōu)化方法可以得到較為準(zhǔn)確的社區(qū)結(jié)構(gòu)，但存在分辨率限制，即在模塊度值最大時，往往無法發(fā)現(xiàn)小社區(qū)結(jié)構(gòu)。標(biāo)簽傳播算法時間復(fù)雜度偏低，但由于需要存儲多個標(biāo)簽信息，耗費的計算資源較多。局部擴(kuò)展方法無需網(wǎng)絡(luò)的全局結(jié)構(gòu)信息且種子擴(kuò)展過程可以并行，算法效率較高，適用于大規(guī)模復(fù)雜網(wǎng)絡(luò)^[4]，但算法的劃分結(jié)果受種子質(zhì)量的影響較大。

局部擴(kuò)展方法旨在選取種子節(jié)點，通過種子節(jié)點的鄰近節(jié)點對社區(qū)進(jìn)行擴(kuò)張^[5]。當(dāng)鄰近節(jié)點的加入不能進(jìn)一步提高社區(qū)質(zhì)量時，擴(kuò)張停止。局部適應(yīng)度算法^[6]（Local Fitness Maximization，LFM）是經(jīng)典的局部擴(kuò)展模型，隨機(jī)選擇網(wǎng)絡(luò)中的節(jié)點作為種子，并通過不斷優(yōu)化適應(yīng)度函數(shù)來擴(kuò)展種子，得到最終的社區(qū)劃分。但由于種子選取的隨機(jī)性，導(dǎo)致算法性能不夠穩(wěn)定。基于核心相似性的局部擴(kuò)展算法^[7]（Local Expansion Based on Core Similarity，LECS）改進(jìn)了LFM算法中的種子選擇和質(zhì)量函數(shù)，提出節(jié)點中心度來選擇高質(zhì)量的種子。但由于該指標(biāo)沒有考慮節(jié)點的鄰居之間不存在連邊的情況，導(dǎo)致所選出的種子質(zhì)量不高，影響了后續(xù)的網(wǎng)絡(luò)劃分?；谄玫腟AT社區(qū)檢測算法^[8]（SAT-based Community Detection，CDSAT）通過集成用戶偏好來確定每個社區(qū)的質(zhì)心，根據(jù)節(jié)點與質(zhì)心的距離來構(gòu)建社區(qū)，通過優(yōu)化目標(biāo)函數(shù)來確定最終社區(qū)的數(shù)量。貪婪耦合種子擴(kuò)展算法^[9]（Greedy Coupled-seeds，GREESE）不同于上述算法，該方法在選取種子時不再依賴于單個節(jié)點，而是將耦合種子視為初始社區(qū)來擴(kuò)展。但隨機(jī)選擇一個節(jié)點與其最相似鄰居來構(gòu)建耦合種子則會導(dǎo)致較多小社區(qū)的生成。

種子的質(zhì)量對算法劃分結(jié)果有很大的影響^[10]。高質(zhì)量的種子有助于社區(qū)擴(kuò)展為一個完整的社區(qū)結(jié)構(gòu)，而低質(zhì)量的種子則會影響后續(xù)其他節(jié)點的擴(kuò)展^[11]，從而使整個網(wǎng)絡(luò)的社區(qū)劃分精確度不高。擴(kuò)展策略設(shè)計的好壞也會影響社區(qū)的擴(kuò)張。目前，大多數(shù)的擴(kuò)展策略是以一個種子為一個初始社區(qū)，然后運行質(zhì)量函數(shù)的貪婪優(yōu)化過程來擴(kuò)展社區(qū)^[12]，而質(zhì)量函數(shù)的設(shè)計主要基于社區(qū)內(nèi)部節(jié)點之間的連通性^[13]，忽略了社區(qū)外部節(jié)點的影響。

因此，為有效度量種子質(zhì)量和確定節(jié)點的社區(qū)歸屬，從節(jié)點的度和鄰域節(jié)點之間的連通性的角度改進(jìn)局部擴(kuò)展方法的種子選擇和社區(qū)擴(kuò)展。算法主要在3個方面進(jìn)行改進(jìn)：①融合節(jié)點度和鄰域結(jié)構(gòu)緊密性定義節(jié)點凝聚度指標(biāo)，尋找高質(zhì)量的種子；②綜合考慮節(jié)點在社區(qū)內(nèi)部和社區(qū)外部的拓?fù)浣Y(jié)構(gòu)信息，提出社區(qū)歸屬度和歸屬阻力來擴(kuò)展節(jié)點；③擴(kuò)展結(jié)束后，增加社區(qū)邊界節(jié)點檢查調(diào)整，通過節(jié)點移動來調(diào)整節(jié)點與社區(qū)之間不準(zhǔn)確的歸屬關(guān)系。

1 相關(guān)理論

假設(shè)網(wǎng)絡(luò)G=（V，E），鄰接矩陣為A，那么對于網(wǎng)絡(luò)中的任意2個節(jié)點u，v，如果2個節(jié)點存在一條邊，則A_uv=1，否則A_uv=0。

1.1 社區(qū)鄰居

社區(qū)鄰居是相對于節(jié)點鄰居而言，如果社區(qū)外的一個節(jié)點u與社區(qū)內(nèi)的節(jié)點存在連邊，則把節(jié)點u看作社區(qū)的鄰居。社區(qū)外所有與社區(qū)內(nèi)的節(jié)點存在連邊的節(jié)點構(gòu)成的集合定義為社區(qū)鄰居集，主要作為擴(kuò)展階段的候選節(jié)點^[19]，見式（1）。

式中 V為網(wǎng)絡(luò)中的節(jié)點集合；C為節(jié)點v所在的社區(qū)。社區(qū)鄰居不包括種子的鄰居。

1.2 邊界節(jié)點

陳界全等給出了邊界節(jié)點的數(shù)學(xué)定義，即對于網(wǎng)絡(luò)G的社區(qū)劃分C={c₁，c₂，…，c_n}，若v∈c_i，u∈c_j，c_i≠c_j且"A_uv=1，則稱節(jié)點v和節(jié)點u為邊界節(jié)點^[16]。

2 改進(jìn)的局部擴(kuò)展算法

主要針對無向復(fù)雜網(wǎng)絡(luò)進(jìn)行研究，算法包括3個主要的過程：首先利用節(jié)點凝聚度指標(biāo)來度量節(jié)點對周圍鄰居的局部凝聚力，并根據(jù)其全局排名選取種子；然后利用社區(qū)歸屬度及歸屬阻力指標(biāo)對種子及其鄰居形成的核心區(qū)域進(jìn)行擴(kuò)展；最后基于社區(qū)邊界節(jié)點調(diào)整策略移動不合理的邊界節(jié)點，修正節(jié)點與社區(qū)之間不準(zhǔn)確的歸屬關(guān)系。

2.1 種子選擇

種子的質(zhì)量對社區(qū)發(fā)現(xiàn)結(jié)果有很大的影響。為快速有效地選擇出種子，最常用的方法是基于節(jié)點度去衡量種子質(zhì)量。節(jié)點度^[17]描述的是節(jié)點對其直接鄰居的影響力，度越大表示其領(lǐng)導(dǎo)力越強(qiáng)。該方法雖然體現(xiàn)了一個節(jié)點的領(lǐng)導(dǎo)力，但無法度量該節(jié)點長久的影響力，當(dāng)節(jié)點的鄰居之間連邊較少時，隨著網(wǎng)絡(luò)的演進(jìn)，該節(jié)點則容易受到其他節(jié)點的吸引，最終失去其領(lǐng)導(dǎo)力。因此，僅從節(jié)點度的角度不能有效衡量一個節(jié)點對周圍鄰居的凝聚力。

KITSAK等提出節(jié)點對信息的傳播能力不僅與節(jié)點度相關(guān)，而且與節(jié)點的鄰域結(jié)構(gòu)緊密程度相關(guān)^[18]。具體來說，節(jié)點度越大，鄰域結(jié)構(gòu)越緊密，節(jié)點的傳播能力越強(qiáng)。因此，應(yīng)綜合考慮節(jié)點度和鄰域結(jié)構(gòu)緊密性來選取種子。節(jié)點的聚類系數(shù)^[19]量化了其鄰居節(jié)點之間相互聚集形成社區(qū)的程度，可以用來衡量節(jié)點鄰域結(jié)構(gòu)的緊密性。節(jié)點聚類系數(shù)越大，表明鄰居之間的連邊越多，其聯(lián)系越緊密。無向無權(quán)圖中，節(jié)點v_i的聚類系數(shù)的定義見式（2）。

式中 N_i為節(jié)點的鄰居集；d_i為節(jié)點的度；C_i=0表示節(jié)點v_i的所有鄰居之間都不存在連邊;C_i=1為節(jié)點v_i的所有鄰居之間都存在連邊。

為提高種子選取的效率，對節(jié)點聚類系數(shù)進(jìn)行簡化，利用鄰居節(jié)點之間存在連邊的數(shù)量來表征節(jié)點鄰域結(jié)構(gòu)的緊密性?？紤]到只利用鄰域結(jié)構(gòu)緊密性不能處理鄰居之間無連邊的情況。因此，結(jié)合節(jié)點度和鄰域結(jié)構(gòu)緊密性來度量一個節(jié)點的凝聚力，根據(jù)節(jié)點凝聚度值對節(jié)點降序排列，并構(gòu)成優(yōu)先級列表，依次選取列表中的第一個節(jié)點即節(jié)點凝聚度最大的節(jié)點作為種子。節(jié)點凝聚度定義如下。

定義1 節(jié)點凝聚度

該指標(biāo)不僅考慮了節(jié)點的鄰居之間聯(lián)系的緊密性，而且增加了節(jié)點度信息來處理節(jié)點的鄰居之間不存在連邊的情況，從而使該指標(biāo)選擇出的節(jié)點更具有代表性，見式（3）。

式中 D（v）為節(jié)點v的凝聚度;N_v為節(jié)點v的鄰居集;d_v為節(jié)點的度。

以圖1為例，僅考慮鄰域結(jié)構(gòu)緊密性來計算節(jié)點的凝聚度，未分配節(jié)點降序排列在集合S={v₃，v₂，v₁，v₀}。若依次選取S中未分配的節(jié)點及其鄰居形成初始社區(qū)，則會生成3個小社區(qū)即C₂={v₃，v₀}、C₃={v₂}、C₄={v₁}。結(jié)合節(jié)點度和鄰域結(jié)構(gòu)緊密性來計算網(wǎng)絡(luò)中未分配節(jié)點的凝聚度，節(jié)點v₀的凝聚度大于節(jié)點v₁，v₂和v₃，因此節(jié)點v₀優(yōu)先成為初始社區(qū)的種子，吸引節(jié)點v₁，v₂和v₃的加入，從而防止了小社區(qū)的生成。因此，將節(jié)點度和鄰域結(jié)構(gòu)緊密性相結(jié)合，可以選出高質(zhì)量的種子，減少低質(zhì)量社區(qū)的生成。

2.2 社區(qū)擴(kuò)展

基于優(yōu)先級列表，對選取的種子進(jìn)行局部擴(kuò)展。首先將種子及其鄰居看作初始社區(qū)，根據(jù)社區(qū)歸屬度及歸屬阻力對不合理的種子鄰居進(jìn)行清洗，以得到與種子聯(lián)系較緊密的核心區(qū)域。然后尋找核心區(qū)域的社區(qū)鄰居，并根據(jù)社區(qū)歸屬度及歸屬阻力對其進(jìn)行擴(kuò)展，如果形成社區(qū)，從優(yōu)先級列表中刪除社區(qū)內(nèi)的節(jié)點，否則從優(yōu)先級列表中刪除選取的種子。重復(fù)上述步驟，當(dāng)優(yōu)先級列表為空時得到多個重疊社區(qū)。下面對社區(qū)歸屬度和歸屬阻力進(jìn)行定義與分析。

社區(qū)歸屬度指標(biāo)用于描述節(jié)點屬于某個社區(qū)的程度。社區(qū)歸屬度值越大，社區(qū)對其吸引力越強(qiáng)。如果待加入節(jié)點在社區(qū)中的鄰居數(shù)較多，且這些節(jié)點之間有較高的聚集程度，表明這個節(jié)點具有較大概率會加入這個社區(qū)。但一個節(jié)點是否會加入社區(qū)不但受社區(qū)內(nèi)部節(jié)點的吸引，而且會受到網(wǎng)絡(luò)中其余節(jié)點的影響，因為這些節(jié)點會阻礙節(jié)點的加入。因此，在擴(kuò)展社區(qū)時，應(yīng)同時考慮到網(wǎng)絡(luò)中其余部分節(jié)點對該節(jié)點的歸屬阻力，通過對比兩者的大小來決定一個節(jié)點的加入。因此，文中提出社區(qū)歸屬度和歸屬阻力的定義。

定義2 社區(qū)歸屬度

將節(jié)點在社區(qū)內(nèi)的鄰居數(shù)與內(nèi)部鄰居節(jié)點之間的連邊數(shù)之和定義為社區(qū)歸屬度，見式（4）。

式中 （N_u∩C）為節(jié)點u在社區(qū)內(nèi)的鄰居集；C為局部社區(qū)。

定義3 歸屬阻力

節(jié)點在社區(qū)外的鄰居數(shù)與外部鄰居節(jié)點之間的連邊數(shù)之和定義為歸屬阻力，見式（5）。

式中 （N_u∩G′）為節(jié)點u在社區(qū)外的鄰居集；G′為社區(qū)外的節(jié)點形成的網(wǎng)絡(luò)。

以圖2為例來說明社區(qū)歸屬度和歸屬阻力在擴(kuò)展節(jié)點時的應(yīng)用。

根據(jù)社區(qū)鄰居的定義可知，社區(qū)C₁的鄰居為v₈和v₉。根據(jù)式（4），節(jié)點v₈加入社區(qū)C₁的歸屬度M（v₈，C₁）=1，社區(qū)外的節(jié)點v₈，v₄，v₇，v₉構(gòu)成的網(wǎng)絡(luò)G′對節(jié)點v₈的歸屬阻力R（v₈，G′）=3。節(jié)點加入社區(qū)C₁的歸屬度小于網(wǎng)絡(luò)G′中節(jié)點對其加入的阻力，因此節(jié)點v₈不能加入社區(qū)C₁，等待后續(xù)擴(kuò)展。同理，節(jié)點v₉也不能加入社區(qū)C₁。

2.3社區(qū)邊界節(jié)點檢查調(diào)整

三支決策理論^[21]與社區(qū)劃分的結(jié)合為改進(jìn)局部擴(kuò)展方法提供了新思路^[22-23]。基于三支決策理論，學(xué)者提出邊界域中的節(jié)點由于信息量不完整可能存在重疊節(jié)點不合理，為獲得更好的社區(qū)性能，設(shè)計算法時需考慮對邊界區(qū)域中的節(jié)點進(jìn)行二次劃分^[24]。

基于上述理論，提出社區(qū)邊界節(jié)點調(diào)整策略，對分配不合理的邊界節(jié)點或未發(fā)現(xiàn)的重疊節(jié)點，通過節(jié)點的移動來修正節(jié)點與社區(qū)之間不準(zhǔn)確的歸屬關(guān)系，以得到準(zhǔn)確率更高的社區(qū)劃分結(jié)果。通過對比邊界節(jié)點在各個社區(qū)中的歸屬度值來判斷一個邊界節(jié)點所在社區(qū)是否合理。社區(qū)邊界節(jié)點調(diào)整策略針對以下3種情況。

1）邊界節(jié)點在其他社區(qū)中的歸屬度大于原始社區(qū)中的歸屬度時，將邊界節(jié)點調(diào)整到最大社區(qū)歸屬度對應(yīng)的社區(qū)，并從原社區(qū)刪除該節(jié)點。

2）歸屬度相等時，說明該邊界節(jié)點是一個重疊節(jié)點，將該邊界節(jié)點復(fù)制到歸屬度相等的社區(qū)。

3）原社區(qū)歸屬度大于其他社區(qū)歸屬度時，說明邊界節(jié)點所在位置合理，不做操作。

2.4 算法實現(xiàn)

改進(jìn)局部擴(kuò)展的復(fù)雜網(wǎng)絡(luò)重疊社區(qū)檢測算法的實現(xiàn)包括種子選擇、社區(qū)擴(kuò)展和社區(qū)邊界節(jié)點檢查調(diào)整三個過程。種子選擇過程的主要思想是以一種混合的方式來選出高質(zhì)量的種子，并限制種子和已在社區(qū)內(nèi)的節(jié)點再次成為種子。社區(qū)擴(kuò)展階段的主要思想是通過綜合考慮節(jié)點在社區(qū)內(nèi)部和社區(qū)外部的網(wǎng)絡(luò)結(jié)構(gòu)信息來擴(kuò)展節(jié)點。社區(qū)邊界節(jié)點檢查調(diào)整過程的主要思想是在得到社區(qū)劃分結(jié)果后，通過邊界節(jié)點的移動來修正節(jié)點與社區(qū)之間不準(zhǔn)確的歸屬關(guān)系，進(jìn)一步提高算法性能。算法的具體實現(xiàn)如下。

3 時間復(fù)雜度分析

由于網(wǎng)絡(luò)的總節(jié)點數(shù)n和總邊數(shù)m要遠(yuǎn)大于社區(qū)數(shù)量和平均社區(qū)規(guī)模，因此，文中算法的時間復(fù)雜度低于上述2種算法。

4 試驗與分析

為驗證文中算法檢測重疊社區(qū)的有效性，將所提算法與GREESE算法、LFM算法、LECS算法和CDSAT算法在合成網(wǎng)絡(luò)和真實網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行對比，對比算法的參數(shù)均設(shè)置為原論文中的最優(yōu)參數(shù)。

4.1 評價指標(biāo)

重疊標(biāo)準(zhǔn)化互信息NMI指標(biāo)^[6]來源于信息論中的熵，用于度量聚類結(jié)果的相似程度。NMI值越大，說明算法所發(fā)現(xiàn)的社區(qū)結(jié)構(gòu)與真實網(wǎng)絡(luò)結(jié)構(gòu)越接近，見式（6）。

式中 H（X|Y）為X在Y上的規(guī)范化條件熵。

擴(kuò)展模塊度EQ指標(biāo)^[27]用于評估重疊社區(qū)發(fā)現(xiàn)算法的性能，EQ值越大，算法識別高度聚集的社區(qū)的性能越好，見式（7）。

式中 A為網(wǎng)絡(luò)的鄰接矩陣；m為網(wǎng)絡(luò)的總邊數(shù)；i為社區(qū)標(biāo)號；k_u，k_v分別為節(jié)點u和v的度數(shù)；O_u，O_v分別為節(jié)點u，v所屬的社區(qū)數(shù)量。

D-Score指標(biāo)^[7，14]用于評估算法發(fā)現(xiàn)的社區(qū)數(shù)量與真實社區(qū)數(shù)量之間的差異，見式（8）。

式中 n^D_c為算法檢測的社區(qū)數(shù)量；n^R_c為真實社區(qū)數(shù)量。D-Score為正時，表示檢測到的社區(qū)數(shù)量大于實際社區(qū)數(shù)量；D-Score為負(fù)值時，表示檢測到的社區(qū)數(shù)量小于實際社區(qū)數(shù)量；文中采用D-Score的絕對值來評價算法的性能，其值越小，說明算法檢測出的社區(qū)數(shù)量與真實情況越接近。

4.2 合成網(wǎng)絡(luò)試驗與分析

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

LANCICHINETTI等提出的LFR基準(zhǔn)^[28]，常用于復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法的對比試驗中。通過調(diào)節(jié)模糊參數(shù)、社區(qū)規(guī)模和重疊節(jié)點數(shù)生成3組合成網(wǎng)絡(luò)數(shù)據(jù)集。具體見表1。

參數(shù)n為網(wǎng)絡(luò)中的總節(jié)點數(shù)；|C|_min為最小的社區(qū)規(guī)模；|C|_max為最大的社區(qū)規(guī)模；MU為網(wǎng)絡(luò)結(jié)構(gòu)的清晰度，其值越大，網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)越難以識別；O_n為網(wǎng)絡(luò)中的重疊節(jié)點數(shù)。

4.2.2 試驗結(jié)果與分析

5種算法在3組合成網(wǎng)絡(luò)數(shù)據(jù)集上的性能采用重疊標(biāo)準(zhǔn)化互信息NMI和D-Score指標(biāo)來評價。NMI值越大，算法檢測的社區(qū)結(jié)構(gòu)與真實分區(qū)越接近；D-Score值越小，算法所發(fā)現(xiàn)的社區(qū)個數(shù)與真實情況越一致。

LFR 1合成網(wǎng)絡(luò)上的試驗結(jié)果如圖3所示，用于研究模糊參數(shù)對算法性能的影響。5種算法的性能都隨模糊參數(shù)MU的增大而呈現(xiàn)不同程度的下降，說明5種算法的性能都受MU的影響，即網(wǎng)絡(luò)結(jié)構(gòu)清晰度會影響算法性能。

隨著混合參數(shù)的不斷變化，網(wǎng)絡(luò)的結(jié)構(gòu)特征也會發(fā)生變化。LFM、CDSAT和LECS算法通過對比質(zhì)量函數(shù)指標(biāo)值與特定閾值之間的大小來進(jìn)行局部擴(kuò)展時則會忽略每個網(wǎng)絡(luò)的結(jié)構(gòu)特征變化，從而導(dǎo)致所發(fā)現(xiàn)的社區(qū)結(jié)構(gòu)與真實社區(qū)存在偏差，NMI值明顯低于GREESE和文中算法。GREESE算法通過逐次迭代縮小閾值來發(fā)現(xiàn)高質(zhì)量的社區(qū)，但由于尋找耦合的種子時采用了隨機(jī)策略，所以其NMI值低于文中算法。

LFR2合成網(wǎng)絡(luò)上的試驗對比結(jié)果如圖4所示，用于探究社區(qū)規(guī)模對算法性能的影響。從圖4可以看出，隨著社區(qū)規(guī)模的增加，5種算法識別真實社區(qū)的性能變差。LECS，LFM和CDSAT算法隨社區(qū)規(guī)模的增加，其NMI值呈逐漸下降趨勢，GRESSE和文中算法的性能基本不隨社區(qū)規(guī)模的增加而下降。在社區(qū)規(guī)模為200時，LECS算法的NMI值最高，隨著社區(qū)規(guī)模的增加，其性能低于文中算法。原因是文中算法的擴(kuò)展規(guī)則是基于節(jié)點與社區(qū)成員關(guān)系的，社區(qū)規(guī)模越大，可利用的結(jié)構(gòu)信息越多，越有利于算法識別社區(qū)結(jié)構(gòu)。同時，文中所提出的邊界節(jié)點調(diào)整策略也進(jìn)一步提高了社區(qū)劃分的質(zhì)量。從表3可以看出，文中算法檢測出來的社區(qū)個數(shù)與真實社區(qū)個數(shù)更趨于一致。

LFR 3合成網(wǎng)絡(luò)上的試驗結(jié)果如圖5所示，用于對比重疊節(jié)點數(shù)對算法性能的影響。從圖5可知，5種算法的性能基本不受重疊節(jié)點數(shù)的影響，隨著重疊節(jié)點數(shù)的增大，5種算法的NMI值走勢比較平穩(wěn)，不會隨著O_n的增加而下降。原因是重疊節(jié)點通常遠(yuǎn)離社區(qū)的核心成員，其數(shù)量的變化基本不影響由特定種子確定的社區(qū)數(shù)量。這也體現(xiàn)了局部擴(kuò)展方法在大規(guī)模網(wǎng)絡(luò)中的優(yōu)勢。

從表2、表3和表4可以看出，LECS和LFM算法的D-Score值較大，明顯高于其他幾種算法，說明這2種算法識別出的社區(qū)數(shù)量與真實社區(qū)個數(shù)相差較大。GREESE，CDSAT和文中算法的D-Score值較小，說明這3種算法劃分的社區(qū)個數(shù)與真實分區(qū)更接近。

綜合5種算法在合成網(wǎng)絡(luò)和真實網(wǎng)絡(luò)數(shù)據(jù)集上的NMI和D-Score值，文中算法的性能較對比算法更具有優(yōu)勢。

4.3 真實網(wǎng)絡(luò)試驗與分析

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

6個真實網(wǎng)絡(luò)數(shù)據(jù)集的具體描述見表5。參數(shù)n為網(wǎng)絡(luò)的節(jié)點總數(shù)；m為網(wǎng)絡(luò)的連邊總數(shù)；c為真實網(wǎng)絡(luò)的社區(qū)個數(shù)；“-”為真實社區(qū)數(shù)量未知。

4.3.2 試驗結(jié)果與分析

在6個真實網(wǎng)絡(luò)數(shù)據(jù)集上，已知真實分區(qū)的網(wǎng)絡(luò)采用擴(kuò)展模塊度EQ和D-Score指標(biāo)評價算法性能，真實分區(qū)未知的網(wǎng)絡(luò)采用擴(kuò)展模塊度EQ對比。

表6是5種算法在真實網(wǎng)絡(luò)上的擴(kuò)展模塊度值，其中，average表示算法在6個網(wǎng)絡(luò)上的平均性能。average值越大，說明算法在真實網(wǎng)絡(luò)上的平均擴(kuò)展模塊度越高，其性能越好。

綜合算法在6個真實網(wǎng)絡(luò)上的平均性能來看，文中算法的擴(kuò)展模塊度達(dá)到0.483 1，明顯高于對比算法，這說明文中算法可以識別真實網(wǎng)絡(luò)中的重疊社區(qū)結(jié)構(gòu)，性能較對比算法有一定的提高。

在已知真實分區(qū)的網(wǎng)絡(luò)上，5種算法識別出的社區(qū)數(shù)量與真實分區(qū)之間的差異情況見表7。對比5種算法的D-Score值，文中算法在polbooks網(wǎng)絡(luò)上的D-Score值略高于CDSAT算法，在karate、dolphin和football 3個網(wǎng)絡(luò)上的D-Score值均最小，說明算法劃分的社區(qū)數(shù)量更符合真實分區(qū)。

綜合真實網(wǎng)絡(luò)上的試驗可知，文中算法的性能優(yōu)于對比算法，可以有效發(fā)現(xiàn)網(wǎng)絡(luò)中的真實社區(qū)，檢測出的社區(qū)結(jié)構(gòu)與真實情況更為一致。

4.4 社區(qū)邊界節(jié)點調(diào)整策略對算法性能的影響

為驗證邊界節(jié)點調(diào)整策略的有效性，通過對比算法在3組合成網(wǎng)絡(luò)上的重疊標(biāo)準(zhǔn)化互信息NMI值來說明該策略對算法性能的影響，結(jié)果如圖6所示。former曲線表示未實施邊界節(jié)點調(diào)整策略時的算法性能，later曲線表示算法擴(kuò)展結(jié)束后實施了邊界節(jié)點調(diào)整策略時的性能。

觀察圖6中的紅色曲線可知，在3組合成網(wǎng)絡(luò)上，邊界節(jié)點調(diào)整策略均使算法的NMI得到了不同程度的提高。這說明在擴(kuò)展結(jié)束后，通過邊界節(jié)點的移動可以修正節(jié)點與社區(qū)之間不準(zhǔn)確的歸屬關(guān)系，得到更加合理的社區(qū)結(jié)構(gòu)。其中，LFR 2和LFR 3合成網(wǎng)絡(luò)中的NMI值較LFR 1合成網(wǎng)絡(luò)有明顯提升，說明邊界節(jié)點檢查調(diào)整策略對社區(qū)規(guī)模較大或重疊節(jié)點較多的網(wǎng)絡(luò)提升效果更為明顯。

5 結(jié) 論

1）根據(jù)節(jié)點局部信息和全局排名，以一種混合的方法來選擇種子，并對種子和已在社區(qū)內(nèi)的節(jié)點限制其再次成為種子，可以得到質(zhì)量較高的種子。

2）綜合考慮節(jié)點在社區(qū)內(nèi)部和外部的拓?fù)浣Y(jié)構(gòu)信息，設(shè)計一種新的擴(kuò)展策略即利用社區(qū)歸屬度和歸屬阻力來擴(kuò)展節(jié)點。這種方法同時考慮了社區(qū)內(nèi)部節(jié)點的吸引力和社區(qū)外部網(wǎng)絡(luò)結(jié)構(gòu)對節(jié)點的歸屬阻力，可以更全面地確定節(jié)點的社區(qū)歸屬。

3）在得到社區(qū)劃分結(jié)果后，通過社區(qū)邊界節(jié)點的移動來修正節(jié)點與社區(qū)之間不準(zhǔn)確的歸屬關(guān)系，可以進(jìn)一步提高算法性能，對社區(qū)規(guī)模較大或重疊節(jié)點較多的網(wǎng)絡(luò)提升效果更為明顯。

4）合成網(wǎng)絡(luò)和真實網(wǎng)絡(luò)數(shù)據(jù)集上的D-Score和NMI值表明，文中算法劃分的社區(qū)數(shù)量與社區(qū)結(jié)構(gòu)更接近于真實情況。

參考文獻(xiàn)（References）：

[1] 李輝，張建朋，陳福才.基于流式分析的大規(guī)模網(wǎng)絡(luò)重疊社區(qū)發(fā)現(xiàn)算法[J].電子學(xué)報，2022，50：1951-1958.

LI Hui，ZHANG Jianpeng，CHEN Fucai.A streaming-based overlapping community detection algorithm in large-scale network[J].Acta Electronica Sinica，2022，50：1951-1958.

[2]李輝，陳福才，張建朋，等.復(fù)雜網(wǎng)絡(luò)中的社團(tuán)發(fā)現(xiàn)算法綜述[J].計算機(jī)應(yīng)用研究，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]AMELIO A，PIZZUTI C.Overlapping community discovery methods：A survey[C]//G?ND?Z-??D?C? ?，ETANER-UYAR A ?.Social Networks：Analysis and Case Studies.Vienna：Springer Vienna，2014：105-125.

[4]皇甫斐斐，楊陽，鄧曉懿.基于節(jié)點影響力的理性節(jié)點標(biāo)簽傳播算法[J].計算機(jī)工程與科學(xué)，2022，44（4）：713-722.

HUANGFU Feifei，YANG Yang，DENG Xiaoyi.A rational label propagation algorithm based on node influence[J].Computer Engineering & Science，2022，44（4），713-722.

[5]WHANG J J，GLEICH D F，DHILLON I S.Overlapping community detection using neighborhood-inflated seed expansion[J].IEEE Transactions on Knowledge and Data Engineering，2016，28（5）：1272-1284.

[6]LANCICHINETTI A，F(xiàn)ORTUNATO S，KERT?SZ J.Detecting the overlapping and hierarchical community structure in complex networks[J/OL].New Journal of Physics，2009，11：033015.Https：//doi.org/10.1088/1367-2630/11/3/033015.

[7]ZHANG J，DING X，YANG J.Revealing the role of node similarity and community merging in community detection[J].Knowledge Based Systems，2019，165：407-419.

[8]JABBOUR S，MHADHBI N，RADDAOUI B，et al.SAT-based models for overlapping community detection in networks[J].Computing，2020，102（5）：1275-1299.

[9]ASMI K，LOTFI D，ABARDA A.The greedy coupled-seeds expansion method for the overlapping community detection in social networks[J].Computing，2022，104（2）：295-313.

[10]YANG J X，ZHANG X D.Finding overlapping communities using seed set[J].Physica A：Statistical Mechanics and its Applications，2017，467：96-106.

[11]馮健，史丹丹，羅香玉，等.利用節(jié)點重要度和社團(tuán)接近度發(fā)現(xiàn)社團(tuán)結(jié)構(gòu)[J].西安科技大學(xué)學(xué)報，2020，40（1）：181-186.

FENG Jian，SHI Dandan，LUO Xiangyu，et al.Discovering community structure using node importance and community proximity[J].Journal of Xian University of Science and Technology，2020，40（1）：181-186.

[12]LUO W，LU N，NI L，et al.Local community detection by the nearest nodes with greater centrality[J].Information Sciences，2020，517：377-392.

[13]DING X，ZHANG J，YANG J.Node-community membership diversifies community structures：An overlapping community detection algorithm based on local expansion and boundary re-checking[J/OL].Knowledge-based Systems，2020，198：105935.Https：//doi.org/10.1016/j.knosys.2020.105935.

[14]DING X，YANG H，ZHANG J，et al.CEO：Identifying overlapping communities via construction，expansion and optimization[J].Information Sciences，2022，596：93-118.

[15]付立東，郝偉，李丹，等.基于共鄰節(jié)點相似度的社區(qū)劃分算法[J].計算機(jī)應(yīng)用，2019，39（7）：2024-2029.

FU Lidong，HAO Wei，LI Dan，et al.Community dividing algorithm based on similarity of common neighbor nodes[J].Journal of Computer Applications，2019，39（7）：2024-2029.

[16]陳界全，王占全，李真，等.基于SLPA優(yōu)化的重疊社區(qū)發(fā)現(xiàn)算法[J].計算機(jī)應(yīng)用與軟件，2021，38：297-302，329.

CHEN Jiequan，WANG Zhanquan，LI Zhen，et al.An improved overlapping community detection algorithm based on SLPA[J].Computer Application and Software，2021，38：297-302，329.

[17]CHAKRABORTY T，DALMIA A，MUKHERJEE A，et al.Metrics for community analysis：A survey[J].ACM Computing Surveys，2017，50（4）：1-37.

[18]KITSAK M，GANIN A，ELMOKASHFI A，et al.Finding shortest and nearly shortest path nodes in large substantially incomplete networks by hyperbolic mapping[J/OL].Nature Communications，2023，14（1）：186.Https：//doi.org/ 10.1038/s41467-022-35181-w.

[19]LIU J，GUO J，LI Q.A local extended algorithm combined with degree and clustering coefficient to optimize overlapping community detection[J/OL].Complexity，2021，7428927.Https：//doi.org/10.1155/2021/7428927.

[20]馬健，劉峰，李紅輝，等.采用PageRank和節(jié)點聚類系數(shù)的標(biāo)簽傳播重疊社區(qū)發(fā)現(xiàn)算法[J].國防科技大學(xué)學(xué)報，2019，41（1）：183-190.

MA Jian，LIU Feng，LI Honghui，et al.Overlapping community detection algorithm by label propagation using PageRank and node clustering coefficients[J].Journal of National University of Defense Technology，2019，41（1）：183-190.

[21]梁德翠，曹雯.三支決策模型及其研究現(xiàn)狀分析[J].電子科技大學(xué)學(xué)報（社會科學(xué)版），2019，21（1）：104-112.

LIANG Decui，CAO Wen.Three-way decisions：Model and the state of the art[J].Journal of University of Electronic Science and Technology of China（Social Science Edition），2019，21（1）：104-112.

[22]方蓮娣，張燕平，陳潔，等.基于三支決策的非重疊社團(tuán)劃分[J].智能系統(tǒng)學(xué)報，2017，12（3）：293-300.

FANG Liandi，ZHANG Yanping，CHEN Jie，et al.Three-way decision based on non-overlapping community division[J].CAAI Transactions on Intelligent Systems，2017，12（3）：293-300.

[23]王平心，劉強(qiáng)，楊習(xí)貝，等.基于動態(tài)鄰域的三支聚類分析[J].計算機(jī)科學(xué)，2018，45（1）：62-66，89.

WANG Pingxin，LIU Qiang，YANG Xibei，et al.Three-way clustering analysis based on dynamic neighborhood[J].Computer Science，2018，45（1）：62-66，89.

[24]楊雪潔，曹風(fēng)云，陳潔，等.基于子模優(yōu)化的邊界域處理社團(tuán)發(fā)現(xiàn)算法[J].電子測量與儀器學(xué)報，2020，34（4）：111-117.

YANG Xuejie，CAO Fengyun，CHEN Jie，et al.Community detection algorithm for boundary region processing based on submodular optimization[J].Journal of Electronic Measurement and Instrumentation，2020，34（4）：111-117.

[25]張應(yīng)龍，夏學(xué)文，徐星，等.面向標(biāo)簽傳播算法的社團(tuán)檢測研究現(xiàn)狀及展望[J].小型微型計算機(jī)系統(tǒng)，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.

[26]喬少杰，韓楠，張凱峰，等.復(fù)雜網(wǎng)絡(luò)大數(shù)據(jù)中重疊社區(qū)檢測算法[J].軟件學(xué)報，2017，28（3）：631-647.

QIAO Shaojie，HAN Nan，ZHANG Kaifeng，et al.Algorithm for detecting overlapping communities from complex network big data[J].Journal of Software，2017，28（3）：631-647.

[27]MA H，YANG H，ZHOU K，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.

[28]LANCICHINETTI A，F(xiàn)ORTUNATO S，RADICCHI F.Benchmark graphs for testing community detection algorithms[J/OL].Physical Review E，2008，78（4）：046110.Https：//doi.org/10.1103/PhysRevE.78.046110.

（責(zé)任編輯：劉潔）