趙 亮，朱征宇

重慶大學(xué) 計(jì)算機(jī)學(xué)院，重慶400044

1 引言

現(xiàn)實(shí)世界很多復(fù)雜的相互作用的關(guān)系往往被抽象成復(fù)雜網(wǎng)絡(luò)來表示，例如互聯(lián)網(wǎng)環(huán)境下的社交網(wǎng)絡(luò)、電子商務(wù)、流行病傳播學(xué)中的預(yù)防控制過程、生物學(xué)網(wǎng)絡(luò)中蛋白質(zhì)組織結(jié)構(gòu)等。而社區(qū)作為復(fù)雜網(wǎng)絡(luò)中廣泛存在的結(jié)構(gòu)，通過研究社區(qū)可以很好地了解和認(rèn)識(shí)復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)和功能。社區(qū)并沒有一個(gè)嚴(yán)格意義上的定義，較為廣泛接受的是Newman和Gievan提出的“同一社區(qū)內(nèi)的點(diǎn)與點(diǎn)之間的連接更緊密，不同社區(qū)之間點(diǎn)的連接更稀疏[1]”。

在現(xiàn)實(shí)世界的復(fù)雜網(wǎng)絡(luò)中，存在一些節(jié)點(diǎn)同時(shí)屬于不同的社區(qū)，這便是所謂的重疊社區(qū)結(jié)構(gòu)[2]。CPM算法[3]是早期能夠發(fā)現(xiàn)重疊社區(qū)的發(fā)現(xiàn)算法，算法通過找出極大完全子圖來發(fā)現(xiàn)重疊社區(qū)；COPRA算法[4]采用標(biāo)簽傳播的方式來發(fā)現(xiàn)重疊社區(qū)，初始化時(shí)，每個(gè)節(jié)點(diǎn)被賦予一個(gè)唯一標(biāo)簽，通過無數(shù)次迭代更新節(jié)點(diǎn)標(biāo)簽及其隸屬度，最終具有相同標(biāo)簽的節(jié)點(diǎn)同屬一個(gè)社區(qū)，其中具有多個(gè)標(biāo)簽的節(jié)點(diǎn)為重疊節(jié)點(diǎn)；CRD-LPA算法[5]通過節(jié)點(diǎn)重要性在標(biāo)簽傳播階段選擇標(biāo)簽，提高了算法的穩(wěn)定性。LBSA算法[6]和OCDEDC算法[7]通過網(wǎng)絡(luò)中邊的特性來發(fā)現(xiàn)重疊社區(qū)。Lancichinetti等人[8]提出基于局部擴(kuò)展的重疊社區(qū)發(fā)現(xiàn)算法（LFM），該算法通過隨機(jī)選擇種子節(jié)點(diǎn)，不斷加入適應(yīng)度增益最大的節(jié)點(diǎn)來組成局部社區(qū)，盡管LFM算法能夠發(fā)現(xiàn)重疊社區(qū)和社區(qū)間的層次關(guān)系，但存在結(jié)果不穩(wěn)定、社區(qū)漂移等問題；文獻(xiàn)[9]采用最大團(tuán)策略進(jìn)行社區(qū)的擴(kuò)展合并，獲得重疊社區(qū)。

本文針對(duì)現(xiàn)有的局部擴(kuò)展類算法的結(jié)果不穩(wěn)定、社區(qū)漂移等問題，提出基于K-核迭代因子和社區(qū)隸屬度的重疊社區(qū)發(fā)現(xiàn)算法（KIMDOC），其基本思想是：首先引用迭代的思想對(duì)K-核分解算法[10]進(jìn)行改進(jìn)，得到K-核迭代因子[11]，然后將K-核迭代因子與節(jié)點(diǎn)密度值相結(jié)合得到節(jié)點(diǎn)影響力，利用節(jié)點(diǎn)影響力找出種子節(jié)點(diǎn)；再通過節(jié)點(diǎn)影響力計(jì)算得到節(jié)點(diǎn)的社區(qū)隸屬度，最后根據(jù)社區(qū)隸屬度從種子節(jié)點(diǎn)局部擴(kuò)展至整個(gè)網(wǎng)絡(luò)，從而發(fā)現(xiàn)網(wǎng)絡(luò)中的重疊社區(qū)。

