代婷婷，劉 秀，韓 艷

基于節(jié)點(diǎn)核心度的重疊社團(tuán)檢測(cè)算法

代婷婷，劉 秀，韓 艷

（昭通學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，云南 昭通 657000）

針對(duì)含有重疊節(jié)點(diǎn)的社團(tuán)提出了新的檢測(cè)算法—NCD算法。提出了節(jié)點(diǎn)核心度的概念，按照節(jié)點(diǎn)核心度的計(jì)算方法選取簇的初始中心點(diǎn)；提出差異性函數(shù)對(duì)重疊部分的節(jié)點(diǎn)進(jìn)行識(shí)別；在中心點(diǎn)擴(kuò)展原則的指導(dǎo)下，通過(guò)判斷網(wǎng)絡(luò)中節(jié)點(diǎn)之間可否構(gòu)成三角模型對(duì)重疊社團(tuán)進(jìn)行檢測(cè)。使用了NMI和模塊度作為社團(tuán)檢測(cè)的指標(biāo)，將NCD算法應(yīng)用在3個(gè)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，結(jié)果表明，NCD算法可以高效地檢測(cè)到社團(tuán)中的重疊節(jié)點(diǎn)，同時(shí)表明了該算法與其他算法對(duì)比具有明顯的優(yōu)越性。

復(fù)雜網(wǎng)絡(luò)；社區(qū)檢測(cè)；核心度；重疊社團(tuán)

近些年來(lái)，隨著社交網(wǎng)絡(luò)和大數(shù)據(jù)技術(shù)的發(fā)展，大規(guī)模復(fù)雜網(wǎng)絡(luò)中的社團(tuán)檢測(cè)已經(jīng)成為研究的熱點(diǎn)，社團(tuán)檢測(cè)作為復(fù)雜網(wǎng)絡(luò)研究中的一項(xiàng)基本而重要的任務(wù)，旨在挖掘集合內(nèi)連接緊密，集合之間連接稀疏的節(jié)點(diǎn)集合[1]。在現(xiàn)實(shí)世界的網(wǎng)絡(luò)中，一些節(jié)點(diǎn)可能同時(shí)屬于多個(gè)社團(tuán)，即重疊的社團(tuán)結(jié)構(gòu)。因此，檢測(cè)重疊社團(tuán)的結(jié)構(gòu)很重要，有助于獲取和理解復(fù)雜網(wǎng)絡(luò)的整體結(jié)構(gòu)特征[2]。然而，傳統(tǒng)的社團(tuán)檢測(cè)算法[3]就不再有效。因?yàn)樵谥丿B社區(qū)檢測(cè)中，一個(gè)節(jié)點(diǎn)可能屬于多個(gè)社區(qū)。隨著復(fù)雜網(wǎng)絡(luò)規(guī)模的擴(kuò)大，現(xiàn)有的重疊社區(qū)挖掘算法在處理大型復(fù)雜網(wǎng)絡(luò)時(shí)效率較低，因此，需要快速準(zhǔn)確的算法應(yīng)對(duì)大規(guī)模復(fù)雜網(wǎng)絡(luò)中的重疊社團(tuán)挖掘，目前已經(jīng)開(kāi)發(fā)了許多用于重疊社區(qū)檢測(cè)的算法，主要包括派系過(guò)濾算法[4]、邊緣圖分割法[5]、局部開(kāi)展法[6]等，派系過(guò)濾算法(clique percolation method，CPM)[7]將社區(qū)視為一組全連通子群(completed subgraph)，因此更適合于更充分的網(wǎng)絡(luò)連通子圖。邊圖劃分[8]利用自然邊緣的重疊特征，通過(guò)生成邊緣圖通過(guò)節(jié)點(diǎn)鏈接到邊緣鏈接的轉(zhuǎn)換，然后劃分它們以獲得社區(qū)結(jié)構(gòu)。而基于局部結(jié)構(gòu)適應(yīng)度的社區(qū)擴(kuò)展方法(local fitness maximization，LFM)[9]考慮局部結(jié)構(gòu)特征，逐步擴(kuò)展生成社區(qū)，多個(gè)擴(kuò)展社區(qū)形成自然重疊。與此同時(shí)，LFM也采用了多分辨率策略來(lái)輔助用戶做出最優(yōu)選擇。除此之外，學(xué)者們還提出了一些混合算法[10]，但是，現(xiàn)有的大多數(shù)方法基于傳統(tǒng)的優(yōu)化[11]或者啟發(fā)式算法[12]，不能同時(shí)滿足速度和精度的要求。因此，本研究提出了一個(gè)基于節(jié)點(diǎn)核心度的重疊社團(tuán)檢測(cè)算法。首先該算法提供了節(jié)點(diǎn)核心度的計(jì)算方法，然后給出了重疊節(jié)點(diǎn)的選取規(guī)則，最后在人工網(wǎng)絡(luò)和實(shí)際網(wǎng)絡(luò)上評(píng)估了該算法的性能并且與現(xiàn)有的經(jīng)典算法做了對(duì)比，結(jié)果表明，本研究的方法在具有更強(qiáng)重疊的網(wǎng)絡(luò)上檢測(cè)效果較優(yōu)。

