譜分析與啟發(fā)式遺傳算法相結(jié)合的多尺度社區(qū)檢測(cè)方法

郭玉泉，李雄飛，劉 昕

（1.吉林大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，長(zhǎng)春130012；2.吉林大學(xué) 網(wǎng)絡(luò)中心，長(zhǎng)春130022）

0 引 言

目前，對(duì)于網(wǎng)絡(luò)社區(qū)還沒有統(tǒng)一定義，通常認(rèn)為社區(qū)是一個(gè)內(nèi)部連接緊密的節(jié)點(diǎn)集合，而該節(jié)點(diǎn)集合與網(wǎng)絡(luò)的其他部分連接稀疏。在現(xiàn)實(shí)網(wǎng)絡(luò)中，網(wǎng)絡(luò)社區(qū)表現(xiàn)出多尺度結(jié)構(gòu)特征，即在不同尺度下有不同的社區(qū)劃分結(jié)果。常用網(wǎng)絡(luò)社區(qū)檢測(cè)方法可以分為三類：第一類是基于優(yōu)化的方法，典型算法有GN［1］、FN［2］、LPAm［3］和LGA［4］方法。優(yōu)化方法多以Newman等［5］提出的Q 函數(shù)為優(yōu)化目標(biāo)，而最大化Q 函數(shù)是NP 完全問題，所以這些優(yōu)化算法都是近似的優(yōu)化算法。第二類是層次聚類方法，典型算法有EAGLE［6］和CPM［7］。層次聚類方法中樹狀圖生成與分割的時(shí)間復(fù)雜度都很高，因此層次聚類方法效率較低。第三類是網(wǎng)絡(luò)動(dòng)力學(xué)方法，如Jin等［8］提出的基于馬爾可夫方法的社區(qū)檢測(cè)方法。以上方法多數(shù)都是單一尺度的網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)檢測(cè)，不能檢測(cè)多尺度網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)。網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的多尺度特征是通過網(wǎng)絡(luò)傳播特性與譜特征來體現(xiàn)的，目前檢測(cè)都是采用基于網(wǎng)絡(luò)動(dòng)力學(xué)與譜方法的檢測(cè)算法。Alex等［9］利用同步過程與拉普拉斯矩陣譜檢測(cè)多尺度社區(qū)；Delvenne等［10］通過在時(shí)間尺度上社區(qū)穩(wěn)定性檢測(cè)多尺度社區(qū)；Cheng等［11］通過復(fù)雜網(wǎng)中傳播過程的穩(wěn)定狀態(tài)檢測(cè)多尺度社區(qū)。

為評(píng)估社區(qū)檢測(cè)結(jié)果的優(yōu)劣，2004 年Newman［5］提出了網(wǎng)絡(luò)社區(qū)的度量標(biāo)準(zhǔn)，稱為模塊 化 函 數(shù)。隨 著 研 究 的 深 入，F(xiàn)ortunato［12］、Arenas［13］等發(fā)現(xiàn)模塊化函數(shù)存在分辨率限制（Resolution limit），無法發(fā)現(xiàn)特定尺寸的社區(qū)結(jié)構(gòu)。2010年，Cheng 等［11］提出的傳導(dǎo)率函數(shù)（C函數(shù)）作為網(wǎng)絡(luò)社區(qū)評(píng)價(jià)標(biāo)準(zhǔn)，傳導(dǎo)率函數(shù)從網(wǎng)絡(luò)動(dòng)力學(xué)角度評(píng)價(jià)網(wǎng)絡(luò)社區(qū)劃分結(jié)果，克服了模塊化函數(shù)的分辨率限制問題。

本文提出的HGASA 算法（Heuristic genetic algorithm with spectral analysis，HGASA）通過譜分析獲得復(fù)雜網(wǎng)絡(luò)多尺度結(jié)構(gòu)信息，將結(jié)構(gòu)信息應(yīng)用于遺傳算法優(yōu)化過程。算法從網(wǎng)絡(luò)動(dòng)力學(xué)角度分析了個(gè)體變異過程，提出基于網(wǎng)絡(luò)動(dòng)力學(xué)的變異操作啟發(fā)函數(shù)，用于指導(dǎo)變異操作，同時(shí)證明該啟發(fā)函數(shù)與優(yōu)化目標(biāo)函數(shù)（C函數(shù)）存在單調(diào)關(guān)系。

1 譜分析

