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

代婷婷，劉 秀，韓 艷

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

代婷婷，劉 秀，韓 艷

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

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

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

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

1 社團(tuán)定義

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

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

2 節(jié)點核心度計算

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

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

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

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

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

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

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

3 檢測重疊節(jié)點的方法

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

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

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

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

4.1 算法步驟描述

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

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

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

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

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

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

算法：NCD算法

輸入：無向圖()，優(yōu)先隊列，節(jié)點數(shù)量，閾值。

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

for每個節(jié)點v

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

end for

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

for vin；

ifC<C/2

break；

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

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

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

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

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

end for

檢測未被劃分的節(jié)點

if(v)=0

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

if(v)=1

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

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

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

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

end for

for每一個節(jié)點v∈

for每一個中心節(jié)點v∈

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

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

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

OPS=OPS∪{v}

end for

end for

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

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

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

5 實證分析

5.1 實驗方法介紹

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

5.2 實驗數(shù)據(jù)集

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

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

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

5.3 評價指標(biāo)

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

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

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

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

5.4 實驗結(jié)果及分析

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

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

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

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

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

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

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

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

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

6 結(jié)論

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

[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] 蔣盛益, 楊博泓, 王連喜. 一種基于增量式譜聚類的動態(tài)社區(qū)自適應(yīng)發(fā)現(xiàn)算法[J]. 自動化學(xué)報, 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-)，女，甘肅慶陽人，講師，碩士。

責(zé)任編輯：孫 林