1 社團(tuán)定義

社團(tuán)結(jié)構(gòu)是網(wǎng)絡(luò)中顯著的結(jié)構(gòu)特征，可以挖掘復(fù)雜網(wǎng)絡(luò)中包含的深層次特性。實(shí)際中整個(gè)網(wǎng)絡(luò)通常被視為由若干個(gè)社團(tuán)構(gòu)成，社團(tuán)內(nèi)部節(jié)點(diǎn)之間連接稠密，社團(tuán)間連接稀疏[13]。例如興趣俱樂(lè)部社團(tuán)，同一個(gè)俱樂(lè)部成員之間的興趣相同聯(lián)系密切而不同俱樂(lè)部間興趣不同則聯(lián)系相對(duì)疏遠(yuǎn)。對(duì)于社團(tuán)的定義沒(méi)有統(tǒng)一的表示，在數(shù)學(xué)角度上對(duì)社團(tuán)結(jié)構(gòu)的簡(jiǎn)單形式化描述為定義1。

定義1 社團(tuán)結(jié)構(gòu)，即網(wǎng)絡(luò)()的一個(gè)劃分，記為={1,2,...C}，其中，C?，U=1=,=||表示網(wǎng)絡(luò)包含社團(tuán)的數(shù)量。

2 節(jié)點(diǎn)核心度計(jì)算

定義2(直接影響因子)[13]對(duì)于給定的無(wú)向圖()，其中={1,2,...,}表示圖中節(jié)點(diǎn)的集合，分別表示節(jié)點(diǎn)的總數(shù)和邊的總數(shù)，={1,2,...}代表圖中所有節(jié)點(diǎn)連邊的集合，節(jié)點(diǎn)v的度用(v)表示，則節(jié)點(diǎn)v、v之間的直接影響因子可定義為：

(vv)表示節(jié)點(diǎn)v對(duì)v的影響力，(vv)的取值為[0,1]，(vv)=1/(v)。

定義3(節(jié)點(diǎn)互信息)[14]在無(wú)向圖(,)，中節(jié)點(diǎn)v與節(jié)點(diǎn)v之間的互信息(vv)定義如下：

節(jié)點(diǎn)v的全局信息為節(jié)點(diǎn)v到圖中所有節(jié)點(diǎn)的互信息之和，公式如下：

