李 明，陳 梅，張 梅

(蘭州交通大學(xué) 電子與信息工程學(xué)院，蘭州 730070)

社團(tuán)檢測可以發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)中結(jié)構(gòu)或功能相似的模塊[1]，對復(fù)雜網(wǎng)絡(luò)進(jìn)行社團(tuán)檢測可以揭示網(wǎng)絡(luò)隱含的結(jié)構(gòu)和潛在的功能，有極為重要的現(xiàn)實(shí)意義[2].研究人員提出了大量的社團(tuán)檢測算法，主要有基于模塊度[3]、基于標(biāo)簽傳播[4]、基于隨機(jī)游走[5]和基于相鄰節(jié)點(diǎn)關(guān)系[6]的社團(tuán)檢測算法.基于模塊度的方法有追求模塊度最大化的Fast Q[3]算法；基于標(biāo)簽傳播的方法有根據(jù)節(jié)點(diǎn)鄰居更新節(jié)點(diǎn)標(biāo)簽的LPA(label propagation algorithm,LPA)[4]算法；基于隨機(jī)游走的約束游走過程的Synwalk[5]算法；基于節(jié)點(diǎn)間關(guān)系的社團(tuán)檢測算法有Black Hole[7]算法、DA(a divide and agglomerate algorithm,DA)[8]算法和棒不打鴛鴦[6]算法.

由于基于節(jié)點(diǎn)間關(guān)系的社團(tuán)檢測算法可以從網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)層面發(fā)現(xiàn)社團(tuán)結(jié)構(gòu)[8]，近年來，研究人員提出了大量該類的社團(tuán)檢測算法.基于節(jié)點(diǎn)間引力與斥力的Black Hole算法通過得到使得整個網(wǎng)絡(luò)合力最小的分布來檢測社團(tuán)結(jié)構(gòu)；基于全局局部關(guān)系的DA算法側(cè)重于同時從全局和局部角度考慮檢測社團(tuán)結(jié)構(gòu)，并在分配無類標(biāo)節(jié)點(diǎn)時利用節(jié)點(diǎn)間的影響力對其進(jìn)行分配[9]；棒不打鴛鴦算法則從“兩個互近鄰節(jié)點(diǎn)極有可能屬于同一個社團(tuán)”出發(fā)生成樹狀圖并剪枝檢測社團(tuán)結(jié)構(gòu).然而，當(dāng)需要檢測任意結(jié)構(gòu)任意規(guī)模的網(wǎng)絡(luò)時，這些算法就難以檢測到準(zhǔn)確的社團(tuán)結(jié)構(gòu)了.

為了檢測任意結(jié)構(gòu)任意規(guī)模的社團(tuán)，本文提出了一種簡單、高效和時間復(fù)雜度低的基于k最近鄰發(fā)現(xiàn)社團(tuán)主干的社團(tuán)檢測算法DCCB.DCCB算法的核心在于：它根據(jù)相似節(jié)點(diǎn)對及其kNN(knearest neighbors,kNN)鄰居生成的社團(tuán)主干進(jìn)行聚類，并利用互kNN連接的關(guān)系對社團(tuán)主干進(jìn)行擴(kuò)展，克服了棒不打鴛鴦算法僅從一個社團(tuán)核心出發(fā)的局限性.此外，DCCB利用kNN擴(kuò)展社團(tuán)主干，這種方法認(rèn)為社團(tuán)內(nèi)所有節(jié)點(diǎn)都以互kNN方式相連，這使得DCCB算法能不受社團(tuán)結(jié)構(gòu)和規(guī)模限制，檢測出正確的社團(tuán)主干；得到社團(tuán)主干后，檢測異常節(jié)點(diǎn)，并將其標(biāo)記為無類標(biāo)節(jié)點(diǎn)；分配無類標(biāo)節(jié)點(diǎn)時，借鑒DA算法的無類標(biāo)節(jié)點(diǎn)分配模式，使用節(jié)點(diǎn)間影響力分配無類標(biāo)節(jié)點(diǎn)即可得到最終的社團(tuán)結(jié)構(gòu).

1 相關(guān)定義

