自適應(yīng)進化蝙蝠算法下的復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)

唐朝偉，李彥，段青言，楊險峰，胡佩，陳冠豪

?

自適應(yīng)進化蝙蝠算法下的復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)

唐朝偉，李彥，段青言，楊險峰，胡佩，陳冠豪

(重慶大學(xué)通信工程學(xué)院，重慶，400030)

針對現(xiàn)有智能優(yōu)化算法解決復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)問題存在求解適應(yīng)度函數(shù)精度低、算法收斂速度慢等不足，在基本蝙蝠算法框架下，結(jié)合遺傳算法的思想，提出一種自適應(yīng)進化蝙蝠算法。首先，算法以模塊度函數(shù)作為適應(yīng)度函數(shù)，采用基于字符的編碼方式，利用標(biāo)簽傳播方法初始化種群；然后，將蝙蝠個體的速度轉(zhuǎn)化為變異概率，使用交叉變異算子更新位置，從而實現(xiàn)蝙蝠的自適應(yīng)進化；最后，在計算機生成網(wǎng)絡(luò)和真實網(wǎng)絡(luò)環(huán)境下進行仿真實驗。研究結(jié)果表明：與用于社區(qū)發(fā)現(xiàn)的其他智能算法相比，該算法具有收斂速度快、求解精度高的優(yōu)點，更適合大規(guī)模網(wǎng)絡(luò)下的社區(qū)發(fā)現(xiàn)。

復(fù)雜網(wǎng)絡(luò)；社區(qū)發(fā)現(xiàn)；模塊度；蝙蝠算法；自適應(yīng)進化

