基于中心節(jié)點(diǎn)和社區(qū)吸引力的重疊社區(qū)識(shí)別算法

姚繼強(qiáng)，鄧琨，劉星妍，趙陽，朱瑩，凡欣

(1.浙江師范大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，浙江金華 321004；2.嘉興學(xué)院：a.信息科學(xué)與工程學(xué)院,b.浙江省醫(yī)學(xué)電子與數(shù)字健康重點(diǎn)實(shí)驗(yàn)室，c.外國(guó)語學(xué)院,d.材料與紡織工程學(xué)院，浙江嘉興 314001)

世界上的復(fù)雜系統(tǒng)通常能夠形式化成復(fù)雜網(wǎng)絡(luò)，[1]如人與人之間的社交網(wǎng)絡(luò)、[2]疫情傳播網(wǎng)絡(luò)等.分析復(fù)雜網(wǎng)絡(luò)發(fā)現(xiàn)，網(wǎng)絡(luò)中存在社區(qū)結(jié)構(gòu)特性，通常表現(xiàn)為社區(qū)內(nèi)部節(jié)點(diǎn)連接緊密、社區(qū)之間節(jié)點(diǎn)連接稀疏的特點(diǎn)，而在現(xiàn)實(shí)世界的網(wǎng)絡(luò)中，社區(qū)結(jié)構(gòu)通常表現(xiàn)出重疊性，即網(wǎng)絡(luò)中存在部分節(jié)點(diǎn)同時(shí)屬于多個(gè)社區(qū)，這類節(jié)點(diǎn)稱為重疊節(jié)點(diǎn)，而這種社區(qū)結(jié)構(gòu)叫做重疊社區(qū).[3]本文將討論的是復(fù)雜網(wǎng)絡(luò)重疊社區(qū)識(shí)別，也就是識(shí)別出不同復(fù)雜網(wǎng)絡(luò)中的重疊社區(qū)結(jié)構(gòu)，其對(duì)于掌握現(xiàn)實(shí)網(wǎng)絡(luò)中的結(jié)構(gòu)特征和運(yùn)行機(jī)理具有重要現(xiàn)實(shí)意義，并被廣泛應(yīng)用于輿情分析與控制[4]、內(nèi)容推薦[5]、網(wǎng)絡(luò)信息通信[6]等方面.

1 研究基礎(chǔ)與CDCNCA算法簡(jiǎn)介

1.1 研究基礎(chǔ)

近年來，學(xué)者提出了許多優(yōu)秀的重疊社區(qū)識(shí)別算法.首先，基于標(biāo)簽傳播的COPRA算法為每個(gè)節(jié)點(diǎn)初始化標(biāo)簽以及隸屬度系數(shù)，并根據(jù)鄰居節(jié)點(diǎn)的標(biāo)簽和隸屬度系數(shù)更新標(biāo)簽，當(dāng)所有節(jié)點(diǎn)的標(biāo)簽不再變化后算法結(jié)束，此時(shí)，具有相同標(biāo)簽的節(jié)點(diǎn)為同一社區(qū)，具有多個(gè)標(biāo)簽的節(jié)點(diǎn)為重疊節(jié)點(diǎn)；[7]基于上述算法，Ding等利用節(jié)點(diǎn)度和鄰居度之和計(jì)算節(jié)點(diǎn)密度，并將密度較大的節(jié)點(diǎn)作為社區(qū)中心節(jié)點(diǎn)，然后采用基于鄰居信息的多標(biāo)簽傳播策略更新標(biāo)簽，從而找到社區(qū)結(jié)構(gòu).[8]基于團(tuán)滲透的CPM算法致力于尋找網(wǎng)絡(luò)中的完全子圖，并通過團(tuán)滲透的方式識(shí)別社區(qū)；[9]基于這一算法，Yan等找到了網(wǎng)絡(luò)中的完全子圖并將其作為初始核心，然后合并相似度較高的初始核心以產(chǎn)生社區(qū)核心，通過適應(yīng)度函數(shù)將社區(qū)核心擴(kuò)展成社區(qū).[10]基于邊聚類的LC算法則利用邊屬于單個(gè)社區(qū)的性質(zhì)，以另一個(gè)角度識(shí)別社區(qū)，通過計(jì)算邊之間相似度，構(gòu)造邊社區(qū)層次樹，并以D函數(shù)切割層次樹，從而實(shí)現(xiàn)最優(yōu)社區(qū)劃分；[11]基于此算法，Chen等將原始網(wǎng)絡(luò)結(jié)構(gòu)轉(zhuǎn)換為鏈接網(wǎng)絡(luò)，利用改進(jìn)的距離動(dòng)力學(xué)模型發(fā)現(xiàn)鏈接網(wǎng)絡(luò)的非重疊社區(qū)結(jié)構(gòu)，并將其轉(zhuǎn)換為原始網(wǎng)絡(luò)的重疊社區(qū)結(jié)構(gòu)，從而完成社區(qū)識(shí)別任務(wù).[12]