1.1 網(wǎng)絡(luò)的定義

網(wǎng)絡(luò)G可表示為G=(V,E).其中V表示節(jié)點(diǎn)集，E表示邊集.記|V|為n，表示網(wǎng)絡(luò)節(jié)點(diǎn)數(shù).記|E|為m，表示網(wǎng)絡(luò)邊數(shù).若G中?xi,xj∈V，?(xi,xj)?E，?(xj,xi)?E且滿足(xi,xj)=(xj,xi),則該網(wǎng)絡(luò)中的邊沒有方向，那么稱圖G為無向網(wǎng)絡(luò)(undirected network).對于網(wǎng)絡(luò)G，若?(xi,xj)?E，則節(jié)點(diǎn)xi與節(jié)點(diǎn)xj為鄰居節(jié)點(diǎn).通常，對于網(wǎng)絡(luò)中的一個節(jié)點(diǎn)xi，定義它的鄰居集合為N(xi)，將節(jié)點(diǎn)xi鄰居的個數(shù)|N(xi)|稱為節(jié)點(diǎn)的度，記作dxi.

1.2 相鄰節(jié)點(diǎn)之間的相似度

本文采用Jaccard相似度[10]計(jì)算兩個節(jié)點(diǎn)xi與xj的相似度，如公式(1)所示，公式(1)中|coc(xi,xj)|表示節(jié)點(diǎn)xi,xj之間公共鄰居的個數(shù).

(1)

1.3 k最近鄰

x1,x2,…,xi,…,xn是節(jié)點(diǎn)集V中的n個節(jié)點(diǎn).對G中的每個節(jié)點(diǎn)xi∈V，與xi最相似的k個鄰居被稱為xi的k最近鄰,表示為Nk(xi)，Nk(xi)?V.

1.4 互k最近鄰

給定節(jié)點(diǎn)集V中的兩個點(diǎn)xi與xj，當(dāng)且僅當(dāng)xi∈Nk(xj)且xj∈Nk(xi)時，稱xi與xj為互k最近鄰 (mutualknearest neighbors,MkNN).如果xi和xj沒有出現(xiàn)在另一個點(diǎn)的k最近鄰中，xi與xj就不是互k最近鄰，也就是不存在互k最近鄰關(guān)系.

1.5 共享k最近鄰

對于節(jié)點(diǎn)xm，如果節(jié)點(diǎn)xi和xj為MkNN，且滿足xm∈Nk(xi)和xm∈Nk(xj)，xm就是xi與xj的共享k最近鄰(sharedknearest neighbors,SkNN).

1.6 吸引力

在社團(tuán)中，存在一些影響力大的核心節(jié)點(diǎn).2019年Li Z團(tuán)隊(duì)[9]提出了傳播者的概念，將該類節(jié)點(diǎn)稱為傳播者，可通過傳播者對其它節(jié)點(diǎn)的影響對無標(biāo)簽節(jié)點(diǎn)進(jìn)行合理分配.本文定義節(jié)點(diǎn)xi對節(jié)點(diǎn)xj的吸引力為gravity(xi,xj)，如公式(2)所示，其中Jaccard(xi,xj)可由公式(1)計(jì)算.在處理無標(biāo)簽節(jié)點(diǎn)時，可以通過計(jì)算吸引力對該節(jié)點(diǎn)進(jìn)行合理分配.

gravity(xi,xj)=dxi·Jaccard(xi,xj).

(2)

2 基于kNN發(fā)現(xiàn)社團(tuán)主干的社團(tuán)檢測算法

本節(jié)將對DCCB算法進(jìn)行詳細(xì)敘述.首先敘述提出該算法的動機(jī)并給出算法整體流程圖；然后詳細(xì)敘述該算法的核心部分，即基于kNN合并社團(tuán)主干；接著描述無標(biāo)簽節(jié)點(diǎn)的分配；最后對該算法的時間復(fù)雜度進(jìn)行分析.

2.1 動機(jī)