節(jié)點(diǎn)的全局信息大小可代表節(jié)點(diǎn)在整個(gè)網(wǎng)絡(luò)圖中的影響力大小，在有了節(jié)點(diǎn)的核心度與節(jié)點(diǎn)的全局信息相關(guān)概念后，由于節(jié)點(diǎn)對(duì)圖中的其他節(jié)點(diǎn)的核心度有一定的影響。因此，本文將核心度影響矩陣表示成鄰接矩陣的形式。經(jīng)過(guò)綜合考慮節(jié)點(diǎn)的直接影響力和節(jié)點(diǎn)的全局信息后，節(jié)點(diǎn)的核心度影響矩陣可用如下公式計(jì)算：

在式(4)中，若節(jié)點(diǎn)v、v之間有邊連接，則ω=1；否則ω=0。W為節(jié)點(diǎn)對(duì)節(jié)點(diǎn)的直接影響力，節(jié)點(diǎn)的核心度影響矩陣代表圖中每個(gè)節(jié)點(diǎn)對(duì)其余節(jié)點(diǎn)核心度的影響程度，因此，節(jié)點(diǎn)v的核心度C可按照下式計(jì)算：

根據(jù)C的表達(dá)式可知，節(jié)點(diǎn)本身的全局信息與其所有鄰接節(jié)點(diǎn)對(duì)節(jié)點(diǎn)的核心度影響的和的平均值構(gòu)成了節(jié)點(diǎn)的核心度。

3 檢測(cè)重疊節(jié)點(diǎn)的方法

對(duì)于重疊社團(tuán)來(lái)說(shuō)，其中的每一個(gè)重疊節(jié)點(diǎn)v周圍都存在與之差別不大的中心節(jié)點(diǎn)可供選擇。所以，可通過(guò)比較節(jié)點(diǎn)v與各個(gè)中心節(jié)點(diǎn)的差異度進(jìn)行選擇重疊節(jié)點(diǎn)，其中差異性函數(shù)的計(jì)算公式為：

在式(6)中，C為社團(tuán)檢測(cè)過(guò)程中斷定給節(jié)點(diǎn)v的中心節(jié)點(diǎn)，C表示為其他社團(tuán)所在的中心節(jié)點(diǎn)，d、d分別表示為節(jié)點(diǎn)C與C的度，(v,C,C)表示對(duì)于節(jié)點(diǎn)v而言，選擇節(jié)點(diǎn)C與節(jié)點(diǎn)C作為中心節(jié)點(diǎn)的差異性。在上面定義的基礎(chǔ)上，本文給出了判斷重疊點(diǎn)的標(biāo)準(zhǔn)：

其中C≠C，參數(shù)為事先設(shè)定的閾值，∈[0, 0.1]，當(dāng)在不同的范圍內(nèi)取值時(shí)可以得到不同數(shù)目的重疊節(jié)點(diǎn)，即可通過(guò)的不同取值對(duì)重疊節(jié)點(diǎn)的數(shù)目進(jìn)行調(diào)整。若式(7)成立，則可得到節(jié)點(diǎn)v是重疊節(jié)點(diǎn)，C或C為其中心節(jié)點(diǎn)。

4 核心度社團(tuán)檢測(cè)算法（NCD）

4.1 算法步驟描述

本文的算法是基于聚類的思想檢測(cè)復(fù)雜網(wǎng)路的重疊社團(tuán)，所以本文在重疊社團(tuán)的檢測(cè)中運(yùn)用了節(jié)點(diǎn)的核心度，節(jié)點(diǎn)的核心度越大，則表明其極有可能成為聚類中心點(diǎn)。首先在算法的每一次迭代過(guò)程中選取核心度大的節(jié)點(diǎn)作為簇初始中心點(diǎn)，然后根據(jù)中心點(diǎn)擴(kuò)展原則[3]判斷初始中心點(diǎn)周圍的節(jié)點(diǎn)是否屬于同一個(gè)社團(tuán)，于是就可得到社團(tuán)的劃分；在完成社團(tuán)的劃分之后還可以利用差異性函數(shù)檢測(cè)具體的重疊節(jié)點(diǎn)。具體的檢測(cè)實(shí)現(xiàn)過(guò)程如下。

