基于蟻群優(yōu)化的多目標(biāo)社區(qū)檢測算法

楊楠呂紅娟++陳婷

摘要：蟻群優(yōu)化算法作為單目標(biāo)優(yōu)化問題，由于只有一個目標(biāo)函數(shù)，通常會將解限制到特定的范圍內(nèi)。當(dāng)優(yōu)化的目標(biāo)不恰當(dāng)時，算法可能失效，比如分辨率限制問題。我們將多目標(biāo)優(yōu)化的思想與傳統(tǒng)的用于社區(qū)檢測的蟻群優(yōu)化算法相結(jié)合，增加了目標(biāo)函數(shù)個數(shù)，即增加了解的評價指標(biāo)數(shù)目。該算法引入多目標(biāo)策略，提出多目標(biāo)ACO算法，該算法在一次運(yùn)行過程中會產(chǎn)生一組Pareto最優(yōu)解。并在三個真實(shí)世界網(wǎng)絡(luò)證明該算法的有效性和準(zhǔn)確性。

關(guān)鍵詞：復(fù)雜網(wǎng)絡(luò)；社區(qū)檢測；蟻群優(yōu)化算法；多目標(biāo)優(yōu)化

中圖分類號：TP18文獻(xiàn)標(biāo)識碼：A

1引言

1991年意大利學(xué)者Dorigo M等人首次提出了蟻群優(yōu)化算法[1，2]引起了學(xué)者的廣泛關(guān)注與研究。蟻群算法是一種基于種群的啟發(fā)式仿生進(jìn)化系統(tǒng)，該算法采用了正反饋分布式并行計算機(jī)制，易于與其它方法相結(jié)合并且具有較強(qiáng)的魯棒性。

本文介紹了一種基于蟻群優(yōu)化的多目標(biāo)社區(qū)檢測方法，將蟻群優(yōu)化算法與多目標(biāo)策略[3]相結(jié)合，是一種優(yōu)化模塊度的社區(qū)檢測方法。對于多目標(biāo)優(yōu)化問題，通常無法得到最優(yōu)解，若同時考慮多個目標(biāo)函數(shù)則算法將會得到一組優(yōu)于其它解的最優(yōu)解集。該集合叫做帕雷托（Pareto）解集或者非支配解集。

2基于蟻群優(yōu)化的多目標(biāo)社區(qū)檢測

蟻群優(yōu)化算法（ACO），是一種基于螞蟻覓食行為的啟發(fā)式方法，用來解決困難的組合優(yōu)化問題，并且已經(jīng)成功的應(yīng)用到了各種棘手的問題，像二次分配問題（QAP），車輛路徑問題（VRP）等。在1996年，Gambardella等人提出了一種修正的蟻群優(yōu)化算法——蟻群系統(tǒng)（Ant System，AS），已經(jīng)成功地應(yīng)用在旅行商問題上。在這之后，科學(xué)家們也發(fā)明了一些改進(jìn)的算法，比如精英蟻群系統(tǒng)（Elitist Ant System，EAS），最大最小蟻群系統(tǒng)（MaxMin Ant System，MMAS）以及排序蟻群系統(tǒng)（RankBased Ant System，ASrank）。

運(yùn)用蟻群優(yōu)化來做社區(qū)檢測，首先需要指出如何表達(dá)一個解，其次就是如何構(gòu)建一個解，然后就是信息素的初始化以及更新。下面我們將詳細(xì)描述該算法。

2.1編碼方式

社區(qū)就是復(fù)雜網(wǎng)絡(luò)的子圖，因而檢測社區(qū)結(jié)構(gòu)就等價于找出能揭示網(wǎng)絡(luò)最好分割的一組子圖。因此，社區(qū)檢測問題的解可以明確地表示為：一個n個元素的向量表示圖，其連通分量相當(dāng)于社區(qū)。向量的元素和索引對應(yīng)于圖G=（V，A）中的節(jié)點(diǎn)。例如，向量中第i個元素等于j，即節(jié)點(diǎn)Vi和Vj之間有邊相連，也就是說這兩個節(jié)點(diǎn)在同一個連通分量里面，即處于同一個社區(qū)。