通過認(rèn)真研究網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)，可以發(fā)現(xiàn)網(wǎng)絡(luò)中互為近鄰且相似度很高的一對節(jié)點(diǎn)極有可能在一個社團(tuán)中.這里以圖1中所示的空手道社交網(wǎng)絡(luò)[11]進(jìn)行舉例說明，該網(wǎng)絡(luò)右側(cè)社團(tuán)中的“1”號節(jié)點(diǎn)和“2”號節(jié)點(diǎn)互為近鄰且相似度較高.這對節(jié)點(diǎn)就是核心節(jié)點(diǎn)，該社團(tuán)中的其余節(jié)點(diǎn)都與核心節(jié)點(diǎn)存在互近鄰關(guān)系.這些核心節(jié)點(diǎn)與人際關(guān)系中的領(lǐng)袖類似，即一個團(tuán)體中其余的人或多或少受領(lǐng)袖的影響，這對核心節(jié)點(diǎn)與核心節(jié)點(diǎn)的鄰居組成的小社團(tuán)就是社團(tuán)主干.受此啟發(fā)，提出了基于相似近鄰節(jié)點(diǎn)發(fā)現(xiàn)社團(tuán)主干的算法DCCB；該算法首先利用互k最近鄰找到相似度較高的一對節(jié)點(diǎn)，接著將這對節(jié)點(diǎn)及他們的共享k最近鄰作為社團(tuán)主干，這樣可以最大可能地找到與他們相似的節(jié)點(diǎn)，即這兩個人的共同朋友；最后通過互近鄰擴(kuò)展社團(tuán)主干，利用網(wǎng)絡(luò)中節(jié)點(diǎn)的相似性以及近鄰關(guān)系進(jìn)行社團(tuán)檢測.

圖1 空手道社交網(wǎng)絡(luò)Fig.1 Karate Network

2.2 算法流程圖

本節(jié)將對算法的具體流程進(jìn)行闡述.圖2(a)為DCCB算法的整體流程圖，圖2(b)為基于kNN合并社團(tuán)主干的具體流程.

圖2 算法流程圖Fig.2 Algorithm flow chart

2.3 基于kNN合并社團(tuán)主干

在識別社團(tuán)主干時，DCCB算法只需一個輸入?yún)?shù)k，即最近鄰個數(shù).開始尋找社團(tuán)主干時，該算法首先從一個從未訪問過的節(jié)點(diǎn)xi開始遍歷，若xi存在互k最近鄰xj，則將xi、xj以及它們的共享k最近鄰節(jié)點(diǎn)集合在一起去生成初始的社團(tuán)主干.若xi不存在互k最近鄰，則將xi單獨(dú)當(dāng)作一個社團(tuán)主干，在檢測異常節(jié)點(diǎn)時再處理.這種互kNN的連接方法使得DCCB能夠發(fā)現(xiàn)任意互k最近鄰節(jié)點(diǎn)所組成的社團(tuán).該種方法生成的社團(tuán)主干受社團(tuán)結(jié)構(gòu)規(guī)模影響較小，可以盡可能的將相似的節(jié)點(diǎn)及與它們聯(lián)系緊密的鄰居節(jié)點(diǎn)劃分到同一個社團(tuán)中去.社團(tuán)主干所屬的社團(tuán)一般由一個或多個社團(tuán)主干構(gòu)成，若兩個社團(tuán)主干之間存在重疊的節(jié)點(diǎn)，則說明這兩個社團(tuán)主干屬于同一個社團(tuán)，應(yīng)當(dāng)合并.找到所有社團(tuán)主干后，用吸引力可輕易的將社團(tuán)中其余節(jié)點(diǎn)劃分到與它有鄰居關(guān)系的社團(tuán)主干中去，得到最終的社團(tuán)結(jié)構(gòu).