(1)根據(jù)公式(5)計(jì)算所有節(jié)點(diǎn)的核心度，然后按照降序排列的方式將節(jié)點(diǎn)的核心度放到隊(duì)列中。

(2)選取具有最大核心度的節(jié)點(diǎn)作為可擴(kuò)展中心點(diǎn)，當(dāng)該節(jié)點(diǎn)沒(méi)有被劃分的時(shí)候，就將該節(jié)點(diǎn)作為初始化社團(tuán)的中心不斷擴(kuò)展社團(tuán)。

(3)當(dāng)以中心節(jié)點(diǎn)v與其鄰接節(jié)點(diǎn)v以及它們的共有鄰接節(jié)點(diǎn)v之間夠成三角模型時(shí)，其鄰接節(jié)點(diǎn)就可以添加到以節(jié)點(diǎn)v為中心的所屬社團(tuán)中，如果v、v、v沒(méi)有構(gòu)成三角模型則，則鄰接節(jié)點(diǎn)v不會(huì)被分配到該社團(tuán)。

(4)不斷重復(fù)以上步驟，當(dāng)隊(duì)列中的節(jié)點(diǎn)核心度小于全部節(jié)點(diǎn)核心度的平均值的1/2時(shí)算法停止。

綜上所述，重疊社團(tuán)檢測(cè)算法偽代碼。

算法：NCD算法

輸入：無(wú)向圖()，優(yōu)先隊(duì)列，節(jié)點(diǎn)數(shù)量，閾值。

輸出：節(jié)點(diǎn)集合的社團(tuán)劃分記為{}=1，其中為算法檢測(cè)到的社團(tuán)數(shù)量；重疊節(jié)點(diǎn)的集合{OPS}=1。

for每個(gè)節(jié)點(diǎn)v

使用公式(5)計(jì)算節(jié)點(diǎn)核心度C，將C按照降序排列放入優(yōu)先隊(duì)列中，

end for

計(jì)算所有節(jié)點(diǎn)核心度的平均值，記為C；

for vin；

ifC<C/2

break；

ifv未被分配到任何一個(gè)社團(tuán)

重新開(kāi)啟一個(gè)新社團(tuán)的初始化，并且標(biāo)注節(jié)點(diǎn)v所在的社團(tuán)數(shù)目

ifv只存在于1個(gè)社團(tuán)內(nèi)

則把v作為初始中心點(diǎn)，依據(jù)中心點(diǎn)可擴(kuò)展原則擴(kuò)展中心節(jié)點(diǎn)v，并標(biāo)注v所在社團(tuán)的數(shù)目；

else將節(jié)點(diǎn)v標(biāo)注為非中心節(jié)點(diǎn)

end for

檢測(cè)未被劃分的節(jié)點(diǎn)

if(v)=0

標(biāo)記v為獨(dú)立社團(tuán)；

if(v)=1

將節(jié)點(diǎn)v劃分到其鄰接節(jié)點(diǎn)v所在社團(tuán)；

得到劃分后的社團(tuán){}=1，并將中心節(jié)點(diǎn)存儲(chǔ)在集合中

for每一個(gè)社團(tuán)V∈{}=1

對(duì)重疊節(jié)點(diǎn)集合初始化，使{OPS}=1=

end for

for每一個(gè)節(jié)點(diǎn)v∈

for每一個(gè)中心節(jié)點(diǎn)v∈

根據(jù)公式(6)計(jì)算=(v,C,v)

if |d-|/≤或|dv-|/≤且v≠C

if|d-|/≤或|dv-|/≤且v≠C

OPS=OPS∪{v}

end for

end for

最終得到重疊點(diǎn)的集合{OPS}=1以及劃分后的社團(tuán){V}=1

4.2 算法時(shí)間復(fù)雜度分析

