一種基于差分進(jìn)化的社團(tuán)檢測(cè)算法

孫韓林　馬素剛　王忠民

摘 要：復(fù)雜網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)分析可抽象為一個(gè)優(yōu)化問(wèn)題，用進(jìn)化算法求解。進(jìn)化類(lèi)算法的一個(gè)基本問(wèn)題是如何把問(wèn)題的候選解編碼到進(jìn)化個(gè)體中。本文將索引局部鄰接表示法用于社團(tuán)檢測(cè)進(jìn)化算法的個(gè)體表示，把社團(tuán)結(jié)構(gòu)分析轉(zhuǎn)化為一個(gè)整數(shù)優(yōu)化問(wèn)題。在該個(gè)體表示方法的基礎(chǔ)上，提出了一種基于差分進(jìn)化的社團(tuán)檢測(cè)算法。在一組合成網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)上驗(yàn)證了算法性能，并與兩種基于遺傳算法的典型社團(tuán)檢測(cè)進(jìn)化算法進(jìn)行了對(duì)比。實(shí)驗(yàn)結(jié)果表明，當(dāng)網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)較為清晰時(shí)，基于差分進(jìn)化的算法檢測(cè)到的社團(tuán)結(jié)構(gòu)具有更好的質(zhì)量。

關(guān)鍵詞：社團(tuán)檢測(cè)；社團(tuán)結(jié)構(gòu)分析；差分進(jìn)化；復(fù)雜網(wǎng)絡(luò)

中圖分類(lèi)號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A

Abstract：Community structure analysis of complex networks can be modeled as an optimizing problem，and then be solved by Evolution Algorithm （EA）.One fundamental issue of EA is how to encode a candidate solution into an evolution individual.In this paper，the Indexed Locus-based Adjacency Representation （ILAR） of evolution individual encoding for the community detection problem is proposed.Therefore，a community detection problem can be converted to a discrete integer optimization problem.Based on the ILAR，a community detection algorithm that uses Differential Evolution （DE） as the search engine is developed.A number of experiments are conducted on synthesized and real-world networks to verify the performance of the proposed algorithm，and the results are compared against those of two typical community detection algorithms based on Genetic Algorithm （GA）.The experiment results show that the community structure discovered by the proposed DE-based algorithm generally has better quality than those of the two compared algorithms as the community structure of the analyzed network is sound.

Keywords：community detection；community structure analysis；differential evolution；complex network

1 引言（Introduction）

社團(tuán)是復(fù)雜網(wǎng)絡(luò)中一組節(jié)點(diǎn)的集合，組內(nèi)節(jié)點(diǎn)具有共同的屬性或在網(wǎng)絡(luò)中具有相似的功能，拓?fù)浣Y(jié)構(gòu)上表現(xiàn)為組內(nèi)節(jié)點(diǎn)間具有更緊密（更多）的連接邊，而組內(nèi)成員與網(wǎng)絡(luò)其余節(jié)點(diǎn)的連接邊相對(duì)稀疏。社團(tuán)結(jié)構(gòu)從中觀（middle-scope level）層次上揭示了網(wǎng)絡(luò)的結(jié)構(gòu)特性，對(duì)理解網(wǎng)絡(luò)性質(zhì)具有重要意義。

社團(tuán)結(jié)構(gòu)檢測(cè)可抽象為一個(gè)優(yōu)化問(wèn)題，利用進(jìn)化算法（Evolution Algorithm，EA）進(jìn)行求解，即定義一種度量社團(tuán)結(jié)構(gòu)質(zhì)量的目標(biāo)函數(shù)，再利用進(jìn)化算法求解函數(shù)的極大值或極小值。用進(jìn)化算法進(jìn)行社團(tuán)檢測(cè)的主要優(yōu)點(diǎn)是不需要事先知道社團(tuán)結(jié)構(gòu)的屬性（例如社團(tuán)的數(shù)量）。常用于社團(tuán)檢測(cè)的進(jìn)化算法有遺傳算法[1-5]（Genetic Algorithm，GA）和差分進(jìn)化[6-8]（Differential Evolution，DE）算法。

