基于面向復(fù)雜網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)算法分析

劉亞瓊 王魯

摘 要：結(jié)合復(fù)雜網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)問(wèn)題，本文提出了經(jīng)過(guò)改進(jìn)的自適應(yīng)蝙蝠算法，以適應(yīng)復(fù)雜網(wǎng)絡(luò)的動(dòng)態(tài)增長(zhǎng)、海量特性，解決社區(qū)發(fā)現(xiàn)問(wèn)題。從分析結(jié)果來(lái)看，該算法可以獲得較高的社區(qū)發(fā)現(xiàn)效率。

關(guān)鍵詞：復(fù)雜網(wǎng)絡(luò)；社區(qū)發(fā)現(xiàn)算法；自適應(yīng)蝙蝠算法

中圖分類號(hào)：O157.5 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2096-4706（2018）02-0126-02

Analysis of Community Detection Based on Complex Networks

LIU Yaqiong，WANG Lu

（Shandong Agricultural University，Taian 271000，China）

Abstract：Combined with the problem of community discovery in complex networks，this paper proposes an improved adaptive bat algorithm to adapt to the dynamic growth and massive characteristics of complex networks，and solve community detection problems. From the analysis results，the algorithm can achieve high efficiency in community discovery.

Keywords：complex network；community detection；adaptive bat algorithm

0 引 言

伴隨著網(wǎng)絡(luò)技術(shù)的快速發(fā)展，各種復(fù)雜的網(wǎng)絡(luò)也隨之出現(xiàn)。針對(duì)這些網(wǎng)絡(luò)，還要利用算法進(jìn)行社區(qū)的查找，以便更好地解答網(wǎng)絡(luò)潛在結(jié)構(gòu)問(wèn)題。而采用傳統(tǒng)的算法目前已經(jīng)無(wú)法滿足復(fù)雜網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)效率要求，因此還要加強(qiáng)對(duì)基于面向復(fù)雜網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)算法的研究。

1 復(fù)雜網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)研究

復(fù)雜網(wǎng)絡(luò)不同于一般網(wǎng)絡(luò)結(jié)構(gòu)，其由結(jié)點(diǎn)和邊組構(gòu)成，結(jié)點(diǎn)為個(gè)體，連接結(jié)點(diǎn)的邊可以表示為個(gè)體的復(fù)雜關(guān)系。在生活中，網(wǎng)絡(luò)都是復(fù)雜且龐大的，通常擁有數(shù)十萬(wàn)乃至數(shù)百萬(wàn)結(jié)點(diǎn)。從屬性上來(lái)看，這些網(wǎng)絡(luò)具有強(qiáng)社區(qū)結(jié)構(gòu)特性，即有相似或相同興趣的個(gè)體容易聚集成群，群體中個(gè)體間的聯(lián)系頻繁、緊密。相反的，不同群體間個(gè)體聯(lián)系減少。在對(duì)結(jié)點(diǎn)間聯(lián)系的緊密度進(jìn)行衡量時(shí)，可以利用聚類系數(shù)。

通常情況下，真實(shí)的網(wǎng)絡(luò)都具有社區(qū)特性，較之隨機(jī)網(wǎng)絡(luò)擁有更高的平均聚類系數(shù)。針對(duì)復(fù)雜網(wǎng)絡(luò)，社區(qū)發(fā)現(xiàn)為關(guān)鍵的分析路徑，可以用于解決網(wǎng)絡(luò)部分結(jié)點(diǎn)集合的查找問(wèn)題。在發(fā)現(xiàn)的集合內(nèi)部，各結(jié)點(diǎn)間聯(lián)系緊密，集合外的結(jié)點(diǎn)聯(lián)系相對(duì)松散。

通過(guò)對(duì)這些社區(qū)的行為結(jié)構(gòu)進(jìn)行分析，可以發(fā)現(xiàn)網(wǎng)絡(luò)的結(jié)構(gòu)特性，繼而為實(shí)際問(wèn)題的解答提供便利。在面向復(fù)雜網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)算法研究方面，目前得到廣泛采用的為模塊度函數(shù)[1]。利用該函數(shù)，可以利用定量評(píng)價(jià)社區(qū)結(jié)構(gòu)優(yōu)劣的度量指標(biāo)進(jìn)行問(wèn)題的轉(zhuǎn)化，從而利用模塊度函數(shù)優(yōu)化方法解決問(wèn)題。采用該算法，得到的函數(shù)越大，網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)越顯著。但是相較于這一算法，利用智能優(yōu)化算法可以在有限時(shí)間內(nèi)完成最優(yōu)解的查找。

2 基于面向復(fù)雜網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)算法

2.1 蝙蝠算法模型

