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

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

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

1 引言

社會網(wǎng)絡是由節(jié)點和邊組成的社會結(jié)構(gòu)，其中節(jié)點表示個體，邊代表個體之間的各種社會關系（如好友關系、合作關系等），具體的社會網(wǎng)絡形式諸如社交網(wǎng)絡、科研合作網(wǎng)絡等。社區(qū)發(fā)現(xiàn)即發(fā)現(xiàn)內(nèi)聚的子集合，使集合內(nèi)的節(jié)點聯(lián)系比它們與集合外的節(jié)點聯(lián)系更強[1]?；跈z測到的社區(qū)結(jié)構(gòu)可以深入揭示復雜網(wǎng)絡的拓撲結(jié)構(gòu)及功能。近年來，社區(qū)發(fā)現(xiàn)算法已在信息網(wǎng)絡的語義社區(qū)發(fā)現(xiàn)[2]、融合多源異構(gòu)數(shù)據(jù)的個性化推薦[3]等領域得到廣泛應用。

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

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

2 差分進化

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

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是迭代次數(shù)，是目標個體是變異個體，NP為種群規(guī)模。

2.2 交叉操作

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

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

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

2.3 選擇操作

3 差分進化的改進

為了提高社區(qū)發(fā)現(xiàn)的準確性和收斂性能，本文在現(xiàn)有差分進化的基礎上進行改進，主要改進措施包括變異策略改進以及動態(tài)自適應參數(shù)調(diào)整。

3.1 變異策略改進

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

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

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

3.2 動態(tài)自適應參數(shù)調(diào)整

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

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

其中，g是迭代次數(shù)，gmax是最大迭代次數(shù)，F(xiàn)min=0.3，F(xiàn)max=0.9。

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

Table 1 Benchmark functions表1 基準函數(shù)

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

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

3.3 實驗驗證

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

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

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

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

以上結(jié)果表明，本文對差分進化的改進措施是有效的，能夠提高原差分進化的準確性和收斂性，并且有效提高了種群質(zhì)量和全局收斂能力，為社區(qū)發(fā)現(xiàn)的模塊密度優(yōu)化問題提供了一種有效的優(yōu)化方法。

4 結(jié)合改進差分進化和模塊密度的社區(qū)發(fā)現(xiàn)

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

4.1 初始化

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

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

例如，圖1（a）顯示了一個包含7 個節(jié)點的網(wǎng)絡。根據(jù)社區(qū)結(jié)構(gòu)的定義，將網(wǎng)絡劃分為兩個以不同顏色節(jié)點表示的社區(qū)。圖1（b）是基于社區(qū)標識符的向量表示。

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

4.2 適應度函數(shù)設置

適應度函數(shù)通常有模塊度和模塊密度兩種，模塊度Q函數(shù)作為社區(qū)發(fā)現(xiàn)算法研究歷史上的里程碑，由于其易于實現(xiàn)而被廣泛應用在社區(qū)檢測中，基于模塊度優(yōu)化的算法已經(jīng)成為社區(qū)發(fā)現(xiàn)算法中的一個研究領域。

但是，Q有幾個缺點：首先，最大化Q值被證明是NP 問題。其次，Q值大并不總是有意義的，存在沒有社區(qū)結(jié)構(gòu)的隨機網(wǎng)絡也可以擁有很大的Q值的情況。最后，Q具有分辨率限制，最大化Q不能發(fā)現(xiàn)社區(qū)規(guī)模較小的社區(qū)，Q值的表示如式（11）所示[10]：

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

其中，m為劃分完成后的社區(qū)數(shù)量，λ為0 到1 之間的數(shù)，L(Vi,Vi) 為子網(wǎng)絡Gi內(nèi)的節(jié)點之間度數(shù)之和，為Gi內(nèi)的節(jié)點與Gi外其他節(jié)點的度數(shù)之和，為Gi的節(jié)點數(shù)量。

4.3 基于社區(qū)結(jié)構(gòu)的修改