給定無(wú)向圖(,)，、分別為網(wǎng)絡(luò)的頂點(diǎn)總數(shù)和網(wǎng)絡(luò)包含的節(jié)點(diǎn)邊數(shù)，假設(shè)全部節(jié)點(diǎn)核心度的平均值為。計(jì)算完所有節(jié)點(diǎn)核心度的時(shí)間復(fù)雜度為(3)，對(duì)所有節(jié)點(diǎn)核心度按照降序排列的時(shí)間復(fù)雜度為(log)；在對(duì)節(jié)點(diǎn)進(jìn)行擴(kuò)展過(guò)程中，查詢節(jié)點(diǎn)的鄰接節(jié)點(diǎn)以及擴(kuò)展的時(shí)間復(fù)雜度為(2)；標(biāo)記重疊節(jié)點(diǎn)所在的社團(tuán)數(shù)量的時(shí)間復(fù)雜度為()；劃分未分配的節(jié)點(diǎn)時(shí)，其時(shí)間復(fù)雜度為()。綜上所述，完成整個(gè)算法的時(shí)間復(fù)雜度為(3)。

5 實(shí)證分析

5.1 實(shí)驗(yàn)方法介紹

為驗(yàn)證NCD算法的性能，本文在真實(shí)數(shù)據(jù)集上進(jìn)行社區(qū)檢測(cè)實(shí)驗(yàn)，并與其他算法的社區(qū)檢測(cè)結(jié)果進(jìn)行對(duì)比，采用標(biāo)準(zhǔn)化互信息(NMI)指標(biāo)和模塊度指標(biāo)對(duì)比評(píng)價(jià)。為更直觀地驗(yàn)證NCD的實(shí)現(xiàn)效果，分別選取GN、ACC、NLA算法進(jìn)行對(duì)比。算法各運(yùn)行20次，并取最大值的平均值進(jìn)行對(duì)比，減小算法隨機(jī)性對(duì)結(jié)果的影響。

5.2 實(shí)驗(yàn)數(shù)據(jù)集

本文用到3個(gè)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集來(lái)自于http:// www.personal.umich.edu/～mejn/net data/的Karate、Dolphins和Football網(wǎng)絡(luò)，具體信息如表1。

表1 真實(shí)網(wǎng)絡(luò)的相關(guān)信息

網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)邊數(shù)社團(tuán)數(shù) Karate34782 Dolphins621594 Football11561312

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

(1)標(biāo)準(zhǔn)化互信息(normalized mutual information，NMI)。標(biāo)準(zhǔn)化互信息指標(biāo)[1]是對(duì)已知網(wǎng)絡(luò)結(jié)構(gòu)的社區(qū)檢測(cè)評(píng)價(jià)的經(jīng)典指標(biāo)。該指標(biāo)主要衡量算法所檢測(cè)到的網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)與真實(shí)社團(tuán)結(jié)構(gòu)之間的相似程度。的取值在0～1之間，其值越大表明檢測(cè)到的網(wǎng)絡(luò)結(jié)構(gòu)和真實(shí)結(jié)構(gòu)越接近。

式(8)中，表示實(shí)際社團(tuán)情況，表示算法檢測(cè)的社團(tuán)情況，C和C分別表示和的真實(shí)社團(tuán)數(shù)目，m表示混亂矩陣中的元素，m表示混亂矩陣中第行的總和，m表示混亂矩陣中第列的總和，表示網(wǎng)絡(luò)的節(jié)點(diǎn)個(gè)數(shù)。

(2)社區(qū)模塊度()。對(duì)于真實(shí)的網(wǎng)絡(luò)數(shù)據(jù)集本文采用Newman提出的模塊度進(jìn)行評(píng)價(jià)。模塊度是衡量社團(tuán)檢測(cè)算法劃分結(jié)果優(yōu)劣的一個(gè)指標(biāo)，的取值范圍為[-0.5, 1.0)，在實(shí)際應(yīng)用中的最大值一般為0.3～0.7。其取值越大表明劃分出的結(jié)果越好。檢測(cè)重疊社團(tuán)的模塊度函數(shù)的計(jì)算公式如下所示：

