基于GA與SA的社區(qū)檢測優(yōu)化算法研究

王妍 吳克晴 劉松華

摘 要：社區(qū)結(jié)構(gòu)是網(wǎng)絡(luò)最重要的屬性之一，近年來社區(qū)檢測受到極大關(guān)注，出現(xiàn)了很多社區(qū)發(fā)現(xiàn)算法。模塊度是衡量社區(qū)劃分好壞的重要指標(biāo)，但是其分辨率卻有一定局限性。將模塊度中加入一個(gè)可調(diào)參數(shù)，根據(jù)社區(qū)結(jié)構(gòu)調(diào)整參數(shù)更適合于需求不同的社區(qū)檢測。隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大，社區(qū)發(fā)現(xiàn)算法既要有較高的準(zhǔn)確性，又要有很低的時(shí)間復(fù)雜性。提出一種發(fā)現(xiàn)算法GASA，該算法將遺傳變異與模擬退火相結(jié)合，既有遺傳算法的全局搜索能力，又有模擬退火算法的局部搜索能力。該算法用于社區(qū)檢測優(yōu)勢明顯，檢測到的社區(qū)更接近真實(shí)社區(qū)。

關(guān)鍵詞：模塊度;遺傳變異算法;模擬退火算法;社區(qū)檢測

DOI：10. 11907/rjdk. 191002 開放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（OSID）：

中圖分類號(hào)：TP312文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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 引言

許多現(xiàn)實(shí)世界都可以表示為網(wǎng)絡(luò)，例如協(xié)作網(wǎng)絡(luò)、萬維網(wǎng)、生物網(wǎng)絡(luò)等。網(wǎng)絡(luò)可以用圖表示，其中節(jié)點(diǎn)表示對象，邊表示對象之間的關(guān)系[1]。近年來復(fù)雜網(wǎng)絡(luò)備受關(guān)注。網(wǎng)絡(luò)具有小世界、傳遞性等特征，其中社區(qū)結(jié)構(gòu)是一個(gè)重要的特征。社區(qū)檢測對于復(fù)雜網(wǎng)絡(luò)研究具有重要意義，社區(qū)是圖節(jié)點(diǎn)的一個(gè)子集，社區(qū)內(nèi)節(jié)點(diǎn)之間的邊相比其它社區(qū)更加緊密，而屬于同一社區(qū)的節(jié)點(diǎn)屬性相似度較高[2]。

社區(qū)檢測最早用來解決圖分割問題，其中最有代表性的就是Kernighan-Lin圖分類算法，但是該算法需要提前知道網(wǎng)絡(luò)社區(qū)規(guī)模，在現(xiàn)實(shí)生活中應(yīng)用有一定難度[3]?；贚aplace矩陣的譜分法是一個(gè)典型代表，但該分類結(jié)果沒有社區(qū)劃分評價(jià)標(biāo)準(zhǔn)，無法確定劃分的社區(qū)是否達(dá)到最優(yōu)[4]。本文采用模塊度作為社區(qū)劃分好壞的評價(jià)標(biāo)準(zhǔn)，不僅解決了譜分類存在的問題，還改善了模塊度由于分辨率限制導(dǎo)致社區(qū)檢測結(jié)果不理想的問題。

模塊度最初由Newman & Girvan引入，是GN算法的一個(gè)停止準(zhǔn)則，現(xiàn)在已經(jīng)成為許多社區(qū)檢測算法的評價(jià)標(biāo)準(zhǔn)。模塊化值越大，社區(qū)劃分的效果就越好。因此，具有最大模塊性的分區(qū)應(yīng)該是最好的分區(qū)，這也是模塊化尋求最大值的主要?jiǎng)訖C(jī)。但由于模塊化優(yōu)化過程中存在分辨率問題，所以加入一個(gè)可調(diào)參數(shù)，利用不同的分辨率進(jìn)行社區(qū)檢測。模塊化在優(yōu)化時(shí)無法識(shí)別較小的模塊，這與網(wǎng)絡(luò)的規(guī)模及模塊中連接的緊密度有關(guān)。有學(xué)者提出了包含可調(diào)參數(shù)的通用函數(shù)，可以利用不同分辨率進(jìn)行社區(qū)劃分[5-6]。

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

本文提出一種社區(qū)檢測算法，將GA算法與模擬退火算法結(jié)合，利用兩種算法的優(yōu)點(diǎn)識(shí)別網(wǎng)絡(luò)結(jié)構(gòu)，并將算法生成的網(wǎng)絡(luò)與真實(shí)網(wǎng)絡(luò)對比，證明算法的可行性。