相較于粒子群算法、遺傳算法等智能優(yōu)化算法，蝙蝠群算法擁有收斂速度快、計(jì)算量小等特點(diǎn)。在解決復(fù)雜網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)問(wèn)題時(shí)，可以嘗試采用該算法解決問(wèn)題。采用該算法，是利用蝙蝠借助超聲波捕食的原理，對(duì)蝙蝠回聲定位行為特征進(jìn)行模擬，將根據(jù)蝙蝠發(fā)射超聲波的脈沖頻數(shù)進(jìn)行指向性搜索。由于脈沖頻數(shù)較低，同時(shí)響度較大，所以在目標(biāo)范圍不斷縮小的情況下，脈沖頻數(shù)會(huì)增加，目標(biāo)信息量也將得到大量獲取，繼而實(shí)現(xiàn)目標(biāo)準(zhǔn)確定位。

如式（1）所示：

（1）

xidt+1為游走在種群最優(yōu)解周圍的蝙蝠個(gè)體位置，vidt+1為第i只蝙蝠在t+1時(shí)刻的飛行速度，ε指的是比例因子，為[-1，1]上的隨機(jī)數(shù)，? t指的是t次迭代中，為蝙蝠響度平均值。從式中可以看出比例因子隨機(jī)游走的強(qiáng)度和方向。

蝙蝠在搜索的過(guò)程中，依靠響度和脈沖頻數(shù)進(jìn)行獵物查找，發(fā)現(xiàn)獵物后信號(hào)響度會(huì)減弱，頻數(shù)則相對(duì)增大，如式（2）所示：

（2）

ri0指的是最大脈沖頻數(shù)，α則為響度減弱系數(shù)，γ為頻數(shù)增加系數(shù)。針對(duì)0<α<1和γ>0的情況，在迭代次數(shù)接近∞的情況下，存在Att無(wú)限趨近0，rit+1無(wú)限趨近ri0的情況。而只有在最優(yōu)位置，脈沖響度和頻數(shù)才能更新，因此可以說(shuō)明蝙蝠接近目標(biāo)。

按照算法步驟，需要先完成初始化參數(shù)設(shè)置，包含脈沖頻率最大值fmax和最小值fmin，最大響度Ai0，最大脈沖頻度，響度衰減系數(shù)、頻度增加系數(shù)和迭代終止條件。而蝙蝠初始位置為Xi，（i=1，2，3，...，NP）；對(duì)當(dāng)前種群適應(yīng)度進(jìn)行計(jì)算后，需完成最佳蝙蝠位置的查找，然后結(jié)合脈沖初始化頻率對(duì)蝙蝠速度及位置進(jìn)行更新，得到隨機(jī)數(shù)r1；在隨機(jī)數(shù)比ri大的情況下，可以利用最優(yōu)蝙蝠尾椎隨機(jī)擾動(dòng)計(jì)算進(jìn)行當(dāng)前個(gè)體位置的替代，得到第二個(gè)隨機(jī)數(shù)；在隨機(jī)數(shù)比Ai大的情況下，同時(shí)F（Xi）比F（X*）大，可以接受最優(yōu)解，進(jìn)行響度和頻數(shù)更新；最后，確認(rèn)算法是否終止，未終止需要重復(fù)更新步驟。

2.2 算法改進(jìn)分析

通過(guò)算法分析可以發(fā)現(xiàn)，采用蝙蝠算法的局部搜索能力與全局搜索能力無(wú)法得到自動(dòng)平衡，所以會(huì)導(dǎo)致算法無(wú)法獲得理想應(yīng)用效果。針對(duì)這一問(wèn)題，還要實(shí)現(xiàn)算法改進(jìn)，得到自適應(yīng)的蝙蝠算法。采用該算法，由于需要實(shí)現(xiàn)字符編碼，因此還要利用標(biāo)簽傳播方式完成初始化。通過(guò)將算法中的速度轉(zhuǎn)化為變異概率，同時(shí)加強(qiáng)交叉變異算子的利用，則能使蝙蝠的位置得到更新，使全局搜索和局部開發(fā)能力得到均衡。具體來(lái)講，就是要利用模塊度函數(shù)作為適應(yīng)度函數(shù)，利用蝙蝠空間位置X進(jìn)行對(duì)應(yīng)節(jié)點(diǎn)社區(qū)編號(hào)的直接表示。在編解碼時(shí)，還要將網(wǎng)絡(luò)中節(jié)點(diǎn)編碼位置維度索引設(shè)定為1、2、3、4、5、6、7，對(duì)應(yīng)編碼為1、6、6、1、1、6、1。由此可知，編碼為1的屬于同一個(gè)社區(qū)，編碼為6的屬于一個(gè)社區(qū)。通過(guò)采取該種初始化策略，可以使搜索空間得到有效減小，并使算法的運(yùn)行時(shí)間得到縮短，同時(shí)也能使種群的多樣性得到保留[2]。

