基于節點核心度的重疊社團檢測算法

代婷婷，劉 秀，韓 艷

基于節點核心度的重疊社團檢測算法

代婷婷，劉 秀，韓 艷

（昭通學院 數學與統計學院，云南 昭通 657000）

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

復雜網絡；社區檢測；核心度；重疊社團

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

1 社團定義

社團結構是網絡中顯著的結構特征，可以挖掘復雜網絡中包含的深層次特性。實際中整個網絡通常被視為由若干個社團構成，社團內部節點之間連接稠密，社團間連接稀疏[13]。例如興趣俱樂部社團，同一個俱樂部成員之間的興趣相同聯系密切而不同俱樂部間興趣不同則聯系相對疏遠。對于社團的定義沒有統一的表示，在數學角度上對社團結構的簡單形式化描述為定義1。

定義1 社團結構，即網絡()的一個劃分，記為={1,2,...C}，其中，C?，U=1=,=||表示網絡包含社團的數量。

2 節點核心度計算

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

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

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

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

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

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

根據C的表達式可知，節點本身的全局信息與其所有鄰接節點對節點的核心度影響的和的平均值構成了節點的核心度。

3 檢測重疊節點的方法

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

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

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

4 核心度社團檢測算法（NCD）

4.1 算法步驟描述

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

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

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

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

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

綜上所述，重疊社團檢測算法偽代碼。

算法：NCD算法

輸入：無向圖()，優先隊列，節點數量，閾值。

輸出：節點集合的社團劃分記為{}=1，其中為算法檢測到的社團數量；重疊節點的集合{OPS}=1。

for每個節點v

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

end for

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

for vin；

ifC<C/2

break；

ifv未被分配到任何一個社團

重新開啟一個新社團的初始化，并且標注節點v所在的社團數目

ifv只存在于1個社團內

則把v作為初始中心點，依據中心點可擴展原則擴展中心節點v，并標注v所在社團的數目；

else將節點v標注為非中心節點

end for

檢測未被劃分的節點

if(v)=0

標記v為獨立社團；

if(v)=1

將節點v劃分到其鄰接節點v所在社團；

得到劃分后的社團{}=1，并將中心節點存儲在集合中

for每一個社團V∈{}=1

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

end for

for每一個節點v∈

for每一個中心節點v∈

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

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

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

OPS=OPS∪{v}

end for

end for

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

4.2 算法時間復雜度分析

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

5 實證分析

5.1 實驗方法介紹

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

5.2 實驗數據集

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

表1 真實網絡的相關信息

網絡節點數邊數社團數 Karate34782 Dolphins621594 Football11561312

5.3 評價指標

(1)標準化互信息(normalized mutual information，NMI)。標準化互信息指標[1]是對已知網絡結構的社區檢測評價的經典指標。該指標主要衡量算法所檢測到的網絡社團結構與真實社團結構之間的相似程度。的取值在0～1之間，其值越大表明檢測到的網絡結構和真實結構越接近。

式(8)中，表示實際社團情況，表示算法檢測的社團情況，C和C分別表示和的真實社團數目，m表示混亂矩陣中的元素，m表示混亂矩陣中第行的總和，m表示混亂矩陣中第列的總和，表示網絡的節點個數。

(2)社區模塊度()。對于真實的網絡數據集本文采用Newman提出的模塊度進行評價。模塊度是衡量社團檢測算法劃分結果優劣的一個指標，的取值范圍為[-0.5, 1.0)，在實際應用中的最大值一般為0.3～0.7。其取值越大表明劃分出的結果越好。檢測重疊社團的模塊度函數的計算公式如下所示：

式(9)中，表示網絡的邊數，a表示網絡鄰接矩陣中的元素，當和相連時a=1，否則為0，表示隸屬函數，當節點和屬于同一個社團時δ=1，否則為0。

5.4 實驗結果及分析

為了說明本文算法的有效性，對NCD算法在Karate、Dolphins和Football網絡3個切實有效的數據集上的檢測結果進行了分析。

圖1表示的是本文算法在Karate數據集上的社團劃分結果，閾值參數的值設置為0.80，NCD算法將該網絡劃分成2個社團1和2，其中社團1的中心節點為2，2社團的中心節點為33，2個社團重疊的節點為3和10。

圖1 karate網絡重疊社團檢測可視化結果

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

圖2 Dolphin網絡重疊社團檢測可視化結果

圖3為NCD算法在足球俱樂部網絡上進行社團檢測的可視化結果，當參數取值為0.08時，該算法將該網絡劃分成11個社團，分別用不同的顏色代表，檢測到的重疊節點為80與82。

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

圖4 3個有效數據集上的模塊度值比較

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

6 結論

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

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

責任編輯：孫 林