基于GA與SA的社區檢測優化算法研究

王妍 吳克晴 劉松華

摘 要：社區結構是網絡最重要的屬性之一，近年來社區檢測受到極大關注，出現了很多社區發現算法。模塊度是衡量社區劃分好壞的重要指標，但是其分辨率卻有一定局限性。將模塊度中加入一個可調參數，根據社區結構調整參數更適合于需求不同的社區檢測。隨著網絡規模的擴大，社區發現算法既要有較高的準確性，又要有很低的時間復雜性。提出一種發現算法GASA，該算法將遺傳變異與模擬退火相結合，既有遺傳算法的全局搜索能力，又有模擬退火算法的局部搜索能力。該算法用于社區檢測優勢明顯，檢測到的社區更接近真實社區。

關鍵詞：模塊度;遺傳變異算法;模擬退火算法;社區檢測

DOI：10. 11907/rjdk. 191002 開放科學（資源服務）標識碼（OSID）：

中圖分類號：TP312文獻標識碼：A 文章編號：1672-7800（2019）009-0077-04

A Community Detection Optimization Algorithm Based on GA and SA

WANG Yan，WU Ke-qing， LIU Song-hua

（College of Science， Jiangxi University of Science and Technology， Ganzhou 341000， China）

Abstract： Community structure is one of the most important attributes in the network. In recent years， community detection has attracted great attention， and many community discovery algorithms have emerged. Modularity is an important index to measure the quality of community division， but its resolution has some limitations. This paper adds an adjustable parameter to modularity， which can be adjusted according to community structure， and is more suitable for community detection with different needs. With the enlargement of network scale， community discovery algorithm not only needs to satisfy higher accuracy， but also reduces the computing time of the algorithm. So a discovery algorithm GASA is proposed， which combines genetic mutation with simulated annealing. It has both global search ability of genetic algorithm and local search ability of simulated annealing algorithm. This algorithm has stronger advantages in community detection， and the detected community is closer to the real community.

Key Words： cluster modularity; GA; SA; community detection

0 引言

許多現實世界都可以表示為網絡，例如協作網絡、萬維網、生物網絡等。網絡可以用圖表示，其中節點表示對象，邊表示對象之間的關系[1]。近年來復雜網絡備受關注。網絡具有小世界、傳遞性等特征，其中社區結構是一個重要的特征。社區檢測對于復雜網絡研究具有重要意義，社區是圖節點的一個子集，社區內節點之間的邊相比其它社區更加緊密，而屬于同一社區的節點屬性相似度較高[2]。

社區檢測最早用來解決圖分割問題，其中最有代表性的就是Kernighan-Lin圖分類算法，但是該算法需要提前知道網絡社區規模，在現實生活中應用有一定難度[3]。基于Laplace矩陣的譜分法是一個典型代表，但該分類結果沒有社區劃分評價標準，無法確定劃分的社區是否達到最優[4]。本文采用模塊度作為社區劃分好壞的評價標準，不僅解決了譜分類存在的問題，還改善了模塊度由于分辨率限制導致社區檢測結果不理想的問題。

模塊度最初由Newman & Girvan引入，是GN算法的一個停止準則，現在已經成為許多社區檢測算法的評價標準。模塊化值越大，社區劃分的效果就越好。因此，具有最大模塊性的分區應該是最好的分區，這也是模塊化尋求最大值的主要動機。但由于模塊化優化過程中存在分辨率問題，所以加入一個可調參數，利用不同的分辨率進行社區檢測。模塊化在優化時無法識別較小的模塊，這與網絡的規模及模塊中連接的緊密度有關。有學者提出了包含可調參數的通用函數，可以利用不同分辨率進行社區劃分[5-6]。

遺傳算法（GA）可用于優化模塊化。首先隨機生成一組解，將適應度高的個體挑選出來，這些個體進行重組或突變形成下一代個體，這樣不斷迭代，最后得到的個體適應性較高[7]。文化基因算法（MA）是Pablo Mosacato提出的一種算法，它將種群的全局搜索和個體的局部搜索結合，是目前廣泛使用的一種算法。