矩陣的譜特性已經(jīng)被廣大學(xué)者深入研究，將其應(yīng)用到復(fù)雜網(wǎng)絡(luò)社區(qū)檢測(cè)中時(shí)，可以根據(jù)復(fù)雜網(wǎng)絡(luò)矩陣的譜特性揭示出復(fù)雜網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)［14］。復(fù)雜網(wǎng)絡(luò)通常使用圖G＝（V，E）來描述，其中V 表示網(wǎng)絡(luò)的節(jié)點(diǎn)集合，E 表示網(wǎng)絡(luò)中邊的集合。鄰接矩陣是圖的主要表示方法，當(dāng)使用鄰接矩陣A 描述圖時(shí)，Aij定義如下：

鄰接矩陣有多種擴(kuò)展形式，如標(biāo)準(zhǔn)拉普拉斯矩陣、規(guī)范化拉普拉斯矩陣、模塊化矩陣、關(guān)聯(lián)矩陣。本文只討論無權(quán)重?zé)o向網(wǎng)絡(luò)，采用規(guī)范化拉普拉斯矩陣［14］用于社區(qū)結(jié)構(gòu)檢測(cè)。規(guī)范化拉普拉斯矩陣定義為N ＝I－T，其中I為單位陣，T＝D－1A，D 為對(duì)角陣，Dii為節(jié)點(diǎn)i的度，A 為網(wǎng)絡(luò)鄰接矩陣。

定義1 假設(shè)λ1，…，λn是規(guī)范化拉普拉斯矩陣N 的n 個(gè)特征值，將特征值按遞增排序并去除重復(fù)的特征值得到一個(gè)遞增序列ω1，…，ωm（m ＜n），稱此序列為矩陣N 的譜，記為S（N）＝｛ω1，…，ωm｝。

定義2 S（N）為規(guī)范化拉普拉斯矩陣N 的譜，設(shè)ei＝ωi＋1－ωi，則ei稱為矩陣N 的第i個(gè)譜隙。

設(shè)定一個(gè)閾值ep，當(dāng)譜隙大于此閾值（即ei＞ep）時(shí)，認(rèn)為ei是一個(gè)有效譜隙，實(shí)際應(yīng)用中ep取值0.5［15］。將矩陣N 的有效譜隙按遞減順序排列，每個(gè)譜隙對(duì)應(yīng)一個(gè)社區(qū)尺度，譜隙的下標(biāo)值與網(wǎng)絡(luò)中社區(qū)的數(shù)量一致，由此得到了復(fù)雜網(wǎng)絡(luò)的多尺度社區(qū)結(jié)構(gòu)。多尺度社區(qū)結(jié)構(gòu)反映了網(wǎng)絡(luò)在傳播過程中的動(dòng)力學(xué)特征［11］，矩陣的譜分析方法可以有效地揭示出網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)。

算法1 多尺度社區(qū)結(jié)構(gòu)的算法

Input：網(wǎng)絡(luò)鄰接矩陣A，譜隙閾值ep，輸出列表中元素的數(shù)量m

Output：社區(qū)數(shù)量值列表L

1 T＝D－1A

2 N＝I－T

3 計(jì)算N 的特征值λ1…λn；

4 計(jì)算N 的譜隙e1…en－1；

5 對(duì)大于閾值ep的譜隙按遞減進(jìn)行排序，得到譜隙序列EP；

6 取EP中前m 個(gè)元素的下標(biāo)值放入到L中；

7 Return

2 HGASA 算法

2.1 編解碼

HGASA 算法采用字符串編碼方式［16］，每個(gè)字符串代表一個(gè)個(gè)體，每個(gè)字符位置代表節(jié)點(diǎn)，每個(gè)字符代表節(jié)點(diǎn)所屬的社區(qū)。Ii＝（Li1，Li2，…，Lin），Ii表示第i個(gè)個(gè)體，Lin表示第i個(gè)個(gè)體中第n個(gè)基因表達(dá)，這里表示節(jié)點(diǎn)n的社區(qū)標(biāo)識(shí)符。由上面的定義知，如果Lip＝Liq，則表明Ii所對(duì)應(yīng)的社區(qū)結(jié)構(gòu)中，節(jié)點(diǎn)p 與節(jié)點(diǎn)q 在同一個(gè)社區(qū)中。

2.2 群體初始化