進(jìn)化算法的一個(gè)基本問(wèn)題是如何將一種可能的候選解決方案編碼到進(jìn)化個(gè)體中。本文提出了索引局部鄰接進(jìn)化個(gè)體表示法，將社團(tuán)檢測(cè)轉(zhuǎn)化為整數(shù)優(yōu)化問(wèn)題；在此基礎(chǔ)上，提出一種以DE為搜索引擎的社團(tuán)檢測(cè)算法。DE被認(rèn)為是求解實(shí)數(shù)優(yōu)化問(wèn)題的最優(yōu)進(jìn)化算法之一[9]。

2 進(jìn)化個(gè)體表示（Evolutionary individual

representation）

在用進(jìn)化算法求解社團(tuán)檢測(cè)問(wèn)題時(shí)，有兩種典型的個(gè)體編碼方案，即“線性組表示法”（String-of-Group Representation，SGR）和“局部鄰接表示法”（Locus-based Adjacency Representation，LAR）[10]。這兩種表示方法中，進(jìn)化個(gè)體都是一個(gè)N維向量，N是網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)，向量的每一維代表了網(wǎng)絡(luò)中的一個(gè)節(jié)點(diǎn)。在SGR中，每個(gè)維度的值是該維代表節(jié)點(diǎn)所屬社團(tuán)的社團(tuán)標(biāo)識(shí)符；而在LAR中，則是該維代表節(jié)點(diǎn)的某個(gè)鄰居的節(jié)點(diǎn)標(biāo)識(shí)符（即該鄰居節(jié)點(diǎn)在向量中的維序數(shù)），通過(guò)鄰接關(guān)系連接在一起的一組節(jié)點(diǎn)構(gòu)成一個(gè)社團(tuán)。

文獻(xiàn)[6]—文獻(xiàn)[8]中基于DE的社團(tuán)檢測(cè)算法都采用了SGR表示法。差分進(jìn)化算法中，變異操作中要進(jìn)行個(gè)體求差運(yùn)算，顯然對(duì)社團(tuán)標(biāo)識(shí)符進(jìn)行求差沒(méi)有實(shí)際意義。同樣，若采用LAR表示法，對(duì)鄰居的節(jié)點(diǎn)標(biāo)識(shí)符求差同樣沒(méi)有意義。本文對(duì)局部鄰接表示法進(jìn)行改進(jìn)，提出“索引局部鄰接表示法”（Indexed Locus-based Adjacency Representation，ILAR），從而將社團(tuán)檢測(cè)問(wèn)題轉(zhuǎn)化為整數(shù)優(yōu)化問(wèn)題，這樣就可以在差分變異操作中直接使用傳統(tǒng)的求差運(yùn)算。endprint

索引局部鄰接表示法中，個(gè)體同樣是一個(gè)N維向量，每一維也代表網(wǎng)絡(luò)中的一個(gè)節(jié)點(diǎn)。與LAR不同的是，向量每一維的值是該維代表節(jié)點(diǎn)的某個(gè)鄰居節(jié)點(diǎn)的鄰居索引標(biāo)識(shí)符，而不是鄰居的節(jié)點(diǎn)標(biāo)識(shí)符。一個(gè)節(jié)點(diǎn)可能有若干鄰居，把所有鄰居按一定順序排列，例如按鄰居的節(jié)點(diǎn)標(biāo)識(shí)符升序或降序排列，則該節(jié)點(diǎn)某個(gè)鄰居的鄰居索引標(biāo)識(shí)符就是此鄰居節(jié)點(diǎn)在鄰居列表中的序數(shù)。一個(gè)節(jié)點(diǎn)可以是多個(gè)節(jié)點(diǎn)的鄰居，對(duì)不同鄰居節(jié)點(diǎn)，它的鄰居索引標(biāo)識(shí)符是不同的。因此，采用索引局部鄰接表示法后，網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)會(huì)同時(shí)有多個(gè)標(biāo)識(shí)符——一個(gè)節(jié)點(diǎn)標(biāo)識(shí)符和若干鄰居索引標(biāo)識(shí)符，鄰居索引標(biāo)識(shí)符的數(shù)量與節(jié)點(diǎn)的鄰居的數(shù)量相同。索引局部鄰接表示可以看作是一種歸一化的局部鄰接矩陣表示。