式(9)中，表示網(wǎng)絡(luò)的邊數(shù)，a表示網(wǎng)絡(luò)鄰接矩陣中的元素，當(dāng)和相連時(shí)a=1，否則為0，表示隸屬函數(shù)，當(dāng)節(jié)點(diǎn)和屬于同一個(gè)社團(tuán)時(shí)δ=1，否則為0。

5.4 實(shí)驗(yàn)結(jié)果及分析

為了說(shuō)明本文算法的有效性，對(duì)NCD算法在Karate、Dolphins和Football網(wǎng)絡(luò)3個(gè)切實(shí)有效的數(shù)據(jù)集上的檢測(cè)結(jié)果進(jìn)行了分析。

圖1表示的是本文算法在Karate數(shù)據(jù)集上的社團(tuán)劃分結(jié)果，閾值參數(shù)的值設(shè)置為0.80，NCD算法將該網(wǎng)絡(luò)劃分成2個(gè)社團(tuán)1和2，其中社團(tuán)1的中心節(jié)點(diǎn)為2，2社團(tuán)的中心節(jié)點(diǎn)為33，2個(gè)社團(tuán)重疊的節(jié)點(diǎn)為3和10。

圖1 karate網(wǎng)絡(luò)重疊社團(tuán)檢測(cè)可視化結(jié)果

本文的NCD算法在Dolphin網(wǎng)絡(luò)數(shù)據(jù)集上的社團(tuán)檢測(cè)可視化結(jié)果如圖2所示，其中參數(shù)=0.08，由圖可知該算法將Dolphin網(wǎng)絡(luò)劃分成了紅色和黑色2個(gè)社區(qū)，它們的中心節(jié)點(diǎn)分別為節(jié)點(diǎn)39和節(jié)點(diǎn)18；2個(gè)社團(tuán)的重疊節(jié)點(diǎn)為紫色的{20, 40, 8}。

圖2 Dolphin網(wǎng)絡(luò)重疊社團(tuán)檢測(cè)可視化結(jié)果

圖3為NCD算法在足球俱樂(lè)部網(wǎng)絡(luò)上進(jìn)行社團(tuán)檢測(cè)的可視化結(jié)果，當(dāng)參數(shù)取值為0.08時(shí)，該算法將該網(wǎng)絡(luò)劃分成11個(gè)社團(tuán)，分別用不同的顏色代表，檢測(cè)到的重疊節(jié)點(diǎn)為80與82。

為了進(jìn)一步突出本文所提算法的優(yōu)越性，本文中選用AC、GN、NLA 3種算法與本文的NCD算法做對(duì)比，首先將參數(shù)統(tǒng)一設(shè)置為0.08，然后將3個(gè)對(duì)比算法及本文提出的NCD算法運(yùn)用在3個(gè)切實(shí)有效的數(shù)據(jù)集上執(zhí)行6次，并對(duì)其平均值結(jié)果進(jìn)行對(duì)比。對(duì)比結(jié)果如圖4所示，從圖4中可以看出各算法分別在3個(gè)真實(shí)有效的數(shù)據(jù)集上模塊度的具體取值，模塊度的值越高說(shuō)明社團(tuán)的劃分結(jié)果越準(zhǔn)確；由圖可知，在3個(gè)數(shù)據(jù)集上實(shí)驗(yàn)結(jié)果表明本文算法的模塊度值比其他3種算法的模塊度值都高，即4種方法中NCD算法劃分的社團(tuán)準(zhǔn)確率最高。Zachary網(wǎng)絡(luò)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，4種方法比較中GN算法和ACC算法的模塊度值比較低，特別是GN算法的模塊度值低于0.3，說(shuō)明了GN算法和ACC算法對(duì)Zachary網(wǎng)絡(luò)的劃分結(jié)果的準(zhǔn)確性較低；在海豚網(wǎng)絡(luò)數(shù)據(jù)集實(shí)驗(yàn)中，GN算法的模塊度值為0.422最低，即該算法劃分效果最差，另外2種算法ACC算法和NLA算法的模塊度分別為0.481和0.499，說(shuō)明這2種算法的劃分效果相當(dāng)；在College Football網(wǎng)絡(luò)的檢測(cè)中，本文的NCD算法的模塊度值為0.597最高，說(shuō)明該算法具有良好的社團(tuán)檢測(cè)性能。其次，NLA算法的模塊度值為0.533，比其他2種算法的模塊度值都高，說(shuō)明其劃分效果較其他2種算法良好；整體來(lái)講，GN算法在3個(gè)數(shù)據(jù)集上的模塊度值最低，由此可知GN算法不能檢測(cè)出高質(zhì)量的社團(tuán)結(jié)構(gòu)。