復(fù)雜系統(tǒng)可以建模成復(fù)雜網(wǎng)絡(luò)進行分析，社區(qū)可以視為系統(tǒng)中具有某些特定屬性或功能的子系統(tǒng)。很多復(fù)雜網(wǎng)絡(luò)都存在社區(qū)結(jié)構(gòu)，研究復(fù)雜網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)有著重要的理論意義。首先，通過社區(qū)結(jié)構(gòu)，可挖掘節(jié)點群體的共同特征和屬性，有助于分析整體與部分的關(guān)系；再者，在基于現(xiàn)有網(wǎng)絡(luò)信息的基礎(chǔ)上可預(yù)測相似節(jié)點的功能，節(jié)點之間潛在的連接可能性[1]；最后，可以探索社區(qū)結(jié)構(gòu)對網(wǎng)絡(luò)傳播、同步、穩(wěn)定性等動力學(xué)特性的影響[2]，且根據(jù)社區(qū)劃分出的網(wǎng)絡(luò)結(jié)構(gòu)更清晰，可視化效果更直觀。社區(qū)發(fā)現(xiàn)的目的是挖掘網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)，社區(qū)發(fā)現(xiàn)的研究思路層出不窮，算法原理和性能指標(biāo)各有差異，從算法求解策略的角度出發(fā)，社區(qū)發(fā)現(xiàn)的算法大體分為基于圖分割的算 法[3?4]、聚類算法[5?8]、基于網(wǎng)絡(luò)動力學(xué)特性的算 法[9?11]和基于目標(biāo)函數(shù)的優(yōu)化算法[12?16]等。其中，基于模塊度函數(shù)(Modularity)的優(yōu)化算法是目前較為普遍的算法之一。模塊度函數(shù)(用表示)是NEWMAN與GIRVAN提出的定量評價社區(qū)結(jié)構(gòu)優(yōu)劣的度量指標(biāo)[5]，從而將復(fù)雜網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)問題轉(zhuǎn)化為模塊度函數(shù)的優(yōu)化問題，越大，網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)越明顯。模塊度函數(shù)的優(yōu)化是一個NP-complete問題，相比于傳統(tǒng)優(yōu)化算法，智能優(yōu)化算法對目標(biāo)函數(shù)的要求更為寬松，可以在有限的時間內(nèi)找到較好的解，因此研究者們更傾向于利用智能優(yōu)化算法解決社區(qū)發(fā)現(xiàn)問題。GUIMERA等[14]于2005年提出基于模擬退火的模塊度優(yōu)化算法，該算法有良好的聚類效果，但運行效率低下，需做進一步研究；TASGIN[15]針對社區(qū)發(fā)現(xiàn)問題提出單路交叉算子，將遺傳算法應(yīng)用于本領(lǐng)域；LI等[17]使用基于二進制矩陣編碼的遺傳算法，雖然這種編碼便于進行交叉操作，但是編解碼復(fù)雜，算法時間復(fù)雜度為(3)，且需要進行編碼修正；張英杰等[18]在離散差分進化算法中加入免疫克隆算子，提高了算法的局部開發(fā)能力，增加了算法的魯棒性；ZHOU 等[19]提出一種離散粒子群算法，對速度更新重新定義并應(yīng)用在符號網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)。模塊度函數(shù)存在分辨率受限的問題，即在大規(guī)模網(wǎng)絡(luò)中存在較小社區(qū)的情況下這類方法的效果不佳。冷作福[20]使用surprise函數(shù)作為社區(qū)評價指標(biāo)，并提出一種基于貪婪思想的局部優(yōu)化surprise函數(shù)的社區(qū)發(fā)現(xiàn)算法。上述智能算法均可以解決復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)問題，基本思路為：根據(jù)求解問題選擇適應(yīng)度函數(shù)和編碼方式，設(shè)置算法參數(shù)，最后采用不同的尋優(yōu)算子不斷逼近最優(yōu)解。然而，在算法求解精度和運行效率方面還有提升空間。2010年由YANG[21]提出一種新型群智能優(yōu)化算法——蝙蝠算法，對比遺傳算法，粒子群算法等，該算法具有計算量小，收斂速度快的特點。本文作者在蝙蝠算法的框架下，結(jié)合遺傳算法，提出自適應(yīng)進化蝙蝠算法，將其應(yīng)用于復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)領(lǐng)域。首先，使用基于字符的編碼方式，采用標(biāo)簽傳播的方式初始化；然后，將蝙蝠算法中的速度轉(zhuǎn)換為變異概率，利用交叉變異算子更新蝙蝠位置，均衡全局搜索和局部開發(fā)能力，并且實現(xiàn)蝙蝠的自適應(yīng)進化。

1 蝙蝠算法

1.1 蝙蝠算法的仿生學(xué)原理

蝙蝠算法(bat algorithm，BA)模擬蝙蝠在黑暗環(huán)境中捕食行為特征，以微蝙蝠的回聲定位特性為基礎(chǔ)，根據(jù)發(fā)射超聲波的脈沖頻率進行指向性飛行。在搜索過程中，發(fā)射脈沖的頻數(shù)較低而響度大，隨著目標(biāo)范圍的縮小，蝙蝠會增加發(fā)射脈沖的頻數(shù)，從而增加獲取目標(biāo)的信息量，最終精確定位到目標(biāo)所在位置。

1.2 BA數(shù)學(xué)模型

1.2.1 蝙蝠的運動

蝙蝠算法包含3個要素，即搜索脈沖頻率、發(fā)射脈沖響度和頻數(shù)。蝙蝠算法中蝙蝠是種群中的個體，同時對應(yīng)解空間中的一個解。在第次迭代中，蝙蝠搜尋獵物時使用的頻率為

在局部搜索部分，蝙蝠個體的位置是隨機游走在當(dāng)前種群最優(yōu)解周圍，更新如下：

1.2.2 發(fā)射脈沖和響度

蝙蝠算法的局部搜索能力依賴于響度和脈沖頻數(shù)。一旦蝙蝠發(fā)現(xiàn)獵物，發(fā)射脈沖信號的響度就會減弱，但頻數(shù)則會逐漸增大。蝙蝠的脈沖頻數(shù)和響度更新公式如下：