而蝙蝠尋優(yōu)的過(guò)程，則是速度和尾椎不斷更新的過(guò)程，可以利用速度進(jìn)行蝙蝠處于最優(yōu)位置概率的表示。在算法逐步收斂的情況下，可以更新的速度逐漸減小，可以證明蝙蝠接近目標(biāo)。結(jié)合速度和迭代次數(shù)關(guān)系，可以對(duì)蝙蝠當(dāng)前處于最佳位置的概率進(jìn)行分析。

針對(duì)蝙蝠局部搜索能力不強(qiáng)的問(wèn)題，還要引入變異算子進(jìn)行局部開發(fā)。采用傳統(tǒng)算法，在利用各基因進(jìn)行節(jié)點(diǎn)所在社區(qū)標(biāo)號(hào)表示時(shí)，各基因存在聯(lián)系，隨機(jī)交換基因?qū)?dǎo)致這種關(guān)系被割裂，造成求解尋優(yōu)倒退[3]。

而采用雙路交叉算子，可以進(jìn)行2個(gè)染色體的隨機(jī)選擇，然后將其分別作為源染色體和目標(biāo)染色體。從中進(jìn)行1個(gè)節(jié)點(diǎn)的選擇，并對(duì)其社區(qū)成員C和標(biāo)號(hào)l進(jìn)行獲取，可以完成成員查找。

通過(guò)雙路交叉，可以保持社區(qū)關(guān)系，并使蝙蝠搜索范圍得到拓寬。從算法流程上來(lái)看，針對(duì)變異蝙蝠，需要依次進(jìn)行維度d更新，在隨機(jī)數(shù)比變異概率小的情況下，需要對(duì)變異節(jié)點(diǎn)vd的局部函數(shù)Fd（Xt）進(jìn)行計(jì)算，得到鄰居節(jié)點(diǎn)標(biāo)簽集合Ld，d屬于{1，2，...，n}；在標(biāo)簽屬于該集合的情況下，對(duì)標(biāo)簽j賦值xd，然后進(jìn)行對(duì)應(yīng)局部函數(shù)計(jì)算；完成對(duì)函數(shù)貢獻(xiàn)度最大標(biāo)簽的選擇，然后將其看成是d維度的標(biāo)簽值，進(jìn)而進(jìn)行上述數(shù)據(jù)更新。如式（3）所示，d維分量可以用j替代，從而進(jìn)行函數(shù)求解，使xdt+1成為最大標(biāo)簽。

（3）

2.3 算法改進(jìn)效果

在確認(rèn)算法效果時(shí)，需要利用主頻3.4GHz的Windows7的臺(tái)式機(jī)操作系統(tǒng)進(jìn)行算法運(yùn)行，同時(shí)與改進(jìn)遺傳算法進(jìn)行對(duì)比。將種群數(shù)設(shè)置為100，迭代次數(shù)和最大響度分別設(shè)定為50和0.95，最大頻度設(shè)置為0.95，響度衰減系數(shù)和頻度增加系數(shù)分別設(shè)為0.95和0.5。從結(jié)果來(lái)看，自適應(yīng)蝙蝠算法的Q為0.95，改進(jìn)遺傳算法為0.92，二者的適應(yīng)度相當(dāng)，但是自適應(yīng)蝙蝠算法的收斂速度更快，因此在復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)問(wèn)題解答方面具有一定優(yōu)勢(shì)。

3 結(jié) 論

通過(guò)分析可以發(fā)現(xiàn)，現(xiàn)實(shí)生活中的網(wǎng)絡(luò)多為復(fù)雜網(wǎng)絡(luò)，針對(duì)這些網(wǎng)絡(luò)進(jìn)行社區(qū)發(fā)現(xiàn)問(wèn)題的解決，采用傳統(tǒng)算法已經(jīng)無(wú)法滿足要求。而采用改進(jìn)的自適應(yīng)蝙蝠算法，可以獲得較高的適應(yīng)度，并能加快算法收斂，因此可以使社區(qū)的發(fā)現(xiàn)效率得到明顯提高，繼而更好地滿足網(wǎng)絡(luò)社區(qū)查找需求。

參考文獻(xiàn)：

[1] 金爽.復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)中標(biāo)簽傳播算法的研究與應(yīng)用 [J].信息與電腦（理論版），2018（3）：53-54.

[2] 楚楊杰，楊忠保，洪葉.局部擴(kuò)展的遺傳優(yōu)化重疊社區(qū)發(fā)現(xiàn)方法 [J].計(jì)算機(jī)應(yīng)用研究，2019（3）：1-2.

[3] 唐朝偉，李彥，段青言，等.自適應(yīng)進(jìn)化蝙蝠算法下的復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn) [J].中南大學(xué)學(xué)報(bào)（自然科學(xué)版），2018，49（1）：109-117.