遺傳算法在群體初始化時(shí)通常采用隨機(jī)生成個(gè)體的方式，這樣可以使初始群體具有多樣性。HGASA 算法中采用標(biāo)簽傳播［17］方法生成個(gè)體，初始時(shí)個(gè)體每個(gè)節(jié)點(diǎn)分配一個(gè)社區(qū)標(biāo)識(shí)符，然后經(jīng)過數(shù)次異步標(biāo)簽傳播產(chǎn)成個(gè)體。標(biāo)簽傳播方法的隨機(jī)性保障生成個(gè)體的多樣性，同時(shí)具有很高的效率。但是標(biāo)簽傳播方法生成個(gè)體的社區(qū)結(jié)構(gòu)具有不確定性，使個(gè)體需要較長(zhǎng)的進(jìn)化時(shí)間才能達(dá)到目標(biāo)狀態(tài)。標(biāo)簽傳播算法生成的個(gè)體雖然具有一定的社區(qū)結(jié)構(gòu)，但與社區(qū)檢測(cè)的目標(biāo)有一定的差距。HGASA 算法利用矩陣譜分析的結(jié)果作為標(biāo)簽傳播的約束條件，在標(biāo)簽傳播過程中控制個(gè)體中標(biāo)簽的數(shù)量與譜分析的結(jié)果一致，這樣個(gè)體生成時(shí)便具有了基本的社區(qū)結(jié)構(gòu)，從而保障后續(xù)優(yōu)化過程的效率和精度。

算法2 群體初始化算法

Input：個(gè)體包含社區(qū)的數(shù)量k，群體包含個(gè)體的數(shù)量m

Output：群體p

1 for i＝1to m

2 生成個(gè)體I；

3 While（個(gè)體I社區(qū)標(biāo)識(shí)數(shù)量＞k）

4 隨機(jī)選擇個(gè)體I的一個(gè)基因位置，進(jìn)行標(biāo)簽傳播操作；

5 將I加入到群體p中；

6 Return p

2.3 交叉操作

采用遺傳算法解決社區(qū)檢測(cè)問題時(shí)，交叉操作中有一定的特殊性，進(jìn)行交叉操作時(shí)要將一組關(guān)聯(lián)密切的基因交叉給下一代而不是個(gè)別基因，因此，不能采用傳統(tǒng)的單點(diǎn)、多點(diǎn)交叉方法，而是采用單路交叉、多路交叉。本文對(duì)Tasgin［16］提出的單路交叉算法進(jìn)行了改進(jìn)，稱為合并式單路交叉（One－way incorporating crossing）。改進(jìn)的目的是使交叉后新個(gè)體保留兩個(gè)父母?jìng)€(gè)體交叉位置的最大社區(qū)結(jié)構(gòu)特征。合并式單路交叉操作過程定義如下：設(shè)A、B是任意兩個(gè)體，A 作為源個(gè)體，B作為目的個(gè)體，CB（n）為個(gè)體B 中節(jié)點(diǎn)n 所屬社區(qū)的節(jié)點(diǎn)集合，CA（n）為個(gè)體A 中與節(jié)點(diǎn)n 在同一社區(qū)節(jié)點(diǎn)的集合，L 為初始狀態(tài)（每個(gè)節(jié)點(diǎn)一個(gè)社區(qū)）社區(qū)標(biāo)識(shí)符的集合，L（B）為個(gè)體B 中社區(qū)標(biāo)識(shí)符的集合，LB（n）為個(gè)體B 中節(jié)點(diǎn)n 的社區(qū)標(biāo)識(shí)符。進(jìn)行交叉操作時(shí)，首先在個(gè)體A 中選擇一個(gè)節(jié)點(diǎn)作為交叉位置，設(shè)節(jié)點(diǎn)n 被選為交叉位置；然后，在個(gè)體B 中所有包含于CB（n）∪CA（n）中的節(jié)點(diǎn)進(jìn)行交叉操作，對(duì)每個(gè)節(jié)點(diǎn)取一個(gè)不同于個(gè)體B 中現(xiàn)有標(biāo)簽進(jìn)行賦值，即LB（m）←L?m∈CB（n）∪CA（n）且L｛L－LB｝。

交叉操作如圖1 所示。在交叉后個(gè)體B 中標(biāo)簽6所代表的社區(qū)結(jié)構(gòu)繼承了個(gè)體A 與個(gè)體B的結(jié)構(gòu)特征。

圖1 交叉操作Fig.1 Cross operation

合并單路交叉能保留上一代個(gè)體的社區(qū)結(jié)構(gòu)特征，在新個(gè)體中社區(qū)結(jié)構(gòu)特征更加突出。

2.4 變異操作

