郭玉泉，李雄飛，劉 昕

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

0 引 言

目前，對于網(wǎng)絡(luò)社區(qū)還沒有統(tǒng)一定義，通常認(rèn)為社區(qū)是一個內(nèi)部連接緊密的節(jié)點集合，而該節(jié)點集合與網(wǎng)絡(luò)的其他部分連接稀疏。在現(xiàn)實網(wǎng)絡(luò)中，網(wǎng)絡(luò)社區(qū)表現(xiàn)出多尺度結(jié)構(gòu)特征，即在不同尺度下有不同的社區(qū)劃分結(jié)果。常用網(wǎng)絡(luò)社區(qū)檢測方法可以分為三類：第一類是基于優(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］。層次聚類方法中樹狀圖生成與分割的時間復(fù)雜度都很高，因此層次聚類方法效率較低。第三類是網(wǎng)絡(luò)動力學(xué)方法，如Jin等［8］提出的基于馬爾可夫方法的社區(qū)檢測方法。以上方法多數(shù)都是單一尺度的網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)檢測，不能檢測多尺度網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)。網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的多尺度特征是通過網(wǎng)絡(luò)傳播特性與譜特征來體現(xiàn)的，目前檢測都是采用基于網(wǎng)絡(luò)動力學(xué)與譜方法的檢測算法。Alex等［9］利用同步過程與拉普拉斯矩陣譜檢測多尺度社區(qū)；Delvenne等［10］通過在時間尺度上社區(qū)穩(wěn)定性檢測多尺度社區(qū)；Cheng等［11］通過復(fù)雜網(wǎng)中傳播過程的穩(wěn)定狀態(tài)檢測多尺度社區(qū)。

為評估社區(qū)檢測結(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ū)評價標(biāo)準(zhǔn)，傳導(dǎo)率函數(shù)從網(wǎng)絡(luò)動力學(xué)角度評價網(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ò)動力學(xué)角度分析了個體變異過程，提出基于網(wǎng)絡(luò)動力學(xué)的變異操作啟發(fā)函數(shù)，用于指導(dǎo)變異操作，同時證明該啟發(fā)函數(shù)與優(yōu)化目標(biāo)函數(shù)（C函數(shù)）存在單調(diào)關(guān)系。

1 譜分析

矩陣的譜特性已經(jīng)被廣大學(xué)者深入研究，將其應(yīng)用到復(fù)雜網(wǎng)絡(luò)社區(qū)檢測中時，可以根據(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é)點集合，E 表示網(wǎng)絡(luò)中邊的集合。鄰接矩陣是圖的主要表示方法，當(dāng)使用鄰接矩陣A 描述圖時，Aij定義如下：

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

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

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

設(shè)定一個閾值ep，當(dāng)譜隙大于此閾值（即ei＞ep）時，認(rèn)為ei是一個有效譜隙，實際應(yīng)用中ep取值0.5［15］。將矩陣N 的有效譜隙按遞減順序排列，每個譜隙對應(yīng)一個社區(qū)尺度，譜隙的下標(biāo)值與網(wǎng)絡(luò)中社區(qū)的數(shù)量一致，由此得到了復(fù)雜網(wǎng)絡(luò)的多尺度社區(qū)結(jié)構(gòu)。多尺度社區(qū)結(jié)構(gòu)反映了網(wǎng)絡(luò)在傳播過程中的動力學(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 計算N 的特征值λ1…λn；

4 計算N 的譜隙e1…en－1；

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

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

7 Return

2 HGASA 算法

2.1 編解碼

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

2.2 群體初始化

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

算法2 群體初始化算法

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

Output：群體p

1 for i＝1to m

2 生成個體I；

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

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

5 將I加入到群體p中；

6 Return p

2.3 交叉操作

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

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

圖1 交叉操作Fig.1 Cross operation

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

2.4 變異操作

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

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

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

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

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

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

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

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

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

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

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

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

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

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

由n 的社區(qū)標(biāo)識變化引起的傳導(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)識符傳遞的過程中不討論社區(qū)標(biāo)識符減少的情況，因為這種情況不滿足優(yōu)化目標(biāo)的要求。

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

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

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

Input：待變異個體Ind，變異基因位置Pos

Output：變異后個體Ind

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

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

3 m＝length（List） ／／計算隊列長度

4 for i ＝1to m

5 t＝h（Vpos，VList［i］） ／／計算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)長