解析索引局部鄰接表示個(gè)體中編碼的社團(tuán)結(jié)構(gòu)分為兩步：首先把向量每一維的鄰居索引標(biāo)識(shí)符替換為相應(yīng)的鄰居節(jié)點(diǎn)標(biāo)識(shí)符；然后再找出通過(guò)鄰居關(guān)系關(guān)聯(lián)在一起的節(jié)點(diǎn)組，每個(gè)組即是一個(gè)社團(tuán)。第二步操作與解析局部鄰接表示個(gè)體中社團(tuán)結(jié)構(gòu)的過(guò)程相同。

圖1給出了一個(gè)簡(jiǎn)單的用索引局部鄰接表示法表示進(jìn)化個(gè)體的例子。圖1（a）是一個(gè)簡(jiǎn)單網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)圖，該網(wǎng)絡(luò)包含9個(gè)節(jié)點(diǎn)，它們分為兩個(gè)社團(tuán)，分別是{1，2，3，4，5}和{6，7，8，9}；圖1（b）列出了每一個(gè)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)列表，按鄰居的節(jié)點(diǎn)標(biāo)識(shí)符升序排列，并給每個(gè)鄰居分配了鄰居索引標(biāo)識(shí)符；圖1（c）給出了一個(gè)采用索引局部鄰接表示法的可能的進(jìn)化個(gè)體，其中節(jié)點(diǎn)1連接到其第1個(gè)鄰居（節(jié)點(diǎn)2），節(jié)點(diǎn)2連接到其第3個(gè)鄰居（節(jié)點(diǎn)4），節(jié)點(diǎn)3連接到其第1個(gè)鄰居（節(jié)點(diǎn)1），其余維類(lèi)似；圖1（d）則是用節(jié)點(diǎn)標(biāo)識(shí)符替換相應(yīng)維鄰居索引標(biāo)識(shí)符后得到的進(jìn)化個(gè)體，即采用局部鄰接表示法的個(gè)體；圖1（e）是在該個(gè)體中編碼的社團(tuán)結(jié)構(gòu)的圖形化表示。

3 算法描述（Algorithm description）

差分進(jìn)化算法包括四個(gè)步驟，即初始化、變異、交叉和選擇，其中初始化只在算法開(kāi)始時(shí)執(zhí)行一次，而后面三步操作則迭代多次，直到算法結(jié)束[11]。在索引局部鄰接個(gè)體表示法的基礎(chǔ)上，本文提出基于差分進(jìn)化的社團(tuán)檢測(cè)算法DECDILAR（Differential Evolution Community Detection Algorithm based on ILAR）。

3.1 初始化

在初始化操作中，差分進(jìn)化算法隨機(jī)生成一個(gè)有NP個(gè)個(gè)體的種群，其中每個(gè)個(gè)體都是一個(gè)N維實(shí)數(shù)向量，代表了一種 維優(yōu)化問(wèn)題的候選解。由于每一維都關(guān)聯(lián)到優(yōu)化問(wèn)題的一個(gè)物理參數(shù)，其取值范圍通常必須限制在一個(gè)范圍內(nèi)，且每一維的取值范圍可能不同。初始化種群中個(gè)體的每一維都要盡可能均勻、隨機(jī)地分布在它的取值范圍內(nèi)。

采用索引局部鄰接表示法時(shí)，社團(tuán)檢測(cè)可以轉(zhuǎn)化成一個(gè)整數(shù)優(yōu)化問(wèn)題。一個(gè)個(gè)體的第維被隨機(jī)初始化為1到第個(gè)節(jié)點(diǎn)的最大鄰居數(shù)（記為）之間的某個(gè)數(shù)值。記第個(gè)個(gè)體的第維為，則初始化可以表示為：

其中是一個(gè)均勻分布在區(qū)間 上的隨機(jī)數(shù)，該隨機(jī)數(shù)對(duì)每個(gè)個(gè)體的每一維都重新獨(dú)立生成一次；函數(shù)將一個(gè)實(shí)數(shù)轉(zhuǎn)換成最接近的整數(shù)；的第三維下表“0”表示當(dāng)前進(jìn)化代數(shù)是初始化。

