結合改進差分進化和模塊密度的社區發現算法*

馮 勇，張冰茹，徐紅艷，王嶸冰+，張永剛

1.遼寧大學 信息學院，沈陽110036

2.吉林大學 符號計算與知識工程教育部重點實驗室，長春130012

1 引言

社會網絡是由節點和邊組成的社會結構，其中節點表示個體，邊代表個體之間的各種社會關系（如好友關系、合作關系等），具體的社會網絡形式諸如社交網絡、科研合作網絡等。社區發現即發現內聚的子集合，使集合內的節點聯系比它們與集合外的節點聯系更強[1]。基于檢測到的社區結構可以深入揭示復雜網絡的拓撲結構及功能。近年來，社區發現算法已在信息網絡的語義社區發現[2]、融合多源異構數據的個性化推薦[3]等領域得到廣泛應用。

社區發現算法可歸結為四類：基于凝聚式與分割的算法[1,4-6]、基于標簽傳播的算法[7-9]、基于模塊度優化的算法[5,9-12]、基于進化算法類的算法[10-12]。其中Girvan 和Newman[1]提出的經典GN（Givern-Newman）算法是一種凝聚式的算法，通過不斷移除網絡中最大的邊介數，能夠準確獲得具有層級結構的社區，但該算法計算速度有待提高；Newman 在GN 算法之上提出了一種基于網絡模塊度最大化的層次聚類方法[5]，該算法每次沿著使模塊度增加最大和減小最少的方向進行合并，使社區發現的準確性得到一定程度提高；Huang等人[10]提出了一種結合差分進化的社區檢測算法（cooperative co-evolutionary differential evolution based community detection，CCDECD），算法中引入協同進化框架并結合差分進化來優化網絡模塊度，以尋找最優的社區網絡；金弟等人[11]分析了模塊度函數的局部單調性，結合遺傳算法，提出快速有效的局部搜索算子，可用于求解大規模社區發現問題。這些算法雖然得到了較為廣泛的應用，但在發現的準確性與收斂速度方面尚存在提升空間。另外，現有算法多是基于模塊度優化的算法[5,9-12]，普遍存在模塊度分辨率限制[13]，即在計算過程中會將某些較小的社區合并，進而產生計算誤差。

為克服模塊度分辨率限制、提升社區發現的準確性和收斂性能，本文利用差分進化具有結構簡單、易于實現、收斂快速、魯棒性強等特點，并引入模塊密度[14]作為適應度函數以解決模塊度分辨率限制問題，提出了一種結合改進差分進化和模塊密度的社區發現算法（improved differential evolution and modularity density community detection，IMDECD）。該方法首先對差分進化進行改進，設計了一種新的變異策略，并對F和CR變量進行動態自適應參數調整；然后將模塊密度作為差分進化的適應度函數，對種群中的個體進行評價；最后基于已知的社區結構進行修改，包括基于社區變量的修正操作，以及初始化和二項交叉階段的修改。通過對比實驗，驗證本文所提算法相較于凝聚式的算法（GN）、基于密度峰值的算法（overlapping community detection algorithm based on density peaks，OCDDP）、結合差分進化和模塊度的算法（CCDECD and CDEMO（classification-based differential evolution algorithm for modularity optimization）），在社區發現的準確性和收斂性能方面得到一定程度的提升。

2 差分進化

近年來，基于進化算法類的社區發現算法由于其強大的全局優化能力，在很多應用場景下優于其他算法。其中差分進化[15]由于其簡單性和有效性被廣泛應用于數據挖掘、模式識別等領域，將其融入社區發現具有如下好處：既不需要復雜二進制編碼，也不需要使用概率密度函數去自適應其個體[16]，更不需要預先掌握任何關于社區結構的知識。差分進化包括三個主要步驟：變異、交叉和選擇。

2.1 變異策略

目前，差分進化使用的變異策略主要有如下四種：DE/rand/1、DE/rand/2、DE/best/1 和DE/rand-tobest/1。如式（1）～式（4）所示[16]：

其中，i∈{1,2,…,NP}，p1、p2 和p3 是從1,2,…,NP中隨機選擇的，且滿足條件p1 ≠p2 ≠p3 ≠i，g是迭代次數，是目標個體是變異個體，NP為種群規模。