10 Return Ind

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

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

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

2.5 HGASA 框 架

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

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

算法4 HGASA

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

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

1 spectrumanalysis（A） ／／對矩陣進(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ū)檢測結(jié)果

11 Return C

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

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

3 實 驗

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

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

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

目前人工生成網(wǎng)絡(luò)方法有多種，本文采用Lancichinetti［18］提出的方法進(jìn)行人工網(wǎng)絡(luò)生成。這種方法可以根據(jù)節(jié)點的度、社區(qū)尺寸等多種方式生成社區(qū)，使生成的網(wǎng)絡(luò)能夠更深入地檢查社區(qū)檢測方法的性能?；旌下蔒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］作 為 對 比 算 法。從圖4可以看出：0.1≤Mix≤0.2時，網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)明顯，對比算法和HGASA 都有較高的召回率和準(zhǔn)確率，隨著Mix 增大網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)變得模糊，對比算法的準(zhǔn)確率和召回率顯著降低，但HGASA 仍可較好地發(fā)現(xiàn)社區(qū)結(jié)構(gòu)，說明HGASA 在檢測模糊社區(qū)結(jié)構(gòu)方面性能明顯優(yōu)于對比算法。

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

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

HGASA 對現(xiàn)實世界網(wǎng)絡(luò)的檢測選用空手道俱樂部網(wǎng)絡(luò)和海豚網(wǎng)絡(luò)來進(jìn)行?？帐值谰銟凡烤W(wǎng)絡(luò)（Karate）［20］展示了美國一所大學(xué)空手道俱樂部34名成員間的社會關(guān)系，每個節(jié)點代表一名成員，兩個節(jié)點間有一條邊則意味著相應(yīng)的兩個成員之間是交往頻繁的朋友關(guān)系。用HGASA 對空手道俱樂部網(wǎng)絡(luò)進(jìn)行檢測的結(jié)果如圖5、圖6所示。圖5是空手道俱樂部網(wǎng)絡(luò)的譜隙，e2、e4是兩個譜隙，對應(yīng)的社區(qū)數(shù)量為2 和4。圖6 為HGASA 對空手道俱樂部網(wǎng)絡(luò)的檢測結(jié)果，此社區(qū)結(jié)構(gòu)與現(xiàn)實觀察的檢測結(jié)果一致。通過實驗可以看到HGASA可以有效地檢測出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通過對新西蘭神奇灣中62只不同性別海豚觀測而構(gòu)建的動物社會網(wǎng)。網(wǎng)絡(luò)中每個節(jié)點代表一只海豚，如果兩個海豚聯(lián)系密切，那么海豚對應(yīng)的頂點之間就會有一條邊連接。這些海豚被天然地分為雄性海豚組和雌性海豚組兩個社區(qū)。由圖7可以看到海豚網(wǎng)絡(luò)的e2、e5對應(yīng)兩個社區(qū)結(jié)構(gòu)。圖8（a）為海豚網(wǎng)絡(luò)對應(yīng)e2的社區(qū)結(jié)構(gòu)，海豚網(wǎng)絡(luò)被分成兩個大的社區(qū)，圖8（b）為海豚網(wǎng)絡(luò)對應(yīng)e5的社區(qū)結(jié)構(gòu)，可以看到在圖8（a）中右側(cè)社區(qū)又被細(xì)分為4個社區(qū)。

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

通過在人工網(wǎng)絡(luò)和現(xiàn)實網(wǎng)絡(luò)上對HGASA的測試可以看出，HGASA 具有較強(qiáng)的社區(qū)檢測能力，在社區(qū)結(jié)構(gòu)不明顯時仍有較好的檢測結(jié)果，并且可以有效地檢測出多尺度網(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ò)動力學(xué)啟發(fā)函數(shù)提出了遺傳算法HGASA。計算機(jī)生成網(wǎng)絡(luò)和現(xiàn)實網(wǎng)絡(luò)的測試結(jié)果表明，HGASA 可有效地檢測多尺度網(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.