綜上所述，蝙蝠算法步驟如下。

4) 生成隨機數(shù)1，若1＞r，則使用最優(yōu)蝙蝠的位置隨機擾動式(4)代替當(dāng)前個體位置；

6) 判斷算法是否達到終止條件，若未達到，則重復(fù)步驟2)~6)。

2 自適應(yīng)進化蝙蝠算法

本文對原始蝙蝠算法進行改進，提出自適應(yīng)進化蝙蝠算法(self-adaptive evolution bat algorithm，SEBA)用于解決社區(qū)發(fā)現(xiàn)問題。下面將介紹利用改進的蝙蝠算法求解復(fù)雜網(wǎng)絡(luò)中的社區(qū)發(fā)現(xiàn)問題。

2.1 適應(yīng)度函數(shù)

模塊度函數(shù)具有求解簡單，易于理解的特點，因此，SEBA采用模塊度函數(shù)作為適應(yīng)度函數(shù)，其數(shù)學(xué)表達式如下：

2.2 編碼方式與初始化

SEBA采用基于字符的編碼方式，這種編碼簡單明了，易于操作?；谧址木幋a是用蝙蝠的空間位置直接表示對應(yīng)節(jié)點的社區(qū)編號，這是一種最傳統(tǒng)也是最直觀有效的編碼方式?；谧址木幗獯a過程如圖1所示，圖1(a)所示為網(wǎng)絡(luò)拓撲圖，假設(shè)網(wǎng)絡(luò)中節(jié)點的編碼(Code)如圖1(b)所示，因為位置維度索引(Index)1，4，5和7的編碼都是1，所以它們同屬一個社區(qū)，如圖1(c)中紅色節(jié)點所示。同理可得節(jié)點2，3和6是一個社區(qū)。

(a) 網(wǎng)絡(luò)示意圖；(b) 基于字符的編碼； (c) 網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)示意圖

好的初始化策略不僅可以減小搜索空間，縮短算法運行時間，還能保證種群的多樣性。因此，本文采用標(biāo)簽傳播的方法初始化種群[16]。

2.3 更新操作

2.3.1 速度更新

2.3.2 位置更新

本文將遺傳算法中的交叉算子和變異算子引入到SEBA中，交叉算子用于提升探索能力，變異算子用于局部開發(fā)，通過交叉變異運算更新蝙蝠的位置。

1) 交叉算子。首先，傳統(tǒng)的交叉算子如單點交叉、多點交叉、均勻交叉只關(guān)注基因本身，因此忽略了基因之間的相互關(guān)系。再者，本文算法采用基于字符的編碼方式，每一個基因表示節(jié)點所在社區(qū)標(biāo)號，也就是說這些基因之間是存在聯(lián)系的，一旦隨意交換基因，就會割裂基因之間的關(guān)系，改變社區(qū)結(jié)構(gòu)，最終使得求解的適應(yīng)度函數(shù)變小，導(dǎo)致尋優(yōu)過程倒退。因此，傳統(tǒng)的交叉算法不能應(yīng)用于本文算法中。

針對上述問題，本文在TASGIN等[15]提出單路交叉的基礎(chǔ)上使用雙路交叉算子。具體的策略如下：隨機選擇2個染色體，分別作為交叉的源染色體和目標(biāo)染色體。然后隨機從源染色體選擇1個節(jié)點，獲取其所在社區(qū)成員和社區(qū)標(biāo)號，接著在目標(biāo)染色體中尋找中的成員，并將其社區(qū)標(biāo)號改為。單路交叉可以形象地比作一種社區(qū)集體搬遷的行為，加入到新環(huán)境后社區(qū)成員之間的聯(lián)系依然存在，雙路交叉不僅保持這種社區(qū)關(guān)系，而且增加了種群多樣性，擴寬了蝙蝠尋優(yōu)搜索范圍。雙路交叉的操作如表1，假設(shè)存在2個染色體A和B，隨機選擇某節(jié)點4，取源染色體A中節(jié)點4的社區(qū)標(biāo)號(=4)，找出其所在社區(qū)的其他節(jié)點(節(jié)點3)，將染色體B中的對應(yīng)節(jié)點(節(jié)點3，節(jié)點4)的社區(qū)標(biāo)號改為，從而生成新染色體C1交換源染色體和目標(biāo)染色體，相同操作生成新染色體C2，根據(jù)模塊度選擇C1或者C2作為雙路交叉的最終結(jié)果。

