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

付立東，劉佳會，王秋紅

（1.西安科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，陜西 西安 710054；2.中國電子科技集團(tuán)有限公司第20所，陜西 西安 710068）

0 引言

重疊社區(qū)廣泛存在于現(xiàn)實(shí)世界復(fù)雜系統(tǒng)中［1］，研究重疊社區(qū)對揭示網(wǎng)絡(luò)的真實(shí)結(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)簽信息，耗費(fèi)的計(jì)算資源較多。局部擴(kuò)展方法無需網(wǎng)絡(luò)的全局結(jié)構(gòu)信息且種子擴(kuò)展過程可以并行，算法效率較高，適用于大規(guī)模復(fù)雜網(wǎng)絡(luò)［4］，但算法的劃分結(jié)果受種子質(zhì)量的影響較大。

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

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

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

1 相關(guān)理論

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

1.1 社區(qū)鄰居

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

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

1.2 邊界節(jié)點(diǎn)

陳界全等給出了邊界節(jié)點(diǎn)的數(shù)學(xué)定義，即對于網(wǎng)絡(luò)G的社區(qū)劃分C＝｛c1，c2，…，cn｝，若v∈ci，u∈cj，ci≠cj且Auv＝1，則稱節(jié)點(diǎn)v和節(jié)點(diǎn)u為邊界節(jié)點(diǎn)［16］。

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

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

2.1 種子選擇

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

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

式中 Ni為節(jié)點(diǎn)的鄰居集；di為節(jié)點(diǎn)的度；Ci＝0表示節(jié)點(diǎn)vi的所有鄰居之間都不存在連邊；Ci＝1為節(jié)點(diǎn)vi的所有鄰居之間都存在連邊。

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

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

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

式中 D（v）為節(jié)點(diǎn)v的凝聚度；Nv為節(jié)點(diǎn)v的鄰居集；dv為節(jié)點(diǎn)的度。

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

圖1 合成網(wǎng)絡(luò)G1Fig.1 Synthetic network G1

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é)點(diǎn)，否則從優(yōu)先級列表中刪除選取的種子。重復(fù)上述步驟，當(dāng)優(yōu)先級列表為空時得到多個重疊社區(qū)。下面對社區(qū)歸屬度和歸屬阻力進(jìn)行定義與分析。

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

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

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

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

定義3 歸屬阻力

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

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

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

圖2 合成網(wǎng)絡(luò)G2Fig.2 Synthetic network G2

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

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

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

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

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

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

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

2.4 算法實(shí)現(xiàn)

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

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

假設(shè)n，m，珔d，｜C｜，珔C分別為網(wǎng)絡(luò)中的所有節(jié)點(diǎn)數(shù)、連邊總數(shù)、節(jié)點(diǎn)的平均度、社區(qū)或檢測出的社區(qū)數(shù)、平均社區(qū)大小。計(jì)算節(jié)點(diǎn)凝聚度的時間復(fù)雜度為O（珔d2），基于最大堆的未分配節(jié)點(diǎn)序列時間復(fù)雜度為O（n log n）。計(jì)算節(jié)點(diǎn)社區(qū)歸屬度的復(fù)雜度為O（珔d（log珔C＋珔d））。擴(kuò)展階段的時間復(fù)雜度為O（n log n＋｜C｜珔C珔d（log珔C＋珔d））。設(shè)k表示邊界節(jié)點(diǎn)數(shù)，邊界節(jié)點(diǎn)檢查調(diào)整階段的時間復(fù)雜度為O（｜C｜k珔d2）。因此，文中算法的總時間復(fù)雜度為O（n log n＋｜C｜珔C珔d（log珔C＋珔d）＋｜C｜k珔d2）。多標(biāo)簽傳播算法（以經(jīng)典的COPRA算法為例），其時間復(fù)雜度為O（｜C｜m log（｜C｜m／n）＋｜C｜3n）?；谀K度的重疊社區(qū)發(fā)現(xiàn)算法［26］（Detecting Overlapping Communities Over Complex Network Big Data，DOC），其時間復(fù)雜度為O（n log2（n）＋n）。由于網(wǎng)絡(luò)的總節(jié)點(diǎn)數(shù)n和總邊數(shù)m要遠(yuǎn)大于社區(qū)數(shù)量和平均社區(qū)規(guī)模，因此，文中算法的時間復(fù)雜度低于上述2種算法。

4 試驗(yàn)與分析

為驗(yàn)證文中算法檢測重疊社區(qū)的有效性，將所提算法與GREESE算法、LFM算法、LECS算法和CDSAT算法在合成網(wǎng)絡(luò)和真實(shí)網(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)與真實(shí)網(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)號；ku，kv分別為節(jié)點(diǎn)u和v的度數(shù)；Ou，Ov分別為節(jié)點(diǎn)u，v所屬的社區(qū)數(shù)量。

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

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

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

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

表1 3組合成網(wǎng)絡(luò)的參數(shù)設(shè)置Table 1 Parameter settings of synthetic network about three groups

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

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

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

LFR 1合成網(wǎng)絡(luò)上的試驗(yàn)結(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)與真實(shí)社區(qū)存在偏差，NMI值明顯低于 GREESE 和文中算法。GREESE算法通過逐次迭代縮小閾值來發(fā)現(xiàn)高質(zhì)量的社區(qū)，但由于尋找耦合的種子時采用了隨機(jī)策略，所以其NMI值低于文中算法。

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

圖4 LFR 2合成網(wǎng)絡(luò)上NMI對比Fig.4 NMI comparison on LFR 2 synthetic network

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

圖5 LFR 3合成網(wǎng)絡(luò)上的NMI對比Fig.5 NMI comparison on LFR 3 synthetic network

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

表2 不同模糊參數(shù)下的D-Score對比Table 2 D-Score comparison on different fuzzy parameters

表3 不同社區(qū)規(guī)模下的D-Score對比Table 3 D-Score comparison on different size of community

表4 重疊節(jié)點(diǎn)數(shù)變化下的D-Score對比Table 4 D-Score comparison under the change of the number of overlapping nodes

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

4.3 真實(shí)網(wǎng)絡(luò)試驗(yàn)與分析

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

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

表5 真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集描述Table 5 Description of real network data sets

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

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

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

表6 真實(shí)數(shù)據(jù)集上的EQ對比Table 6 EQ comparison on a real data set

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

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

表7 真實(shí)社區(qū)結(jié)構(gòu)已知的D-Score對比Table 7 D-Score comparison of real community structures

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

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

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

圖6 邊界節(jié)點(diǎn)調(diào)整策略對算法NMI值的影響Fig.6 Effects of boundary node adjustment strategy on NMI

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

5 結(jié)論

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

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

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

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