基于面向復雜網絡的社區發現算法分析

劉亞瓊 王魯

摘 要：結合復雜網絡的社區發現問題，本文提出了經過改進的自適應蝙蝠算法，以適應復雜網絡的動態增長、海量特性，解決社區發現問題。從分析結果來看，該算法可以獲得較高的社區發現效率。

關鍵詞：復雜網絡；社區發現算法；自適應蝙蝠算法

中圖分類號：O157.5 文獻標識碼：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 引 言

伴隨著網絡技術的快速發展，各種復雜的網絡也隨之出現。針對這些網絡，還要利用算法進行社區的查找，以便更好地解答網絡潛在結構問題。而采用傳統的算法目前已經無法滿足復雜網絡的社區發現效率要求，因此還要加強對基于面向復雜網絡的社區發現算法的研究。

1 復雜網絡的社區發現研究

復雜網絡不同于一般網絡結構，其由結點和邊組構成，結點為個體，連接結點的邊可以表示為個體的復雜關系。在生活中，網絡都是復雜且龐大的，通常擁有數十萬乃至數百萬結點。從屬性上來看，這些網絡具有強社區結構特性，即有相似或相同興趣的個體容易聚集成群，群體中個體間的聯系頻繁、緊密。相反的，不同群體間個體聯系減少。在對結點間聯系的緊密度進行衡量時，可以利用聚類系數。

通常情況下，真實的網絡都具有社區特性，較之隨機網絡擁有更高的平均聚類系數。針對復雜網絡，社區發現為關鍵的分析路徑，可以用于解決網絡部分結點集合的查找問題。在發現的集合內部，各結點間聯系緊密，集合外的結點聯系相對松散。

通過對這些社區的行為結構進行分析，可以發現網絡的結構特性，繼而為實際問題的解答提供便利。在面向復雜網絡的社區發現算法研究方面，目前得到廣泛采用的為模塊度函數[1]。利用該函數，可以利用定量評價社區結構優劣的度量指標進行問題的轉化，從而利用模塊度函數優化方法解決問題。采用該算法，得到的函數越大，網絡社區結構越顯著。但是相較于這一算法，利用智能優化算法可以在有限時間內完成最優解的查找。

2 基于面向復雜網絡的社區發現算法

2.1 蝙蝠算法模型

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

如式（1）所示：

（1）

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

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

（2）

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

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

2.2 算法改進分析

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

而蝙蝠尋優的過程，則是速度和尾椎不斷更新的過程，可以利用速度進行蝙蝠處于最優位置概率的表示。在算法逐步收斂的情況下，可以更新的速度逐漸減小，可以證明蝙蝠接近目標。結合速度和迭代次數關系，可以對蝙蝠當前處于最佳位置的概率進行分析。

針對蝙蝠局部搜索能力不強的問題，還要引入變異算子進行局部開發。采用傳統算法，在利用各基因進行節點所在社區標號表示時，各基因存在聯系，隨機交換基因將導致這種關系被割裂，造成求解尋優倒退[3]。

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

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

（3）

2.3 算法改進效果

在確認算法效果時，需要利用主頻3.4GHz的Windows7的臺式機操作系統進行算法運行，同時與改進遺傳算法進行對比。將種群數設置為100，迭代次數和最大響度分別設定為50和0.95，最大頻度設置為0.95，響度衰減系數和頻度增加系數分別設為0.95和0.5。從結果來看，自適應蝙蝠算法的Q為0.95，改進遺傳算法為0.92，二者的適應度相當，但是自適應蝙蝠算法的收斂速度更快，因此在復雜網絡社區發現問題解答方面具有一定優勢。

3 結 論

通過分析可以發現，現實生活中的網絡多為復雜網絡，針對這些網絡進行社區發現問題的解決，采用傳統算法已經無法滿足要求。而采用改進的自適應蝙蝠算法，可以獲得較高的適應度，并能加快算法收斂，因此可以使社區的發現效率得到明顯提高，繼而更好地滿足網絡社區查找需求。

參考文獻：

[1] 金爽.復雜網絡社區發現中標簽傳播算法的研究與應用 [J].信息與電腦（理論版），2018（3）：53-54.

[2] 楚楊杰，楊忠保，洪葉.局部擴展的遺傳優化重疊社區發現方法 [J].計算機應用研究，2019（3）：1-2.

[3] 唐朝偉，李彥，段青言，等.自適應進化蝙蝠算法下的復雜網絡社區發現 [J].中南大學學報（自然科學版），2018，49（1）：109-117.