該編碼框架的優(yōu)點(diǎn)有很多，最重要的是不需要預(yù)先知道復(fù)雜網(wǎng)絡(luò)的社區(qū)劃分?jǐn)?shù)目。解碼的過程需要找出所有的連通分量。所有屬于同一個連通分量的節(jié)點(diǎn)被劃分到一個社區(qū)，解碼過程是有必要的且可以通過廣度優(yōu)先搜索（breadthfirst search，BFS）或者深度優(yōu)先搜索（depthfirst search，DFS）在線性時間內(nèi)完成。解碼完成后，會得到一個表示每個節(jié)點(diǎn)歸屬的向量。這種基于基因近鄰的編碼框架已經(jīng)應(yīng)用到了多目標(biāo)聚類領(lǐng)域。該框架在社區(qū)檢測的應(yīng)用中有幾個主要的優(yōu)點(diǎn)，最重要的是，不需要預(yù)先知道社區(qū)的真實(shí)劃分?jǐn)?shù)目K，因為在解碼過程中能夠自動地得到K的取值。

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

本節(jié)將MOACO算法應(yīng)用在三個真實(shí)世界網(wǎng)絡(luò)上，分別是Zacharys Karate Club、Bottlenose Dolphins、Books about US politics。以上復(fù)雜網(wǎng)絡(luò)是社會網(wǎng)絡(luò)分析領(lǐng)域中的經(jīng)典數(shù)據(jù)集，將這些數(shù)據(jù)在并與沒有加入多目標(biāo)策略的ACO算法以及GA、GAloacal算法進(jìn)行了對比。由表2可以看出，三十次獨(dú)立運(yùn)行后，在Zacharys Karate Club網(wǎng)絡(luò)中，ACO和MOACO的平均模塊度值均不如GA和GA-local算法的結(jié)果好，而MOACO和ACO的平均模塊度相差不大；在Dolphin social network網(wǎng)絡(luò)中，本文提出的MOACO算法的平均NMI值明顯好于其它算法。在Dolphin social network網(wǎng)絡(luò)中，MOACO算法的模塊度Q平均值與ACO算法的結(jié)果相差不大，而NMI的平均值要好于ACO算法。

為了驗證蟻群規(guī)模和迭代次數(shù)對算法的影響，以Zacharys Karate Club網(wǎng)絡(luò)為例進(jìn)行參數(shù)分析，參數(shù)α、β、T、ρ、ε的值不變化，算法獨(dú)立運(yùn)行三十次求平均模塊度值Q和平均NMI值，討論蟻群規(guī)模N對算法結(jié)果的影響。

由表3可以看出，隨著蟻群規(guī)模的增加，平均模塊度值呈增長趨勢，在蟻群規(guī)模為80時，達(dá)到了最大值。而由于蟻群優(yōu)化算法中螞蟻個體選擇路徑是隨機(jī)的，因而平均NMI值沒有呈現(xiàn)一定的規(guī)律，而當(dāng)蟻群規(guī)模為40時，平均NMI值取得最大值。

表4表示參數(shù)α、β、N、ρ、ε保持不變，討論迭代次數(shù)T對算法結(jié)果的影響，算法獨(dú)立運(yùn)行三十次的算法結(jié)果如表4所示。

由表4可知，迭代次數(shù)對算法的平均模塊度值影響不大，而當(dāng)?shù)螖?shù)為150次的時候，平均NMI值取得了最大值。

圖2表示調(diào)節(jié)參數(shù)過程中，算法取得的最優(yōu)結(jié)果，即每一次運(yùn)行的模塊度值和NMI值，data1表示平均模塊度值，data2表示平均NMI值。最優(yōu)參數(shù)為：迭代次數(shù)150次，種群規(guī)模40。可以看出模塊度值非常穩(wěn)定。

3.2計算機(jī)仿真網(wǎng)絡(luò)