基于種子的局部擴(kuò)展算法通常從網(wǎng)絡(luò)的種子節(jié)點(diǎn)或者種子社區(qū)開始，利用網(wǎng)絡(luò)局部信息識(shí)別社區(qū).LFM算法隨機(jī)選取未歸屬社區(qū)的節(jié)點(diǎn)作為種子，以節(jié)點(diǎn)提高社區(qū)的適應(yīng)度值作為加入社區(qū)的評(píng)判標(biāo)準(zhǔn)，以此將種子擴(kuò)展成社區(qū).[13]這種以隨機(jī)節(jié)點(diǎn)作為種子的方式，會(huì)導(dǎo)致所識(shí)別社區(qū)不穩(wěn)定.GCE算法則用較小完全子圖作為種子，對(duì)適應(yīng)度函數(shù)進(jìn)行貪婪優(yōu)化，以此發(fā)現(xiàn)重疊社區(qū).[14]此種采用完全子圖作為種子的方式，使其在尋找種子階段時(shí)間復(fù)雜度較高，并對(duì)網(wǎng)絡(luò)結(jié)構(gòu)要求嚴(yán)格，不適用于規(guī)模較大的稀疏網(wǎng)絡(luò).利用半局部相似度對(duì)網(wǎng)絡(luò)邊進(jìn)行加權(quán)，根據(jù)邊的總權(quán)重求得節(jié)點(diǎn)強(qiáng)度，將節(jié)點(diǎn)強(qiáng)度最大的節(jié)點(diǎn)作為種子節(jié)點(diǎn)，可不斷優(yōu)化歸屬度函數(shù)并將種子節(jié)點(diǎn)擴(kuò)展成社區(qū).[15]該算法在社區(qū)擴(kuò)展時(shí)只考慮相鄰節(jié)點(diǎn)，但往往單靠一階鄰居節(jié)點(diǎn)不足以充分利用網(wǎng)絡(luò)結(jié)構(gòu)信息，從而降低了社區(qū)識(shí)別效率.[16]將節(jié)點(diǎn)度數(shù)作為中心節(jié)點(diǎn)的評(píng)價(jià)指標(biāo)，并以此構(gòu)建種子進(jìn)行社區(qū)識(shí)別，此算法將節(jié)點(diǎn)度中心性高的節(jié)點(diǎn)作為種子節(jié)點(diǎn)，可能并不適合應(yīng)用在社區(qū)識(shí)別領(lǐng)域.[17]上述社區(qū)識(shí)別算法雖然對(duì)于識(shí)別社區(qū)都有一定的優(yōu)勢(shì)，但在種子選取策略和社區(qū)擴(kuò)展策略上仍然存在問題.

1.2 CDCNCA算法簡(jiǎn)介

本文提出基于中心節(jié)點(diǎn)和社區(qū)吸引力的重疊社區(qū)識(shí)別算法(Overlapping Community Detection Algorithm Based on Central Node and Community Attraction，簡(jiǎn)稱CDCNCA算法).在局部中心節(jié)點(diǎn)識(shí)別階段，利用節(jié)點(diǎn)度數(shù)以及節(jié)點(diǎn)與相鄰節(jié)點(diǎn)的區(qū)域內(nèi)部連通性給出節(jié)點(diǎn)中心性系數(shù)，通過局部搜索找到中心節(jié)點(diǎn)，并作為社區(qū)擴(kuò)展階段的種子社區(qū)；在社區(qū)擴(kuò)展階段，考慮社區(qū)對(duì)一階鄰居節(jié)點(diǎn)的直接吸引力以及社區(qū)對(duì)二階鄰居節(jié)點(diǎn)的間接吸引力，以社區(qū)對(duì)這兩類節(jié)點(diǎn)的吸引力作為節(jié)點(diǎn)歸屬社區(qū)的判斷標(biāo)準(zhǔn)；最后，在不預(yù)設(shè)閾值的情況下，對(duì)重疊節(jié)點(diǎn)進(jìn)行處理，使重疊節(jié)點(diǎn)識(shí)別更為準(zhǔn)確，從而提高社區(qū)識(shí)別準(zhǔn)確率.CDCNCA算法主要在3個(gè)方面有所創(chuàng)新：第一，利用節(jié)點(diǎn)度數(shù)和局部連通性建立局部中心節(jié)點(diǎn)評(píng)價(jià)模型，并通過局部搜索找到中心節(jié)點(diǎn)，將其作為社區(qū)擴(kuò)展階段的種子社區(qū)；第二，通過吸引力度量公式對(duì)社區(qū)的一階鄰居節(jié)點(diǎn)與二階鄰居節(jié)點(diǎn)是否能加入社區(qū)進(jìn)行評(píng)判，彌補(bǔ)僅考慮一階鄰居節(jié)點(diǎn)的片面性，提高社區(qū)識(shí)別的準(zhǔn)確率和效率；第三，在無需預(yù)先設(shè)置參數(shù)的情況下，對(duì)重疊節(jié)點(diǎn)作進(jìn)一步分析處理，以完成社區(qū)識(shí)別任務(wù).

2 CDCNCA算法

2.1 局部中心節(jié)點(diǎn)識(shí)別算法

通常，復(fù)雜網(wǎng)絡(luò)表示為G=(V,E)，其中V代表網(wǎng)絡(luò)中節(jié)點(diǎn)個(gè)數(shù)為n的節(jié)點(diǎn)集合，E代表網(wǎng)絡(luò)中連接個(gè)數(shù)為m的邊集合.在復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)中，N(u)表示節(jié)點(diǎn)u的鄰居節(jié)點(diǎn)集合，定義為：N(u)={v|(u,v)∈E,v∈V}，節(jié)點(diǎn)度表示為D(u)=|N(u)|.

在復(fù)雜網(wǎng)絡(luò)中，正確選取作為種子的中心節(jié)點(diǎn)對(duì)識(shí)別社區(qū)的準(zhǔn)確度有直接影響.[18]因此，準(zhǔn)確找到局部中心節(jié)點(diǎn)使其他節(jié)點(diǎn)在加入社區(qū)時(shí)更具目的性，也能快速加入社區(qū)，并且減少算法在社區(qū)擴(kuò)展過程中的隨機(jī)性.

圖1 復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)圖