3.2 差分變異

差分進(jìn)化算法中，從當(dāng)前種群中選擇的一個(gè)父輩個(gè)體稱(chēng)為“目標(biāo)向量”（target vector）；通過(guò)差分變異（mutation）操作生成的變異個(gè)體稱(chēng)為“捐贈(zèng)向量”（donor vector）；而通過(guò)捐贈(zèng)向量和目標(biāo)向量的交叉（crossover）操作生成的后代個(gè)體稱(chēng)為“試驗(yàn)向量”（trail vector）。

變異指?jìng)€(gè)體的某些維突然發(fā)生改變。與其他多數(shù)進(jìn)化算法不同，差分進(jìn)化采用向量（個(gè)體）間的差異來(lái)探索搜索空間。實(shí)際上，不同差分進(jìn)化算法的區(qū)別就在于變異操作中使用個(gè)體差異的模式不同。DECDILAR在生成捐贈(zèng)向量的變異運(yùn)算中采用了一種最簡(jiǎn)單的變異模式“DE/best/1”，其中“DE”代表差分進(jìn)化，“best”表示選擇當(dāng)前種群中的最優(yōu)個(gè)體作為變異的基向量（base vector），“1”表示在擾動(dòng)基向量時(shí)只考慮了一個(gè)差分向量（即個(gè)體間的差異）。為了防止種群早熟，我們對(duì)“DE/best/1”進(jìn)行了改進(jìn)，通過(guò)引入一個(gè)新參數(shù)“變異率”（mutation ratio），設(shè)計(jì)了一種受控的變異運(yùn)算。記第個(gè)個(gè)體的捐贈(zèng)向量為（表示當(dāng)前進(jìn)化代數(shù)），則這種受控差分變異操作可表示為：

其中是從當(dāng)前種群中選擇的最好個(gè)體，作為變異的基向量；是參數(shù)“變異速率”（mutation rate）；和是兩個(gè)從當(dāng)前種群中隨機(jī)選取的個(gè)體；是均勻分布在區(qū)間上的一個(gè)隨機(jī)數(shù)，該隨機(jī)數(shù)在生成每個(gè)個(gè)體的捐贈(zèng)向量時(shí)重新生成一次。

需要注意的是，通過(guò)差分變異運(yùn)算獲得的捐贈(zèng)向量中，某些維的取值可能超出了其限制區(qū)間。如果第維的取值超出了其限制區(qū)間，則將其隨機(jī)地設(shè)置為一個(gè)有效值。

3.3 交叉

交叉操作的作用在于增強(qiáng)種群的多樣性。通過(guò)交叉操作，捐贈(zèng)向量與相應(yīng)的目標(biāo)向量交換部分維的值，從而生成一個(gè)新個(gè)體——試驗(yàn)向量。差分進(jìn)化常用的一種典型交叉運(yùn)算是“二項(xiàng)式交叉”（binomial crossover），即對(duì)試驗(yàn)向量的第維，當(dāng)一個(gè)在區(qū)間上產(chǎn)生的隨機(jī)數(shù)小于或等于給定的“交叉速率”（crossover rate）時(shí)，其值來(lái)自于捐贈(zèng)向量的第維，否則來(lái)自于目標(biāo)向量的第維。二項(xiàng)式交叉可表示為：

其中是針對(duì)第維生成的一個(gè)均勻分布在區(qū)間上的隨機(jī)數(shù)；而則是一個(gè)隨機(jī)選擇的維數(shù)標(biāo)識(shí)，條件保證了試驗(yàn)向量中至少有一維來(lái)自于捐贈(zèng)向量；在每代進(jìn)化中針對(duì)一個(gè)個(gè)體（即目標(biāo)向量）生成一次。