本節(jié)使用經(jīng)典的GN benchmark復(fù)雜網(wǎng)絡(luò)來檢測算法的可行性和有效性。GN基準(zhǔn)網(wǎng)絡(luò)是由Newman等提出。對于該基準(zhǔn)網(wǎng)絡(luò)，每個圖包含了128個節(jié)點(diǎn)，分為4個由32個節(jié)點(diǎn)構(gòu)成的社區(qū)。每個節(jié)點(diǎn)平均有Zin條邊與同社區(qū)內(nèi)節(jié)點(diǎn)連接，Zout條邊與社區(qū)外節(jié)點(diǎn)連接。其中Zin+Zout = 16，作為每個節(jié)點(diǎn)的期望的度。隨著Zout的增大，所產(chǎn)生的隨機(jī)網(wǎng)絡(luò)給社區(qū)檢測算法帶來了更大的挑戰(zhàn)。特別是當(dāng)Zout大于8時，意味著每個節(jié)點(diǎn)在社區(qū)內(nèi)的邊都要小于社區(qū)外的邊，這時網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)就會非常模糊。當(dāng)Zout≤ 8時，節(jié)點(diǎn)外度所占的比例小于內(nèi)度所占的比例，因此算法應(yīng)該能檢測出網(wǎng)絡(luò)中存在的社區(qū)結(jié)構(gòu)，當(dāng)Zout = 0時，表明節(jié)點(diǎn)的外度為0，此時節(jié)點(diǎn)僅與自身社區(qū)內(nèi)的節(jié)點(diǎn)相連接，社區(qū)結(jié)構(gòu)非常明顯。分別對Zout從0到2進(jìn)行了測試，對每種類型的網(wǎng)絡(luò)產(chǎn)生一個復(fù)雜網(wǎng)絡(luò)，使用NMI來衡量算法檢測的結(jié)果和真實(shí)網(wǎng)絡(luò)劃分之間的相似性。對于每個網(wǎng)絡(luò)，計算三十次獨(dú)立運(yùn)行的平均值。

由表5可以看出，當(dāng)GN網(wǎng)絡(luò)的外度為0時，該算法可以準(zhǔn)確地檢測出網(wǎng)絡(luò)劃分情況；當(dāng)GN網(wǎng)絡(luò)的外度為1和2的時候，該算法得到的結(jié)果也還都是有效的。

但是，在蟻群優(yōu)化方法中，其算法復(fù)雜度比較高，所需要的搜索時間很長，而且容易出現(xiàn)所有的螞蟻所對應(yīng)的解完全相同這種“停滯現(xiàn)象”。導(dǎo)致了當(dāng)復(fù)雜網(wǎng)絡(luò)的社區(qū)數(shù)目較大時，算法不能產(chǎn)生有效解。另外，該算法對計算機(jī)生成的仿真網(wǎng)絡(luò)不能得到有效的結(jié)果，這是我們進(jìn)一步研究的內(nèi)容。

4小結(jié)

基于傳統(tǒng)的蟻群優(yōu)化算法（ACO）算法的缺陷，提出了一種用于復(fù)雜網(wǎng)絡(luò)社區(qū)檢測的多目標(biāo)蟻群優(yōu)化算法MOACO，該算法將繼續(xù)沿用傳統(tǒng)的基于模塊度優(yōu)化的策略，加入了多目標(biāo)的思想，每次迭代過程中，根據(jù)兩個目標(biāo)函數(shù)的不同折中，最終得到Pareto解集，選取每一代中優(yōu)先級最高的那一組解。在三個真實(shí)世界網(wǎng)絡(luò)和GN網(wǎng)絡(luò)中的外度較小的網(wǎng)絡(luò)上證明了算法的有效性，并將提出算法與ACO算法進(jìn)行了比較，NMI平均值要優(yōu)于ACO算法，模塊度Q的平均值與ACO算法相當(dāng)。缺點(diǎn)是不能處理社區(qū)劃分類別多的復(fù)雜網(wǎng)絡(luò)，對于結(jié)構(gòu)模糊的GN網(wǎng)絡(luò)，算法的效果不明顯。

參考文獻(xiàn)

[1]HONGHAO C， ZUREN F， ZHIGANG R. Community detection using ant colony optimization [C] Evolutionary Computation （CEC）， 2013 IEEE Congress on. IEEE， 2013： 3072-3078.

[2]DORIGO M，BIRATTARI M，STUTZLE T. Ant colony optimization[J]. Computational Intelligence Magazine， IEEE， 2006， 1（4）： 28-39.

[3]SOLNON C， Ghédira K. Ant colony optimization for multi-objective optimization problems[J]. Internation Journal on computer science， 2010.

[4]GONG M， CAI Q，CHEN X， et al. Complex network clustering by multiobjective discrete particle swarm optimization based on decomposition[J]. Evolutionary Computation， IEEE Transactions on， 2014， 18（1）： 82-97.

[5]SRINIVAS N，DEB K. Muiltiobjective optimization using nondominated sorting in genetic algorithms[J]. Evolutionary computation， 1994， 2（3）： 221-248.