本文提出一種社區檢測算法，將GA算法與模擬退火算法結合，利用兩種算法的優點識別網絡結構，并將算法生成的網絡與真實網絡對比，證明算法的可行性。

1 網絡模型概念

網絡：就是若干元素的集合，這些元素是節點，把連接節點之間的關系叫做邊。網絡在生活中隨處可見，通過邊將一組節點連接起來是最簡單的網絡類型。在對地理環境進行建模時，圖論提供了一個重要模型。

節點：一張圖G由有限集合（V，E）構成，其中V表示節點集合，V={Vi|i=1，…n}，是網絡的基礎單元。在進行網絡分析時，通常用帶有某個屬性的節點表示真實的個體，本文中的節點用來表示研究區域的村落，n=|V|為節點總數，即村落個數。

邊：圖中E表示邊的集合，用來表示兩個節點之間的關系，E={eij|Vi，Vj∈V}，m=|E|為邊的總數。

鄰接矩陣：Aij表示鄰接矩陣，其值為1或0。當Aij為1時，表示節點i與節點j之間存在邊。當Aij為0時，表示節點i與節點j之間不存在邊[8]。

2 遺傳模擬退火

2.1 遺傳算法

遺傳算法（Genetic Algorithm）模擬生物進化形成的計算模型，生物進化中當產生下一代時存在自然選擇和遺傳變異，遺傳算法在搜索最優解時模擬生物進化方式。通常從一組隨機個體開始，在每一代種群中，對每個人的適應度進行評估，根據其適應性，從當前種群隨機選擇多個個體進行交叉、變異以形成新的群體。然后在算法的下一次迭代中使用新的群體。經過幾次迭代，只有適應能力強的個體才能生存 [11]。遺傳算法步驟如圖1所示。

2.2 模擬退火算法

模擬退火（Simulated Annealing）由Metropolis在1953年提出，基于物理中固體物質的退火過程。模擬退火算法首先會設定一個很高的初始溫度，當溫度很高時突跳率也會很高，這有利于當前解跳出局部最優，隨著溫度降低突跳率會變低，當前解開始逐漸趨于全局最優[12]。模擬退火算法步驟如圖2所示。

3 改進GASA算法

3.1 改進算法步驟

初始參數設置：①Gmax：最大迭代次數;Spop：種群大小;Spool：交配種群;Stour：旅行商大小;Pc交叉概率;Pm變異概率;②生成初始種群P;③隨機選取Stour個個體進行比較，將適應度高的個體放入交配池。再從剩下的種群中挑選兩個個體，選擇其中適應度較高的個體放入交配池，不斷進行此操作，直到種群中沒有個體;④基因操作：從交配種群中挑選Pparent進行遺傳變異操作，產生Pchild;⑤模擬退火操作：對Pchild進行模擬退火找到最優個體;⑥重復上述步驟，直到達到最大迭代次數;⑦更新最優解。

3.2 改進算法步驟說明

3.2.1 參數設置

3.2.2 初始化種群

一個網絡被編碼成為整數串x={x1x2…xn}，n是圖中的頂點數，xi是頂點vi所在的簇，它可以是1到n的任意整數，有相同分類的點被分在相同的社區[13]。一個有n個頂點的圖最多能分成n個簇，意思是每個簇最多包含一個頂點，可記作{1 2 …n}。需要注意的是不同的點可以分為同一類，例如一個圖中有4個點，{3 1 2 3}和{1 2 3 1}都代表著相同的分類{{1，4}，{2}，{3}}，表示第1個和第4個點被分為一類。開始時，所有染色體上每個點都單獨分為一類{1 2 …n}，但是最開始的基因缺少多樣性而且計算的適應度很差，沒有實際意義。初始化一個好的染色體基因能夠加快收斂，節省時間，提高效率。對每個染色體先隨機選取一個點，將這個點的分類類別賦給與它相連的點，然后重復這個操作α*n次，α=0.2，這樣就能快速找到局部最好的分類，但是這樣產生的初始解相對于最優解還是很差。

3.2.3 遺傳變異

（1）遺傳操作：傳統方法是取兩個個體，隨機選擇一個交叉點，將兩個染色體中交叉點以后的全部元素交換，產生兩個新的染色體[14]。但是這種直接交叉操作并不適合本算法。對于每個染色體，頂點簇是隨機的一個數字。

