融入K-核迭代因子的重疊社區發現算法

趙 亮，朱征宇

重慶大學 計算機學院，重慶400044

1 引言

現實世界很多復雜的相互作用的關系往往被抽象成復雜網絡來表示，例如互聯網環境下的社交網絡、電子商務、流行病傳播學中的預防控制過程、生物學網絡中蛋白質組織結構等。而社區作為復雜網絡中廣泛存在的結構，通過研究社區可以很好地了解和認識復雜網絡的結構和功能。社區并沒有一個嚴格意義上的定義，較為廣泛接受的是Newman和Gievan提出的“同一社區內的點與點之間的連接更緊密，不同社區之間點的連接更稀疏[1]”。

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

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

2 相關工作

2.1 LFM算法

LFM算法是局部擴展類重疊社區發現算法的經典算法，大多數局部擴展類算法都是以此算法為基礎進行改進的，該算法通過引入適應度函數來衡量社區C的緊密程度，計算社區C鄰接點的適應度并將適應度最大的鄰接點加入到社區C中，重新計算社區C中各個點的適應度并去除適應度小于零的節點，當社區C不再變化時擴展終止。適應度計算方式如式（1）所示：

（1）隨機選擇一個未加入社區的節點作為種子節點，初始認為該種子節點為社區C。

（2）計算社區C所有鄰接點的適應度，將適應度最大的節點加入到社區C中，形成新社區C′。

（3）計算新社區C′中所有節點的適應度，如果存在適應度小于0的節點，從社區C′中刪除該節點，并重復該步驟直到不存在適應度小于0的節點。

（4）從（2）開始重新計算，直到社區的鄰接點的適應度都小于0，則結束此次擴展，獲得一個社區。

LFM算法具有較低的時間復雜度。但是隨機選擇種子節點造成算法結果的不穩定；同時在計算適應度時僅考慮了節點的局部特征，沒有考慮節點的全局影響力，造成社區劃分結果準確性較低。

2.2 K-核分解算法

Stephen等人提出的K-核分解算法被廣泛應用于網絡中核心節點的識別。K-核分解算法通過遞歸的方式將節點從較低的等級修剪到較高的等級。

算法過程如下：

（1）移除所有度數為1的節點，如果產生度數為1或者小于1的節點就繼續移除，直到不存在度數小于等于1的節點為止，這些所有被移除的節點被標記為ki=1。

（2）移除所有度數為2的節點，在此過程中會產生新的度數為2或者度數小于2的節點，這些節點也被移除，在這一步被移除的所有節點被標記為ki=2。

（3）依次類推，直到移除所有節點為止。

通過K-核分解算法可以為每個節點標記ki，ki代表節點的核心程度，其中ki越大表示節點的核心程度越高。

K-核分解算法能夠有效地得到節點核心程度，因此ki越大的節點越可能是種子節點。但由于在復雜網絡中存在許多相同核心程度的節點，無法判斷這些節點核心程度的差異，因此直接引用k-核分解算法會造成種子節點選擇的不確定性，從而導致社區劃分結果不夠穩定。

3 基于K-核迭代因子的重疊社區發現算法

通過分析局部擴展類算法和K-核分解算法所存在的問題，本文引入K-核迭代因子和歸一化的節點密度函數，設計了一種新的節點影響力函數，并在此基礎上設計了一種社區隸屬度函數，提出了基于K-核迭代因子和社區隸屬度的重疊社區發現算法KIMDOC。該算法的具體步驟為：

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

（2）選擇節點影響力最大且未被劃入社區的節點作為種子節點，形成初始社區C。

（3）從社區C出發，計算鄰接節點對于社區C的社區隸屬度，把社區隸屬度大于閾值的節點劃到社區C中，重復此步，直到該社區C不再擴展為止。

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

其中節點影響力計算和節點隸屬度計算為KIMDOC算法的核心，下面將對其進行詳細闡述與分析。

3.1 K-核迭代因子

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