2 相關(guān)工作

2.1 LFM算法

LFM算法是局部擴(kuò)展類重疊社區(qū)發(fā)現(xiàn)算法的經(jīng)典算法，大多數(shù)局部擴(kuò)展類算法都是以此算法為基礎(chǔ)進(jìn)行改進(jìn)的，該算法通過引入適應(yīng)度函數(shù)來衡量社區(qū)C的緊密程度，計(jì)算社區(qū)C鄰接點(diǎn)的適應(yīng)度并將適應(yīng)度最大的鄰接點(diǎn)加入到社區(qū)C中，重新計(jì)算社區(qū)C中各個(gè)點(diǎn)的適應(yīng)度并去除適應(yīng)度小于零的節(jié)點(diǎn)，當(dāng)社區(qū)C不再變化時(shí)擴(kuò)展終止。適應(yīng)度計(jì)算方式如式（1）所示：

（1）隨機(jī)選擇一個(gè)未加入社區(qū)的節(jié)點(diǎn)作為種子節(jié)點(diǎn)，初始認(rèn)為該種子節(jié)點(diǎn)為社區(qū)C。

（2）計(jì)算社區(qū)C所有鄰接點(diǎn)的適應(yīng)度，將適應(yīng)度最大的節(jié)點(diǎn)加入到社區(qū)C中，形成新社區(qū)C′。

（3）計(jì)算新社區(qū)C′中所有節(jié)點(diǎn)的適應(yīng)度，如果存在適應(yīng)度小于0的節(jié)點(diǎn)，從社區(qū)C′中刪除該節(jié)點(diǎn)，并重復(fù)該步驟直到不存在適應(yīng)度小于0的節(jié)點(diǎn)。

（4）從（2）開始重新計(jì)算，直到社區(qū)的鄰接點(diǎn)的適應(yīng)度都小于0，則結(jié)束此次擴(kuò)展，獲得一個(gè)社區(qū)。

LFM算法具有較低的時(shí)間復(fù)雜度。但是隨機(jī)選擇種子節(jié)點(diǎn)造成算法結(jié)果的不穩(wěn)定；同時(shí)在計(jì)算適應(yīng)度時(shí)僅考慮了節(jié)點(diǎn)的局部特征，沒有考慮節(jié)點(diǎn)的全局影響力，造成社區(qū)劃分結(jié)果準(zhǔn)確性較低。

2.2 K-核分解算法

Stephen等人提出的K-核分解算法被廣泛應(yīng)用于網(wǎng)絡(luò)中核心節(jié)點(diǎn)的識(shí)別。K-核分解算法通過遞歸的方式將節(jié)點(diǎn)從較低的等級(jí)修剪到較高的等級(jí)。

算法過程如下：

（1）移除所有度數(shù)為1的節(jié)點(diǎn)，如果產(chǎn)生度數(shù)為1或者小于1的節(jié)點(diǎn)就繼續(xù)移除，直到不存在度數(shù)小于等于1的節(jié)點(diǎn)為止，這些所有被移除的節(jié)點(diǎn)被標(biāo)記為ki=1。

（2）移除所有度數(shù)為2的節(jié)點(diǎn)，在此過程中會(huì)產(chǎn)生新的度數(shù)為2或者度數(shù)小于2的節(jié)點(diǎn)，這些節(jié)點(diǎn)也被移除，在這一步被移除的所有節(jié)點(diǎn)被標(biāo)記為ki=2。

（3）依次類推，直到移除所有節(jié)點(diǎn)為止。

通過K-核分解算法可以為每個(gè)節(jié)點(diǎn)標(biāo)記ki，ki代表節(jié)點(diǎn)的核心程度，其中ki越大表示節(jié)點(diǎn)的核心程度越高。