2.2 交叉操作

差分進化常用的交叉方式有二項交叉與指數交叉。二項交叉方案對n個分量中的每一個分量都進行交叉；指數交叉方案選擇變異個體的一段，且該段以具有隨機長度的隨機整數k開始，該隨機整數k可以包含多個分量。

由于二項交叉更易于實現，時間復雜度較低，因此本文選擇二項交叉對變異個體和目標個體實施交叉操作，以產生實驗個體。二項式交叉如式（5）所示：

其中，i∈{1,2,…,NP}，j∈{1,2,…,n}，rand是0 和1 之間的均勻分布的隨機數，分別是第i目標個體、變異個體和實驗個體的第j維分量。

2.3 選擇操作

3 差分進化的改進

為了提高社區發現的準確性和收斂性能，本文在現有差分進化的基礎上進行改進，主要改進措施包括變異策略改進以及動態自適應參數調整。

3.1 變異策略改進

在2.1 節式（1）～式（4）中，式（1）和式（2）的基矢量從種群中隨機選取，具有全局搜索能力強、不易陷入局部最優的優勢，但收斂速度慢；式（3）和式（4）的基矢量是當前種群中最優個體，因而局部搜索能力強，收斂速度較快但易陷入局部最優。

以上四種變異策略均存在如下問題：僅側重準確性或收斂性中一方面的性能。例如式（1）和式（2）準確性高，但收斂速度慢，式（3）和式（4）收斂速度快，但容易陷入局部最優解，導致準確性低。因此，本文將構建一種混合變異策略以平衡準確性和收斂速度，如式（7）所示：

式（7）中采用“DE/rand/1”來保持種群的準確性，隨機生成新的個體以防止種群陷入局部最優。然后采用“DE/rand-to-best/1”，利用當前種群中最優個體的信息生成新的個體，來加快收斂速度。其中fi為2.3 節中的適應度函數值，對于目標個體，如果其適應度函數值fi大于當前群體中所有個體的平均適應值fˉ，則將其歸為優秀個體，采用DE/rand/1 防止陷入局部最優；否則，就將其歸為淘汰個體，采用DE/rand-to-best/1 利用最優個體生成新的個體。

3.2 動態自適應參數調整

差分進化中有兩個重要參數：縮放因子F值和交叉概率CR。經過實驗觀察和數據研究表明參數值的選擇應進行自適應調整[16-17]。

式（7）中的縮放因子F值通常是常數，起到控制差異變量縮放幅度的作用。F值較小時，種群差異度減少，全局搜索能力降低，容易導致局部收斂；F值較大時，雖然容易跳出局部最優解，但收斂速度會減慢。因此，采用式（8）對F值進行動態自適應調整[17]。

其中，g是迭代次數，gmax是最大迭代次數，Fmin=0.3，Fmax=0.9。

式（5）中CR是交叉概率，CR越大收斂速度越快，但易早熟，陷入局部最優。因此，采用式（9）對CR值進行動態自適應參數調整[17]，以找到使準確性和收斂性最佳的CR，其中CRmin=0.1，CRmax=0.9。

Table 1 Benchmark functions表1 基準函數

Table 2 Performance comparison of different mutation strategies表2 不同變異策略的性能比較

通過動態自適應參數調整，自適應地確定種群的變異率，從而使種群在初始階段保持多樣性，避免早熟收斂現象；并且通過逐步降低后期的突變率，避免破壞最優解，增加搜索全局最優解的可能性。

3.3 實驗驗證

為了驗證上述對差分進化改進措施的有效性，本文在5 個常用的標準基準函數上進行測試，表1 為5 個測試函數的名稱、公式、搜索空間和最優值，其中F1、F2 是單峰函數，F3～F5 是多峰函數。

將本文3.1節和3.2 節中的改進策略相結合，命名為IMDE（improved differential evolution），與式（1）～式（4）的變異策略進行比較，同時選擇與本文改進策略相近的文獻[17]中的變異策略DE_version 1 進行比較，其中每個變異策略的F值和交叉操作中的CR值均由式（8）和式（9）計算所得。實驗結果如表2所示，結果包括30 次獨立運行測試的平均值和標準差（表2中括號內的數據為標準差）。在實驗中，選擇與變異策略DE_version 1 相同的實驗參數：種群規模大小NP=100，維度大小D=30，F∈[0.3,0.9]和CR∈[0.1,0.9]。