關(guān)于中心節(jié)點(diǎn)擴(kuò)展的研究通常把節(jié)點(diǎn)度高的節(jié)點(diǎn)作為網(wǎng)絡(luò)中心節(jié)點(diǎn)，未必適合在社區(qū)識(shí)別過程中應(yīng)用.[19]因此，本算法同時(shí)考慮節(jié)點(diǎn)度以及節(jié)點(diǎn)與相鄰節(jié)點(diǎn)的區(qū)域內(nèi)部連通性這兩個(gè)特性，以此提高局部中心節(jié)點(diǎn)的識(shí)別準(zhǔn)確率.復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)圖如圖1所示，節(jié)點(diǎn)b的度為6，但它被兩個(gè)社區(qū)共有，屬于邊界節(jié)點(diǎn).雖然a、c的節(jié)點(diǎn)度分別只為5和4，但其與鄰居節(jié)點(diǎn)之間連通性強(qiáng)并共同組成了一個(gè)連接稠密的小網(wǎng)絡(luò)，有理由相信節(jié)點(diǎn)a、c可以作為局部中心節(jié)點(diǎn).局部社區(qū)識(shí)別算法克服了只通過節(jié)點(diǎn)度數(shù)尋找局部中心節(jié)點(diǎn)的局限性.在給出局部中心節(jié)點(diǎn)識(shí)別算法前，先給出局部連通性和節(jié)點(diǎn)中心性系數(shù)的定義.

(1)

由定義1可知，在n固定的情況下，d越大，說明區(qū)域范圍內(nèi)節(jié)點(diǎn)連接越緊密，則節(jié)點(diǎn)x所在局部連通性越強(qiáng)，這符合社區(qū)結(jié)構(gòu)中局部中心節(jié)點(diǎn)擁有高連通性的直觀認(rèn)識(shí).

定義2(中心性系數(shù))若節(jié)點(diǎn)x∈V、D(x)表示節(jié)點(diǎn)的度，則節(jié)點(diǎn)x的中心性系數(shù)可以表示為

(2)

可以看出，節(jié)點(diǎn)的中心性系數(shù)由節(jié)點(diǎn)度和表示局部連接緊密度的局部連通性共同決定，即從節(jié)點(diǎn)的個(gè)體角度與個(gè)體所在區(qū)域的角度共同分析節(jié)點(diǎn)在網(wǎng)絡(luò)中的角色，局部中心節(jié)點(diǎn)識(shí)別算法如算法1所示.

算法1局部中心節(jié)點(diǎn)識(shí)別算法

輸入網(wǎng)絡(luò)G=(V,E)

輸出局部中心節(jié)點(diǎn)集合S

1)begin

2)初始化集合S為空

3)whileV中未被訪問的節(jié)點(diǎn)集合NV不為空

4) 從NV中隨機(jī)選取一個(gè)節(jié)點(diǎn)node

5)cnode←根據(jù)公式(1)、(2)計(jì)算節(jié)點(diǎn)node的中心性系數(shù)

6)maxC=-1

7) whilecnode>maxC

8)maxC=cnode

9)Nnode←節(jié)點(diǎn)node的鄰居節(jié)點(diǎn)集合

10) whileNnodei∈Nnode

11)C(Nnodei)←節(jié)點(diǎn)Nnodei的中心性系數(shù)

12) ifC(Nnodei)>cnode

13)cnode=C(Nnodei)

14)node=Nnodei

15) end if

16)Nnodei節(jié)點(diǎn)標(biāo)記為已訪問

17) end while

18)end while

19)S=S∪node

20)end while

21)end

在算法1中，第1～2行將中心節(jié)點(diǎn)集合初始化為空；第3～4行在網(wǎng)絡(luò)中隨機(jī)選取一個(gè)未被訪問的節(jié)點(diǎn)；第5行計(jì)算隨機(jī)選取節(jié)點(diǎn)的中心性系數(shù)；第7～19行將隨機(jī)選取節(jié)點(diǎn)的中心性系數(shù)與其鄰居節(jié)點(diǎn)的中心性系數(shù)進(jìn)行比較，一直沿著該值增大的方向進(jìn)行訪問，直到所訪問的區(qū)域內(nèi)該節(jié)點(diǎn)的中心性系數(shù)最大，則此節(jié)點(diǎn)作為局部中心節(jié)點(diǎn)；第20行代表網(wǎng)絡(luò)中的節(jié)點(diǎn)都已被訪問，算法結(jié)束.

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

本社區(qū)識(shí)別算法為基于中心節(jié)點(diǎn)和社區(qū)吸引力的重疊社區(qū)識(shí)別算法.通過算法1找到復(fù)雜網(wǎng)絡(luò)的局部中心節(jié)點(diǎn)，將其看作社區(qū)擴(kuò)展過程中的種子社區(qū)，計(jì)算社區(qū)對(duì)節(jié)點(diǎn)的吸引力，并將其作為社區(qū)擴(kuò)展的依據(jù).本社區(qū)擴(kuò)展算法不僅考慮社區(qū)對(duì)一階鄰居節(jié)點(diǎn)的吸引力，同時(shí)考慮社區(qū)對(duì)二階鄰居節(jié)點(diǎn)的吸引力，避免僅考量一階鄰居節(jié)點(diǎn)作為待加入節(jié)點(diǎn)的片面性，提高了社區(qū)識(shí)別的準(zhǔn)確率.