本文算法采用雙向交叉操作，交叉結果步驟如下：①選擇兩個染色體Xa和Xb;②隨機選擇一個頂點Vi并確定頂點在染色體Xa上所在的簇xai，將染色體Xa上簇號為xai中所有頂點分配給染色體Xb相同的簇;③確定Vi在染色體Xb上所在的簇xbi，將染色體Xb上簇號為xai中所有頂點分配給染色體Xa相同的簇;④得到兩個新的染色體Xc和Xd。

交叉操作以后產生具有雙親特征的子代，子代攜帶了父母的基因。

（2）變異操作：隨機選擇一個染色體進行突變，在染色體上找一個頂點，將頂點的簇改變為其鄰居的簇。頂點的鄰居即為與其相連的頂點，但是兩個頂點所在的簇不同。重復操作n次，得到變異以后的染色體[15]。突變時，突變節點只可能變為與其相連節點的簇，減少了無用搜索。將遺傳變異后的結果作為模擬退火的初始解，利用模擬退火搜索尋找最優解。

3.2.4 模擬退火搜索

（1）初始溫度TT，最低溫度Tmin，α為降溫概率，初始狀態xx=Pchild，最優解x_best=xx，評價函數f為模塊密度。

（2）產生新解：將xx表示的圖G劃分為不同的簇，[Ω=V1，V2，？，Vm（2mn）]，m是簇的大小，n是頂點數，xx作為當前解。從Vi簇中選擇一個頂點重新分配給另一個簇，產生新解x_new[16]。

（3）計算模塊密度：計算當前染色體xx的模塊密度fxx和產生的新解x_new的模塊密度fx_new。

（4）接受新解作為當前解的概率：接受概率如式（3）所示[17]，如果接受新解作為當前解則xx=x_new，否則重復步驟（2）到步驟（4）。

①最優解更新：如果接受新解作為當前解時，需要將新的fxx與fx_best作比較，如果fxx比fx_best大，需要更新最優解，將xx值賦給x_bes，即x_best=xx，否則最優解不更新;②降低溫度：TT=TT*α;③重復上述步驟，直到達到終止條件，結束程序[18]。

4 實驗結果及分析

數據來源：實驗數據采用Lancichinetti等提出的社區網絡數據，網絡中包含128個節點，這些節點劃分為4個社區，每個社區包含32個節點，每個節點平均與16個節點相連，即節點平均度為16。但是與節點相連的其它節點可能與其在同一個簇也可能屬于不同的簇，引入參數u，u代表與此節點相連的其它節點屬于不同簇的比例。好的算法就是要發現社區中的結構，利用GASA算法來檢測社區結構是否有效[19]。

評價函數如下：

（1）模塊度公式指子圖內部與外部度之差與子圖大小的比率，模塊度越大，分區效果越好，社區檢測的目標就是不斷尋找模塊度的最大值。如式（4）所示，加入參數r，使得模塊度具有一般性。

當r=0.5時，Dr與模塊密度D大小相等，當r<0.5時，優化算法用來發現大社區，當r>0.5時，優化算法用來發現小社區，加入參數r后，避免了分辨率的限制。通過改變r的值分析復雜網絡內部結構。

（2）NMI：是Leon Danon提出用來評價劃分社區與已知社區之間差異性的指標。給定兩個社區[a=（a1，a2，？][an）]，[b=（b1，b2，？bn）]，其中ap和bp表示第p個節點在兩種社區劃分中的社區編號，網絡節點數量為n，NMI計算公式如下：

式（5）中，矩陣N的第i行元素之和用Ni表示，矩陣N第j列元素之和用Nj表示。NMI值越大表明社區劃分效果越好，當NMI值為1時，表示利用算法劃分的社區與原社區結構相同。