其中δi表示節點i的K-核迭代因子，ki表示通過K-核分解算法得到節點i的核心程度，mki表示在計算ki時總共經過幾次迭代，ni表示在mki次迭代中節點是第幾次迭代時被移除。

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

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

輸入：復雜網絡G=(V,E)；

輸出：所有節點的迭代因子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-核迭代因子計算過程為：當k取值為1時，第一次迭代移除的節點為1、2、3、5、9、11，第二次迭代移除的節點為4，第三次迭代移除的節點為6，之后沒有度數小于等于1的節點，此次移除結束，其中節點1、2、3、5、9、11的K-核迭代因子為1×（1+1/3），節點4的K-核迭代因子為1×（1+2/3）；依次類推計算出如表1所示所有節點的K-核迭代因子。

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

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

3.2 種子節點選擇

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

其中，Ni表示節點i的鄰接節點集，dj表示節點j的度數。

K-核迭代因子作用在點的度數上面，通過公式（2）可以發現，迭代因子不大于節點度數的兩倍，而公式（3）所計算的節點密度是度數的累加，會產生一個很大的值，不利于兩者的結合計算，因此對節點密度進行歸一化處理。首先求出每個節點的密度，找出網絡所有節點的最大密度，將每個節點的密度除以最大密度，得到歸一化處理的結果，如公式（4）所示：

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

通過節點影響力就可以找出種子節點，提高了算法在種子節點選取的穩定性和準確性。

3.3 社區局部擴展

局部擴展類社區發現算法判斷一個節點是否加入社區，是通過計算隸屬度函數來確定的，所以隸屬度函數的正確性對社區劃分的結果有很大的影響。本文在節點影響力的基礎上設計了一種社區隸屬度函數。

在復雜網絡中節點越重要，對其他節點的影響力越大。基于這種思想，先定義節點i的鄰接節點集的影響力為：

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

因此節點i鄰接節點集在社區C的影響力可定義為：

其中NC(i)為節點i鄰接節點中屬于社區C的節點集合。

社區是聯系緊密的節點構成的團或簇。一個節點在社區中的影響力越高，與這個社區聯系越緊密，節點越可能屬于這個社區。文獻[14]通過節點影響力的強弱來判斷鄰接節點是否加入社區，僅考慮了節點影響力而沒有考慮節點加入社區后影響力的變化。因此對節點影響力計算公式進行變形，定義節點在社區C中的影響力。首先根據公式（8）計算社區的K-核迭代因子，把社區C作為一個獨立網絡圖進行計算。

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

算法2列出了采用社區隸屬度函數的局部擴展算法的偽代碼，其中行2是得到社區C的所有鄰接節點，行4通過算法1得到節點的社區影響力δCi，S為社區C中所有節點社區影響力集合，行6～8是當節點的隸屬度大于閾值α時，把節點i劃到社區C中。局部擴展就是循環運行算法2，直到社區C不再變化為止。

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

輸入：復雜網絡G=(V,E)，初始社區C。輸出：最終社區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 相似社區合并

劃分出來的社區并不是最終社區，可能存在一個節點自己單獨成為一個社區，雖然與許多社區相連，但是該節點對每個社區的隸屬度都小于閾值α，這種節點被稱為孤立節點，對孤立節點的處理方式是：重新計算節點與周圍社區的社區隸屬度，把該節點劃入社區隸屬度最高的社區。

社區中可能存在相似度很高的社區，對相似度高的社區可以定義為：存在一個社區中2/3以上的節點同時屬于另一個社區，則認為這兩個社區相似度高。把相似度高的兩個社區合并成一個社區，通過這步處理得到最終的劃分結果。

3.5 時間復雜度分析

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

4 實驗

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

4.1 實驗數據

本文選取10個真實網絡數據集和LFR基準網絡[17]進行實驗。真實網絡相關信息如表2所示。

表2 真實網絡數據集信息