定義3(社區(qū)-節(jié)點(diǎn)直接吸引力)設(shè)BC為社區(qū)擴(kuò)展過程中的社區(qū)，節(jié)點(diǎn)v是社區(qū)BC的一階鄰居節(jié)點(diǎn)，社區(qū)BC對(duì)一階鄰居節(jié)點(diǎn)v的吸引力叫做直接吸引力，S(u,v)表示節(jié)點(diǎn)u和節(jié)點(diǎn)v的相似度，這里用Jaccard相似度求得；BCc、BCc+v分別表示節(jié)點(diǎn)v加入前與加入后的社區(qū)；m、m′表示節(jié)點(diǎn)v加入社區(qū)BC前后社區(qū)內(nèi)部的邊數(shù).具體表示為

(3)

從直接吸引力函數(shù)可以看出，前半部分是節(jié)點(diǎn)v未加入到社區(qū)BC時(shí)，其社區(qū)內(nèi)部節(jié)點(diǎn)間的平均相似度；后半部分是節(jié)點(diǎn)v加入到社區(qū)BC后，其社區(qū)內(nèi)部節(jié)點(diǎn)間的平均相似度，其中差值代表被吸引節(jié)點(diǎn)對(duì)社區(qū)內(nèi)部稠密程度影響的度量.直接吸引力大于0，則說明被吸引力節(jié)點(diǎn)對(duì)社區(qū)稠密度為正影響，可以將此節(jié)點(diǎn)加入到社區(qū)中，反之說明被吸引力節(jié)點(diǎn)會(huì)使社區(qū)內(nèi)部稠密度降低，此節(jié)點(diǎn)不應(yīng)該加到該社區(qū)中.

定義4(社區(qū)-節(jié)點(diǎn)間接吸引力)設(shè)BC為社區(qū)擴(kuò)展過程中的社區(qū)，節(jié)點(diǎn)u是社區(qū)的二階鄰居節(jié)點(diǎn)，社區(qū)BC對(duì)二階鄰居節(jié)點(diǎn)u的吸引力叫做間接吸引力，具體表示為

(4)

可以看出，社區(qū)對(duì)節(jié)點(diǎn)的間接吸引力表示為社區(qū)BC中的節(jié)點(diǎn)對(duì)節(jié)點(diǎn)u的吸引力最大值，現(xiàn)給出節(jié)點(diǎn)間的間接吸引力定義.

定義5(節(jié)點(diǎn)間的間接吸引力)設(shè)節(jié)點(diǎn)i,j∈V且滿足N(i)∩N(j)≠?、i?N(j)、j?N(i)，因此，節(jié)點(diǎn)間的間接吸引力可定義為

(5)

由公式可知，公式前半部分為邊相似度函數(shù)，用來計(jì)算節(jié)點(diǎn)i、j之間兩條邊的相似度，以此量化節(jié)點(diǎn)間的吸引力；邊相似度越高，說明節(jié)點(diǎn)間的互相吸引力越大.公式的后半部分為節(jié)點(diǎn)i、j的公共鄰居節(jié)點(diǎn)與去除節(jié)點(diǎn)i、j之外的其他相鄰節(jié)點(diǎn)平均相似度的總和，其含義為對(duì)節(jié)點(diǎn)i、j產(chǎn)生的排斥力.例如，在現(xiàn)實(shí)社交網(wǎng)絡(luò)中，擁有共同朋友的兩個(gè)人具有相似愛好，但此共同朋友可能不止一個(gè)愛好，導(dǎo)致這兩個(gè)人建立朋友關(guān)系時(shí)有其他阻礙.在給出上述定義后，社區(qū)擴(kuò)展算法可表述為算法2.

算法2社區(qū)擴(kuò)展算法

輸入 局部中心節(jié)點(diǎn)集合CN，復(fù)雜網(wǎng)絡(luò)G

輸出 重疊社區(qū)結(jié)構(gòu)C

1) begin

2) 初始化集合為空

3) whilec∈CN

4)BC←僅包含c的社區(qū)

5)n∈neighborNodes←社區(qū)的一階鄰居節(jié)點(diǎn)集合

6) while true

7) whilen∈neighborNodes

8)sim_dict(BC,n)←根據(jù)公式(3)計(jì)算BC對(duì)n的直接吸引力

9) end while

10)smax←sim_dict最大值

11) ifsmax>0

12)nmax←smax對(duì)應(yīng)的一階鄰居節(jié)點(diǎn)

13)neighborNodes′←節(jié)點(diǎn)nmax的鄰居節(jié)點(diǎn)集合

14)neighborNodes′←neighborNodes′-neighborNodes′∩BC

15) whilei∈neighborNodes′

16)sim_indict(BC,i)←根據(jù)公式(4)、(5)計(jì)算BC對(duì)i的間接吸引力

17) ifsim_indict(BC,i)>0

18) 將節(jié)點(diǎn)i加入到BC中

19) end if

20) end while

21) 將節(jié)點(diǎn)nmax加入到BC中

22) 更新BC的鄰居節(jié)點(diǎn)集合neighborNodes

23) ifBC不再變化 break;

24) end if

25) end if

26) end while

27)C←C∪BC

28) end while

29)C←找到的社區(qū)結(jié)構(gòu)

30)end

在算法2中，第1～2行是初始化集合；第7～9行是求社區(qū)對(duì)一階鄰居節(jié)點(diǎn)的直接吸引力值；第10～21行是得到直接吸引力最大值對(duì)應(yīng)的一階鄰居節(jié)點(diǎn)和其相鄰節(jié)點(diǎn)為社區(qū)二階鄰居節(jié)點(diǎn)的節(jié)點(diǎn)集合，計(jì)算社區(qū)對(duì)該類節(jié)點(diǎn)的間接吸引力值，將滿足條件的一階鄰居節(jié)點(diǎn)與二階鄰居節(jié)點(diǎn)加入到社區(qū)中；第22行是執(zhí)行一次操作后的社區(qū)鄰居節(jié)點(diǎn)集合；第23～24行是判斷社區(qū)結(jié)構(gòu)是否變化，若不再變化則跳出循環(huán)并得到社區(qū)結(jié)果.

