孫韓林　馬素剛　王忠民

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

關鍵詞：社團檢測；社團結構分析；差分進化；復雜網絡

中圖分類號：TP311 文獻標識碼：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）

社團是復雜網絡中一組節(jié)點的集合，組內節(jié)點具有共同的屬性或在網絡中具有相似的功能，拓撲結構上表現為組內節(jié)點間具有更緊密（更多）的連接邊，而組內成員與網絡其余節(jié)點的連接邊相對稀疏。社團結構從中觀（middle-scope level）層次上揭示了網絡的結構特性，對理解網絡性質具有重要意義。

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

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

2 進化個體表示（Evolutionary individual

representation）

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

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

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

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

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

3 算法描述（Algorithm description）

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

3.1 初始化

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

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

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

3.2 差分變異

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

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

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

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

3.3 交叉

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

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

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

3.4 選擇及優(yōu)化目標函數

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

其中是優(yōu)化目標函數。注意當試驗向量的目標函數值與目標向量的目標函數值相等時，差分進化算法也用試驗向量取代目標向量。

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

3.5 算法框架

基于差分進化的社團檢測算法DECDILAR的框架如下：

4 實驗結果及分析（Experiment results and analysis）

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

4.1 實驗設置

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

對每一個測試的網絡，所有算法都執(zhí)行10次；對每次運行所發(fā)現的社團結構計算模塊度或歸一化互信息，最后計算10次運行結果的平均值及標準差。

4.2 合成網絡實驗結果及分析

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

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

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

4.3 真實網絡實驗結果及分析

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

表2中也給出了寬吻海豚網絡和美國學院足球比賽網絡的真實網絡社團結構的模塊度值。可以看到，三種算法檢測到的社團結構的模塊度值均比真實模塊度值大，尤其是寬吻海豚網絡。表2也給出了各算法發(fā)現的社團的數量，可以看到，對寬吻海豚網絡，三種算法發(fā)現的社團數量比真實社團數量（2個）更多，平均接近5個，表明算法發(fā)現的社團結構更為精細；而對美國學院足球比賽網絡，盡管算法發(fā)現的社團數量小于真實社團數量（19個），但真實社團結構中包含有8個只有1個成員節(jié)點的社團，主要社團的數量（11個）與算法發(fā)現的社團數量相當（平均接近10個）。模塊度表明算法發(fā)現的社團結構質量更好。

圖2是DECDILAR檢測到的一種寬吻海豚網絡的社團結構，其中不同的節(jié)點形狀表示真實的社團，不同形狀及填充顏色表示算法發(fā)現的社團?？梢钥吹?，算法共發(fā)現了5個社團，其中社團1、3、4、5節(jié)點形狀相同，它們合并后就是一個真實的社團，即算法發(fā)現的社團結構更為精細。表3是DECDILAR算法檢測到的一種美國學院足球網絡的社團結構及其與真實社團結構的對應關系（由于該網絡的節(jié)點數較多，我們通過列表方式給出它的社團結構）?？梢姡惴ㄕ_發(fā)現了6個真實社團（社團2、3、4、5、9及10）；發(fā)現的社團1是兩個真實社團（BigWest和MountainWest）的合并；3個社團（社團6、7及8）與8個只包含1個成員的社團混合在了一起。endprint

綜上所述，DECDILAR是一種有效的社團檢測算法。

5 結論（Conclusion）

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

參考文獻（References）

[1] Han Liu，Fan 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，Fuzzy 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，Fortunato 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-），男，博士，副教授.研究領域：復雜網絡，大數據分析.

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

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