通過(guò)多次試驗(yàn)，我們發(fā)現(xiàn)“均勻交叉”（uniform crossover）運(yùn)算在社團(tuán)檢測(cè)中很有效。均勻交叉等可能地在搜索空間中探測(cè)各個(gè)方向。差分進(jìn)化中，等效的均勻交叉可通過(guò)設(shè)置二項(xiàng)式交叉的交叉速率為0.5來(lái)實(shí)現(xiàn)。由于此時(shí)試驗(yàn)向量的每一維等可能地來(lái)自于捐贈(zèng)向量或目標(biāo)向量，而又無(wú)法事先假設(shè)哪種取值更好，因此我們?yōu)槊總€(gè)目標(biāo)向量同時(shí)生成并保留兩個(gè)試驗(yàn)向量，其中一個(gè)向量的一維來(lái)自于捐贈(zèng)向量，而另一向量的相應(yīng)維則來(lái)自于目標(biāo)向量。endprint

3.4 選擇及優(yōu)化目標(biāo)函數(shù)

差分進(jìn)化算法中選擇（selection）操作用于確定是目標(biāo)向量還是其對(duì)應(yīng)的試驗(yàn)向量在下一代種群中存活。對(duì)最大化優(yōu)化問(wèn)題，選擇操作可表示為：

其中是優(yōu)化目標(biāo)函數(shù)。注意當(dāng)試驗(yàn)向量的目標(biāo)函數(shù)值與目標(biāo)向量的目標(biāo)函數(shù)值相等時(shí)，差分進(jìn)化算法也用試驗(yàn)向量取代目標(biāo)向量。

DECDILAR算法采用Newman和Girvan提出的模塊度（modularity）[12]作為優(yōu)化目標(biāo)函數(shù)。模塊度值越大，表明社團(tuán)結(jié)構(gòu)的質(zhì)量越好。注意在交叉操作中為每個(gè)目標(biāo)向量保留了兩個(gè)試驗(yàn)向量，因此選擇操作是從目標(biāo)向量和兩個(gè)試驗(yàn)向量中選擇最好的個(gè)體在下一代中存活。

3.5 算法框架

基于差分進(jìn)化的社團(tuán)檢測(cè)算法DECDILAR的框架如下：

4 實(shí)驗(yàn)結(jié)果及分析（Experiment results and analysis）

在一組合成網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)上對(duì)DECDILAR算法的性能進(jìn)行測(cè)試。為了對(duì)比不同搜索引擎（GA和DE），以及進(jìn)化個(gè)體表示方法對(duì)社團(tuán)結(jié)構(gòu)檢測(cè)的影響，實(shí)驗(yàn)中也實(shí)現(xiàn)了兩種基于GA的算法——GACDSGR和GACDLAR，其中GACDSGR中個(gè)體表示采用了線性組表示法，而GACDLAR中則采用了局部鄰接表示法。關(guān)于這兩種算法更多的細(xì)節(jié)請(qǐng)分別參考文獻(xiàn)[2]和文獻(xiàn)[3]。社團(tuán)結(jié)構(gòu)質(zhì)量的度量則采用了模塊度和歸一化互信息（Normalized Mutual Information，NMI）[13]。如果網(wǎng)絡(luò)的真實(shí)社團(tuán)結(jié)構(gòu)已知，可用NMI指示算法檢測(cè)到的社團(tuán)結(jié)構(gòu)與真實(shí)社團(tuán)結(jié)構(gòu)的相似程度，值越大，表明兩種結(jié)果越相似。

4.1 實(shí)驗(yàn)設(shè)置

參考相關(guān)文獻(xiàn)及通過(guò)多次試驗(yàn)，在兩種基于GA的算法中，設(shè)置交叉率為0.8，變異率為0.2；在DECDILAR算法中設(shè)置變異率（）為0.2，變異速率（）為0.1，交叉率（）為0.5。三種算法的種群規(guī)模（）均設(shè)置為300，最大進(jìn)化代數(shù)（）也設(shè)置為300。

對(duì)每一個(gè)測(cè)試的網(wǎng)絡(luò)，所有算法都執(zhí)行10次；對(duì)每次運(yùn)行所發(fā)現(xiàn)的社團(tuán)結(jié)構(gòu)計(jì)算模塊度或歸一化互信息，最后計(jì)算10次運(yùn)行結(jié)果的平均值及標(biāo)準(zhǔn)差。

4.2 合成網(wǎng)絡(luò)實(shí)驗(yàn)結(jié)果及分析