K-核分解算法能夠有效地得到節(jié)點(diǎn)核心程度，因此ki越大的節(jié)點(diǎn)越可能是種子節(jié)點(diǎn)。但由于在復(fù)雜網(wǎng)絡(luò)中存在許多相同核心程度的節(jié)點(diǎn)，無法判斷這些節(jié)點(diǎn)核心程度的差異，因此直接引用k-核分解算法會(huì)造成種子節(jié)點(diǎn)選擇的不確定性，從而導(dǎo)致社區(qū)劃分結(jié)果不夠穩(wěn)定。

3 基于K-核迭代因子的重疊社區(qū)發(fā)現(xiàn)算法

通過分析局部擴(kuò)展類算法和K-核分解算法所存在的問題，本文引入K-核迭代因子和歸一化的節(jié)點(diǎn)密度函數(shù)，設(shè)計(jì)了一種新的節(jié)點(diǎn)影響力函數(shù)，并在此基礎(chǔ)上設(shè)計(jì)了一種社區(qū)隸屬度函數(shù)，提出了基于K-核迭代因子和社區(qū)隸屬度的重疊社區(qū)發(fā)現(xiàn)算法KIMDOC。該算法的具體步驟為：

（1）計(jì)算所有節(jié)點(diǎn)的K-核迭代因子和節(jié)點(diǎn)密度，對(duì)節(jié)點(diǎn)密度進(jìn)行歸一化處理，將K-核迭代因子與節(jié)點(diǎn)密度相結(jié)合，計(jì)算得到節(jié)點(diǎn)影響力。

（2）選擇節(jié)點(diǎn)影響力最大且未被劃入社區(qū)的節(jié)點(diǎn)作為種子節(jié)點(diǎn)，形成初始社區(qū)C。

（3）從社區(qū)C出發(fā)，計(jì)算鄰接節(jié)點(diǎn)對(duì)于社區(qū)C的社區(qū)隸屬度，把社區(qū)隸屬度大于閾值的節(jié)點(diǎn)劃到社區(qū)C中，重復(fù)此步，直到該社區(qū)C不再擴(kuò)展為止。

（4）重復(fù)（2）、（3）兩步，直到所有節(jié)點(diǎn)都被劃到社區(qū)為止，最后處理孤立節(jié)點(diǎn)，并把相似度高的社區(qū)合并，得到最終劃分結(jié)果。

其中節(jié)點(diǎn)影響力計(jì)算和節(jié)點(diǎn)隸屬度計(jì)算為KIMDOC算法的核心，下面將對(duì)其進(jìn)行詳細(xì)闡述與分析。

3.1 K-核迭代因子

為避免直接引用K-核分解算法選擇種子節(jié)點(diǎn)的不確定性，本文引入了K-核迭代因子的概念，用以區(qū)別節(jié)點(diǎn)核心程度的差異，K-核迭代因子的計(jì)算公式如式（2）所示：

其中δi表示節(jié)點(diǎn)i的K-核迭代因子，ki表示通過K-核分解算法得到節(jié)點(diǎn)i的核心程度，mki表示在計(jì)算ki時(shí)總共經(jīng)過幾次迭代，ni表示在mki次迭代中節(jié)點(diǎn)是第幾次迭代時(shí)被移除。

算法1列出了K-核迭代因子的計(jì)算偽代碼，其中行2的k用來表示K-核的核心程度，行5的m用來記錄每輪K-核分解時(shí)最多迭代幾次，行10的ni用來記錄節(jié)點(diǎn)i是第幾次迭代被移除，行17、18用來計(jì)算節(jié)點(diǎn)i的K-核迭代因子并將其并到集合S中。

算法1 KIMDOC的K-核迭代因子算法（Kernel Iterative Algorithm，KIA）

輸入：復(fù)雜網(wǎng)絡(luò)G=(V,E)；

輸出：所有節(jié)點(diǎn)的迭代因子S={ δi|i∈V ； }

1.S←?；

2.k←1；

3.do

4.T←?；