為了更直觀明了的展示該過程，將對該過程進(jìn)行可視化描述，具體步驟如圖3所示.圖3(a)表示初始網(wǎng)絡(luò)，該網(wǎng)絡(luò)由3個小網(wǎng)絡(luò)構(gòu)成.圖3(b)中，從節(jié)點(diǎn)“0”出發(fā)，找到該節(jié)點(diǎn)的互k最近鄰節(jié)點(diǎn)“1”，然后發(fā)現(xiàn)該節(jié)點(diǎn)對的共享k最近鄰節(jié)點(diǎn)“3”，就找到了該社團(tuán)的主干.圖3(c)中，從節(jié)點(diǎn)“1”出發(fā)，找到該節(jié)點(diǎn)的互k最近鄰節(jié)點(diǎn)“3”，然后發(fā)現(xiàn)該節(jié)點(diǎn)對的共享k最近鄰節(jié)點(diǎn)“2”.此時，由于節(jié)點(diǎn)“1”和節(jié)點(diǎn)“3”在已有社團(tuán)主干中，將節(jié)點(diǎn)“2”加入到該社團(tuán)主干中.圖3(d)中，繼續(xù)通過社團(tuán)主干的合并將節(jié)點(diǎn)“4”納入進(jìn)去，即得到第一個社團(tuán)的社團(tuán)主干.圖3(e)中，由于節(jié)點(diǎn)“5”沒有互k最近鄰節(jié)點(diǎn)，將該節(jié)點(diǎn)擱置.圖3(f)與圖3(g)中，則采用與找第一個社團(tuán)主干同樣的方法找第二個社團(tuán)主干.最終，通過kNN合并社團(tuán)主干，得到了正確的社團(tuán)主干，如圖3(h)所示.

圖3 社團(tuán)主干的生成Fig.3 Generation of the community backbone

2.4 異常點(diǎn)檢測及無標(biāo)簽節(jié)點(diǎn)的分配

DCCB算法識別社團(tuán)主干時，會將不存在互k最近鄰的單個節(jié)點(diǎn)，包含2個節(jié)點(diǎn)及1個共同鄰居的3個節(jié)點(diǎn)作為社團(tuán)主干加入到已有社團(tuán)主干中.生成社團(tuán)主干時若該類節(jié)點(diǎn)無法吸引外部節(jié)點(diǎn)，則說明該類節(jié)點(diǎn)不是社團(tuán)主干，需要重新劃分.DCCB算法檢測異常節(jié)點(diǎn)時，將包含節(jié)點(diǎn)數(shù)小于3的社團(tuán)主干中的節(jié)點(diǎn)分配到無類標(biāo)節(jié)點(diǎn)中重新劃分.

DCCB算法在進(jìn)行無類標(biāo)節(jié)點(diǎn)的分配時，借鑒了LPA算法以及LGM&GM[9]模式.該模式認(rèn)為節(jié)點(diǎn)的影響力與節(jié)點(diǎn)度的大小成正比，度越大影響力越大，綜合考量節(jié)點(diǎn)的度以及兩個節(jié)點(diǎn)間的相似性，提出了節(jié)點(diǎn)間的吸引力.在分配時，首先利用公式(2)找到對無類標(biāo)節(jié)點(diǎn)吸引力最大的鄰居節(jié)點(diǎn)，然后將該無類標(biāo)節(jié)點(diǎn)劃分到鄰居節(jié)點(diǎn)所在社團(tuán)主干，得到最終的社團(tuán)結(jié)構(gòu).

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

DCCB算法計(jì)算k近鄰時，用“k-d tree”實(shí)現(xiàn)，時間復(fù)雜度為O(n·logn)，其中n為節(jié)點(diǎn)集V中節(jié)點(diǎn)的個數(shù).計(jì)算k近鄰與形成社團(tuán)主干時間復(fù)雜度為O(n·k)，其中n為圖中節(jié)點(diǎn)的個數(shù)，k為每個點(diǎn)最近鄰個數(shù)，由于k?n，這2個步驟時間復(fù)雜度可近似的認(rèn)為是O(n).

檢測異常節(jié)點(diǎn)時查找包含節(jié)點(diǎn)小于等于3的社團(tuán)主干時間復(fù)雜度為O(n).劃分無類標(biāo)節(jié)點(diǎn)的時間復(fù)雜度為O(z·davg)，z表示無類標(biāo)節(jié)點(diǎn)數(shù)，davg表示節(jié)點(diǎn)的平均度.由于davg?z，分配無類標(biāo)節(jié)點(diǎn)的時間復(fù)雜度為O(z).整個算法時間復(fù)雜度為O(n·logn+n+n+z)，由于O(z)和O(n)時間復(fù)雜度相當(dāng)，且n?n·logn，所以DCCB的時間復(fù)雜度為O(n·logn).