實(shí)驗(yàn)中用LFR模型[14]生成五個(gè)無(wú)向、無(wú)權(quán)重的復(fù)雜網(wǎng)絡(luò)，其混合參數(shù)（）分別取0.1、0.2、0.3、0.4及0.5。混合參數(shù)指明了社團(tuán)外部連接數(shù)占社團(tuán)成員節(jié)點(diǎn)總連接數(shù)的比率，值越大，表明網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)越模糊。LFR模型的其余參數(shù)設(shè)置為：網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)（N）200，平均節(jié)點(diǎn)度（k）20，最大節(jié)點(diǎn)度（kmax）50，最大社團(tuán)規(guī)模（cmax）40，最小社團(tuán)規(guī)模（cmin）20，節(jié)點(diǎn)度負(fù)指數(shù)分布指數(shù)（t1）-2，社團(tuán)規(guī)模負(fù)指數(shù)分布指數(shù)（t2）-1。各種算法在這些網(wǎng)絡(luò)上10次運(yùn)行結(jié)果的平均模塊度和平均歸一化互信息如表1所示。

從表中可以看出，當(dāng)混合參數(shù)（）取0.1、0.2和0.3時(shí)，算法GACDLAR和DECDILAR均能發(fā)現(xiàn)正確的社團(tuán)結(jié)構(gòu)，且它們的結(jié)果都遠(yuǎn)好于算法GACDSGR。當(dāng)取0.4時(shí)，兩種基于局部鄰接個(gè)體表示及其改進(jìn)的算法檢測(cè)到的社團(tuán)結(jié)構(gòu)質(zhì)量仍遠(yuǎn)好于GACDSGR，且DECDILAR比GACDLAR稍好。而當(dāng)增加至0.5時(shí)，算法DECDILAR發(fā)現(xiàn)的社團(tuán)結(jié)構(gòu)質(zhì)量卻最差，而GACDLAR算法發(fā)現(xiàn)的最好。但從歸一化互信息看，此時(shí)即使是最好的社團(tuán)結(jié)構(gòu)，其與網(wǎng)絡(luò)真實(shí)社團(tuán)結(jié)構(gòu)的平均相似度也只有0.5061。在實(shí)際應(yīng)用中，這種質(zhì)量水平也是不可接受的。

上述試驗(yàn)結(jié)果表明，局部鄰接個(gè)體表示法及其改進(jìn)比線性組表示法更適合于社團(tuán)檢測(cè)問(wèn)題。此外，當(dāng)網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)較為清晰（實(shí)驗(yàn)中）時(shí)，遺傳算法和差分進(jìn)化兩種搜索引擎都能夠發(fā)現(xiàn)高質(zhì)量的社團(tuán)結(jié)構(gòu)，且DE更有可能發(fā)現(xiàn)更好的結(jié)果。

4.3 真實(shí)網(wǎng)絡(luò)實(shí)驗(yàn)結(jié)果及分析

真實(shí)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)特性可能比合成網(wǎng)絡(luò)更為復(fù)雜。我們也用三個(gè)真實(shí)的網(wǎng)絡(luò)上測(cè)試了三種算法。這些網(wǎng)絡(luò)分別是：寬吻海豚網(wǎng)絡(luò)（bottlenose dolphins network）[14]，共有62個(gè)節(jié)點(diǎn)、159條邊；美國(guó)學(xué)院足球比賽網(wǎng)絡(luò)（American college football network）[15]，共有115個(gè)節(jié)點(diǎn)、616條邊；新陳代謝網(wǎng)絡(luò)（metabolic network）[16]，共有453個(gè)節(jié)點(diǎn)、2025條邊。其中寬吻海豚網(wǎng)絡(luò)和美國(guó)學(xué)院足球比賽網(wǎng)絡(luò)的真實(shí)社團(tuán)結(jié)構(gòu)已知（由人手工建立），分別包含兩個(gè)和19個(gè)社團(tuán)。對(duì)這三個(gè)網(wǎng)絡(luò)各算法10次運(yùn)行結(jié)果的平均模塊度及平均歸一化互信息如表2所示（新陳代謝網(wǎng)絡(luò)的真實(shí)社團(tuán)結(jié)構(gòu)未知，因而無(wú)法計(jì)算其歸一化互信息值）。從表中可以看出，結(jié)果與合成網(wǎng)絡(luò)類(lèi)似：兩種基于局部鄰接個(gè)體表示及其改進(jìn)的算法發(fā)現(xiàn)的社團(tuán)結(jié)構(gòu)質(zhì)量要好于GACDSGR算法，而DECDILAR發(fā)現(xiàn)的社團(tuán)結(jié)構(gòu)質(zhì)量要好于GACDLAR。