變異算子的具體操作步驟流程如下。

④ 選擇對局部函數(shù)貢獻度大的標(biāo)簽作為第維的標(biāo)簽值。更新公式見式(10)~(12)。

表1 雙路交叉示意說明

2.3.3 隨機擾動

(a) 網(wǎng)絡(luò)示意圖；(b) 隨機擾動示意圖

2.4 算法流程圖

綜上所述，自適應(yīng)進化蝙蝠算法的流程如圖3 所示。

2.5 時間復(fù)雜度分析

3 實驗與分析

為了驗證自適應(yīng)進化蝙蝠算法的性能，選擇計算機合成網(wǎng)絡(luò)和7種現(xiàn)實網(wǎng)絡(luò)兩類實驗環(huán)境，并與免疫離散差分進化(IDDE)算法[18]和改進的遺傳算法(IGA)[23]進行對比實驗測試。實驗均在Inter(R) Core(TM) i7?3770處理器，主頻3.4 GHz，內(nèi)存4 G，操作系統(tǒng)Windows 7的臺式機下運行。

圖3 SEBA流程圖

3.1 計算機合成網(wǎng)絡(luò)測試

計算NM首先需要定義混淆矩陣，矩陣行號代表參考社區(qū)結(jié)構(gòu)，列號代表算法實驗發(fā)現(xiàn)社區(qū)結(jié)構(gòu)，p表示劃分在標(biāo)準(zhǔn)社區(qū)和發(fā)現(xiàn)社區(qū)中共同存在的節(jié)點數(shù)。NM取值范圍是[0,1]，NM越大，表明算法劃分的結(jié)果越接近參考網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)，表示為

SEBA快速收斂特性分析：蝙蝠算法更新速度選擇的參照標(biāo)準(zhǔn)為當(dāng)前最佳蝙蝠位置，所以蝙蝠位置更易接近極值點；雙路交叉算子起全局搜索作用，變異算子進行局部開發(fā)，保證算法求解精度；蝙蝠位置的更新有一部分依靠當(dāng)前最佳位置隨機擾動產(chǎn)生，即每只蝙蝠都在最佳位置附近飛行，因此壓縮了搜索空間，更易找到最優(yōu)解或次優(yōu)解。隨著計算機和信息技術(shù)的迅猛發(fā)展和普及應(yīng)用，網(wǎng)絡(luò)規(guī)模呈爆炸性增加，SEBA在保證一定求解精度的同時能夠快速收斂，比其他對比算法更加具有應(yīng)用優(yōu)勢。

1—SEBA；2—IGA；3—IDDE。

3.2 真實網(wǎng)絡(luò)數(shù)據(jù)集

本文選用Karate，Dolphin，Book，F(xiàn)ootball，Jazz，E-mail以及Science共7個真實網(wǎng)絡(luò)數(shù)據(jù)集進行仿真實驗，其中Karate，Dolphin，Book，F(xiàn)ootball和Jazz網(wǎng)絡(luò)規(guī)模較小，具體描述見表2。

表2 真實網(wǎng)絡(luò)數(shù)據(jù)集信息