表2 從準確性和收斂性能兩方面對6 種變異策略進行了比較，平均值體現準確性，標準差體現收斂性能，每種情況下的最優解都用粗體表示，可以看到，本文提出的改進策略IMDE 明顯優于其他5 種變異策略，在80%的測試函數上獲得了最優解。

通過表2 可以看出，IMDE 與式（1）DE/rand/1 單獨比較，在F1～F4 這4 個函數上標準差均有顯著提高，驗證了IMDE 采用“DE/rand-to-best/1” 可加快收斂速度；再與式（4）DE/rand-to-best/1 單獨比較，在F1～F4 這4 個函數上解的準確性有了顯著的提高，驗證了IMDE 采用“DE/rand/1”可防止種群陷入局部極值，提高了差分進化算法求解全局極值的能力。

以上結果表明，本文對差分進化的改進措施是有效的，能夠提高原差分進化的準確性和收斂性，并且有效提高了種群質量和全局收斂能力，為社區發現的模塊密度優化問題提供了一種有效的優化方法。

4 結合改進差分進化和模塊密度的社區發現

本文利用上述改進差分進化的優勢，結合模塊密度，對社區發現算法的改進策略開展研究。首先，在初始化階段，將網絡中每個節點用社區標識符進行規范化表示；然后，進行適應度函數設置，針對模塊度存在的分辨率限制問題，用模塊密度[14]代替模塊度作為適應度函數；最后，利用已知的社區結構，進行修改操作，包括基于社區變量的修正操作，以及初始化和二項交叉階段的修改。

4.1 初始化

對于具有n個節點的復雜網絡G=(V,E)，種群中的第k個個體由式（10）構成：

其中，ci表示節點i所屬社區，即社區標識符。IMDECD 在初始化時，每個節點所屬社區是隨機分配的，因此G中最多存在n個社區，社區標識符的最大值為n。

例如，圖1（a）顯示了一個包含7 個節點的網絡。根據社區結構的定義，將網絡劃分為兩個以不同顏色節點表示的社區。圖1（b）是基于社區標識符的向量表示。

Fig.1 Vectorization representation of individuals圖1 個體的向量化表示

4.2 適應度函數設置

適應度函數通常有模塊度和模塊密度兩種，模塊度Q函數作為社區發現算法研究歷史上的里程碑，由于其易于實現而被廣泛應用在社區檢測中，基于模塊度優化的算法已經成為社區發現算法中的一個研究領域。

但是，Q有幾個缺點：首先，最大化Q值被證明是NP 問題。其次，Q值大并不總是有意義的，存在沒有社區結構的隨機網絡也可以擁有很大的Q值的情況。最后，Q具有分辨率限制，最大化Q不能發現社區規模較小的社區，Q值的表示如式（11）所示[10]：

為了克服模塊度的分辨率限制，提高算法的準確性，Li 等人[14]在經過一系列理論推導和實踐測試后，提出了一種模塊密度計算方法，如式（12）所示。經Sato 等人[13]的實驗驗證，證實了模塊密度解決分辨率限制問題的有效性。因此，本文選擇模塊密度作為適應度函數。

其中，m為劃分完成后的社區數量，λ為0 到1 之間的數，L(Vi,Vi) 為子網絡Gi內的節點之間度數之和，為Gi內的節點與Gi外其他節點的度數之和，為Gi的節點數量。

4.3 基于社區結構的修改

由于差分進化在進行函數求解和社區發現上存在差異，本文在結合改進差分進化和模塊密度時，利用已知的社區結構，進行以下修改操作，以提高計算的準確性。

（1）社區變量CV(i)

在社區發現的迭代過程中，可能會出現某些節點被放入錯誤的社區的情況，這些錯誤會削弱算法尋找最優解的能力，降低準確性。