由于差分進化在進行函數(shù)求解和社區(qū)發(fā)現(xiàn)上存在差異，本文在結(jié)合改進差分進化和模塊密度時，利用已知的社區(qū)結(jié)構(gòu)，進行以下修改操作，以提高計算的準確性。

（1）社區(qū)變量CV(i)

在社區(qū)發(fā)現(xiàn)的迭代過程中，可能會出現(xiàn)某些節(jié)點被放入錯誤的社區(qū)的情況，這些錯誤會削弱算法尋找最優(yōu)解的能力，降低準確性。

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

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

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

（2）初始化階段

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

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

（3）二項交叉階段

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

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

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

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

4.4 算法描述

結(jié)合社區(qū)結(jié)構(gòu)，IMDECD 算法的具體執(zhí)行步驟如下：

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

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

（3）If(g＜gmax)Then

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

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

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

④g=g+1。

（4）算法運行結(jié)束，輸出對復雜網(wǎng)絡社區(qū)結(jié)構(gòu)的最優(yōu)劃分結(jié)果以及對應的模塊密度值。

4.5 時間復雜度分析

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

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

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

5 實驗與結(jié)果分析

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

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

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

5.1 計算機生成網(wǎng)絡

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

上述網(wǎng)絡中的混合參數(shù)μ主要用于確定某一社區(qū)中任意一個節(jié)點與其他社區(qū)的節(jié)點之間共享邊的數(shù)量，隨著μ的不斷增大，網(wǎng)絡中的社區(qū)結(jié)構(gòu)將變得越來越模糊，性能一般的社區(qū)發(fā)現(xiàn)算法的NMI會開始下降，以此達到區(qū)分的目的。

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

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

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

5.2 真實世界網(wǎng)絡

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

Table 4 Real network dataset表4 真實網(wǎng)絡數(shù)據(jù)集

關于模塊密度Dλ中的λ取值為λ∈(0,1)。為分析λ對本文算法社區(qū)發(fā)現(xiàn)結(jié)果產(chǎn)生的影響，取λ不同數(shù)值下對社區(qū)發(fā)現(xiàn)結(jié)果的模塊度Q值和互信息值NMI的影響情況。圖3 為Karate 網(wǎng)絡的社區(qū)發(fā)現(xiàn)結(jié)果隨λ值變化的結(jié)果。

Fig.3 Effect of λ on Q and NMI in Karate network圖3 Karate網(wǎng)絡中λ 對Q 值和NMI 的影響結(jié)果

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

圖4 顯示Football 網(wǎng)絡的社區(qū)發(fā)現(xiàn)結(jié)果隨λ值變化的結(jié)果。

Fig.4 Effect of λ on Q and NMI in Football network圖4 Football網(wǎng)絡中λ 對Q 值和NMI 的影響結(jié)果

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

由于Karate 和Football 網(wǎng)絡都有已知的社區(qū)結(jié)構(gòu)，可以用模塊度Q值和互信息值NMI兩個標準來衡量社區(qū)劃分的結(jié)果；而Jazz、US AirLines 和Polblogs 網(wǎng)絡沒有已知社區(qū)結(jié)構(gòu)，因此只能以模塊度Q值為標準來衡量。圖5為其他3個網(wǎng)絡的社區(qū)發(fā)現(xiàn)結(jié)果隨λ值變化的結(jié)果?？梢钥闯?，當λ=0.6 時，Q值都較高，因此模塊密度Dλ中的λ取值0.6。

Fig.5 Effect of λ on Q in other networks圖5 其他網(wǎng)絡中λ 對Q 值的影響結(jié)果

5.3 結(jié)果分析

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

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

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

表6 中，IMDECD 在Jazz、US AirLines 和Polblogs這3 個網(wǎng)絡的Q值和標準差都最優(yōu)，這說明本文所提IMDECD 算法更適用于規(guī)模較大的網(wǎng)絡。因此，相較于其他4 種算法，本文提出的算法在社區(qū)發(fā)現(xiàn)方面具有更高的準確性和更好的收斂性能。

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 其他網(wǎng)絡的模塊度比較

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

6 結(jié)束語

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