圖4 3個(gè)有效數(shù)據(jù)集上的模塊度值比較

度量社團(tuán)劃分準(zhǔn)確性的指標(biāo)除了模塊度之外還有NMI值，當(dāng)NMI值越大時(shí)說(shuō)明其劃分的社團(tuán)結(jié)果越精確。4個(gè)對(duì)比算法在Zachary、Dolphin和College Football 3個(gè)真實(shí)有效的數(shù)據(jù)集上得到的NMI值比較結(jié)果如圖5所示，Zachary網(wǎng)絡(luò)數(shù)據(jù)集上，NCD算法的NMI值為0.601，比其他3個(gè)算法的值都高，說(shuō)明此算法社團(tuán)檢測(cè)結(jié)果準(zhǔn)確率比其他3種算法都高；NLA算法的NMI取值略高于ACC算法；GN算法的NMI值為0.489最低，說(shuō)明其社團(tuán)劃分結(jié)果最差；在Dolphin數(shù)據(jù)集上，NCD算法的NMI值為0.596，比ACC算法的值略高，而GN算法的NMI值0.502最低檢測(cè)效果最差；在College Football網(wǎng)絡(luò)中，NMI值最高的算法為NCD，該算法的NMI值達(dá)到了0.876，說(shuō)明其測(cè)到的社團(tuán)與真實(shí)的網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)最接近，4個(gè)比較算法中GN算法的值為0.718最低，由此可以推出此算法在網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)劃分上有效性最差。

6 結(jié)論

針對(duì)復(fù)雜網(wǎng)絡(luò)中的重疊社區(qū)檢測(cè)，本文提出了一個(gè)基于節(jié)點(diǎn)核心度的社團(tuán)檢測(cè)算法—NCD算法。首先給出了節(jié)點(diǎn)核心度的定義以及核心度的計(jì)算公式，并將核心度值按照降序順序排列；其次依據(jù)中心點(diǎn)可擴(kuò)展原則判斷節(jié)點(diǎn)之間能否構(gòu)成三角模型對(duì)網(wǎng)絡(luò)進(jìn)行初步的重疊社團(tuán)檢測(cè)；最后在已經(jīng)劃分好的社團(tuán)上識(shí)別網(wǎng)絡(luò)的重疊節(jié)點(diǎn)。為了驗(yàn)證本文所提算法具有良好的復(fù)雜網(wǎng)絡(luò)重疊社區(qū)檢測(cè)能力，在Karate、Dolphins和Football網(wǎng)絡(luò)3個(gè)切實(shí)有效的數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)并且與AC、GN、NLA 3種算法做了對(duì)比分析，試驗(yàn)結(jié)果表明，與選用的3種比較算法相比，NCD算法都具有較高的模塊度值和NMI值，即本文的NCD算法不但能夠檢測(cè)出重疊性強(qiáng)的網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)，還能有效地檢測(cè)出具體的重疊節(jié)點(diǎn)。