2.3 重疊節(jié)點(diǎn)分析

目前，眾多重疊社區(qū)識(shí)別算法需要預(yù)設(shè)參數(shù)對(duì)重疊節(jié)點(diǎn)進(jìn)行處理，但在網(wǎng)絡(luò)信息無法掌握的情況下，設(shè)置閾值變得不太現(xiàn)實(shí).因此，本文提出一種只需掌握重疊節(jié)點(diǎn)的點(diǎn)邊信息就能準(zhǔn)確識(shí)別重疊節(jié)點(diǎn)的分析方法，以此提高算法的普適性.

定義6(社區(qū)緊密度評(píng)價(jià)指標(biāo))設(shè)節(jié)點(diǎn)i為網(wǎng)絡(luò)中的一個(gè)節(jié)點(diǎn)，社區(qū)C為已劃分的社區(qū)，mc表示社區(qū)C內(nèi)部擁有的邊數(shù)，nc表示社區(qū)C內(nèi)部擁有的節(jié)點(diǎn)數(shù)，則社區(qū)緊密度評(píng)價(jià)指標(biāo)表示為

(6)

由上述定義可知，以社區(qū)內(nèi)部邊數(shù)量和社區(qū)內(nèi)部點(diǎn)數(shù)量的比例作為評(píng)價(jià)指標(biāo)，可以看出當(dāng)社區(qū)緊密度評(píng)價(jià)指標(biāo)越大時(shí)，社區(qū)內(nèi)部節(jié)點(diǎn)連接越緊密.

定義7(社區(qū)緊密度增量)若節(jié)點(diǎn)i為一個(gè)重疊節(jié)點(diǎn)，CCc+i為重疊節(jié)點(diǎn)i加入社區(qū)C后的社區(qū)緊密度評(píng)價(jià)指標(biāo)，CCc為重疊節(jié)點(diǎn)i未加入社區(qū)C后的社區(qū)緊密度評(píng)價(jià)指標(biāo).因此社區(qū)緊密度增量可以表示為

ΔCC=CCc+i-CCc

(7)

可以看出，當(dāng)ΔCC>0時(shí)，重疊節(jié)點(diǎn)i加入社區(qū)C使得社區(qū)緊密度增大，反之社區(qū)緊密度減小.ΔCC越大，說明節(jié)點(diǎn)i加入社區(qū)C使社區(qū)內(nèi)部節(jié)點(diǎn)越緊密.因此，通過社區(qū)緊密度增量可以判斷重疊節(jié)點(diǎn)是否屬于某社區(qū).重疊節(jié)點(diǎn)分析算法如算法3所示.

算法3重疊節(jié)點(diǎn)分析算法

輸入 已劃分社區(qū)結(jié)構(gòu)C={C1,C2,…,Cn}，重疊節(jié)點(diǎn)集合O

輸出 重疊節(jié)點(diǎn)分析后的社區(qū)結(jié)構(gòu)

1) begin

2) for eacho∈O

3)OC←o所屬的社區(qū)

4) for eachc∈OC

5) 根據(jù)公式(6)、(7)計(jì)算ΔCC

6) ifΔCC<0

7) 將節(jié)點(diǎn)o從社區(qū)c中刪除

8) end if

9) end for

10) end for

11)end

2.4 CDCNCA算法

CDCNCA算法利用局部中心節(jié)點(diǎn)識(shí)別算法，得到網(wǎng)絡(luò)中的局部中心節(jié)點(diǎn)集，使得局部中心節(jié)點(diǎn)組成的社區(qū)可以將周圍節(jié)點(diǎn)快速吸引到社區(qū)中，確保算法快速收斂；在社區(qū)擴(kuò)展階段，以局部中心節(jié)點(diǎn)作為種子社區(qū)進(jìn)行社區(qū)擴(kuò)展，因?yàn)榫植恐行墓?jié)點(diǎn)擁有較高的區(qū)域中心性，其范圍內(nèi)的節(jié)點(diǎn)在加入社區(qū)時(shí)更具目標(biāo)性，從而減小社區(qū)擴(kuò)展過程的隨機(jī)性，增強(qiáng)社區(qū)結(jié)構(gòu)的穩(wěn)定性.另外，社區(qū)邊界節(jié)點(diǎn)由于受到多個(gè)社區(qū)的吸引，容易成為重疊節(jié)點(diǎn).為了提高社區(qū)識(shí)別的準(zhǔn)確性，利用重疊節(jié)點(diǎn)分析算法對(duì)重疊節(jié)點(diǎn)進(jìn)行處理，以社區(qū)緊密度增量為評(píng)價(jià)指標(biāo)，精確識(shí)別重疊節(jié)點(diǎn)，從而找到網(wǎng)絡(luò)的重疊社區(qū)結(jié)構(gòu).CDCNCA算法具體表述為算法4.

算法4CDCNCA算法

1) 通過局部中心節(jié)點(diǎn)識(shí)別算法得到局部中心節(jié)點(diǎn)集合S

2)S作為社區(qū)擴(kuò)展算法的輸入，輸出網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)C

3) 通過網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)C得到重疊節(jié)點(diǎn)集合O

4) 社區(qū)結(jié)構(gòu)C和重疊集合O為重疊節(jié)點(diǎn)分析算法的輸入，輸出處理完成的社區(qū)結(jié)構(gòu)

5) 算法完成，返回最終社區(qū)劃分

2.5 算法復(fù)雜度分析