1 網(wǎng)絡(luò)模型概念

網(wǎng)絡(luò)：就是若干元素的集合，這些元素是節(jié)點(diǎn)，把連接節(jié)點(diǎn)之間的關(guān)系叫做邊。網(wǎng)絡(luò)在生活中隨處可見，通過邊將一組節(jié)點(diǎn)連接起來是最簡單的網(wǎng)絡(luò)類型。在對地理環(huán)境進(jìn)行建模時(shí)，圖論提供了一個(gè)重要模型。

節(jié)點(diǎn)：一張圖G由有限集合（V，E）構(gòu)成，其中V表示節(jié)點(diǎn)集合，V={Vi|i=1，…n}，是網(wǎng)絡(luò)的基礎(chǔ)單元。在進(jìn)行網(wǎng)絡(luò)分析時(shí)，通常用帶有某個(gè)屬性的節(jié)點(diǎn)表示真實(shí)的個(gè)體，本文中的節(jié)點(diǎn)用來表示研究區(qū)域的村落，n=|V|為節(jié)點(diǎn)總數(shù)，即村落個(gè)數(shù)。

邊：圖中E表示邊的集合，用來表示兩個(gè)節(jié)點(diǎn)之間的關(guān)系，E={eij|Vi，Vj∈V}，m=|E|為邊的總數(shù)。

鄰接矩陣：Aij表示鄰接矩陣，其值為1或0。當(dāng)Aij為1時(shí)，表示節(jié)點(diǎn)i與節(jié)點(diǎn)j之間存在邊。當(dāng)Aij為0時(shí)，表示節(jié)點(diǎn)i與節(jié)點(diǎn)j之間不存在邊[8]。

2 遺傳模擬退火

2.1 遺傳算法

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

2.2 模擬退火算法

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

3 改進(jìn)GASA算法

3.1 改進(jìn)算法步驟

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

3.2 改進(jìn)算法步驟說明

3.2.1 參數(shù)設(shè)置

3.2.2 初始化種群

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

3.2.3 遺傳變異

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

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

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

（2）變異操作：隨機(jī)選擇一個(gè)染色體進(jìn)行突變，在染色體上找一個(gè)頂點(diǎn)，將頂點(diǎn)的簇改變?yōu)槠溧従拥拇?。頂點(diǎn)的鄰居即為與其相連的頂點(diǎn)，但是兩個(gè)頂點(diǎn)所在的簇不同。重復(fù)操作n次，得到變異以后的染色體[15]。突變時(shí)，突變節(jié)點(diǎn)只可能變?yōu)榕c其相連節(jié)點(diǎn)的簇，減少了無用搜索。將遺傳變異后的結(jié)果作為模擬退火的初始解，利用模擬退火搜索尋找最優(yōu)解。

3.2.4 模擬退火搜索

（1）初始溫度TT，最低溫度Tmin，α為降溫概率，初始狀態(tài)xx=Pchild，最優(yōu)解x_best=xx，評價(jià)函數(shù)f為模塊密度。

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

（3）計(jì)算模塊密度：計(jì)算當(dāng)前染色體xx的模塊密度fxx和產(chǎn)生的新解x_new的模塊密度fx_new。

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

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

4 實(shí)驗(yàn)結(jié)果及分析

數(shù)據(jù)來源：實(shí)驗(yàn)數(shù)據(jù)采用Lancichinetti等提出的社區(qū)網(wǎng)絡(luò)數(shù)據(jù)，網(wǎng)絡(luò)中包含128個(gè)節(jié)點(diǎn)，這些節(jié)點(diǎn)劃分為4個(gè)社區(qū)，每個(gè)社區(qū)包含32個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)平均與16個(gè)節(jié)點(diǎn)相連，即節(jié)點(diǎn)平均度為16。但是與節(jié)點(diǎn)相連的其它節(jié)點(diǎn)可能與其在同一個(gè)簇也可能屬于不同的簇，引入?yún)?shù)u，u代表與此節(jié)點(diǎn)相連的其它節(jié)點(diǎn)屬于不同簇的比例。好的算法就是要發(fā)現(xiàn)社區(qū)中的結(jié)構(gòu)，利用GASA算法來檢測社區(qū)結(jié)構(gòu)是否有效[19]。

評價(jià)函數(shù)如下：

