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

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

1.遼寧大學(xué) 信息學(xué)院，沈陽(yáng)110036

2.吉林大學(xué) 符號(hào)計(jì)算與知識(shí)工程教育部重點(diǎn)實(shí)驗(yàn)室，長(zhǎng)春130012

1 引言

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

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

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

2 差分進(jìn)化

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

2.1 變異策略

目前，差分進(jìn)化使用的變異策略主要有如下四種：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中隨機(jī)選擇的，且滿足條件p1 ≠p2 ≠p3 ≠i，g是迭代次數(shù)，是目標(biāo)個(gè)體是變異個(gè)體，NP為種群規(guī)模。

2.2 交叉操作

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

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

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

2.3 選擇操作

3 差分進(jìn)化的改進(jìn)

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

3.1 變異策略改進(jìn)

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

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

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

3.2 動(dòng)態(tài)自適應(yīng)參數(shù)調(diào)整

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

式（7）中的縮放因子F值通常是常數(shù)，起到控制差異變量縮放幅度的作用。F值較小時(shí)，種群差異度減少，全局搜索能力降低，容易導(dǎo)致局部收斂；F值較大時(shí)，雖然容易跳出局部最優(yōu)解，但收斂速度會(huì)減慢。因此，采用式（8）對(duì)F值進(jìn)行動(dòng)態(tài)自適應(yīng)調(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）對(duì)CR值進(jìn)行動(dòng)態(tài)自適應(yīng)參數(shù)調(diào)整[17]，以找到使準(zhǔn)確性和收斂性最佳的CR，其中CRmin=0.1，CRmax=0.9。

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

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

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

3.3 實(shí)驗(yàn)驗(yàn)證

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

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

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

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

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

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

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

4.1 初始化

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

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

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

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

4.2 適應(yīng)度函數(shù)設(shè)置

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

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

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

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

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

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

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

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

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

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

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

（2）初始化階段

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

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

（3）二項(xiàng)交叉階段

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

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

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

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

4.4 算法描述

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

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

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

（3）If(g＜gmax)Then

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

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

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

④g=g+1。

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

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

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

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

Table 3 Comparisons of time complexity表3 時(shí)間復(fù)雜度比較

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

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

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

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

5.1 計(jì)算機(jī)生成網(wǎng)絡(luò)

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

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

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

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

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

5.2 真實(shí)世界網(wǎng)絡(luò)

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

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

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

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

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

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

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

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

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

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

5.3 結(jié)果分析

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

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

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

表6 中，IMDECD 在Jazz、US AirLines 和Polblogs這3 個(gè)網(wǎng)絡(luò)的Q值和標(biāo)準(zhǔn)差都最優(yōu)，這說(shuō)明本文所提IMDECD 算法更適用于規(guī)模較大的網(wǎng)絡(luò)。因此，相較于其他4 種算法，本文提出的算法在社區(qū)發(fā)現(xiàn)方面具有更高的準(zhǔ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)絡(luò)的模塊度比較

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

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

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