對(duì)于復(fù)雜網(wǎng)絡(luò)社區(qū)檢測(cè)問題，遺傳算法通常采用隨機(jī)方式變異，變異操作缺乏必要的啟發(fā)信息，對(duì)于變異操作的進(jìn)化方向缺乏有效控制，從而使個(gè)體進(jìn)化速度緩慢，優(yōu)化效果不佳。基于上述原因，遺傳算法難以應(yīng)用于大規(guī)模網(wǎng)絡(luò)的社區(qū)檢測(cè)。本節(jié)針對(duì)復(fù)雜網(wǎng)絡(luò)社區(qū)檢測(cè)過程，構(gòu)建了局部動(dòng)力學(xué)啟發(fā)函數(shù)，以啟發(fā)變異操作進(jìn)化方向，并且證明啟發(fā)函數(shù)和HGASA 算法目標(biāo)函數(shù)單調(diào)，從而提高個(gè)體進(jìn)化速度和檢測(cè)精度。

HGASA 算法采用傳導(dǎo)率函數(shù)C（P）作為目標(biāo)函數(shù)，其定義如下：

式中：P 為復(fù)雜網(wǎng)絡(luò)的一個(gè)社區(qū)檢測(cè)結(jié)果，P ＝｛V1，…，Vk｝，其中k為社區(qū)個(gè)數(shù)，Vi表示第i個(gè)社區(qū)中的節(jié)點(diǎn)集合。

定義3 社區(qū)Vi的內(nèi)部度in＿vol（Vi）定義為

定義4 社區(qū)Vi的度vol（Vi）定義為vol（Vi）

從傳導(dǎo)率定義（式（2））可以看出，傳導(dǎo)率是每個(gè)社區(qū)分離概率的平均值，反映了復(fù)雜網(wǎng)絡(luò)中社區(qū)間傳播的能力，體現(xiàn)了復(fù)雜網(wǎng)絡(luò)的一種動(dòng)力學(xué)特征。傳導(dǎo)率越小，社區(qū)結(jié)構(gòu)劃分越合理。

命 題1 n 是 一 個(gè) 節(jié) 點(diǎn)，C 是 一 個(gè) 社 區(qū)，n ?C，n與C 中節(jié)點(diǎn)存在一條邊，當(dāng)節(jié)點(diǎn)n社區(qū)標(biāo)識(shí)符由l變化為l′時(shí)，社區(qū)C的內(nèi)部度in＿vol（C）不變化。

證明 如圖2所示，在圖2（a）中，n∈Vi，節(jié)點(diǎn)n與社區(qū)Vk中某一節(jié)點(diǎn)間存在一條邊。當(dāng)節(jié)點(diǎn)n由社區(qū)Vi劃分到Vj后，即Vi－｛n｝，Vj＋｛n｝，如圖2（b）所示，社區(qū)Vk的內(nèi)部度與外部度都沒有變化，所以命題1成立，證畢。

圖2 節(jié)點(diǎn)社區(qū)變化示意圖Fig.2 Community of node

命題1闡明了節(jié)點(diǎn)社區(qū)標(biāo)識(shí)變化和其相鄰社區(qū)內(nèi)部度的關(guān)系，在變異操作中性質(zhì)1表現(xiàn)為將一個(gè)節(jié)點(diǎn)由包含它的當(dāng)前社區(qū)分離，然后融入到與節(jié)點(diǎn)連接更緊密的相鄰社區(qū)。從網(wǎng)絡(luò)動(dòng)力學(xué)角度分析此過程，可以認(rèn)為是“社區(qū)標(biāo)識(shí)符”從鄰居社區(qū)傳遞到當(dāng)前節(jié)點(diǎn)過程，即節(jié)點(diǎn)i的社區(qū)標(biāo)識(shí)符由L（V（i））變?yōu)長(zhǎng)（V（j）），其中L（V（i））表示包含節(jié)點(diǎn)i的社區(qū)，L（V（i））表示節(jié)點(diǎn)i的社區(qū)標(biāo)識(shí)符。由于社區(qū)標(biāo)識(shí)符傳播導(dǎo)致復(fù)雜網(wǎng)絡(luò)社區(qū)劃分的傳導(dǎo)率發(fā)生變化。社區(qū)標(biāo)識(shí)符由一個(gè)社區(qū)傳播到相鄰社區(qū)邊緣節(jié)點(diǎn)時(shí)連接兩個(gè)社區(qū)間邊的數(shù)量發(fā)生變化，因此引入函數(shù)h（Ci，Cj）（簡(jiǎn)稱h 函數(shù)）評(píng)估兩個(gè)社區(qū)之間社區(qū)標(biāo)識(shí)符的傳播能力，其定義如下：

式中：Ci、Cj代表兩個(gè)相鄰的社區(qū)。

h（Ci，Cj）函數(shù)代表兩個(gè)相鄰社區(qū)的凝聚概率的平均值。當(dāng)社區(qū)標(biāo)識(shí)傳播達(dá)到穩(wěn)定狀態(tài)時(shí)，社區(qū)標(biāo)識(shí)符所表達(dá)的社區(qū)結(jié)構(gòu)是網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)。