5.m←0；

6. do

7. For each i∈V do

8. if(di＜=K)then

9. remove(V,i)；

10.ni←m+1；

11.T←T∪{i}；

12. end if

13. end for

14.m←m+1；

15. while（T＞0）

16.for each i∈T do

17.δi=k·1 +〔

18.S←S∪{δi}；

19. end for

20.while（V＞0）

21.return S；

如圖1所示，K-核迭代因子計(jì)算過程為：當(dāng)k取值為1時(shí)，第一次迭代移除的節(jié)點(diǎn)為1、2、3、5、9、11，第二次迭代移除的節(jié)點(diǎn)為4，第三次迭代移除的節(jié)點(diǎn)為6，之后沒有度數(shù)小于等于1的節(jié)點(diǎn)，此次移除結(jié)束，其中節(jié)點(diǎn)1、2、3、5、9、11的K-核迭代因子為1×（1+1/3），節(jié)點(diǎn)4的K-核迭代因子為1×（1+2/3）；依次類推計(jì)算出如表1所示所有節(jié)點(diǎn)的K-核迭代因子。

圖1 K-核迭代因子示意圖

表1 K-核迭代因子算法的過程

3.2 種子節(jié)點(diǎn)選擇

雖然K-核迭代因子可以進(jìn)一步區(qū)分節(jié)點(diǎn)核心程度的差異，但還會(huì)產(chǎn)生少數(shù)無法區(qū)分的節(jié)點(diǎn)，例如圖1中節(jié)點(diǎn)7、8、10，都是在k取值為2時(shí)的第一次迭代就被移除了，因此直接通過k-核迭代因子選擇種子節(jié)點(diǎn)也會(huì)造成不確定性。文獻(xiàn)[12]的研究結(jié)果已經(jīng)表明，一個(gè)節(jié)點(diǎn)的度數(shù)越大越具有更大的影響力。同時(shí)PageRank算法[13]指出節(jié)點(diǎn)的影響力由節(jié)點(diǎn)的鄰接節(jié)點(diǎn)的數(shù)量和鄰接節(jié)點(diǎn)的影響力決定。所以，一個(gè)節(jié)點(diǎn)的影響力由節(jié)點(diǎn)和節(jié)點(diǎn)周圍所有節(jié)點(diǎn)決定，本文引入了節(jié)點(diǎn)密度的概念。公式如式（3）所示：

其中，Ni表示節(jié)點(diǎn)i的鄰接節(jié)點(diǎn)集，dj表示節(jié)點(diǎn)j的度數(shù)。

K-核迭代因子作用在點(diǎn)的度數(shù)上面，通過公式（2）可以發(fā)現(xiàn)，迭代因子不大于節(jié)點(diǎn)度數(shù)的兩倍，而公式（3）所計(jì)算的節(jié)點(diǎn)密度是度數(shù)的累加，會(huì)產(chǎn)生一個(gè)很大的值，不利于兩者的結(jié)合計(jì)算，因此對(duì)節(jié)點(diǎn)密度進(jìn)行歸一化處理。首先求出每個(gè)節(jié)點(diǎn)的密度，找出網(wǎng)絡(luò)所有節(jié)點(diǎn)的最大密度，將每個(gè)節(jié)點(diǎn)的密度除以最大密度，得到歸一化處理的結(jié)果，如公式（4）所示：

將K-核迭代因子與節(jié)點(diǎn)密度歸一化值相結(jié)合，將其作為本文的節(jié)點(diǎn)影響力。其計(jì)算公式如式（5）所示：

通過節(jié)點(diǎn)影響力就可以找出種子節(jié)點(diǎn)，提高了算法在種子節(jié)點(diǎn)選取的穩(wěn)定性和準(zhǔn)確性。

3.3 社區(qū)局部擴(kuò)展

