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

劉亞瓊 王魯

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

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

中圖分類號：O157.5 文獻(xiàn)標(biāo)識碼：A 文章編號：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)。針對這些網(wǎng)絡(luò)，還要利用算法進(jìn)行社區(qū)的查找，以便更好地解答網(wǎng)絡(luò)潛在結(jié)構(gòu)問題。而采用傳統(tǒng)的算法目前已經(jīng)無法滿足復(fù)雜網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)效率要求，因此還要加強(qiáng)對基于面向復(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é)點和邊組構(gòu)成，結(jié)點為個體，連接結(jié)點的邊可以表示為個體的復(fù)雜關(guān)系。在生活中，網(wǎng)絡(luò)都是復(fù)雜且龐大的，通常擁有數(shù)十萬乃至數(shù)百萬結(jié)點。從屬性上來看，這些網(wǎng)絡(luò)具有強(qiáng)社區(qū)結(jié)構(gòu)特性，即有相似或相同興趣的個體容易聚集成群，群體中個體間的聯(lián)系頻繁、緊密。相反的，不同群體間個體聯(lián)系減少。在對結(jié)點間聯(lián)系的緊密度進(jìn)行衡量時，可以利用聚類系數(shù)。

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

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

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

2.1 蝙蝠算法模型

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

如式（1）所示：

（1）

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

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

（2）

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

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

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

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

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

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

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

通過雙路交叉，可以保持社區(qū)關(guān)系，并使蝙蝠搜索范圍得到拓寬。從算法流程上來看，針對變異蝙蝠，需要依次進(jìn)行維度d更新，在隨機(jī)數(shù)比變異概率小的情況下，需要對變異節(jié)點vd的局部函數(shù)Fd（Xt）進(jìn)行計算，得到鄰居節(jié)點標(biāo)簽集合Ld，d屬于{1，2，...，n}；在標(biāo)簽屬于該集合的情況下，對標(biāo)簽j賦值xd，然后進(jìn)行對應(yīng)局部函數(shù)計算；完成對函數(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)算法效果時，需要利用主頻3.4GHz的Windows7的臺式機(jī)操作系統(tǒng)進(jìn)行算法運行，同時與改進(jìn)遺傳算法進(jìn)行對比。將種群數(shù)設(shè)置為100，迭代次數(shù)和最大響度分別設(shè)定為50和0.95，最大頻度設(shè)置為0.95，響度衰減系數(shù)和頻度增加系數(shù)分別設(shè)為0.95和0.5。從結(jié)果來看，自適應(yīng)蝙蝠算法的Q為0.95，改進(jìn)遺傳算法為0.92，二者的適應(yīng)度相當(dāng)，但是自適應(yīng)蝙蝠算法的收斂速度更快，因此在復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)問題解答方面具有一定優(yōu)勢。

3 結(jié) 論

通過分析可以發(fā)現(xiàn)，現(xiàn)實生活中的網(wǎng)絡(luò)多為復(fù)雜網(wǎng)絡(luò)，針對這些網(wǎng)絡(luò)進(jìn)行社區(qū)發(fā)現(xiàn)問題的解決，采用傳統(tǒng)算法已經(jīng)無法滿足要求。而采用改進(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ī)應(yīng)用研究，2019（3）：1-2.

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