命題2 當(dāng)社區(qū)數(shù)量不變時(shí)，傳導(dǎo)率函數(shù)C（P）與h（Vi，Vj）單調(diào)遞減，P 為一個(gè)分區(qū)，Vi、Vj為相鄰的社區(qū)，Vi∈P，Vj∈P，P ＝｛V1，…，Vk｝。

證明 設(shè)P 為一個(gè)社區(qū)劃分，P ＝｛V1，…，Vk｝，節(jié)點(diǎn)n∈Vi。社區(qū)標(biāo)識(shí)符通過網(wǎng)絡(luò)傳播，節(jié)點(diǎn)n當(dāng)前標(biāo)識(shí)符為L(zhǎng)（Vi），當(dāng)社區(qū)標(biāo)識(shí)符L（Vj）傳播至節(jié)點(diǎn)n時(shí)，引發(fā)社區(qū)劃分由P變?yōu)镻′，P′＝｛V′1，…，V′k｝。社區(qū)標(biāo)識(shí)符L（Vj）傳播到節(jié)點(diǎn)n后引起的函數(shù)h的增量如下：

由n 的社區(qū)標(biāo)識(shí)變化引起的傳導(dǎo)率函數(shù)C（P）的增量如下：

根據(jù)命題1 除社區(qū)Vi與Vj外其他社區(qū)有in＿vol（V′i）＝in＿vol（Vi），于是有：

綜上所述，C（P）與h（Ci，Cj）單調(diào)遞減，命題2成立。需要特別說明的是，命題2 中在社區(qū)標(biāo)識(shí)符傳遞的過程中不討論社區(qū)標(biāo)識(shí)符減少的情況，因?yàn)檫@種情況不滿足優(yōu)化目標(biāo)的要求。

從命題2 可知：傳導(dǎo)率函數(shù)C（P）與函數(shù)h（Vi，Vj）單調(diào)遞減，因此使用h（Vi，Vj）作為社區(qū)標(biāo)識(shí)符傳播的啟發(fā)信息，當(dāng)社區(qū)標(biāo)識(shí)符向著h（Vi，Vj）增大的方向傳播時(shí)，C（P）將變小，此時(shí)得到的社區(qū)結(jié)構(gòu)更優(yōu)良。

當(dāng)社區(qū)標(biāo)識(shí)符在網(wǎng)絡(luò)上傳播時(shí)，它到達(dá)的下一個(gè)節(jié)點(diǎn)與它在同一社區(qū)的概率最大?；诖吮疚奶岢鋈缦碌淖儺惙椒ǎ簩?duì)于個(gè)體I的第i個(gè)基因（即節(jié)點(diǎn)i被選擇進(jìn)行變異），節(jié)點(diǎn)i的鄰接社區(qū)標(biāo)識(shí)符集合為L(zhǎng)n（i），只需在Ln（i）中選擇一個(gè)社區(qū)標(biāo)識(shí)符，不需要考慮節(jié)點(diǎn)i的所有鄰居節(jié)點(diǎn)的社區(qū)標(biāo)識(shí)符，而是以h（Vi，Vj）作為啟發(fā)函數(shù)，選擇具有最大h 值的標(biāo)簽傳播到當(dāng)前節(jié)點(diǎn)。Li←arg maxL｛h（Vi，VL）L ∈Ln（i）｝。Li為節(jié)點(diǎn)i的社區(qū)標(biāo)識(shí)符。

算法3 基于h函數(shù)的局部啟發(fā)式變異算法（Local heuristic mutation algorithm，LHMA）

Input：待變異個(gè)體Ind，變異基因位置Pos

Output：變異后個(gè)體Ind

1 for k＝1to n ／／n為節(jié)點(diǎn)數(shù)量

2 List ＝NeiLabel（pos，Ind）／／求節(jié)點(diǎn)相鄰社區(qū)標(biāo)識(shí)符集合

3 m＝length（List） ／／計(jì)算隊(duì)列長(zhǎng)度

4 for i ＝1to m

5 t＝h（Vpos，VList［i］） ／／計(jì)算h函數(shù)

6 if（t＞max＿h(yuǎn)）

7 max＿h(yuǎn)＝t

8 L＝Label（VList［i］）

9 將Ind中pos位置基因變?yōu)長(zhǎng)

10 Return Ind

性質(zhì)1 LHMA 的時(shí)間復(fù)雜度為O（Cn）。