局部擴(kuò)展類社區(qū)發(fā)現(xiàn)算法判斷一個(gè)節(jié)點(diǎn)是否加入社區(qū)，是通過計(jì)算隸屬度函數(shù)來確定的，所以隸屬度函數(shù)的正確性對(duì)社區(qū)劃分的結(jié)果有很大的影響。本文在節(jié)點(diǎn)影響力的基礎(chǔ)上設(shè)計(jì)了一種社區(qū)隸屬度函數(shù)。

在復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)越重要，對(duì)其他節(jié)點(diǎn)的影響力越大?；谶@種思想，先定義節(jié)點(diǎn)i的鄰接節(jié)點(diǎn)集的影響力為：

其中N(i)為節(jié)點(diǎn)i的鄰接節(jié)點(diǎn)集，NI(j)為節(jié)點(diǎn)j的節(jié)點(diǎn)影響力。

因此節(jié)點(diǎn)i鄰接節(jié)點(diǎn)集在社區(qū)C的影響力可定義為：

其中NC(i)為節(jié)點(diǎn)i鄰接節(jié)點(diǎn)中屬于社區(qū)C的節(jié)點(diǎn)集合。

社區(qū)是聯(lián)系緊密的節(jié)點(diǎn)構(gòu)成的團(tuán)或簇。一個(gè)節(jié)點(diǎn)在社區(qū)中的影響力越高，與這個(gè)社區(qū)聯(lián)系越緊密，節(jié)點(diǎn)越可能屬于這個(gè)社區(qū)。文獻(xiàn)[14]通過節(jié)點(diǎn)影響力的強(qiáng)弱來判斷鄰接節(jié)點(diǎn)是否加入社區(qū)，僅考慮了節(jié)點(diǎn)影響力而沒有考慮節(jié)點(diǎn)加入社區(qū)后影響力的變化。因此對(duì)節(jié)點(diǎn)影響力計(jì)算公式進(jìn)行變形，定義節(jié)點(diǎn)在社區(qū)C中的影響力。首先根據(jù)公式（8）計(jì)算社區(qū)的K-核迭代因子，把社區(qū)C作為一個(gè)獨(dú)立網(wǎng)絡(luò)圖進(jìn)行計(jì)算。

同理，可以得到如下公式：

算法2列出了采用社區(qū)隸屬度函數(shù)的局部擴(kuò)展算法的偽代碼，其中行2是得到社區(qū)C的所有鄰接節(jié)點(diǎn)，行4通過算法1得到節(jié)點(diǎn)的社區(qū)影響力δCi，S為社區(qū)C中所有節(jié)點(diǎn)社區(qū)影響力集合，行6～8是當(dāng)節(jié)點(diǎn)的隸屬度大于閾值α?xí)r，把節(jié)點(diǎn)i劃到社區(qū)C中。局部擴(kuò)展就是循環(huán)運(yùn)行算法2，直到社區(qū)C不再變化為止。

算法2 KIMDOC的局部擴(kuò)展算法（Local Extension Algorithm，LEA）

輸入：復(fù)雜網(wǎng)絡(luò)G=(V,E)，初始社區(qū)C。輸出：最終社區(qū)C。

1.N←?；

2.N←getAdjacentNodes（C）；

3.C′←C∪N；

4.S←KIA(C′)；

5.For each i∈N do

6. if(fn(i,C)＞α)then

7.C←C∪{}i；

8. end if

9.end for

10.return C；

3.4 相似社區(qū)合并

劃分出來的社區(qū)并不是最終社區(qū)，可能存在一個(gè)節(jié)點(diǎn)自己?jiǎn)为?dú)成為一個(gè)社區(qū)，雖然與許多社區(qū)相連，但是該節(jié)點(diǎn)對(duì)每個(gè)社區(qū)的隸屬度都小于閾值α，這種節(jié)點(diǎn)被稱為孤立節(jié)點(diǎn)，對(duì)孤立節(jié)點(diǎn)的處理方式是：重新計(jì)算節(jié)點(diǎn)與周圍社區(qū)的社區(qū)隸屬度，把該節(jié)點(diǎn)劃入社區(qū)隸屬度最高的社區(qū)。