各算法適應(yīng)度隨迭代次數(shù)變化如圖5所示。從圖5可知：當(dāng)網(wǎng)絡(luò)規(guī)模較小時(Karate，Dolphin，Book，F(xiàn)ootball和Jazz)，本文SEBA與對比算法求解的相當(dāng)，但是收斂速度要比其他算法的快，如圖5中曲線1所示。當(dāng)網(wǎng)絡(luò)規(guī)模增大時(如E-mail和Science)，自適應(yīng)進化蝙蝠算法快速收斂的優(yōu)勢明顯，且在Science網(wǎng)絡(luò)中求解的顯著比其他2種算法的高。

(a) Karate; (b) Dolphin; (c) Book; (d) Football; (e) Jazz; (f) E-mail; (g) Science

通過網(wǎng)絡(luò)可視化手段考察本文自適應(yīng)進化蝙蝠算法的性能。Karate網(wǎng)絡(luò)和Dolphin網(wǎng)絡(luò)的可視化結(jié)果分別如圖6和圖7所示。

Karate數(shù)據(jù)集是20世紀(jì)70年代由ZACHARY[25]用來進行復(fù)雜網(wǎng)絡(luò)信息流研究。他通過近3年的時間觀察某大學(xué)空手道俱樂部的業(yè)務(wù)和人員交往情況，該俱樂部有4位老師分工管理，其中1名教練和經(jīng)理在授課費用方面存在分歧，隨著日積月累，最終爆發(fā)矛盾沖突，俱樂部分裂為2部分，如圖6(a)所示，其中根據(jù)節(jié)點度值排序位列前三的是：節(jié)點34，節(jié)點1和節(jié)點33。而節(jié)點1和節(jié)點33恰恰代表發(fā)生沖突的教練和經(jīng)理，作為網(wǎng)絡(luò)的重要連通節(jié)點，他們的離開導(dǎo)致整個網(wǎng)絡(luò)分裂，很好地解釋了空手道俱樂部一分為二的原因。在空手道網(wǎng)絡(luò)隨機運行SEBA 1次，求得=0.419 8，NM=0.618 7，社區(qū)劃分結(jié)果如圖6(b)所示。從圖6可以看出：SEBA在標(biāo)準(zhǔn)劃分的基礎(chǔ)上對2個派別進行更細致的劃分，得到4個社區(qū)。圖6(b)中最右邊社區(qū)完全只與節(jié)點1連接，可以看作教練的忠實盟友。此外，節(jié)點9在參考劃分中屬于教練派，但是可以看出他與經(jīng)理派的連邊要多于教練派，因此本算法將其劃為經(jīng)理派的社區(qū)內(nèi)。

Dolphin數(shù)據(jù)集是LUSSEAU[26]研究海豚群體生活習(xí)性構(gòu)建的動物社區(qū)網(wǎng)絡(luò)，該網(wǎng)絡(luò)共有62個節(jié)點，159條邊，根據(jù)海豚性別可以把網(wǎng)絡(luò)劃分出2個社區(qū)，如圖7(a)所示。

(a) 參考社區(qū)結(jié)構(gòu)；(b) SEBA結(jié)果

(a) 參考社區(qū)結(jié)構(gòu)；(b) SEBA結(jié)果

隨機抽取SEBA運行1次，求得=0.528 5，NM=0.644 1，社區(qū)劃分結(jié)果如圖7(b)所示。本文算法依然保持了原有劃分，并未出現(xiàn)錯劃性別的情況，值得注意的是，根據(jù)海豚間的交流程度，還將雌性海豚社區(qū)細化為4個小社區(qū)，社區(qū)內(nèi)部明顯比社區(qū)之間交流更為頻繁，因此，海豚網(wǎng)絡(luò)具有一定的層次結(jié)構(gòu)。

4 結(jié)論

1) 針對社區(qū)發(fā)現(xiàn)場景，本文從遺傳算法中的交叉編譯和變異算子中得到啟發(fā)，對蝙蝠算法進行改進，提出了自適應(yīng)進化蝙蝠算法。該算法摒棄原始蝙蝠算法速度和位置更新思想，引入進化過程，通過交叉變異算子計算位置更新，利用速度更新的快慢提供變異概率值，自適應(yīng)進行變異操作。