證明 假設(shè)網(wǎng)絡(luò)的社區(qū)數(shù)量為k，節(jié)點(diǎn)的平均外度為dout，網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量為n，對(duì)于個(gè)體I發(fā)生變異節(jié)點(diǎn)的概率為β。

設(shè)計(jì)算h函數(shù)的平均時(shí)間為t，每個(gè)節(jié)點(diǎn)直接相連外部社區(qū)數(shù)量為dout，則每個(gè)節(jié)點(diǎn)計(jì)算所有h函數(shù)的時(shí)間的最大值為O（doutt），總的時(shí)間復(fù)雜度為O（βdouttn）。將tdoutβ看作常數(shù)C，則LHMA的時(shí)間復(fù)雜度為O（Cn）。

2.5 HGASA 框 架

HGASA 的流程圖如圖3所示。算法首先對(duì)復(fù)雜網(wǎng)絡(luò)的拉普拉斯矩陣進(jìn)行譜分析，得到不同尺度下復(fù)雜網(wǎng)絡(luò)的社區(qū)數(shù)量；然后根據(jù)社區(qū)數(shù)量進(jìn)行群體初始化，得到具有特定尺度社區(qū)結(jié)構(gòu)的個(gè)體；最后使用局部啟發(fā)式變異算法與合并式單路交叉算法對(duì)群體進(jìn)行優(yōu)化，從而得到復(fù)雜網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)。HGASA 算法選擇在所有個(gè)體進(jìn)行完交叉或變異操作后進(jìn)行，將交叉和變異產(chǎn)生的新個(gè)體加入群體中，然后在新群體中選擇傳導(dǎo)率最小的個(gè)體作為下一代種群。

圖3 HGASA算法流程圖Fig.3 Flow diagram of HGASA

算法4 HGASA

Input：鄰接矩陣A，變異概率β，進(jìn)化代數(shù)L，種群數(shù)量I

Output：為社區(qū)檢測(cè)結(jié)果C

1 spectrumanalysis（A） ／／對(duì)矩陣進(jìn)行譜分析

2 Initialization（） ／／群體初始化

3 While（進(jìn)化代數(shù)＜L）

4 for i＝1to I

5 If rand（）＞β

6 LHMA（）；／／局部啟發(fā)式變異算法

7 Else

8 OWICA（）；／／合并式單路交叉算法

9 Select（）；／／選擇操作

10 C←社區(qū)檢測(cè)結(jié)果

11 Return C

性質(zhì)2 HGASA 算法的時(shí)間復(fù)雜度為O（Mn）。

證明 步驟1的時(shí)間復(fù)雜性為O（kn）。步驟2對(duì)于每個(gè)個(gè)體經(jīng)2～3次的標(biāo)簽傳播可以得到滿足要求的個(gè)體，步驟2時(shí)間復(fù)雜性為O（2In），步驟5 至 步 驟8 時(shí) 間 復(fù) 雜 度 為O（LβCn）。所 以HGASA 算 法 時(shí) 間 復(fù) 雜 度 為O（kn ＋2In ＋LβCn），即O（（k＋2I＋LβC）n），設(shè)k＋2I＋LC ＝M，所以算法時(shí)間復(fù)雜度為O（Mn）。

3 實(shí) 驗(yàn)

采用人工網(wǎng)絡(luò)和現(xiàn)實(shí)網(wǎng)絡(luò)對(duì)HGASA 的性能進(jìn)行測(cè)試。算法采用VC＋＋6.0、Matlab7.0在Windows XP 下實(shí)現(xiàn)。VC＋＋6.0實(shí)現(xiàn)遺傳算法部分，Matlab7.0實(shí)現(xiàn)矩陣分析。

HGASAd的主要參數(shù)有5 個(gè)，群體規(guī)模I、進(jìn)化代數(shù)G、個(gè)體變異概率α、個(gè)體基因發(fā)生變異的概率β和隙閾值ep。前四個(gè)參數(shù)是遺傳算法常用參數(shù)。第五個(gè)參數(shù)是用于控制譜隙的有效值，一般取0.5。實(shí)驗(yàn)采用召回率和精度來比較不同算法的分區(qū)結(jié)果。

3.1 人工網(wǎng)絡(luò)