社區(qū)中可能存在相似度很高的社區(qū)，對(duì)相似度高的社區(qū)可以定義為：存在一個(gè)社區(qū)中2/3以上的節(jié)點(diǎn)同時(shí)屬于另一個(gè)社區(qū)，則認(rèn)為這兩個(gè)社區(qū)相似度高。把相似度高的兩個(gè)社區(qū)合并成一個(gè)社區(qū)，通過這步處理得到最終的劃分結(jié)果。

3.5 時(shí)間復(fù)雜度分析

假設(shè)復(fù)雜網(wǎng)絡(luò)G包含n個(gè)節(jié)點(diǎn)和m條邊，Wang等人提出計(jì)算K-核迭代因子的時(shí)間復(fù)雜度為O(n)，計(jì)算節(jié)點(diǎn)密度要考慮節(jié)點(diǎn)的度和鄰接節(jié)點(diǎn)的度，時(shí)間復(fù)雜度為O( n×d )，其中d為節(jié)點(diǎn)的度，所以尋找種子節(jié)點(diǎn)的時(shí)間復(fù)雜度為O( n+n×d)；從算法2社區(qū)局部擴(kuò)展的時(shí)間復(fù)雜為O( n×(nC×dmCax))，其中nC為社區(qū)C的節(jié)點(diǎn)數(shù)量，dCmax為社區(qū)C中最大節(jié)點(diǎn)度，(nC×dCmax)用來計(jì)算節(jié)點(diǎn)的社區(qū)影響力，局部擴(kuò)展就是重復(fù)算法2，因此如果最終結(jié)果獲得c個(gè)社區(qū)，則局部擴(kuò)展的時(shí)間復(fù)雜度為O( c ×n×(nC×dmCax))；對(duì)孤立節(jié)點(diǎn)和相似度高社區(qū)合并的時(shí)間復(fù)雜度遠(yuǎn)遠(yuǎn)小于K-核迭代因子和局部擴(kuò)展的計(jì)算，因此KIMDOC算法的時(shí)間復(fù)雜度為O(n+n×d+c×n×(nC×dCmax))=O(c×n×(nC×dCmax))，理想情況下社區(qū)數(shù)c、社區(qū)總節(jié)點(diǎn)數(shù)nC和最大節(jié)點(diǎn)度dCmax遠(yuǎn)遠(yuǎn)小于n，因此時(shí)間復(fù)雜度接近O(n)，在最壞情況下社區(qū)數(shù)為n并且最大節(jié)點(diǎn)度也為n，則找到最終社區(qū)的時(shí)間復(fù)雜度為O(n3)。

4 實(shí)驗(yàn)

為了驗(yàn)證基于K-核迭代因子和社區(qū)隸屬度的重疊社區(qū)發(fā)現(xiàn)算法（KIMDOC）的有效性，本文算法分別與其他幾種具有代表性的發(fā)現(xiàn)算法進(jìn)行比較，待比較的算法分別是COPRA[4]、LFM[8]、QLFM[15]、OMKLP[16]、OCDEDC[7]。實(shí)驗(yàn)環(huán)境為：內(nèi)存4 GB，處理器Inter?Core?2 2.00 GHz，操作系統(tǒng)為64位Win7，開發(fā)環(huán)境為Intellij IDEA2017，開發(fā)語(yǔ)言為Java。

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

本文選取10個(gè)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集和LFR基準(zhǔn)網(wǎng)絡(luò)[17]進(jìn)行實(shí)驗(yàn)。真實(shí)網(wǎng)絡(luò)相關(guān)信息如表2所示。

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