2) SEBA具有收斂速度快、求解精度高的特點，比IGA和IDDE等算法具有更優(yōu)的性能，在大規(guī)模網(wǎng)絡(luò)能夠更高效地進行社區(qū)發(fā)現(xiàn)。

[1] FAN L, WU W, LU Z, et al. Influence diffusion, community detection, and link prediction in social network analysis[J]. Springer Proceedings in Mathematics and Statistics, 2013, 51(1): 305?325.

[2] SUN H J, GAO Z Y. Dynamical behaviors of epidemics on scale-free networks with community structure[J]. Physica A: Statistical Mechanics and its Applications, 2007, 381(1): 491?496.

[3] KERNIGHAN B W, LIN S. An efficient heuristic procedure for partitioning graphs[J]. Bell system technical journal, 1970, 49(2): 291?307.

[4] SUARIS P R, KEDEM G. An algorithm for quadrisection and its application to standard cell placement[J]. IEEE Transactions on Circuits and Systems, 1988, 35(3): 294?303.

[5] NEWMANM M E J, Girvan M. Finding and evaluating community structure in networks[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2004, 69(2): 026113?026127.

[6] CLAUSET A, NEWMAN M E, MOORE C. Finding community structure in very large networks[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2004, 70(6): 264?277.

[7] NEWMAN M E J. Fast algorithm for detecting community structure in networks[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2004, 69(6): 066133-1?066133-5.

[8] NEWMAN M E J. Modularity and community structure in networks[J]. Proceedings of the national academy of sciences, 2006, 103(23): 8577?8582.

[9] XING Y, MENG F, ZHOU Y, et al. A node influence based label propagation algorithm for community detection in networks[J]. The Scientific World Journal, 2014, 2014(5): 1?13.

[10] DONGEN S V. Graph clustering by flow simulation[D]. Netherlands: University of Utrecht. Department of Mathematics and Computer Science, 2000: 57?160.

[11] ROSVALL M, BERGSTROM C T. Maps of random walks on complex networks reveal community structure[J]. Proceedings of the National Academy of Sciences, 2008, 105(4): 1118?1123.

[12] CAI Q, GONG M, MA L, et al. Greedy discrete particle swarm optimization for large-scale social network clustering[J]. Information Sciences, 2015, 9(410): 503?516.

[13] HE D, LIU J, LIU D, et al. Ant colony optimization for community detection in large-scale complex networks[C]// International Conference on Natural Computation. Shanghai, China, 2011: 1151?1155.

[14] GUIMERA R, AMARAL L A N. Functional cartography of complex metabolic networks[J]. Nature, 2005, 433(7028): 895?900.

[15] TASGIN M, HERDAGDELEN A, BINGOL H. Community detection in complex networks using genetic algorithms[J]. EprintarXiv, 2006, 2005(1): 1?6.

[16] 金弟, 劉杰, 楊博, 等. 局部搜索與遺傳算法結(jié)合的大規(guī)模復(fù)雜網(wǎng)絡(luò)社區(qū)探測[J]. 自動化學(xué)報, 2011, 37(7): 873?882. JIN Di, LIU Jie, YANG Bo, et al. Genetic algorithm with local search for community detection in large-scale complex networks[J]. Acta Automatica Sinica, 2011, 37(7): 873?882.

[17] LI Y, LIU G, LAO S. A genetic algorithm for community detection in complex networks[J]. Journal of Central South University, 2013, 20(5): 1269?1276.

[18] 張英杰, 龔中漢, 陳乾坤. 基于免疫離散差分進化算法的復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)[J]. 自動化學(xué)報, 2015, 41(4): 749?757. ZHANG Yingjie, GONG Zhonghan, CHEN Qiankun. Community detection in complex networks using immune discrete di?erential evolution algorithm[J]. Acta Automatica Sinica, 2015, 41(4): 749?757.

[19] ZHOU D, WANG X. A Neighborhood-impact based community detection algorithm via discrete PSO[J]. Mathematical Problems in Engineering, 2016(4): 1?15.

[20] 冷作福. 基于貪婪優(yōu)化技術(shù)的網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法研究[J]. 電子學(xué)報, 2014, 42(4): 723?729. LENG Zuofu. Community detection in complex networks based on greedy optimization[J]. Acta Electronic Sinica, 2014, 42(4): 723?729.

[21] YANG X S. A new metaheuristic bat-inspired algorithm[C]// Nature Inspired Cooperative Strategies for Optimization (NICSO2010), Berlin, Heidelberg: Springer, 2010: 65?74.

[22] OSABA E, YANG X S, DIAZ F, et al. An improved discrete bat algorithm for symmetric and asymmetric Traveling Salesman Problems[J]. Engineering Applications of Artificial Intelligence, 2016, 48: 59?71.

[23] 鄧琨, 張健沛, 楊靜.利用改進遺傳算法進行復(fù)雜網(wǎng)絡(luò)社團發(fā)現(xiàn)[J]. 哈爾濱工程大學(xué)學(xué)報, 2013, 34(11): 1438?1444. DENG Kun, ZHANG Jianpei, YANG Jing. Community detection in complex networks using an improved genetic algorithm[J]. Journal of Harbin Engineering University, 2013, 34(11): 1438?1444.

[24] LANCICHINETTI A, FORTUNATO S, RADICCHI F. Benchmark graphs for testing community detection algorithms[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2008, 78(4): 561?570.

[25] ZACHARY W W. An information flow model for conflict and fission in small groups[J]. Journal of Anthropological Research, 1977, 33(4): 452?473.

[26] LUSSEAU D. The emergent properties of a dolphin social network[J]. Proceedings Biological Sciences, 2003, 270(Suppl 2): s186?s188.

(編輯 楊幼平)

Research on community detection in complex networks based on self-adaptive evolution bat algorithm

TANG Chaowei, LI Yan, DUAN Qingyan, YANG Xianfeng, HU Pei, CHEN Guanhao

(School of Communication Engineering, Chongqing University, Chongqing 400030, China)

To solve the problem of low accuracy and slow convergence speed in the community detection of the complex networks, an improved bat algorithm called self-adaptive evolution bat algorithm (SEBA) was proposed by combining the idea of location update and speed update which exists in genetic algorithm. Firstly, network modularitywasemployed as objective function and label propagation method was applied to initialize the population based on the character encoding; then the speed of bat individuals is turned into mutation probability and crossover operator was used to update location information to achieve the self-adaptive evolutionary of bat. Finally, the proposed SEBA was tested on both benchmark networks and real networks in order to compare with other competitive community detection algorithms. The results show that the proposed algorithm significantly accelerates the convergence speed and increases accuracy in the presence of large-scale network structure.

complex network; community detection; modularity; bat algorithm; self-adaptive; evolution

TP31

A

1672?7207(2018)01?0109?09

10.11817/j.issn.1672-7207.2018.01.015

2017?01?12；

2017?03?19

重慶市科委社會民生專項(cstc2013shmszx0500)；重慶市教委科學(xué)技術(shù)研究項目(KJ1729405)；佛山市經(jīng)濟科技發(fā)展專項(2015) (Project(cstc2013shmszx0500) supported by a research grant from Chongqing Science & Technology Commission; Project(KJ1729405) supported by a Scientific and Technological Research Program from Chongqing Municipal Education Commission; Project(2015) supported by Foshan Economic and Information Bureau)

唐朝偉，博士(后)，研究員，從事模式識別，智能信息處理，物聯(lián)網(wǎng)與大數(shù)據(jù)分析等研究；E-mail: cwtang@cqu.edu.cn