目前人工生成網(wǎng)絡(luò)方法有多種，本文采用Lancichinetti［18］提出的方法進(jìn)行人工網(wǎng)絡(luò)生成。這種方法可以根據(jù)節(jié)點(diǎn)的度、社區(qū)尺寸等多種方式生成社區(qū)，使生成的網(wǎng)絡(luò)能夠更深入地檢查社區(qū)檢測(cè)方法的性能?；旌下蔒ix（0≤Mix≤1）是Lancichinetti方法控制網(wǎng)絡(luò)生成的重要參數(shù)，它反映了社區(qū)結(jié)構(gòu)的清晰程度，Mix越小網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)越清晰，反之社區(qū)結(jié)構(gòu)模糊。選擇GCE［19］、CPM［7］、COPRA［17］、EAGALE［6］作 為 對(duì) 比 算 法。從圖4可以看出：0.1≤Mix≤0.2時(shí)，網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)明顯，對(duì)比算法和HGASA 都有較高的召回率和準(zhǔn)確率，隨著Mix 增大網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)變得模糊，對(duì)比算法的準(zhǔn)確率和召回率顯著降低，但HGASA 仍可較好地發(fā)現(xiàn)社區(qū)結(jié)構(gòu)，說明HGASA 在檢測(cè)模糊社區(qū)結(jié)構(gòu)方面性能明顯優(yōu)于對(duì)比算法。

圖4 HGASA算法的召回率和準(zhǔn)確率Fig.4 Recall rate and precision of HGASA

3.2 現(xiàn)實(shí)網(wǎng)絡(luò)

HGASA 對(duì)現(xiàn)實(shí)世界網(wǎng)絡(luò)的檢測(cè)選用空手道俱樂部網(wǎng)絡(luò)和海豚網(wǎng)絡(luò)來進(jìn)行?？帐值谰銟凡烤W(wǎng)絡(luò)（Karate）［20］展示了美國(guó)一所大學(xué)空手道俱樂部34名成員間的社會(huì)關(guān)系，每個(gè)節(jié)點(diǎn)代表一名成員，兩個(gè)節(jié)點(diǎn)間有一條邊則意味著相應(yīng)的兩個(gè)成員之間是交往頻繁的朋友關(guān)系。用HGASA 對(duì)空手道俱樂部網(wǎng)絡(luò)進(jìn)行檢測(cè)的結(jié)果如圖5、圖6所示。圖5是空手道俱樂部網(wǎng)絡(luò)的譜隙，e2、e4是兩個(gè)譜隙，對(duì)應(yīng)的社區(qū)數(shù)量為2 和4。圖6 為HGASA 對(duì)空手道俱樂部網(wǎng)絡(luò)的檢測(cè)結(jié)果，此社區(qū)結(jié)構(gòu)與現(xiàn)實(shí)觀察的檢測(cè)結(jié)果一致。通過實(shí)驗(yàn)可以看到HGASA可以有效地檢測(cè)出Karate的多尺度社區(qū)結(jié)構(gòu)。

圖5 Karate網(wǎng)絡(luò)譜隙Fig.5 Spectral of Karate

圖6 Karate網(wǎng)絡(luò)的多尺度社區(qū)結(jié)構(gòu)Fig.6 Multiple－scale community structure of Karate

海豚網(wǎng)絡(luò)［21］是Lusseau通過對(duì)新西蘭神奇灣中62只不同性別海豚觀測(cè)而構(gòu)建的動(dòng)物社會(huì)網(wǎng)。網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)代表一只海豚，如果兩個(gè)海豚聯(lián)系密切，那么海豚對(duì)應(yīng)的頂點(diǎn)之間就會(huì)有一條邊連接。這些海豚被天然地分為雄性海豚組和雌性海豚組兩個(gè)社區(qū)。由圖7可以看到海豚網(wǎng)絡(luò)的e2、e5對(duì)應(yīng)兩個(gè)社區(qū)結(jié)構(gòu)。圖8（a）為海豚網(wǎng)絡(luò)對(duì)應(yīng)e2的社區(qū)結(jié)構(gòu)，海豚網(wǎng)絡(luò)被分成兩個(gè)大的社區(qū)，圖8（b）為海豚網(wǎng)絡(luò)對(duì)應(yīng)e5的社區(qū)結(jié)構(gòu)，可以看到在圖8（a）中右側(cè)社區(qū)又被細(xì)分為4個(gè)社區(qū)。

圖7 海豚網(wǎng)絡(luò)譜隙Fig.7 Spectra of dolphin

通過在人工網(wǎng)絡(luò)和現(xiàn)實(shí)網(wǎng)絡(luò)上對(duì)HGASA的測(cè)試可以看出，HGASA 具有較強(qiáng)的社區(qū)檢測(cè)能力，在社區(qū)結(jié)構(gòu)不明顯時(shí)仍有較好的檢測(cè)結(jié)果，并且可以有效地檢測(cè)出多尺度網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)。