LFR基準(zhǔn)網(wǎng)絡(luò)是一種人工合成網(wǎng)絡(luò)，具有真實(shí)網(wǎng)絡(luò)的許多特性，通過調(diào)整參數(shù)，可以生產(chǎn)不同類型的網(wǎng)絡(luò)，被廣泛應(yīng)用于復(fù)雜網(wǎng)絡(luò)的研究中。如表3所示，N表示節(jié)點(diǎn)數(shù)；d表示網(wǎng)絡(luò)節(jié)點(diǎn)平均度數(shù)；max d表示網(wǎng)絡(luò)節(jié)點(diǎn)最大度數(shù)；min c和max c表示社區(qū)的規(guī)模；on表示重疊節(jié)點(diǎn)的個(gè)數(shù)；om表示重疊節(jié)點(diǎn)所屬社區(qū)數(shù)目；mu表示社區(qū)間邊與社區(qū)內(nèi)邊的比值，比值越大表示社區(qū)結(jié)構(gòu)越模糊。

表3 LFR基準(zhǔn)網(wǎng)絡(luò)

4.2 實(shí)驗(yàn)評(píng)估方法

對(duì)于真實(shí)網(wǎng)絡(luò)，本文采用擴(kuò)展模塊度函數(shù)EQ[28]來評(píng)價(jià)，用來判斷重疊社區(qū)劃分的準(zhǔn)確性，如公式（13）所示：

其中，m表示網(wǎng)絡(luò)中邊的數(shù)量，Qu表示節(jié)點(diǎn)u所屬社區(qū)的個(gè)數(shù)，Auv表示u和v之間是否有邊，若有邊Auv為1，否則為0，ku表示節(jié)點(diǎn)u的度。EQ越大表示重疊社區(qū)結(jié)構(gòu)越好。

對(duì)于人工基準(zhǔn)網(wǎng)絡(luò)，在網(wǎng)絡(luò)形成時(shí)就知道社區(qū)劃分的結(jié)果，社區(qū)發(fā)現(xiàn)算法的結(jié)果可以和真實(shí)的劃分結(jié)果對(duì)比，本文采用標(biāo)準(zhǔn)互信息量（NMI）[29]來作為評(píng)價(jià)指標(biāo)，NMI越大表示社區(qū)發(fā)現(xiàn)結(jié)果越準(zhǔn)確，如公式（14）所示：

其中，X和Y表示真實(shí)社區(qū)結(jié)構(gòu)和算法產(chǎn)生的社區(qū)結(jié)構(gòu)。

4.3 實(shí)驗(yàn)結(jié)構(gòu)與分析

由于COPRA、LFM、QLFM算法都是不穩(wěn)定算法，所以取10次運(yùn)行中最好的結(jié)果。KIMDOC算法運(yùn)行多次實(shí)驗(yàn)結(jié)果是相同的，因此相比LFM算法提升了局部擴(kuò)展類社區(qū)發(fā)現(xiàn)算法的穩(wěn)定性。對(duì)于COPRA算法選擇v=2；QLFM算法使用原作者論文中的數(shù)據(jù)0.9；對(duì)于OMKLP算法，因?yàn)闊o法得到原始代碼，因此直接引用原文中真實(shí)數(shù)據(jù)實(shí)驗(yàn)結(jié)果，而對(duì)人工基準(zhǔn)網(wǎng)絡(luò)不進(jìn)行比較；對(duì)于OCDEDC算法，使用文章中給出的參數(shù)ε=0.3，u=4；對(duì)于本文算法KIMDOC的閾值α=0.6。

對(duì)于真實(shí)網(wǎng)路數(shù)據(jù)集，實(shí)驗(yàn)結(jié)果如表4所示。從表4可以看出，除了在Polblogs和PGP兩個(gè)數(shù)據(jù)集EQ結(jié)果較差外，本文算法KIMDOC在真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上劃分的社區(qū)結(jié)構(gòu)擴(kuò)展模塊度比其他算法有所提高，特別是在Football和Internet數(shù)據(jù)集上提升顯著。表明本文提出的算法能夠有效地提高重疊社區(qū)發(fā)現(xiàn)算法的擴(kuò)展模塊度，得到質(zhì)量更高的社區(qū)。

對(duì)于人工基準(zhǔn)網(wǎng)絡(luò)的實(shí)驗(yàn)結(jié)果如圖2和圖3所示。由于OMKLP算法沒有原實(shí)驗(yàn)代碼，在人工基準(zhǔn)網(wǎng)絡(luò)不進(jìn)行比較。