3 實(shí)驗(yàn)結(jié)果與分析

為了檢驗(yàn)DCCB算法能否檢測出不同結(jié)構(gòu)不同規(guī)模的社團(tuán)，本節(jié)實(shí)驗(yàn)選取了4個便于可視化展示的不同結(jié)構(gòu)的真實(shí)網(wǎng)絡(luò)以及3個不同規(guī)模的人工合成網(wǎng)絡(luò)[12]，并與常見的5個社團(tuán)檢測算法進(jìn)行了對比，驗(yàn)證了DCCB算法的有效性及正確性.

3.1 數(shù)據(jù)集及對比算法

本節(jié)的實(shí)驗(yàn)使用了表1所示的4個真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集和3個人工合成網(wǎng)絡(luò)數(shù)據(jù)集.4個真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集是空手道俱樂部網(wǎng)絡(luò)(Karate)、游戲地圖網(wǎng)絡(luò)(Risk map)、海豚社交網(wǎng)絡(luò)(Dolphins)和大學(xué)生足球聯(lián)賽賽程表網(wǎng)絡(luò)(Football)[11].這些網(wǎng)絡(luò)都是公開發(fā)布的真實(shí)數(shù)據(jù)集，網(wǎng)絡(luò)規(guī)模較小，結(jié)構(gòu)各異，便于可視化處理，能直觀的展示實(shí)驗(yàn)結(jié)果.此外，這些網(wǎng)絡(luò)的真實(shí)結(jié)構(gòu)都已知，便于進(jìn)行指標(biāo)量化處理，評估不同算法的檢測結(jié)果.3個不同規(guī)模的人工合成網(wǎng)絡(luò)數(shù)據(jù)集由LFR(a lancichinetti,s fortunato,f network,LFR)測試網(wǎng)絡(luò)生成工具程序生成[12]，分別包含2 000，5 000和20 000個節(jié)點(diǎn).這些網(wǎng)絡(luò)的統(tǒng)計(jì)信息如表1所列.

表1 實(shí)驗(yàn)所用數(shù)據(jù)集Tab.1 Networks used in the experiment

LFR人工合成網(wǎng)絡(luò)需指定參數(shù).為了測試DCCB算法在不同規(guī)模社團(tuán)上的效果，生成了L_2k與L_5k數(shù)據(jù)集；為了測試DCCB算法在大規(guī)模網(wǎng)絡(luò)上的表現(xiàn)，生成了L_20k數(shù)據(jù)集；這些數(shù)據(jù)集參數(shù)設(shè)置如表2所列.在這些參數(shù)中，混合系數(shù)μ很關(guān)鍵，若μ>0.5，則生成的社團(tuán)結(jié)構(gòu)趨于模糊，檢測困難；若μ<0.5，則生成的社團(tuán)結(jié)構(gòu)很清晰，易于檢測.由于實(shí)驗(yàn)需要驗(yàn)證DCCB算法在不同規(guī)模網(wǎng)絡(luò)上的效果，這3個網(wǎng)絡(luò)混合系數(shù)μ設(shè)置為0.4即可.

本文選取5個典型的社團(tuán)檢測算法作為對比算法，包括模塊度最優(yōu)算法(Fast Q，F(xiàn)Q)[3]、典型的標(biāo)簽傳播算法LPA[4]算法、經(jīng)典的譜聚類算法(Spectral Clustering,SC)[13]、新型的基于節(jié)點(diǎn)間作用的算法(Attractor,Att)[14]以及基于吸引力模式的算法(Black Hole,BH)[7].為了更直觀的看出算法在數(shù)據(jù)集上的表現(xiàn)，本文采用了2個常用的評價(jià)指標(biāo)，即歸一化互信息量(normalized mutual information,NMI)和調(diào)整蘭德指數(shù)(adjusted Rand index,ARI)來對不同算法做統(tǒng)一衡量.對于不穩(wěn)定的算法，評價(jià)指標(biāo)取運(yùn)行30次該算法結(jié)果的平均值，結(jié)果圖為檢測到的社團(tuán)結(jié)構(gòu)評價(jià)指標(biāo)最高的一次.