圖8 海豚網(wǎng)絡(luò)多尺度社區(qū)結(jié)構(gòu)Fig.8 Multiple－scale community structure of dolphin

4 結(jié)束語

利用矩陣譜分析方法揭示出復(fù)雜網(wǎng)絡(luò)的多尺度特征，并且結(jié)合局部網(wǎng)絡(luò)動(dòng)力學(xué)啟發(fā)函數(shù)提出了遺傳算法HGASA。計(jì)算機(jī)生成網(wǎng)絡(luò)和現(xiàn)實(shí)網(wǎng)絡(luò)的測(cè)試結(jié)果表明，HGASA 可有效地檢測(cè)多尺度網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)。在后續(xù)的研究中，作者將進(jìn)一步研究多尺度社區(qū)結(jié)構(gòu)與網(wǎng)絡(luò)功能演化的關(guān)系。

［1］Girvan M，Newman M E J.Community structure in social and biological networks［J］.Proceedings of the National Academy of Sciences of the United States of America，2002，99（12）：7821－7826.

［2］Newman M E J.Fast algorithm for detecting community structure in networks［J］.Physical Review E，2004，69（6）：066133.

［3］Barber M J，Clark J W.Detecting network communities by propagating labels under constraints［J］.Physical Review E，2009，80（2）：026129.

［4］Liu D Y，Jin D，Baquero C，et al.Genetic algorithm with a local search strategy for discovering communities in complex networks［J］.International Journal of Computational Intelligence Systems，2013，6（2）：354－369.

［5］Newman M E J.Detecting community structure in networks［J］.European Physical Journal B，2004，38（2）：321－330.

［6］Shen H W，Cheng X Q，Cai K，et al.Detect overlapping and hierarchical community structure in networks［J］.Physica A：Statistical Mechanics and Its Applications，2009，388（8）：1706－1712.

［7］Palla G，Derenyi I，F(xiàn)arkas I，et al.Uncovering the overlapping community structure of complex networks in nature and society［J］.Nature，2005，435（7043）：814－818.

［8］Jin D，Yang B，Baquero C，et al.A Markov random walk under constraint for discovering overlapping communities in complex networks［J］.Journal of Statistical Mechanics－Theory and Experiment，2011（5）：P05031.

［9］Alex Arenas，Albert Diaz－Guilera，Conrad J.Synchronization reveals topological scales in complex networks［J］.Physical Review Letters，2006，96（11）：114102.

［10］Delvenne J C，Yaliraki S N，Barahona M.Stability of graph communities across time scales［J］.Proceedings of the National Academy of Sciences，2010，107（29）：12755－12760.

［11］Cheng X Q，Shen H W.Uncovering the community structure associated with the diffusion dynamics on networks［J］.Journal of Statistical Mechanics－Theory and Experiment，2010（4）：P04024，

［12］Fortunato S，Barthelemy M.Resolution limit in community detection［J］.Proceedings of the National Academy of Sciences，2007，104（1）：36－41.

［13］Arenas A，F(xiàn)ernandez A，Gomez S.Analysis of the structure of complex networks at different resolution levels［J］.New Journal of Physics，2008，10（5）：053039.

［14］Shen H W，Cheng X Q.Spectral methods for the detection of network community structure：a comparative analysis［J］.Journal of Statistical Mechanics－Theory and Experiment，2010（10）：P10020，

［15］Shen H W，Cheng X Q，Wang Y Z，et al.A dimensionality reduction framework for detection of multiscale structure in heterogeneous networks［J］.Journal of Computer Science and Technology，2012，27（2）：341－357.

［16］Tasgin M，Herdagdelen A，Bingol H.Community detection in complex networks using genetic algorithms［EB／OL］.［2013－07－08］.http：／／arxiv.org／abs／0711.0491.

［17］Gregory S.Finding overlapping communities in networks by label propagation［J］.New Journal of Physics，2010，12（10）：103018

［18］Lancichinetti A，F(xiàn)ortunato S，Radicchi F.Benchmark graphs for testing community detection algorithms［J］.Physical Review E，2008，78（4）：046110.

［19］Lee C，Reid F，Mcdaid A，et al.Detecting highly overlapping community structure by greedy clique expansion［EB／OL］.［2013－09－22］.http：／／arxiv.org／abs／1002.1827.

［20］Zachary W.An information flow modelfor conflict and fission in small groups1［J］.Journal of Anthropological Research，1977，33（4）：452－473.

［21］Lusseau D.The emergent properties of a dolphin social network［J］.Proceedings of the Royal Society of London Series B：Biological Sciences，2003，270（Suppl 2）：186－188.