設(shè)網(wǎng)絡(luò)G共有n個(gè)節(jié)點(diǎn)、m條邊，節(jié)點(diǎn)的平均度為k，社區(qū)的平均節(jié)點(diǎn)數(shù)為w，網(wǎng)絡(luò)G的局部核心節(jié)點(diǎn)數(shù)為c，社區(qū)擴(kuò)展過程發(fā)現(xiàn)的重疊節(jié)點(diǎn)數(shù)為o.在算法1尋找局部中心節(jié)點(diǎn)過程中，計(jì)算節(jié)點(diǎn)中心性系數(shù)c(x)所需的最壞時(shí)間復(fù)雜度為O(k(k-1)/2)，每個(gè)節(jié)點(diǎn)與其鄰居節(jié)點(diǎn)的中心性系數(shù)進(jìn)行比較的時(shí)間復(fù)雜度為O(k)，從而找到局部中心節(jié)點(diǎn)的時(shí)間復(fù)雜度為O((k(k-1)/2+k))，所以算法1的最壞時(shí)間復(fù)雜度為O(k2n).在進(jìn)行社區(qū)擴(kuò)展時(shí)，要判斷由局部核心節(jié)點(diǎn)構(gòu)成的社區(qū)對(duì)其一階鄰居節(jié)點(diǎn)和二階鄰居節(jié)點(diǎn)的作用力：在分析社區(qū)的一階鄰居節(jié)點(diǎn)時(shí)，最壞情況下所需時(shí)間為O(cwk)；對(duì)于社區(qū)二階鄰居節(jié)點(diǎn)的判斷，其最壞時(shí)間復(fù)雜度為O(cwk2).因此，社區(qū)擴(kuò)展過程的時(shí)間復(fù)雜度為O(cwk+cwk2).在重疊節(jié)點(diǎn)分析過程中，需要考慮o個(gè)重疊節(jié)點(diǎn)的連接邊，時(shí)間復(fù)雜度為O(ko)，計(jì)算每個(gè)重疊節(jié)點(diǎn)的社區(qū)局部增量值，其最壞時(shí)間復(fù)雜度為O(ko).最終，本算法的時(shí)間復(fù)雜度為O(k2+k2n+cwk+cwk2+ko).由于在社區(qū)識(shí)別過程中，隨著迭代次數(shù)的增加，節(jié)點(diǎn)數(shù)n會(huì)遠(yuǎn)大于k和w，因此算法時(shí)間復(fù)雜度可以表示為O(k2n).

進(jìn)一步分析算法的空間復(fù)雜度可知，局部中心節(jié)點(diǎn)識(shí)別算法需要存儲(chǔ)所有節(jié)點(diǎn)的中心性系數(shù)，所需空間為O(n)；社區(qū)擴(kuò)展階段，需要存儲(chǔ)社區(qū)對(duì)一階鄰居節(jié)點(diǎn)和二階鄰居節(jié)點(diǎn)的吸引力，其空間復(fù)雜度為O(cwk+cwk2)；對(duì)重疊節(jié)點(diǎn)進(jìn)行分析時(shí)，需要的空間為O(ko).由上可知，CDCNCA算法空間復(fù)雜度為O(n+cwk+cwk2+ko).因此，算法的空間復(fù)雜度為O(n).

3 實(shí)驗(yàn)分析

本節(jié)將給出算法在真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集和人工基準(zhǔn)網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果，并與經(jīng)典算法CoEus[20]、SLPA[21]、EMOFM[22]、APAL[23]進(jìn)行對(duì)比分析，以驗(yàn)證本算法的有效性，各對(duì)比算法的提出時(shí)間和開發(fā)環(huán)境如表1所示.實(shí)驗(yàn)運(yùn)行環(huán)境是Intel Core i7-7500U 2.90GHz處理器，8GB內(nèi)存，Windows 10操作系統(tǒng).本文所提算法采用MATLAB R2021a編程.

表1 相關(guān)對(duì)比算法介紹

由于SLPA、APAL算法需要設(shè)置相關(guān)參數(shù)才能得到運(yùn)行結(jié)果，因此，這些算法的參數(shù)設(shè)置如下：對(duì)于SLPA，將迭代次數(shù)T設(shè)置為100，過濾參數(shù)r設(shè)置為0.01到0.1，取值間隔為0.01；對(duì)于APAL，參數(shù)t設(shè)置為0.1到1，取值間隔為0.1.實(shí)驗(yàn)結(jié)果選取各參數(shù)下得到的最大值進(jìn)行比較.

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

為充分評(píng)價(jià)本算法的可行性，本文采用社區(qū)識(shí)別精度評(píng)價(jià)指標(biāo)(NMI)[13]、社區(qū)連接緊密度評(píng)價(jià)指標(biāo)(EQ)[24]兩個(gè)評(píng)價(jià)指標(biāo).

3.2 實(shí)驗(yàn)方案

在采用本領(lǐng)域內(nèi)經(jīng)典的LFR-Benchmark人工基準(zhǔn)網(wǎng)絡(luò)生成器生成人工基準(zhǔn)網(wǎng)絡(luò)時(shí)，會(huì)同時(shí)給出網(wǎng)絡(luò)真實(shí)社區(qū)結(jié)構(gòu).經(jīng)典的社區(qū)識(shí)別精度評(píng)價(jià)指標(biāo)NMI是通過比較算法識(shí)別的社區(qū)結(jié)構(gòu)與網(wǎng)絡(luò)真實(shí)社區(qū)結(jié)構(gòu)之間的相似度來評(píng)價(jià)社區(qū)識(shí)別精度，從而在人工基準(zhǔn)網(wǎng)絡(luò)中運(yùn)用NMI指標(biāo)評(píng)價(jià)社區(qū)識(shí)別的精度.在真實(shí)網(wǎng)絡(luò)中，已知真實(shí)社區(qū)結(jié)構(gòu)的網(wǎng)絡(luò)較少，無法進(jìn)行算法識(shí)別社區(qū)結(jié)構(gòu)與真實(shí)社區(qū)結(jié)構(gòu)之間的精度比較，鑒于此，在真實(shí)網(wǎng)絡(luò)中，本文采用了通用的評(píng)價(jià)社區(qū)內(nèi)部節(jié)點(diǎn)連接緊密度的EQ指標(biāo)來衡量算法的識(shí)別質(zhì)量.