[1] STROGATS H. Exploring complex networks[J]. Nature, 2001, 410: 268–276.

[2] FORTUNATO S. Community detection in graphs[J]. Phys, 2010, 486(3): 75-174.

[3] FANG Y, HUANG X, QIN L, et al. A survey of c ommunity search over big graphs[J]. Vldbj, 2020, 29(8): 353–392.

[4] LI H J, WANG L, ZHANG Y. Optimization of identififiability for effificient community detection[J]. Physical(A), 2020, 22(6): 063035.

[5] CAO J, DING D, LIU J. Hybrid triggered based security controller design for networked control system under multiple cyber attacks[J]. Inf Sci, 2021, 548: 69–84.

[6] CAO J, BU Z, WANG Y, et al. Detecting prosumer community groups in smart grids from the multiagent perspective[J]. Systems Man Cybernetics, 2019, 49(8): 1652–1664.

[7] CAO J, WANG Y, HE J, et al. Predicting grain losses and waste rate along the entire chain: a multitask multigated recurrent unit autoencoder based method[J]. Statistical Analysis and Data Mining, 2020, 17(16): 12-16.

[8] PALLAL G. Uncovering the overlapping community structure of complex networks in nature and society[J]. Nature, 2005, 435(7043): 814–818.

[9] AHN Y Y, BAGROW J P, LEHMANN S. Link communities reveal multiscale complexity in networks[J]. Nature, 2010, 466(7307): 761–764.

[10] PSORAKIS I, ROBERTS S, EBDEN M, et al. Overlapping community detection using Bayesian non-negative matrix factorization[J]. Phys Rev E, 2011, 83(5): 66-114.

[11] LIU W, WANG Z, YUAN Y, et al. A Novel Sigmoid- Function[1]Based Adaptive Weighted Particle Swarm Optimizer[J]. Trans Cybern, 2021, 51(2): 1085–1093.

[12] SUN J, XIE Y, ZHANG H, et al. Less is more: Sparse graph mining with compact matrix decomposition[J]. Statistical Analysis and Data Mining, 2008, 1(1): 6-22.

[13] GREGORY S. An Algorithm to Find Overlapping Community Structure in Networks[C]// European Conference on Principles of Data Mining & Knowledge Discovery. Springer, Berlin, Heidelberg, 2007.

[14] 蔣盛益, 楊博泓, 王連喜. 一種基于增量式譜聚類的動(dòng)態(tài)社區(qū)自適應(yīng)發(fā)現(xiàn)算法[J]. 自動(dòng)化學(xué)報(bào), 2015, 41(12): 2017-2025.

Overlapping Community Detection Algorithm Based on Node Core Degree

DAI Ting-ting, LIU Xiu, HAN Yan

（Mathematics and Statistics College, Zhaotong University, Zhaotong 657000, China）

A new detection algorithm-NCD algorithm is proposed for the community with overlapping nodes. The concept of node core degree is proposed, and the initial center point of cluster is selected according to the calculation method of node core degree. The difference function is proposed to identify the overlapping nodes. Under the guidance of the central point extension principle, the overlapping community is detected by judging whether a triangle model can be formed between nodes in the network. NMI and modularity are used as indicators of community detection, and the NCD algorithm is applied to three real network data sets. The results show that the NCD algorithm can efficiently detect overlapping nodes in the community, and it also shows that the algorithm has obvious advantages compared with other algorithms.

complex network; community detection; coreness; overlapping communities

10.15916/j.issn1674-3261.2023.02.011

TP124

A

1674-3261(2023)02-0130-06

2022-10-01

代婷婷(1986-)，女，甘肅慶陽(yáng)人，講師，碩士。

責(zé)任編輯：孫 林