為解決上述問題，本文采用Tasgin 和Bingol[18]提出的基于社區變量CV(i)的修正操作，以減少節點被分配錯誤的情況。CV(i)被定義為節點i及其鄰居節點不在同一社區中的個數與節點i的度的比值，如式（13）所示：其中，deg(i)是第i個節點的度，ci是包含第i個節點的社區。

修正操作過程如下：首先，隨機選擇一些節點。然后，對每個節點計算其社區變量，并與閾值進行比較，閾值是在反復實驗之后獲得的預定義常數，本實驗中取0.3。如果該節點的社區變量大于這個閾值，則該節點及其所有鄰居將被放入同一社區，新社區為鄰居節點中包含最多節點數量的社區。否則，該節點將不執行任何操作。

通過基于社區變量的修正操作，每次節點被分配時，都會考慮到其鄰居節點，可減少節點分配錯誤的情況，提高準確性。

（2）初始化階段

在初始化過程中，每個節點是隨機分配到一個社區中的，然而這可能會導致一些沒有聯系的節點被分配到同一社區。為減少計算量，對初始化階段進行修改[18]。

修改后的初始化過程如下：一旦生成一個個體，就隨機選擇個體中的節點，將其社區標識符分配給其鄰居節點，生成初始種群，讓每個節點與其鄰居節點在初始化階段處于同一個社區中。通過此操作，限制了可能解的空間，消除了不必要的迭代，提高了IMDECD 算法的收斂速度。

（3）二項交叉階段

由于每次分配社區標識符都是隨機的，可能會出現以下情況：對于兩個個體{1,1,1,2,3} 和{3,3,3,2,1}，節點i多次分配到相同的社區，但每次對應的社區標識符卻不同，即社區和社區標識符之間不是一對一的對應關系。若按社區標識符統計節點i被分配到哪個社區時，就會出現錯誤結果，進而導致節點i被劃分到錯誤的社區中。這種情況下，若想得到正確的統計結果，算法必然要根據鄰居節點、社群結構判斷不同的標識符是否對應同一社區，因而會導致搜索最優解的效率下降。基于以上考慮，根據文獻[18]對交叉操作進行如下修改。

提高語文課堂教學效率，是當今語文教學的迫切要求，是語文教師不可推卸的責任。教師只有從培養學生良好的課堂學習習慣、激發學生學習語文的興趣、引導學生將學與練結合、指導學生學習的方法等方面著手，才能真正提高語文課堂教學的效率，減輕學生的課業負擔，讓學生樂于學習。

二項交叉過程的修改：首先，為每個i∈{1,2,…,NP}設置實驗個體ui=xi。然后，對每個j∈{1,2,…,n}考慮ui和變異個體vi中的第j個分量。如果rand≤CR，找到社區標識符為vi,j的所有節點，然后將ui中相應節點的社區標識符分配為vi,j，實現對應關系；否則，將不對ui執行操作。

修改后的二項交叉使每個社區有唯一的標識符與之對應，因而不會出現節點被分到同一社區卻對應不同標識符的情況，因此僅通過社區標識符就可以完成統計功能，從而提高算法搜索最優解的效率。

4.4 算法描述

結合社區結構，IMDECD 算法的具體執行步驟如下：

（1）初始化IMDECD 算 法的相關參數NP、n、gmax，詳見第5 章實驗參數設置。

（2）根據修改后的初始化過程，生成NP個n維向量組成初始群體P0={x1,x2,…,xNP}，其中每個個體xk由式（10）表示。計算P0中每個個體的模塊密度值，并保存當前最優個體及其對應的模塊密度值。

（3）If(g＜gmax)Then

①由式（7）和式（8）組成的自適應混合變異策略，對種群中的每個個體執行變異操作，生成對應的變異個體；執行式（13）中的修正操作，校正中的偏移向量。

②由式（5）和式（9）組成的自適應交叉策略，對種群中的每個個體執行修改后的二項交叉操作，生成對應的實驗個體；執行式（13）中的修正操作，校正中的偏移向量。

③采用式（6）的貪婪選擇策略，分別將種群中的目標個體與其對應的實驗個體進行比較，選擇其中的較優個體組成下一代種群Pg+1。式（6）中的適應度函數使用式（12）中給出的模塊密度。

④g=g+1。

（4）算法運行結束，輸出對復雜網絡社區結構的最優劃分結果以及對應的模塊密度值。