3.2 真實(shí)網(wǎng)絡(luò)的結(jié)果分析

3.2.1 Karate網(wǎng)絡(luò)的結(jié)果分析

圖4展示了DCCB與5種對比算法在Karate數(shù)據(jù)集上的社團(tuán)檢測結(jié)果.從圖4中可以看出，F(xiàn)ast Q算法，Spectral Clustering算法以及Black Hole算法檢測效果不佳，未能得到清晰良好的社團(tuán)劃分.DCCB算法、Attractor算法表現(xiàn)良好，能得到質(zhì)量較高的社團(tuán)結(jié)構(gòu).DCCB算法除了將節(jié)點(diǎn)32劃分錯誤外，其余節(jié)點(diǎn)都被正確地劃分到了相應(yīng)的社團(tuán).圖4(c)是LPA在Karate上最好的檢測結(jié)果，該次結(jié)果錯誤地劃分了節(jié)點(diǎn)3，但從表3可以看到該算法多次得到的結(jié)果評價(jià)指標(biāo)平均值較DCCB算法差.Fast Q算法和Black Hole算法表現(xiàn)較差，SC算法錯誤地劃分了節(jié)點(diǎn)3、節(jié)點(diǎn)20和節(jié)點(diǎn)14.Attractor算法除了將節(jié)點(diǎn)10劃分錯誤外，其余的節(jié)點(diǎn)都劃分正確.Black Hole算法將網(wǎng)絡(luò)劃分為4個社團(tuán).

圖4 Karate網(wǎng)絡(luò)上的檢測結(jié)果Fig.4 Detection results on Karate network

3.2.2 Risk map網(wǎng)絡(luò)的結(jié)果分析

圖5展示了DCCB與5種對比算法在Risk map數(shù)據(jù)集上的聚類結(jié)果.可以從圖5(b)明顯看到：DCCB算法除了將節(jié)點(diǎn)26劃分錯誤外，其余節(jié)點(diǎn)都被正確地劃分到了相應(yīng)的社團(tuán)，且成功檢測了右上角較難檢測的2個社團(tuán).從表3也可以看到，DCCB得到了最高的ARI和NMI值，較其它5個對比算法劃分的社團(tuán)結(jié)構(gòu)更準(zhǔn)確.從圖5可看出，算法LPA、Fast Q和Spectral Clustering分配的結(jié)果都不太理想，未能成功地檢測出良好的社團(tuán)結(jié)構(gòu).網(wǎng)絡(luò)右側(cè)的兩個社團(tuán)比較難檢測，基于互近鄰的DCCB在該網(wǎng)絡(luò)表現(xiàn)良好，可以檢測出該社團(tuán).

圖5 Risk map網(wǎng)絡(luò)上的檢測結(jié)果Fig.5 Detection results on Risk map network

3.2.3 Dolphins網(wǎng)絡(luò)的結(jié)果分析

圖6展示了DCCB與5種對比算法在Dolphins數(shù)據(jù)集上的聚類結(jié)果.圖6(a)是Dolphins的真實(shí)社團(tuán)結(jié)構(gòu)，圖6(b)為DCCB算法的社團(tuán)檢測結(jié)果.該網(wǎng)絡(luò)結(jié)構(gòu)比較復(fù)雜，難以檢測.從圖6與表3可以看出，大部分算法在該網(wǎng)絡(luò)上表現(xiàn)不太好，但DCCB仍然能檢測出高質(zhì)量的社團(tuán)結(jié)構(gòu)，且比其它5個對比算法檢測出的結(jié)果更優(yōu).通過圖6(c)可以看出，LPA算法、Fast Q算法、Spectral Clustering、Attractor以及Black Hole算法在Dolphins數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果并不理想，得到的社團(tuán)結(jié)構(gòu)與真實(shí)的社團(tuán)結(jié)構(gòu)有很大偏差.從表3可以看到，DCCB得到了最高的ARI和NMI值，較其它5個對比算法劃分的社團(tuán)結(jié)構(gòu)更準(zhǔn)確.從圖6(b)可以看到，DCCB算法除了將社團(tuán)邊緣的3個節(jié)點(diǎn)8、40及60分配錯誤外，其余節(jié)點(diǎn)均分配正確.