3.3 人工基準(zhǔn)網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果

本文采用的人工基準(zhǔn)網(wǎng)絡(luò)有以下參數(shù)：N表示網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)量；kmax表示節(jié)點(diǎn)的最大度數(shù)；Cmax與Cmin分別代表社區(qū)中擁有的最大節(jié)點(diǎn)數(shù)和最小節(jié)點(diǎn)數(shù)；On表示網(wǎng)絡(luò)中的重疊節(jié)點(diǎn)數(shù)量；Om表示重疊節(jié)點(diǎn)最多歸屬的社區(qū)數(shù)；μ是混合參數(shù)，用來控制社區(qū)結(jié)構(gòu)，μ越小，則社區(qū)結(jié)構(gòu)越明顯.本文設(shè)計(jì)了4組不同類型的網(wǎng)絡(luò)，具體如表2所示.

表2 人工基準(zhǔn)網(wǎng)絡(luò)參數(shù)設(shè)置

圖2 針對(duì)重疊節(jié)點(diǎn)分析算法的消融實(shí)驗(yàn)結(jié)果

為驗(yàn)證重疊節(jié)點(diǎn)分析算法的有效性，將使用重疊節(jié)點(diǎn)分析算法的CDCNCA算法與未使用重疊節(jié)點(diǎn)分析算法的CDCNCA算法進(jìn)行消融實(shí)驗(yàn)，采用上述人工基準(zhǔn)網(wǎng)絡(luò)，將N1和N2網(wǎng)絡(luò)設(shè)置Om=3，N3和N4網(wǎng)絡(luò)設(shè)置μ=0.1，實(shí)驗(yàn)結(jié)果如圖2所示.

從圖2可以看出，采用重疊節(jié)點(diǎn)分析算法的CDCNCA算法在4個(gè)人工基準(zhǔn)網(wǎng)絡(luò)上比未采用重疊節(jié)點(diǎn)分析算法的CDCNCA算法效果更好，取得了更高的NMI值，這是由于重疊節(jié)點(diǎn)分析算法從社區(qū)內(nèi)部節(jié)點(diǎn)連接緊密度這一角度對(duì)重疊節(jié)點(diǎn)作進(jìn)一步分析，以提高算法識(shí)別社區(qū)的準(zhǔn)確率.

人工基準(zhǔn)網(wǎng)絡(luò)參數(shù)設(shè)置的不同，可以使得網(wǎng)絡(luò)規(guī)模與復(fù)雜度具有一定區(qū)別，從而更好地驗(yàn)證各算法在不同網(wǎng)絡(luò)的性能.圖3給出了各算法在N1與N2網(wǎng)絡(luò)中針對(duì)NMI評(píng)價(jià)指標(biāo)的結(jié)果.

(a)N1

(b)N2

從圖3可以看出，針對(duì)重疊度較低的N1網(wǎng)絡(luò)，隨著Om增加，CDCNCA算法、EMOFM算法和APAL算法的社區(qū)識(shí)別精度具有下降趨勢(shì)，另外三種算法則趨于平穩(wěn).從總體上看，CDCNCA算法在Om=3～6的時(shí)候仍然取得最佳社區(qū)識(shí)別精度，SLPA算法由于隨機(jī)選取節(jié)點(diǎn)作為初始節(jié)點(diǎn)，導(dǎo)致其隨機(jī)性較強(qiáng)，故社區(qū)識(shí)別精度小于其他網(wǎng)絡(luò).在重疊節(jié)點(diǎn)較多的N2網(wǎng)絡(luò)，5種算法的社區(qū)識(shí)別精度都隨著Om的增大而逐漸減小，但CDCNCA算法的社區(qū)識(shí)別精度大于其他對(duì)比算法的社區(qū)識(shí)別精度.

圖4給出了各算法在小規(guī)模網(wǎng)絡(luò)N3和大規(guī)模網(wǎng)絡(luò)N4中的社區(qū)識(shí)別精度對(duì)比結(jié)果.可以看出，各算法的社區(qū)識(shí)別精度大都隨著μ增大而減小，這是因?yàn)殡S著μ增大，社區(qū)結(jié)構(gòu)逐漸變得模糊，增加了社區(qū)識(shí)別的難度.在小規(guī)模網(wǎng)絡(luò)N3中，當(dāng)μ=0.2時(shí)，EMOFM算法的識(shí)別社區(qū)精度大于CDCNCA算法的社區(qū)識(shí)別精度，但在其他網(wǎng)絡(luò)中，EMOFM算法求得的社區(qū)識(shí)別精度普遍小于CDCNCA算法的社區(qū)識(shí)別精度，這是由于EMOFM算法優(yōu)化社區(qū)中心時(shí)僅考慮了節(jié)點(diǎn)度數(shù)，并不完全適用于所有網(wǎng)絡(luò)，導(dǎo)致在其他網(wǎng)絡(luò)識(shí)別的社區(qū)可能存在識(shí)別精度較低的問題.由此可以看出，CDCNCA算法在不同規(guī)模網(wǎng)絡(luò)中相比于其他算法擁有較好的社區(qū)識(shí)別精度.