4.5 時間復雜度分析

假設社區網絡中節點數為n，邊數為t，劃分完后的社區數量為m，種群規模為NP，迭代次數為g。對于具有n個節點的社區網絡，本文的模塊密度函數時間復雜度為O(g2×NP×m)，式（7）的混合變異策略和式（6）的貪婪選擇策略的時間復雜度均為O(g2×NP)，式（5）的自適應交叉策略的時間復雜度為O(g2×NP×n)，因此本文算法的時間復雜度為O(g2×NP×(n+m))，與其他算法的時間復雜度的對比如表3所示。

由表3 可知，IMDECD 算法在時間復雜度上明顯優于GN 算法和OCDDP 算法。與CDEMO 算法相比，當節點數n大于迭代次數g時，IMDECD 算法的時間復雜度低，即更適合規模較大的復雜網絡。與CCDECD算法相比雖然時間復雜度持平，但后續實驗證明本文算法具有更高的準確性和更好的收斂性能。

Table 3 Comparisons of time complexity表3 時間復雜度比較

5 實驗與結果分析

本文實驗硬件環境為Intel?Pentium?，CPU 3.0 GHz，內存8.0 GB，仿真軟件為Windows 10 系統和Matlab R2017a。本文選擇計算機生成網絡和5個不同規模的真實世界網絡開展實驗，將所提算法與GN[1]、OCDDP[19]、CCDECD[10]以及CDEMO[17]算法進行比較。為了減少統計誤差，在每個數據集上獨立運行算法30 次，選擇平均值進行比較，所有算法的實驗參數設置和環境配置均相同。

根據數據集規模大小進行參數設置，在Karate 網絡中設置種群規模大小NP為20，最大迭代次數為50；Football 網絡中NP設置為30，最大迭代次數為300；在Jazz 和US AirLines 網絡中NP設置為30，最大迭代次數為600；在Polblogs 網絡中NP設置為60，最大迭代次數為600。

本文選擇式（11）所示的模塊度Q值和式（14）所示[17]的互信息值NMI作為評價函數：

5.1 計算機生成網絡

本文采用Lancichinetti 提出的人工計算機生成網絡GN Benchmark[20]驗證IMDECD 算法檢測網絡社區結構的性能。GN Benchmark 網絡中有128 個節點，它們被分成4 個社區，每個社區有32 個節點。

上述網絡中的混合參數μ主要用于確定某一社區中任意一個節點與其他社區的節點之間共享邊的數量，隨著μ的不斷增大，網絡中的社區結構將變得越來越模糊，性能一般的社區發現算法的NMI會開始下降，以此達到區分的目的。

圖2給出了IMDECD 算法與其他對比算法在GN Benchmark 網絡上，隨μ值的增大NMI的變化情況。

Fig.2 Average NMI of IMDECD and other algorithms圖2 IMDECD 與其他算法的平均NMI

從圖2 可以看出，與其他4 種算法對比，隨著μ的不斷增大，IMDECD 算法的性能優勢變得越來越明顯。當混合參數μ等于0.7 時，才開始出現下降，結果驗證了IMDECD 算法的有效性。

5.2 真實世界網絡

本節采用5 個具有代表性的、不同規模大小的真實網絡數據集進行測試，各數據集的詳細信息如表4所示，包括空手道俱樂部網絡[21]（Karate）、美國大學生2000賽季美式足球聯賽網絡[1]（Football）、爵士音樂家合作網絡[22]（Jazz）、美國航空網絡[23]（US AirLines）以及2004 年美國大選政治博客網絡[24]（Polblogs）。表4 說明了數據集的規模：節點數和邊數。

Table 4 Real network dataset表4 真實網絡數據集

關于模塊密度Dλ中的λ取值為λ∈(0,1)。為分析λ對本文算法社區發現結果產生的影響，取λ不同數值下對社區發現結果的模塊度Q值和互信息值NMI的影響情況。圖3 為Karate 網絡的社區發現結果隨λ值變化的結果。

Fig.3 Effect of λ on Q and NMI in Karate network圖3 Karate網絡中λ 對Q 值和NMI 的影響結果