參數u取值范圍是0～0.5，生成11個不同網絡，利用NMI測試真實分區與算法檢測到的分區之間的相似度，每個網絡運行10次取平均值作為NMI的最終值。圖（3）為當混合參數u從0增加到0.5時不同r值對應的NMI。當r=0.5、混合參數u值小于0.3時，算法可找到正確的社區劃分。當u增加時，社區檢測的正確度下降。u值為0.35時，NMI值為0.95;u值為0.4時，NMI值為0.9;當u值增大到0.45時，無法檢測到真實社區。但是隨著r值的增加，發現小社區的能力更強，r增大到0.7、u值為0.5時，NMI值仍能達到0.35。r值為0.3、u值達到0.3以后，此時NMI為0，社區檢測結果為將整個社區劃分為一個大社區。

將r值設置為0.5，分別用GA算法、MA算法、GASA算法進行社區檢測，如圖4所示。當u值小于0.1時，GA算法可以檢測到真實社區;當u值小于0.25時，MA算法可以檢測到真實社區;當u值小于0.3時，GASA算法可以檢測到真實社區。雖然3種算法在u值增大到0.45時都無法檢測到真實社區，但是在u值小于0.45時，本文提出的GASA算法較GA和MA算法卻可以較好地檢測到真實社區。

? ?

5 結語

本文提出的GASA改進算法能在社區檢測時提高檢測模塊的密度值，將遺傳算法與模擬退火算法相結合，實驗表明GASA 比GA算法和MA算法在發現真實社區時更有優勢。通過調整模塊密度參數r，可以分析不同分辨率網絡。未來研究工作主要是模塊密度優化問題，避免人工調整參數r，將單一的模塊密度優化問題轉化為多目標優化問題。

參考文獻：

[1] 陳爭光，楊冬風. 特征選擇與提取研究與應用[M]. 哈爾濱：黑龍江教育出版社， 2012：109-112.

[2] 張敏輝，賴麟，孫連海. 基于遺傳算法的研究與Matlab代碼實現 [J]. 四川教育學院學報，2012（1）：115-117.

[3] KERNIGHAN B W，LIN S. An efficient heuristic procedure for partitioning graphs[J]. Bell System Technical Journal，1970，49（2）：291-307.

[4] FORTUNATO S. Community detection in graphs[J]. Physics Reports，2010，486（3）：75-174.

[5] 陳穎，劉連光. 微網與智能配電網 [J]. 企業文化，2012（5）：46-48.

[6] 張炳達. 智能信息處理技術基礎[M]. 天津：天津大學出版社，2008：98-102.

[7] 金志剛，徐珮軒. 密度峰值聚類的自適應社區發現算法[J]. 哈爾濱工業大學學報，2008（5）：44-51.

[8] 王耀南. 智能信息處理技術[M]. 北京：高等教育出版社，2003：178-184.

[9] 林順剛. 遺傳算法概述[J]. 科技信息，2007（2）：11-14.

[10] 石純一，王家. 樹立邏輯與集合論[M]. 北京：清華大學出版社，2000：198-2003

[11] 劉敬宇，朱朝艷. 遺傳模擬退火算法在結構優化設計中的應用[J]. 吉林建筑工程學院學報，2010 （2）：5-8.

[12] 水超，李慧. 基于“次中心”的社區結構探索算法[J]. 計算機應用，2012 （8）：2154-2158.

[13] 張余. 隨機能力提升下知識型員工調度問題研究[D]. 西安：西安電子科技大學，2012：33-38.

[14] 何云斌，張曉瑞，萬靜，等. 基于改進遺傳模擬退火K-means的心電波形的分類研究[J]. 計算機應用研究，2014（11）：3328-3332.

[15] 陳麗，朱裴松，錢鐵云，等. 基于邊采樣的網絡表示學習模型[J]. 軟件學報，2018（3）：756-771.

[16] 武兆慧，張桂娟，劉希玉. 基于模擬退火算法的聚類分析[J]. 計算機應用研究，2015（8）：24-26.

[17] 楊令興，張喜斌. 基于單目標PSO的社區檢測算法[J]. 計算機科學，2015（1）：57-60.

[18] 張健沛，姜延良. 一種基于節點相似性的連接預測算法[J]. 中國科技論文，2013（7）：659-662.

[19] 楊冬旺. 基于遺傳模擬退火算法的熱泵和制冷系統優化[D]. 天津：天津大學，2007：34-36.

（責任編輯：杜能鋼）