(a)N3

(b)N4

3.4 真實(shí)網(wǎng)絡(luò)中的實(shí)驗(yàn)結(jié)果

社區(qū)識(shí)別算法的提出是為了將其應(yīng)用到真實(shí)網(wǎng)絡(luò)中，雖然已在人工基準(zhǔn)網(wǎng)絡(luò)上驗(yàn)證了算法的有效性和可行性，但還需要進(jìn)一步驗(yàn)證其在真實(shí)網(wǎng)絡(luò)中的性能.由于在真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集中已知的真實(shí)社區(qū)結(jié)構(gòu)較少，并且都是非重疊社區(qū)，無法較好地對(duì)算法進(jìn)行全面的檢驗(yàn)，故采用EQ評(píng)價(jià)指標(biāo)來檢驗(yàn)社區(qū)內(nèi)部節(jié)點(diǎn)的連接緊密度.本節(jié)運(yùn)用表3中的真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集來驗(yàn)證各算法的社區(qū)連接緊密度.

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

表4給出了CDCNCA算法與其他算法針對(duì)7個(gè)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集求得的EQ值(“～”表示算法無法求出社區(qū)結(jié)構(gòu)或者EQ值趨近于0).從表4可知，CDCNCA在Karate、Dolphins、Polbooks、Polblogs、Internet網(wǎng)絡(luò)中EQ值最高，在Email真實(shí)網(wǎng)絡(luò)中取得的EQ值為第二，在Email網(wǎng)絡(luò)中小于EMOFM算法，在PGP網(wǎng)絡(luò)中EQ值小于SLPA算法和EMOFM算法，這是由于EMOFM算法在這兩個(gè)網(wǎng)絡(luò)中選取了較準(zhǔn)確的中心節(jié)點(diǎn).另外，SLPA算法在相對(duì)稀疏的PGP網(wǎng)絡(luò)中識(shí)別出規(guī)模較小的網(wǎng)絡(luò)，從而社區(qū)內(nèi)部節(jié)點(diǎn)連接緊密度較高.綜上可知，CDCNCA對(duì)于真實(shí)網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)具有較強(qiáng)的識(shí)別能力，對(duì)于不同規(guī)模的網(wǎng)絡(luò)都具有一定的穩(wěn)定性.這是由于CDCNCA算法采用了質(zhì)量較高的中心性系數(shù)識(shí)別中心節(jié)點(diǎn)作為種子，因此，所識(shí)別社區(qū)的社區(qū)連接緊密度較高.

表4 各算法的EQ值

4 結(jié)語

CDCNCA算法通過中心性系數(shù)評(píng)價(jià)指標(biāo)找到網(wǎng)絡(luò)中的局部中心節(jié)點(diǎn)，使網(wǎng)絡(luò)中其他節(jié)點(diǎn)在加入社區(qū)時(shí)更具目的性，從而提高社區(qū)識(shí)別的準(zhǔn)確率，加快了算法的收斂速度；而將局部中心節(jié)點(diǎn)作為種子社區(qū)，充分考慮了網(wǎng)絡(luò)結(jié)構(gòu)對(duì)社區(qū)形成過程的影響，以社區(qū)對(duì)一階鄰居節(jié)點(diǎn)和二階鄰居節(jié)點(diǎn)的吸引力作為加入社區(qū)的判斷標(biāo)準(zhǔn)，從而找到了重疊社區(qū)；對(duì)重疊節(jié)點(diǎn)的處理方法無需設(shè)置閾值，既能提高對(duì)重疊社區(qū)的識(shí)別精度，又可提高算法的普適性.CDCNCA算法僅需掌握復(fù)雜網(wǎng)絡(luò)點(diǎn)邊結(jié)構(gòu)信息，無需獲取先驗(yàn)知識(shí)便可找到重疊社區(qū)結(jié)構(gòu).

在人工基準(zhǔn)網(wǎng)絡(luò)數(shù)據(jù)集中，通過對(duì)社區(qū)識(shí)別精度分析可知，隨著重疊節(jié)點(diǎn)歸屬數(shù)Om增大，CDCNCA算法較為穩(wěn)定并且社區(qū)識(shí)別精度整體大于其他算法；隨著μ值的增大，NMI評(píng)價(jià)值逐漸減小，與其他對(duì)比算法相比，CDCNCA算法在社區(qū)識(shí)別精度方面有較大優(yōu)勢(shì).這是由于CDCNCA算法在局部中心節(jié)點(diǎn)選取時(shí)，同時(shí)考慮了局部連通性和節(jié)點(diǎn)度，并且相比其他算法，本算法在社區(qū)擴(kuò)展時(shí)另外考慮了社區(qū)對(duì)二階鄰居節(jié)點(diǎn)的吸引力，使得算法充分利用網(wǎng)絡(luò)結(jié)構(gòu)信息.另外，在7個(gè)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集中，除了PGP網(wǎng)絡(luò)數(shù)據(jù)集和Email網(wǎng)絡(luò)數(shù)據(jù)集，CDCNCA算法在EQ指標(biāo)上未取得最大值，在其他5個(gè)網(wǎng)絡(luò)中得到了對(duì)比算法中的最佳值.通過對(duì)不同規(guī)模網(wǎng)絡(luò)的劃分結(jié)果可知，CDCNCA算法可以合理地識(shí)別社區(qū)結(jié)構(gòu).因此，在人工基準(zhǔn)網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)中，CDCNCA算法都表現(xiàn)出了良好的性能，從而驗(yàn)證了本算法的可行性、有效性.