表4 算法在真實(shí)數(shù)據(jù)集上的EQ比較

圖2 算法在LFR-1000上的NMI比較

圖3 算法在LFR-5000上的NMI比較

圖4 閾值α變化對(duì)EQ的影響

從圖2和圖3中可以看出，KIMDOC算法在兩種人工基準(zhǔn)網(wǎng)絡(luò)中，NMI值比其他算法有所提高，且mu在0.25～0.45時(shí)有更明顯的提高，結(jié)果表明本文所提出的方法能有效提高社區(qū)劃分結(jié)果的準(zhǔn)確性。

4.4 算法參數(shù)取值

KIMDOC中閾值α的選取會(huì)影響最終的實(shí)驗(yàn)結(jié)果，因此對(duì)閾值α的變化進(jìn)行分析和實(shí)驗(yàn)。

閾值α的取值范圍就是公式（12）社區(qū)隸屬度函數(shù)的范圍。通過對(duì)公式（6）和公式（7）的定義分析可知：節(jié)點(diǎn)i的鄰接節(jié)點(diǎn)中屬于社區(qū)C的節(jié)點(diǎn)影響力之和NNIC(i)小于等于節(jié)點(diǎn)所有鄰接節(jié)點(diǎn)的節(jié)點(diǎn)影響力之和；通過分析K-核迭代因子和節(jié)點(diǎn)密度可知，節(jié)點(diǎn)在社區(qū)中的影響力NIC()i小于等于節(jié)點(diǎn)在整個(gè)網(wǎng)絡(luò)的影響力NI()i。因此，可以得出社區(qū)隸屬度函數(shù)的范圍是0～1，即閾值α的范圍是0～1。

為了探究閾值α對(duì)重疊社區(qū)劃分結(jié)果的影響，本文選擇五種不同規(guī)模的真實(shí)網(wǎng)絡(luò)進(jìn)行實(shí)驗(yàn)，觀察不同閾值α的選取對(duì)擴(kuò)展模塊度的影響。實(shí)驗(yàn)結(jié)果如圖4所示，橫坐標(biāo)表示閾值α的選取，最小單位為0.05，縱坐標(biāo)是擴(kuò)展模塊度EQ，隨著α的增大，算法在各個(gè)網(wǎng)絡(luò)上的模塊度呈現(xiàn)先上升后下降的趨勢(shì)。當(dāng)α取0.5～0.65時(shí)，算法在絕大多數(shù)網(wǎng)絡(luò)上都具有較高的擴(kuò)展模塊度值。因此，在本文實(shí)驗(yàn)中KIMDOC算法閾值參數(shù)α的取值為0.6。

5 結(jié)束語(yǔ)

在現(xiàn)實(shí)社會(huì)網(wǎng)絡(luò)中，復(fù)雜網(wǎng)絡(luò)是普遍存在的，因此，面向復(fù)雜網(wǎng)絡(luò)的重疊社區(qū)發(fā)現(xiàn)算法具有重要的研究意義和使用價(jià)值。本文提出的基于K-核迭代因子的重疊社區(qū)發(fā)現(xiàn)算法（KIMDOC），通過引入K-核迭代因子的概念，結(jié)合節(jié)點(diǎn)密度，量化節(jié)點(diǎn)影響力，在計(jì)算節(jié)點(diǎn)社區(qū)隸屬度時(shí)保留了節(jié)點(diǎn)網(wǎng)絡(luò)影響力和社區(qū)影響力兩個(gè)重要特性，既繼承了傳統(tǒng)局部擴(kuò)展類社區(qū)發(fā)現(xiàn)算法的速度優(yōu)勢(shì)，又能提高算法的穩(wěn)定性和準(zhǔn)確性。通過在人工基準(zhǔn)網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行測(cè)試，可以看出本文算法運(yùn)行結(jié)果理想，對(duì)社區(qū)劃分結(jié)果有一定提升。