表2中也給出了寬吻海豚網(wǎng)絡(luò)和美國(guó)學(xué)院足球比賽網(wǎng)絡(luò)的真實(shí)網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的模塊度值。可以看到，三種算法檢測(cè)到的社團(tuán)結(jié)構(gòu)的模塊度值均比真實(shí)模塊度值大，尤其是寬吻海豚網(wǎng)絡(luò)。表2也給出了各算法發(fā)現(xiàn)的社團(tuán)的數(shù)量，可以看到，對(duì)寬吻海豚網(wǎng)絡(luò)，三種算法發(fā)現(xiàn)的社團(tuán)數(shù)量比真實(shí)社團(tuán)數(shù)量（2個(gè)）更多，平均接近5個(gè)，表明算法發(fā)現(xiàn)的社團(tuán)結(jié)構(gòu)更為精細(xì)；而對(duì)美國(guó)學(xué)院足球比賽網(wǎng)絡(luò)，盡管算法發(fā)現(xiàn)的社團(tuán)數(shù)量小于真實(shí)社團(tuán)數(shù)量（19個(gè)），但真實(shí)社團(tuán)結(jié)構(gòu)中包含有8個(gè)只有1個(gè)成員節(jié)點(diǎn)的社團(tuán)，主要社團(tuán)的數(shù)量（11個(gè)）與算法發(fā)現(xiàn)的社團(tuán)數(shù)量相當(dāng)（平均接近10個(gè)）。模塊度表明算法發(fā)現(xiàn)的社團(tuán)結(jié)構(gòu)質(zhì)量更好。

圖2是DECDILAR檢測(cè)到的一種寬吻海豚網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)，其中不同的節(jié)點(diǎn)形狀表示真實(shí)的社團(tuán)，不同形狀及填充顏色表示算法發(fā)現(xiàn)的社團(tuán)。可以看到，算法共發(fā)現(xiàn)了5個(gè)社團(tuán)，其中社團(tuán)1、3、4、5節(jié)點(diǎn)形狀相同，它們合并后就是一個(gè)真實(shí)的社團(tuán)，即算法發(fā)現(xiàn)的社團(tuán)結(jié)構(gòu)更為精細(xì)。表3是DECDILAR算法檢測(cè)到的一種美國(guó)學(xué)院足球網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)及其與真實(shí)社團(tuán)結(jié)構(gòu)的對(duì)應(yīng)關(guān)系（由于該網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)較多，我們通過(guò)列表方式給出它的社團(tuán)結(jié)構(gòu)）。可見(jiàn)，算法正確發(fā)現(xiàn)了6個(gè)真實(shí)社團(tuán)（社團(tuán)2、3、4、5、9及10）；發(fā)現(xiàn)的社團(tuán)1是兩個(gè)真實(shí)社團(tuán)（BigWest和MountainWest）的合并；3個(gè)社團(tuán)（社團(tuán)6、7及8）與8個(gè)只包含1個(gè)成員的社團(tuán)混合在了一起。endprint

綜上所述，DECDILAR是一種有效的社團(tuán)檢測(cè)算法。

5 結(jié)論（Conclusion）

本文在局部鄰接表示法的基礎(chǔ)上，提出了一種改進(jìn)的索引局部鄰接進(jìn)化個(gè)體表示法，從而將復(fù)雜網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)分析問(wèn)題轉(zhuǎn)化為一個(gè)離散整數(shù)優(yōu)化問(wèn)題，并以差分進(jìn)化算法為搜索引擎，設(shè)計(jì)了一種進(jìn)化社團(tuán)檢測(cè)算法DECEILAR。在一系列合成網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)上驗(yàn)證了該算法的性能，并與以遺傳算法為搜索引擎、采用線性組表示或局部鄰接表示進(jìn)化個(gè)體的進(jìn)化社團(tuán)檢測(cè)算法進(jìn)行了對(duì)比。實(shí)驗(yàn)結(jié)果表明，應(yīng)用進(jìn)化算法求解社團(tuán)檢測(cè)問(wèn)題時(shí)，局部鄰接表示法及其改進(jìn)比線性組表示法更適合于進(jìn)化個(gè)體的表示，差分進(jìn)化比遺傳算法的搜索性能更好（在網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)較為清晰時(shí)）。

