郭玉泉，李雄飛，劉 昕

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

0 引 言

目前，對于網(wǎng)絡(luò)社區(qū)還沒有統(tǒng)一定義，通常認為社區(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)化目標，而最大化Q 函數(shù)是NP 完全問題，所以這些優(yōu)化算法都是近似的優(yōu)化算法。第二類是層次聚類方法，典型算法有EAGLE［6］和CPM［7］。層次聚類方法中樹狀圖生成與分割的時間復雜度都很高，因此層次聚類方法效率較低。第三類是網(wǎng)絡(luò)動力學方法，如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ò)動力學與譜方法的檢測算法。Alex等［9］利用同步過程與拉普拉斯矩陣譜檢測多尺度社區(qū)；Delvenne等［10］通過在時間尺度上社區(qū)穩(wěn)定性檢測多尺度社區(qū)；Cheng等［11］通過復雜網(wǎng)中傳播過程的穩(wěn)定狀態(tài)檢測多尺度社區(qū)。

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

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

1 譜分析

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

鄰接矩陣有多種擴展形式，如標準拉普拉斯矩陣、規(guī)范化拉普拉斯矩陣、模塊化矩陣、關(guān)聯(lián)矩陣。本文只討論無權(quán)重無向網(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 個特征值，將特征值按遞增排序并去除重復的特征值得到一個遞增序列ω1，…，ωm（m ＜n），稱此序列為矩陣N 的譜，記為S（N）＝｛ω1，…，ωm｝。

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

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

6 取EP中前m 個元素的下標值放入到L中；

7 Return

2 HGASA 算法

2.1 編解碼

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

2.2 群體初始化

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

4 隨機選擇個體I的一個基因位置，進行標簽傳播操作；

5 將I加入到群體p中；

6 Return p

2.3 交叉操作

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

交叉操作如圖1 所示。在交叉后個體B 中標簽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 變異操作

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

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

式中：P 為復雜網(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）

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

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

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

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

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

命題2 當社區(qū)數(shù)量不變時，傳導率函數(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ū)標識符通過網(wǎng)絡(luò)傳播，節(jié)點n當前標識符為L（Vi），當社區(qū)標識符L（Vj）傳播至節(jié)點n時，引發(fā)社區(qū)劃分由P變?yōu)镻′，P′＝｛V′1，…，V′k｝。社區(qū)標識符L（Vj）傳播到節(jié)點n后引起的函數(shù)h的增量如下：

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

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

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

算法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ū)標識符集合

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

4 for i ＝1to m

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

6 if（t＞max＿h）

7 max＿h＝t

8 L＝Label（VList［i］）

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

10 Return Ind

性質(zhì)1 LHMA 的時間復雜度為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），總的時間復雜度為O（βdouttn）。將tdoutβ看作常數(shù)C，則LHMA的時間復雜度為O（Cn）。

2.5 HGASA 框 架

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

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

算法4 HGASA

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

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

1 spectrumanalysis（A） ／／對矩陣進行譜分析

2 Initialization（） ／／群體初始化

3 While（進化代數(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 算法的時間復雜度為O（Mn）。

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

3 實 驗

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

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

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

目前人工生成網(wǎng)絡(luò)方法有多種，本文采用Lancichinetti［18］提出的方法進行人工網(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 都有較高的召回率和準確率，隨著Mix 增大網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)變得模糊，對比算法的準確率和召回率顯著降低，但HGASA 仍可較好地發(fā)現(xiàn)社區(qū)結(jié)構(gòu)，說明HGASA 在檢測模糊社區(qū)結(jié)構(gòu)方面性能明顯優(yōu)于對比算法。

圖4 HGASA算法的召回率和準確率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ò)來進行?？帐值谰銟凡烤W(wǎng)絡(luò)（Karate）［20］展示了美國一所大學空手道俱樂部34名成員間的社會關(guān)系，每個節(jié)點代表一名成員，兩個節(jié)點間有一條邊則意味著相應(yīng)的兩個成員之間是交往頻繁的朋友關(guān)系。用HGASA 對空手道俱樂部網(wǎng)絡(luò)進行檢測的結(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ū)又被細分為4個社區(qū)。

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

通過在人工網(wǎng)絡(luò)和現(xiàn)實網(wǎng)絡(luò)上對HGASA的測試可以看出，HGASA 具有較強的社區(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é)束語

利用矩陣譜分析方法揭示出復雜網(wǎng)絡(luò)的多尺度特征，并且結(jié)合局部網(wǎng)絡(luò)動力學啟發(fā)函數(shù)提出了遺傳算法HGASA。計算機生成網(wǎng)絡(luò)和現(xiàn)實網(wǎng)絡(luò)的測試結(jié)果表明，HGASA 可有效地檢測多尺度網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)。在后續(xù)的研究中，作者將進一步研究多尺度社區(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.