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

孫韓林　馬素剛　王忠民

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

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

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：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é)點的集合，組內(nèi)節(jié)點具有共同的屬性或在網(wǎng)絡(luò)中具有相似的功能，拓?fù)浣Y(jié)構(gòu)上表現(xiàn)為組內(nèi)節(jié)點間具有更緊密（更多）的連接邊，而組內(nèi)成員與網(wǎng)絡(luò)其余節(jié)點的連接邊相對稀疏。社團(tuán)結(jié)構(gòu)從中觀（middle-scope level）層次上揭示了網(wǎng)絡(luò)的結(jié)構(gòu)特性，對理解網(wǎng)絡(luò)性質(zhì)具有重要意義。

社團(tuán)結(jié)構(gòu)檢測可抽象為一個優(yōu)化問題，利用進(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)檢測的主要優(yōu)點是不需要事先知道社團(tuán)結(jié)構(gòu)的屬性（例如社團(tuán)的數(shù)量）。常用于社團(tuán)檢測的進(jìn)化算法有遺傳算法[1-5]（Genetic Algorithm，GA）和差分進(jìn)化[6-8]（Differential Evolution，DE）算法。

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

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

representation）

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

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

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

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

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

3 算法描述（Algorithm description）

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

3.1 初始化

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

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

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

3.2 差分變異

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

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

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

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

3.3 交叉

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

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

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

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

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

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

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

3.5 算法框架

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

4 實驗結(jié)果及分析（Experiment results and analysis）

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

4.1 實驗設(shè)置

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

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

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

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

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

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

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

真實網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)特性可能比合成網(wǎng)絡(luò)更為復(fù)雜。我們也用三個真實的網(wǎng)絡(luò)上測試了三種算法。這些網(wǎng)絡(luò)分別是：寬吻海豚網(wǎng)絡(luò)（bottlenose dolphins network）[14]，共有62個節(jié)點、159條邊；美國學(xué)院足球比賽網(wǎng)絡(luò)（American college football network）[15]，共有115個節(jié)點、616條邊；新陳代謝網(wǎng)絡(luò)（metabolic network）[16]，共有453個節(jié)點、2025條邊。其中寬吻海豚網(wǎng)絡(luò)和美國學(xué)院足球比賽網(wǎng)絡(luò)的真實社團(tuán)結(jié)構(gòu)已知（由人手工建立），分別包含兩個和19個社團(tuán)。對這三個網(wǎng)絡(luò)各算法10次運行結(jié)果的平均模塊度及平均歸一化互信息如表2所示（新陳代謝網(wǎng)絡(luò)的真實社團(tuán)結(jié)構(gòu)未知，因而無法計算其歸一化互信息值）。從表中可以看出，結(jié)果與合成網(wǎng)絡(luò)類似：兩種基于局部鄰接個體表示及其改進(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ò)和美國學(xué)院足球比賽網(wǎng)絡(luò)的真實網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的模塊度值?？梢钥吹?，三種算法檢測到的社團(tuán)結(jié)構(gòu)的模塊度值均比真實模塊度值大，尤其是寬吻海豚網(wǎng)絡(luò)。表2也給出了各算法發(fā)現(xiàn)的社團(tuán)的數(shù)量，可以看到，對寬吻海豚網(wǎng)絡(luò)，三種算法發(fā)現(xiàn)的社團(tuán)數(shù)量比真實社團(tuán)數(shù)量（2個）更多，平均接近5個，表明算法發(fā)現(xiàn)的社團(tuán)結(jié)構(gòu)更為精細(xì)；而對美國學(xué)院足球比賽網(wǎng)絡(luò)，盡管算法發(fā)現(xiàn)的社團(tuán)數(shù)量小于真實社團(tuán)數(shù)量（19個），但真實社團(tuán)結(jié)構(gòu)中包含有8個只有1個成員節(jié)點的社團(tuán)，主要社團(tuán)的數(shù)量（11個）與算法發(fā)現(xiàn)的社團(tuán)數(shù)量相當(dāng)（平均接近10個）。模塊度表明算法發(fā)現(xiàn)的社團(tuán)結(jié)構(gòu)質(zhì)量更好。

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

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

5 結(jié)論（Conclusion）

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

參考文獻(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.

作者簡介：

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

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

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