參考文獻(xiàn)（References）

[1] Han Liu，F(xiàn)an Yang，Ding Liu.Genetic algorithm optimizing modularity for community detection in complex networks[C].Proceedings of the 35th Chinese Control Conference，2016：1252-1256.

[2] Clara Pizzuti.A multiobjective genetic algorithm to find communities in complex networks[J].IEEE Transactions on Evolutionary Computation，2012，16（3）：418-430.

[3] Zhang Xiaohong，Zhang Bin，Zhang Changsheng，et al.A multi-objective hybrid genetic algorithm for detecting communities in complex networks[C].2016 12th International Conference on Natural Computation，F(xiàn)uzzy Systems and Knowledge Discovery，2016：691-695.

[4] Mursel Tasgin，Haluk Bingol.Community detection in complex networks using genetic algorithm[EB/OL].https：//arxiv.org/abs/1509.00556，2017-11-02.

[5] Clara Pizzuti.Boosting the detection of modular community structure with genetic algorithms and local search[C].The 27th Annual ACM Symposium on Applied Computing，2012：226-231.

[6] G. Jia，Z.Cai，M.Musolesi，et al.Community detection in social and biological networks using differential evolution[C].The 6th International Conference on Learning and Intelligent Optimization，2012：71-85.

[7] Wang Guoshun，Zhang Xuan，Jia Guanbo，et al.Application of Algorithm used in Community Detection of Complex Network[J].International Journal of Future Generation Communication and Networking，2013，6（4）：219-229.

[8] Leal Thiago P，Gonalves Amanda C A，Vieira Vinícius Da F，et al.Decode—differential evolution algorithm for community detection[C].2013 IEEE International Conference on Systems，Man，and Cybernetics（SMC），2013，13-16：4635-4640.

[9] Das Swagatam，Suganthan Ponnuthurai Nagaratnam.Differential evolution：A survey of the state-of-the-art[J].IEEE Transactions on Evolutionary Computation，2011，15（1）：4-31.

[10] Y J Park，M S Song.A genetic algorithm for clustering problems[C].Proceeding of the 3rd Annual Conference Genetic Algorithms，1989：2-9.

[11] Newman M.E.J.，Girvan M.Finding and evaluating community structure in networks[J].Physical review E，2004，69（22）：1-15.

[12] Leon Danon，Jordi Duch，Albert Diaz-Guilera，et al.Comparing community structure identification[J].Journal of Statistical Mechanics：Theory and Experiment，2005（9）：P09008.

[13] Lancichinetti Andrea，F(xiàn)ortunato Santo，adicchi Filippo.Benchmark graphs for testing community detection algorithms[J].Physical Review E，2008，78（4）：046110.

[14] David Lusseau，Karsten Schneider，Oliver J.Boisseau，et al.The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations[J].Behavioral Ecology and Sociobiology，2003，54（4）：396-405.

[15] Tim S Evans.Clique graphs and overlapping communities[J].Journal of Statistical Mechanics Theory & Experiment，2010（12）：257-265.

[16] Duch Jordi，Arenas Alex.Community detection in complex networks using extremal optimization[J].Physical Review E，2005，72（2）：027104.

作者簡(jiǎn)介：

孫韓林（1980-），男，博士，副教授.研究領(lǐng)域：復(fù)雜網(wǎng)絡(luò)，大數(shù)據(jù)分析.

馬素剛（1981-），男，碩士，高級(jí)工程師.研究領(lǐng)域：圖像處理.

王忠民（1967-），男，博士，教授.研究領(lǐng)域：大數(shù)據(jù)分析與應(yīng)用，嵌入式系統(tǒng)，機(jī)器人技術(shù).endprint