（1）模塊度公式指子圖內(nèi)部與外部度之差與子圖大小的比率，模塊度越大，分區(qū)效果越好，社區(qū)檢測的目標(biāo)就是不斷尋找模塊度的最大值。如式（4）所示，加入?yún)?shù)r，使得模塊度具有一般性。

當(dāng)r=0.5時(shí)，Dr與模塊密度D大小相等，當(dāng)r<0.5時(shí)，優(yōu)化算法用來發(fā)現(xiàn)大社區(qū)，當(dāng)r>0.5時(shí)，優(yōu)化算法用來發(fā)現(xiàn)小社區(qū)，加入?yún)?shù)r后，避免了分辨率的限制。通過改變r(jià)的值分析復(fù)雜網(wǎng)絡(luò)內(nèi)部結(jié)構(gòu)。

（2）NMI：是Leon Danon提出用來評價(jià)劃分社區(qū)與已知社區(qū)之間差異性的指標(biāo)。給定兩個(gè)社區(qū)[a=（a1，a2，？][an）]，[b=（b1，b2，？bn）]，其中ap和bp表示第p個(gè)節(jié)點(diǎn)在兩種社區(qū)劃分中的社區(qū)編號(hào)，網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量為n，NMI計(jì)算公式如下：

式（5）中，矩陣N的第i行元素之和用Ni表示，矩陣N第j列元素之和用Nj表示。NMI值越大表明社區(qū)劃分效果越好，當(dāng)NMI值為1時(shí)，表示利用算法劃分的社區(qū)與原社區(qū)結(jié)構(gòu)相同。

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

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

? ?

5 結(jié)語

本文提出的GASA改進(jìn)算法能在社區(qū)檢測時(shí)提高檢測模塊的密度值，將遺傳算法與模擬退火算法相結(jié)合，實(shí)驗(yàn)表明GASA 比GA算法和MA算法在發(fā)現(xiàn)真實(shí)社區(qū)時(shí)更有優(yōu)勢。通過調(diào)整模塊密度參數(shù)r，可以分析不同分辨率網(wǎng)絡(luò)。未來研究工作主要是模塊密度優(yōu)化問題，避免人工調(diào)整參數(shù)r，將單一的模塊密度優(yōu)化問題轉(zhuǎn)化為多目標(biāo)優(yōu)化問題。

參考文獻(xiàn)：

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

[2] 張敏輝，賴麟，孫連海. 基于遺傳算法的研究與Matlab代碼實(shí)現(xiàn) [J]. 四川教育學(xué)院學(xué)報(bào)，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] 陳穎，劉連光. 微網(wǎng)與智能配電網(wǎng) [J]. 企業(yè)文化，2012（5）：46-48.

[6] 張炳達(dá). 智能信息處理技術(shù)基礎(chǔ)[M]. 天津：天津大學(xué)出版社，2008：98-102.

[7] 金志剛，徐珮軒. 密度峰值聚類的自適應(yīng)社區(qū)發(fā)現(xiàn)算法[J]. 哈爾濱工業(yè)大學(xué)學(xué)報(bào)，2008（5）：44-51.

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

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

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

[11] 劉敬宇，朱朝艷. 遺傳模擬退火算法在結(jié)構(gòu)優(yōu)化設(shè)計(jì)中的應(yīng)用[J]. 吉林建筑工程學(xué)院學(xué)報(bào)，2010 （2）：5-8.

[12] 水超，李慧. 基于“次中心”的社區(qū)結(jié)構(gòu)探索算法[J]. 計(jì)算機(jī)應(yīng)用，2012 （8）：2154-2158.

[13] 張余. 隨機(jī)能力提升下知識(shí)型員工調(diào)度問題研究[D]. 西安：西安電子科技大學(xué)，2012：33-38.

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

[15] 陳麗，朱裴松，錢鐵云，等. 基于邊采樣的網(wǎng)絡(luò)表示學(xué)習(xí)模型[J]. 軟件學(xué)報(bào)，2018（3）：756-771.

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

[17] 楊令興，張喜斌. 基于單目標(biāo)PSO的社區(qū)檢測算法[J]. 計(jì)算機(jī)科學(xué)，2015（1）：57-60.

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

[19] 楊冬旺. 基于遺傳模擬退火算法的熱泵和制冷系統(tǒng)優(yōu)化[D]. 天津：天津大學(xué)，2007：34-36.

（責(zé)任編輯：杜能鋼）