圖6 Dolphins網(wǎng)絡(luò)上的檢測結(jié)果Fig.6 Detection results on Dolphins network

3.2.4 Football網(wǎng)絡(luò)的結(jié)果分析

圖7展示了DCCB與5種對比算法在Football數(shù)據(jù)集上的聚類結(jié)果.圖7(a)是Football的真實(shí)社團(tuán)結(jié)構(gòu)，圖7(b)為DCCB算法的社團(tuán)檢測結(jié)果.DCCB除了將中間的一個包含4個節(jié)點(diǎn)的小社團(tuán)錯誤劃分到左上角社團(tuán)外，其余部分的社團(tuán)結(jié)構(gòu)完全正確.Attractor算法劃分時也錯誤地將左上角社團(tuán)的一個節(jié)點(diǎn)劃分給該小社團(tuán).從表3可以看出，Attractor算法、DCCB算法以及Black Hole算法在該網(wǎng)絡(luò)表現(xiàn)良好，其余幾個算法在該網(wǎng)絡(luò)表現(xiàn)較差.

圖7 Football網(wǎng)絡(luò)上的檢測結(jié)果Fig.7 Detection results on Football network

表3 多個有真實(shí)標(biāo)簽網(wǎng)絡(luò)數(shù)據(jù)集檢測結(jié)果比較Tab.3 A comparison of detection results on the various network datasets with ground truth

3.3 LFR網(wǎng)絡(luò)的結(jié)果分析

L_2k數(shù)據(jù)集有2 000個節(jié)點(diǎn)，包含103個社團(tuán).從表3可以看出，在該網(wǎng)絡(luò)上，DCCB方法得到的ARI及NMI均為最大，識別出了完全正確的社團(tuán)結(jié)構(gòu).Attractor算法的結(jié)果與其相同，Black Hole算法、LPA算法的結(jié)果與其比較相近但稍差于DCCB算法，F(xiàn)ast Q算法及Spectral Clustering算法的ARI和NMI均低于DCCB算法.其中，Attractor算法在運(yùn)行L_5k和L_20k時出現(xiàn)內(nèi)存錯誤，未能得到結(jié)果.L_5k數(shù)據(jù)集有5 000個節(jié)點(diǎn)，包含219個社團(tuán)，從表3可以看出，在該網(wǎng)絡(luò)上，DCCB檢測到的社團(tuán)結(jié)構(gòu)的ARI是最高的，其它的社團(tuán)檢測算法除了LPA和Black Hole外社團(tuán)檢測結(jié)果并不理想.Black Hole算法在不同數(shù)據(jù)集上均有良好的表現(xiàn)，在L_5k數(shù)據(jù)集的結(jié)果比DCCB更好.L_20k參數(shù)設(shè)置與L_5k保持一致，該網(wǎng)絡(luò)有20 000個節(jié)點(diǎn)，包含219個社團(tuán)，從表3可以看出，DCCB在該網(wǎng)絡(luò)上的ARI和NMI均為最高，較其它算法表現(xiàn)好.LFR網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果表明DCCB能很好的檢測出不同規(guī)模的社團(tuán).

3.4 算法的時間復(fù)雜度比較

優(yōu)秀的算法應(yīng)有較低的時間復(fù)雜度[15-17].Spectral Clustering時間復(fù)雜度O(n3)；Fast Q的時間復(fù)雜度為O(n2)；LPA的時間復(fù)雜度為O(n)，但該算法結(jié)果不穩(wěn)定且準(zhǔn)確度很差.Attractor算法時間復(fù)雜度為O(m+am+Tm)，其中：a為兩節(jié)點(diǎn)間外部鄰居的平均數(shù)；T為迭代次數(shù).Black Hole算法的時間復(fù)雜度為O(n·logn).DCCB的時間復(fù)雜度為O(n·logn).總體來說，DCCB時間復(fù)雜度較低，且能得到較準(zhǔn)確的社團(tuán)結(jié)構(gòu).