從圖3 中可以看出，在Karate 網絡中，當λ=0.3時，NMI=1，Q=0.371 8，其社區劃分后的結果與真實的網絡社區一樣，Q值卻較低；當λ=0.6，0.7，0.8 時，Q值均為0.419 8，NMI值卻分別為0.725 3、0.639 9、0.652 8。因此，在Karate 網絡中，當λ=0.6 時，NMI=0.725 3，Q=0.419 8，兩者的值都較高。

圖4 顯示Football 網絡的社區發現結果隨λ值變化的結果。

Fig.4 Effect of λ on Q and NMI in Football network圖4 Football網絡中λ 對Q 值和NMI 的影響結果

從圖4 中可以看出，在Football 網絡中，λ=0.4～0.8 時，Q值變化不大，均在0.604 6 左右，NMI值變化較大。當λ=0.6 時，NMI值最大，為0.935 4。因此，在Football網絡中，當λ=0.6 時，NMI=0.935 4，Q=0.604 6，兩者的值都較高。

由于Karate 和Football 網絡都有已知的社區結構，可以用模塊度Q值和互信息值NMI兩個標準來衡量社區劃分的結果；而Jazz、US AirLines 和Polblogs 網絡沒有已知社區結構，因此只能以模塊度Q值為標準來衡量。圖5為其他3個網絡的社區發現結果隨λ值變化的結果。可以看出，當λ=0.6 時，Q值都較高，因此模塊密度Dλ中的λ取值0.6。

Fig.5 Effect of λ on Q in other networks圖5 其他網絡中λ 對Q 值的影響結果

5.3 結果分析

根據以上研究，表5和表6為每個算法在5個數據集上獨立運行30次后的實驗結果，表中包括：模塊度Q的平均值、互信息值NMI、標準差和社區個數。表中數據格式說明：0.419 8/4，其中0.419 8 表示模塊度，4 表示社區個數；（0.00E-00）表示運行30 次的標準差。

從表5和表6中可以看出，相對于其他算法而言，IMDECD 在5 個真實網絡數據集上具有較好的效果。

表5 中，在Karate 網絡，IMDECD 的Q值和標準差與CCDECD、CDEMO 同時達到最優，Q值相較于OCDDP 提高了3.3%，與GN 相比提高了4.6%；互信息值NMI未達到最優，這是因為GN 算法更適合小規模網絡；在Football 網絡中NMI達到最優，Q值和標準差較低，這說明IMDECD 在Football 網絡上的劃分結果和真實網絡劃分最為接近，但由于真實網絡的模塊度并不高，導致IMDECD 算法的Q值較低，也說明了IMDECD 算法不適合規模較小的網絡。

表6 中，IMDECD 在Jazz、US AirLines 和Polblogs這3 個網絡的Q值和標準差都最優，這說明本文所提IMDECD 算法更適用于規模較大的網絡。因此，相較于其他4 種算法，本文提出的算法在社區發現方面具有更高的準確性和更好的收斂性能。

Table 5 Comparison of NMI and modularity between Karate and Football network表5 Karate和Football的NMI、模塊度比較

Table 6 Comparison of modularity of other networks表6 其他網絡的模塊度比較

關于分辨率限制，4 個對比算法中，CCDECD 和CDEMO 算法是基于模塊度優化的算法。在Football、Jazz、US AirLines 以及Polblogs 網絡中，IMDECD 算法劃分的社區個數均大于CCDECD 和CDEMO 算法，表明使用模塊密度的IMDECD 算法能劃分得到更多的社區，即能分辨出更多較小的社區。

6 結束語

為克服模塊度分辨率限制，提升社區發現的準確性和收斂性能，本文提出了一種結合改進差分進化和模塊密度的社區發現算法。該算法首先調整差分進化的變異策略，并對F和CR變量進行動態自適應參數調整；然后針對模塊度的分辨率限制問題，將模塊密度作為差分進化的適應度函數，對種群中的個體進行評價；最后基于已知的社區結構進行修改，包括基于社區變量的修正操作，以及初始化和二項交叉階段的修正。對比實驗表明，本文提出的IMDECD 算法具有更高的社區發現準確性和更好的收斂性能，更強的尋優能力與魯棒性，能夠有效探測真實世界網絡中存在的社區結構。