LFR基準網絡是一種人工合成網絡，具有真實網絡的許多特性，通過調整參數，可以生產不同類型的網絡，被廣泛應用于復雜網絡的研究中。如表3所示，N表示節點數；d表示網絡節點平均度數；max d表示網絡節點最大度數；min c和max c表示社區的規模；on表示重疊節點的個數；om表示重疊節點所屬社區數目；mu表示社區間邊與社區內邊的比值，比值越大表示社區結構越模糊。

表3 LFR基準網絡

4.2 實驗評估方法

對于真實網絡，本文采用擴展模塊度函數EQ[28]來評價，用來判斷重疊社區劃分的準確性，如公式（13）所示：

其中，m表示網絡中邊的數量，Qu表示節點u所屬社區的個數，Auv表示u和v之間是否有邊，若有邊Auv為1，否則為0，ku表示節點u的度。EQ越大表示重疊社區結構越好。

對于人工基準網絡，在網絡形成時就知道社區劃分的結果，社區發現算法的結果可以和真實的劃分結果對比，本文采用標準互信息量（NMI）[29]來作為評價指標，NMI越大表示社區發現結果越準確，如公式（14）所示：

其中，X和Y表示真實社區結構和算法產生的社區結構。

4.3 實驗結構與分析

由于COPRA、LFM、QLFM算法都是不穩定算法，所以取10次運行中最好的結果。KIMDOC算法運行多次實驗結果是相同的，因此相比LFM算法提升了局部擴展類社區發現算法的穩定性。對于COPRA算法選擇v=2；QLFM算法使用原作者論文中的數據0.9；對于OMKLP算法，因為無法得到原始代碼，因此直接引用原文中真實數據實驗結果，而對人工基準網絡不進行比較；對于OCDEDC算法，使用文章中給出的參數ε=0.3，u=4；對于本文算法KIMDOC的閾值α=0.6。

對于真實網路數據集，實驗結果如表4所示。從表4可以看出，除了在Polblogs和PGP兩個數據集EQ結果較差外，本文算法KIMDOC在真實網絡數據集上劃分的社區結構擴展模塊度比其他算法有所提高，特別是在Football和Internet數據集上提升顯著。表明本文提出的算法能夠有效地提高重疊社區發現算法的擴展模塊度，得到質量更高的社區。

對于人工基準網絡的實驗結果如圖2和圖3所示。由于OMKLP算法沒有原實驗代碼，在人工基準網絡不進行比較。

表4 算法在真實數據集上的EQ比較

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

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

圖4 閾值α變化對EQ的影響

從圖2和圖3中可以看出，KIMDOC算法在兩種人工基準網絡中，NMI值比其他算法有所提高，且mu在0.25～0.45時有更明顯的提高，結果表明本文所提出的方法能有效提高社區劃分結果的準確性。

4.4 算法參數取值

KIMDOC中閾值α的選取會影響最終的實驗結果，因此對閾值α的變化進行分析和實驗。

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

為了探究閾值α對重疊社區劃分結果的影響，本文選擇五種不同規模的真實網絡進行實驗，觀察不同閾值α的選取對擴展模塊度的影響。實驗結果如圖4所示，橫坐標表示閾值α的選取，最小單位為0.05，縱坐標是擴展模塊度EQ，隨著α的增大，算法在各個網絡上的模塊度呈現先上升后下降的趨勢。當α取0.5～0.65時，算法在絕大多數網絡上都具有較高的擴展模塊度值。因此，在本文實驗中KIMDOC算法閾值參數α的取值為0.6。

5 結束語

在現實社會網絡中，復雜網絡是普遍存在的，因此，面向復雜網絡的重疊社區發現算法具有重要的研究意義和使用價值。本文提出的基于K-核迭代因子的重疊社區發現算法（KIMDOC），通過引入K-核迭代因子的概念，結合節點密度，量化節點影響力，在計算節點社區隸屬度時保留了節點網絡影響力和社區影響力兩個重要特性，既繼承了傳統局部擴展類社區發現算法的速度優勢，又能提高算法的穩定性和準確性。通過在人工基準網絡和真實網絡數據集上進行測試，可以看出本文算法運行結果理想，對社區劃分結果有一定提升。