3.5 總體分析

為量化分析DCCB算法以及其它5個算法的效果，選取了兩個社團(tuán)檢測中最常見的評價(jià)指標(biāo)ARI、NMI對社團(tuán)檢測結(jié)果量化分析，結(jié)果如表3所示.除了在Football數(shù)據(jù)集上較Attractor算法稍差，在L_5k數(shù)據(jù)集上較Black Hole算法稍差，在其余5個數(shù)據(jù)集上，DCCB檢測到的社團(tuán)質(zhì)量較其它算法都好.對不同算法在不同數(shù)據(jù)集上的量化評價(jià)指標(biāo)ARI、NMI取均值，如圖8所示，很明顯DCCB算法取得的ARI、NMI均值是最高的，優(yōu)于其它算法.此外，本節(jié)還采用盒圖作為可視化統(tǒng)計(jì)方法，對算法的表現(xiàn)進(jìn)行評估，如圖9所示.在7個數(shù)據(jù)集上，對于ARI、NMI這兩個評價(jià)指標(biāo)，DCCB算法在四分位數(shù)、中位數(shù)、最大值及最小值均有著優(yōu)秀的表現(xiàn).L_2k以及L_5k人工合成網(wǎng)絡(luò)的實(shí)驗(yàn)表明，DCCB可以準(zhǔn)確識別出不同規(guī)模的社團(tuán).L_20k數(shù)據(jù)集上的實(shí)驗(yàn)表明，DCCB在規(guī)模較大數(shù)據(jù)集上發(fā)揮穩(wěn)定，可以檢測到高質(zhì)量的社團(tuán)劃分.綜上所述，DCCB是一個簡單、時間復(fù)雜度較低、結(jié)果穩(wěn)定且能在不同結(jié)構(gòu)不同規(guī)模網(wǎng)絡(luò)中檢測到高質(zhì)量社團(tuán)結(jié)構(gòu)的社團(tuán)檢測算法.

圖8 DCCB及對比算法在不同數(shù)據(jù)集上ARI，NMI均值比較Fig.8 A comparison of average ARI,NMI on the various network datasets with DCCB and contrast algorithms

圖9 具有真實(shí)社團(tuán)結(jié)構(gòu)網(wǎng)絡(luò)上的ARI，NMI盒圖Fig.9 Box plots of ARI,NMI on the networks with ground-truth community structures

4 結(jié)論

本文提出了一種基于kNN發(fā)現(xiàn)社團(tuán)主干的社團(tuán)檢測算法，在4個不同結(jié)構(gòu)真實(shí)網(wǎng)絡(luò)和3個不同規(guī)模的人工合成網(wǎng)絡(luò)進(jìn)行實(shí)驗(yàn)，并與5個常見的社團(tuán)檢測算法對比，得到以下結(jié)論：

1) 基于kNN發(fā)現(xiàn)社團(tuán)主干的社團(tuán)檢測方法可有效解決現(xiàn)有的社團(tuán)檢測算法不能很好的檢測出任意結(jié)構(gòu)任意規(guī)模社團(tuán)的問題，且該算法時間復(fù)雜度較低，提高了社團(tuán)檢測效率.

2) 本文提出了通過互kNN連接發(fā)現(xiàn)社團(tuán)主干的方法，該方法具有良好的應(yīng)用價(jià)值和適用性，對于社團(tuán)檢測及聚類的相關(guān)研究，都有良好的借鑒價(jià)值.

3) 在實(shí)驗(yàn)過程中，發(fā)現(xiàn)該算法合并社團(tuán)主干時容易混淆社團(tuán)邊界處的節(jié)點(diǎn).可通過引入目標(biāo)函數(shù)的方法對社團(tuán)主干的合并過程進(jìn)行約束，來得到準(zhǔn)確度更高的社團(tuán)結(jié)構(gòu).