楊 波, 程維政, 朱 超

(武漢理工大學(xué) 自動化學(xué)院, 武漢 430070)

現(xiàn)實世界中許多的復(fù)雜系統(tǒng)都可以抽象為網(wǎng)絡(luò)模型，例如在社交網(wǎng)絡(luò)[1]中，每個人都是節(jié)點，人與人之間的關(guān)系是網(wǎng)絡(luò)中的邊；在交通網(wǎng)絡(luò)[2]中，每個交通樞紐是節(jié)點，交通路線是邊；在傳感器網(wǎng)絡(luò)[3]中，傳感器是節(jié)點，它們之間的通訊關(guān)系是邊；在電力網(wǎng)絡(luò)[4]中，電力器件是節(jié)點，器件的作用關(guān)系是邊等.

傳統(tǒng)數(shù)理方法很難分析這種研究對象眾多、作用關(guān)系復(fù)雜的問題，于是復(fù)雜網(wǎng)絡(luò)理論逐漸興起，并成為人們分析與研究復(fù)雜系統(tǒng)的工具. 復(fù)雜網(wǎng)絡(luò)中有一類中觀結(jié)構(gòu)，如社團結(jié)構(gòu)[5-6]、核心外圍結(jié)構(gòu)[7]等，研究這些中觀結(jié)構(gòu)有助于理解復(fù)雜系統(tǒng)本身的性質(zhì)和特點. 其中，社團結(jié)構(gòu)的識別是復(fù)雜網(wǎng)絡(luò)理論研究中的一項重要內(nèi)容. 社團是指在網(wǎng)絡(luò)中具有相似特征一類節(jié)點；或是在內(nèi)部連接比較緊密，與其他節(jié)點連接稀疏的一組節(jié)點[8].

網(wǎng)絡(luò)在社團結(jié)構(gòu)這一中觀尺度上所表現(xiàn)出來的動力學(xué)特性、結(jié)構(gòu)特性等和其在整體上所表現(xiàn)出來的特性相比差異很大，識別社團結(jié)構(gòu)可以幫助挖掘那些網(wǎng)絡(luò)中無法先驗得知的功能模塊，更好地分析復(fù)雜系統(tǒng). 例如尋找信息網(wǎng)絡(luò)屬于同一話題的信息、預(yù)測新陳代謝網(wǎng)絡(luò)中未知蛋白質(zhì)的功能、投放社交網(wǎng)站中的廣告、挖掘Web社區(qū)中的數(shù)據(jù)、調(diào)度并行計算中的子程序[9-10]等都可以歸為社團識別問題；社團結(jié)構(gòu)揭示了網(wǎng)絡(luò)的拓撲特點，能夠幫助解析復(fù)雜系統(tǒng)內(nèi)在的功能，分析復(fù)雜網(wǎng)絡(luò)的動力學(xué)特性. 故此，社團識別的研究具有重要的意義.

典型的社團識別算法整體上可作如下分類：基于網(wǎng)絡(luò)拓撲的識別算法，這類算法又可以分為分裂式算法和聚類式算法兩種，前者有譜劃分算法等，后者有CNM算法[10]、利用相似性測度的層次聚類算法等；基于信息論的社團識別算法，將社團識別轉(zhuǎn)化為信息論中的拓撲壓縮問題[11]，如基于隨機游走的識別算法；基于網(wǎng)絡(luò)動力學(xué)特性的識別算法，如基于一致性動力學(xué)的算法[12-15]；基于統(tǒng)計學(xué)的識別算法，如隨機塊模型[16]；基于優(yōu)化方法的直接尋優(yōu)識別算法，如基于遺傳算法[17]、貪婪算法、粒子群算法的識別算法[6]等.

生物地理學(xué)優(yōu)化(biogeography-based optimization, BBO)作為一種新穎的群體智能優(yōu)化方法，盡管相關(guān)研究尚處于起步階段，但由于其較好的全局搜索能力，使得其在高維問題上的表現(xiàn)超過了傳統(tǒng)優(yōu)化方法[18]. 另一方面，生物地理學(xué)優(yōu)化方法仍受限于進化優(yōu)化方法框架，普遍效率較低.

小世界效應(yīng)是現(xiàn)實網(wǎng)絡(luò)普遍具有的一種網(wǎng)絡(luò)結(jié)構(gòu)特征，典型的小世界網(wǎng)絡(luò)模型由于少數(shù)長程連邊的存在，使得網(wǎng)絡(luò)整體平均連通路徑長度顯著降低，從而具有超快的信息傳播能力[19-21]. 文獻[19]通過矩陣特征值方法發(fā)現(xiàn)在小世界網(wǎng)絡(luò)能夠?qū)崿F(xiàn)超快一致性動力學(xué)過程(ultrafast consensus dynamics). 而另一方面，群體智能進化算法普遍基于不同個體(例如遺傳算法中的染色體，蟻群算法中的螞蟻)之間的信息交換與信息共享，從而完成對解空間的搜索與尋優(yōu)過程[17]. 上述過程與網(wǎng)絡(luò)中的信息傳播過程[19-21]類似. 由于提出的群體智能算法需要在多個棲息地之間傳遞與搜索網(wǎng)絡(luò)社團結(jié)構(gòu)信息，受此兩者之間重要內(nèi)在關(guān)聯(lián)的啟發(fā)，提出了利用小世界效應(yīng)加速生物地理學(xué)優(yōu)化過程的網(wǎng)絡(luò)社團識別算法(biogeography-based optimization with small-world effects, BBOSW). 建立了網(wǎng)絡(luò)社團結(jié)構(gòu)識別問題的BBOSW方法與框架. 特別地，在棲息地之間的遷移操作建模中，利用具有小世界效應(yīng)的典型網(wǎng)絡(luò)模型來進行快速信息交換，從而建立了新穎的生物地理學(xué)優(yōu)化棲息地遷移過程的更新策略，大幅度提升了算法的社團結(jié)構(gòu)識別效率.

1 BBOSW

1.1 算法初始化

生物地理學(xué)方法的核心思想是通過模擬物種的產(chǎn)生、滅絕與遷移來實現(xiàn)數(shù)學(xué)問題的優(yōu)化[18]. BBO方法的生物模型為一組孤立的島嶼(棲息地)，物種在棲息地之間遷移尋找更好的生存環(huán)境. 用適宜度指數(shù)向量來描述棲息地的特征，向量中的每個值為棲息地的一個適宜度指數(shù)特征值(suitability index variable, SIV)，可以是降雨量、氣候、光照、地理環(huán)境等和生存相關(guān)的環(huán)境參數(shù). 棲息地適宜度指數(shù)向量SIVs組合在一起就構(gòu)成了區(qū)域矩陣X，其中矩陣每個棲息地的SIVs作為矩陣的行向量. 為了衡量棲息地適合物種生存的程度，引入與棲息地的物種多樣性程度相關(guān)聯(lián)的棲息地適應(yīng)度指數(shù)(habitat suitability index, HSI). 一般地，物種豐富的棲息地HSI值較大，但與此同時物種的生存壓力也較大，物種更傾向于遷入HSI值較低的棲息地去，使遷入后的棲息地物種多樣性增加，HSI值提高；如果遷入物種無法增加棲息地HSI值，則遷入的物種會趨于滅絕或是遷移到別的棲息地.

給定一個網(wǎng)絡(luò)G=(V,E)，V為網(wǎng)絡(luò)G節(jié)點集，E為網(wǎng)絡(luò)G邊集，節(jié)點數(shù)n=|V|，邊數(shù)m=|E|. 使用矩陣XH×n表示一組棲息地(解空間)，即

(1)

式中棲息地的數(shù)目為H. 矩陣X的行向量Xi表示一個棲息地，每個節(jié)點所屬的社團編號xij為棲息地SIV值，xij的值滿足1≤xij≤k(k為社團數(shù)，滿足1≤k?n).

圖1為一個簡單的初始化示例，網(wǎng)絡(luò)共有7個節(jié)點，在棲息地i最初的分配中，節(jié)點[1,3,7]被分配到社團1，剩下的節(jié)點被分配到社團2中. 棲息地i的初始化向量見圖1.

圖1 棲息地向量初始化

1.2 HSI函數(shù)選擇

適應(yīng)度函數(shù)的選擇關(guān)系到潛在解的進化方向，不同的適應(yīng)度函數(shù)對應(yīng)不同的優(yōu)化問題. 模塊度是最常用的衡量社團劃分結(jié)果好壞的標(biāo)準(zhǔn)，因此選擇的適應(yīng)度函數(shù)為模塊度函數(shù). 一般地，模塊度的值越高，表明社團劃分的結(jié)果越好. 模塊度Q的計算公式[22]為

(2)

式中：c為社團個數(shù)，M為網(wǎng)絡(luò)中總邊數(shù)，ls為社團s內(nèi)部總邊數(shù)，ds為社團s內(nèi)部所有節(jié)點的節(jié)點度之和.

1.3 應(yīng)用小世界效應(yīng)的遷移策略

BBO方法利用遷移規(guī)則來更新潛在解，保持解的多樣性，棲息地物種線性遷移模型見圖2.

圖2 棲息地物種線性遷移模型

從圖2中可以看到物種遷移行為分為遷入和遷出，Imax和Emax分別為最大遷入概率和最大遷出概率，在一個棲息地內(nèi)，隨著物種數(shù)的增加，遷出率逐漸升高，隨著棲息地物種數(shù)目達到最高Smax，遷出率也達到最高遷出率Emax. 遷入率變化與之相反，遷入率λ和遷出率μ的計算公式分別為

(3)

(4)

式中S為物種數(shù). 通常情況下，物種數(shù)量會在圖2中動態(tài)平衡點S0附近波動，物種數(shù)目一般處于[S1,S2].

遷移操作模型見圖3，圖中棲息地i發(fā)生遷移，遷移對象為棲息地j. 物種遷移后，棲息地的物種數(shù)目發(fā)生變化，棲息地i適宜度指數(shù)向量SIVs發(fā)生變化，其中適宜度指數(shù)特征SIV3的值(圖中為1)變化為遷移對象棲息地j中SIV3的值(圖中為2). 初始化時，給予每個棲息地一個初始物種數(shù)目，依據(jù)式(3)、(4)計算遷移發(fā)生的概率.

優(yōu)化類社團識別算法一般采用隨機更新規(guī)則，來確保解的多樣性，避免陷入局部最優(yōu)解，但隨之而來的問題是潛在解更新效率的低下. 在BBO方法中，發(fā)生遷移的棲息地由遷移率決定，信息交換效率同樣不高.

圖3 遷移操作

棲息地之間的遷移過程類似網(wǎng)絡(luò)中的信息交換，因此建立一個網(wǎng)絡(luò)模型來刻畫區(qū)域內(nèi)的棲息地的信息交換過程，每個棲息地看作網(wǎng)絡(luò)中的一個點，若是棲息地之間可以進行信息交換,則其對應(yīng)點之間存在一條邊. 選擇合適的網(wǎng)絡(luò)生成模型，既可以保證信息交換的充分性，同時也可以有效減少信息遍布整個區(qū)域的傳播時間.

小世界效應(yīng)是復(fù)雜網(wǎng)絡(luò)中普遍存在的一種現(xiàn)象. 具有該效應(yīng)的網(wǎng)絡(luò)模型具有較低的平均路徑，即使網(wǎng)絡(luò)規(guī)模較大，任兩個節(jié)點之間也可以通過少數(shù)幾個中間節(jié)點連接. 與其他網(wǎng)絡(luò)模型相比，在具有小世界效應(yīng)的網(wǎng)絡(luò)中信息的傳播速度很快[19]. 將這一效應(yīng)與遷移策略結(jié)合得到的新策略可以直接定向到達目的棲息地，在不影響解的多樣性的情況下，大幅度提高棲息地之間遷移操作的效率，降低算法最后收斂所需要的時間.

小世界拓撲網(wǎng)絡(luò)是利用小世界效應(yīng)產(chǎn)生的網(wǎng)絡(luò)模型，針對現(xiàn)存的小世界拓撲網(wǎng)絡(luò)生成模型，經(jīng)過實驗和對比，選擇小世界模型為NMW小世界拓撲網(wǎng)絡(luò)模型[23]，在社團識別算法初始化時，產(chǎn)生一個小世界網(wǎng)絡(luò)G0=(H,kn,p)，其中H為棲息地數(shù)目，kn為最近鄰網(wǎng)絡(luò)節(jié)點度，p為小世界連接概率. 為每個棲息地分配一個小世界網(wǎng)絡(luò)中的節(jié)點，遷移操作僅在兩個棲息地對應(yīng)的節(jié)點有連接時發(fā)生. 圖4中小世界網(wǎng)絡(luò)模型包含20個節(jié)點，其最近鄰網(wǎng)絡(luò)節(jié)點度為2，小世界連接概率為0.2. 該網(wǎng)絡(luò)對應(yīng)的棲息地數(shù)目為20. 將網(wǎng)絡(luò)中的節(jié)點按順時針方向編號，在每次迭代時，棲息地1對應(yīng)小世界網(wǎng)絡(luò)中的節(jié)點1. 若棲息地1和3，1和6之間都滿足遷移發(fā)生的條件，按照原遷移策略，遷移操作在兩組棲息地之間會都發(fā)生；而依據(jù)改進后的遷移策略，在小世界拓撲網(wǎng)絡(luò)中，節(jié)點1和3無連接，而節(jié)點1和6有連接，遷移操作只會在棲息地1和6之間發(fā)生.

圖4 棲息地信息交換模型

1.4 變異策略

除遷移操作外，變異操作也是BBO算法保持解的多樣性的重要一步，變異率和棲息地的HSI值密切相關(guān)，棲息地的HSI值較低，表明該棲息地不適應(yīng)物種生存，變異就越容易發(fā)生，以此來保證物種適應(yīng)該棲息地的環(huán)境[18]. 變異率的計算和Ps(一個棲息地含有物種數(shù)量恰好為s的概率)有關(guān). 令Ps(t)表示棲息地在時刻t具有物種數(shù)量s的概率，λs與μs分別表示當(dāng)棲息地具有物種數(shù)量s時對應(yīng)的遷入率與遷出率. 當(dāng)Δt充分小時，物種數(shù)量變化超過1的概率可以忽略. 在此條件下，要使棲息地在時刻t+Δt含有物種數(shù)量s，要么棲息地在時刻t含有物種數(shù)量s且Δt時間內(nèi)無遷移發(fā)生；要么棲息地在時刻t含有物種數(shù)量s-1且Δt時間內(nèi)發(fā)生1次遷入；要么棲息地在時刻t含有物種數(shù)量s+1且Δt時間內(nèi)發(fā)生1次遷出. 記o(Δt)為Δt的高階無窮小項，則概率Ps(t+Δt)的計算公式可寫為

Ps(t+ΔT)=Ps(t)(1-λsΔt-μsΔt)+

Ps-1(t)λs-1Δt+Ps+1(t)μx+1Δt+

o(Δt).

(5)

變異率的計算公式為

(6)

其中：M(Xi)為棲息地i的變異率；Mmax為最大變異率；Pmax為物種最大存在率，可以通過式(5)計算并排序得到. 當(dāng)發(fā)生物種變異時，棲息地適宜度指數(shù)向量發(fā)生變化，使用該棲息地的變異率選擇SIV. 當(dāng)滿足變異率條件時，改變該SIV值.

1.5 精英個體保留策略

因為變異操作和遷移操作的隨機性，在某一代進化中，棲息地也許會產(chǎn)生不可逆的變化，對應(yīng)現(xiàn)實環(huán)境中棲息地如果發(fā)生了惡劣的自然災(zāi)害，比如山洪爆發(fā)、地震、火山噴發(fā)等，環(huán)境原有的特性可能發(fā)生巨變，影響物種的遷移. 為此，算法同時提出了精英個體保留策略. 精英個體為具有高HSI的棲息地，在不影響解的多樣性的情況下，替換掉遷移和變異后較差的個體. 使用α表示解空間中精英個體的比例，則精英個體數(shù)目可表示為

E=αH.

(7)

1.6 算法復(fù)雜度分析

在該算法過程中，計算各棲息地適應(yīng)度函數(shù)值最為耗時. 因此該算法的時間復(fù)雜度為O(GeHm)，其中m為網(wǎng)絡(luò)連邊數(shù)，Ge為算法迭代次數(shù)參數(shù)，H為算法棲息地數(shù)目參數(shù).

BBOSW算法的空間復(fù)雜度與傳統(tǒng)BBO方法相比，增加了棲息地信息交換模型的臨時存儲空間. 該部分存儲空間與棲息地數(shù)目H和小世界網(wǎng)絡(luò)模型平均節(jié)點度ks有關(guān). 當(dāng)采用較為緊密的數(shù)據(jù)結(jié)構(gòu)存儲時(如邊列表)，空間復(fù)雜度為O(Hks)，而BBO方法空間復(fù)雜度為O(Hn). 因此在ks和H均遠小于n的情況下，BBOSW算法的空間復(fù)雜度增加不顯著.

2 實驗及分析

實驗主要是將提出的算法同以下幾類算法進行比較：1)基于模塊度的社區(qū)劃分算法，即FN算法[24]和確定性Louvain算法[25]；2)基于進化算法的社區(qū)劃分算法，即遺傳算法的社團識別算法(GA-net)[17,26]；3)基于圖的拓撲的社區(qū)劃分算法，即基于最小生成樹的社團識別算法(MST)[22].

同時使用模塊度Q和標(biāo)準(zhǔn)化互信息(normalized mutual information, NMI)[6,27-28]來衡量社團劃分結(jié)果.Q值越高意味著該劃分結(jié)果社團結(jié)構(gòu)越顯著，在拓撲連接上社團內(nèi)部更加緊密，模塊度的計算公式見式(2). NMI從信息論角度表征算法劃分結(jié)果與標(biāo)準(zhǔn)劃分之間的差異程度. 現(xiàn)實世界網(wǎng)絡(luò)標(biāo)準(zhǔn)劃分來源于對網(wǎng)絡(luò)中個體與連接性質(zhì)的觀察與統(tǒng)計，而合成網(wǎng)絡(luò)上的標(biāo)準(zhǔn)劃分源于網(wǎng)絡(luò)模型生成的內(nèi)部較為緊密的模塊. NMI值越高意味著兩組社團劃分間差異越小. NMI計算公式為

(8)

式中：A為標(biāo)準(zhǔn)社團劃分，B為算法識別到的社團劃分，CA、CB分別為兩個社團劃分中的社團個數(shù)，Ni.為標(biāo)準(zhǔn)劃分中第i個社團的節(jié)點數(shù)，N.j為算法識別到的第j個社團的節(jié)點數(shù)，Nij為社團i和j中相同節(jié)點數(shù)，log(·)為對數(shù)函數(shù).

2.1 參數(shù)選擇

一般而言，棲息地的數(shù)目H越高，解的多樣性越高，最終收斂的代數(shù)較低，但每次迭代需要的運行時間較長. 最大遷出率、最大遷入率以及變異率控制潛在社團劃分的更新頻率和程度，當(dāng)三者較高時，潛在解更新頻繁，且更新程度高，在搜索過程中不易陷入局部最優(yōu)值，但收斂所需要的迭代代數(shù)增加，運行時間增長.

小世界參數(shù)的設(shè)置決定遷移過程中信息交換的充分性，節(jié)點度和連接概率越高，信息交換越充分，但隨之而來的問題是遷移效率低下. 精英個體的保留比例不宜過高，過高的精英個體比例會影響解的多樣性，使迭代過程陷于局部最優(yōu).

根據(jù)前期實驗結(jié)果選取的典型參數(shù)如下：棲息地數(shù)目H=50，最大遷入率Imax=1，最大遷出率Emax=1，最大變異率Mmax=0.05，精英個體比例α=4%，迭代次數(shù)Ge=500，最近鄰網(wǎng)絡(luò)節(jié)點度kn=4，小世界連接概率p=0.2.

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

用于實驗的數(shù)據(jù)集有空手道俱樂部Karate網(wǎng)絡(luò)[29]，海豚社區(qū)Dolphins網(wǎng)絡(luò)[30]和美國政治書Books網(wǎng)絡(luò)[31]. 實驗結(jié)果見表1～4，其中BBO為沒有采用新策略的社團識別算法，BBOSW為采用結(jié)合了小世界效應(yīng)遷移策略的社團識別算法. 在表1～3中，針對進化算法，同時記錄評價指標(biāo)的平均值與最優(yōu)值；針對其他算法，記錄評價指標(biāo)的最優(yōu)值. avgQ、avg NMI分別為模塊度和標(biāo)準(zhǔn)化互信息的均值；bestQ、best NMI分別為模塊度和標(biāo)準(zhǔn)化互信息的最優(yōu)值. 實驗環(huán)境為MATLAB R2010a，CPU運行主頻為2.99 GHz，運行內(nèi)存為4.0 GB.

從表1～3(算法在每個網(wǎng)絡(luò)上運行100次)中可以看到，所提出算法的識別效果與經(jīng)典算法相近. 在Karate網(wǎng)絡(luò)上，BBOSW的平均NMI和最佳NMI高于其他算法；在Dolphins網(wǎng)絡(luò)和Books網(wǎng)絡(luò)上的平均模塊度Q、平均NMI以及最佳模塊度Q都要優(yōu)于其他算法. 從表4(算法在每個現(xiàn)實網(wǎng)絡(luò)上運行30次)中可以看到，采用改進策略的BBOSW算法的平均所需收斂時間得到減少.

表1 Karate網(wǎng)絡(luò)上的模塊度和標(biāo)準(zhǔn)化互信息比較

Tab.1 Comparison between values ofQand NMI in the Karate club network

算法best Qbest NMIavg Qavg NMIBBO0.4200.8370.3990.558BBOSW0.4201.0000.3960.681GA-net0.4150.7070.4000.648MST0.4160.602FN0.3810.693Louvain0.4190.859

表2 Dolphins網(wǎng)絡(luò)上的模塊度和標(biāo)準(zhǔn)化互信息比較

Tab.2 Comparison between values ofQand NMI in the Dolphins network

算法best Qbest NMIavg Qavg NMIBBO0.5270.6970.5050.543BBOSW0.5270.6970.5110.546GA-net0.4910.4670.4290.401MST0.5020.514FN0.4920.621Louvain0.5190.766

表3 Books網(wǎng)絡(luò)上的模塊度和標(biāo)準(zhǔn)化互信息比較

Tab.3 Comparison between values ofQand NMI in the Books network

算法best Qbest NMIavg Qavg NMIBBO0.5270.5770.5060.478BBOSW0.5270.5770.5060.479GA-net0.4770.4480.4280.406MST0.5190.584FN0.5020.531Louvain0.4990.575

表4 算法平均收斂時間比較

進化算法普遍采用矩陣編碼的方式進行算法的初始化，依據(jù)算法的特點不同，采用的矩陣編碼方式不同，最終算法的收斂時間不同. 一般而言，在高維問題上，BBO方法的表現(xiàn)要好于其他優(yōu)化算法[18]，即未采用改進策略的BBO社團識別算法與其他進化算法性能相近或優(yōu)于其他進化算法，如遺傳算法等. 實驗結(jié)果表明，基于小世界效應(yīng)加速生物地理學(xué)優(yōu)化的網(wǎng)絡(luò)社團識別算法可以有效提高社團識別效率.

2.3 人工合成網(wǎng)絡(luò)實驗

使用計算機合成網(wǎng)絡(luò)(GN網(wǎng)絡(luò))來驗證算法效果[32]，實驗結(jié)果見圖5. 同其他算法相比(對于每個節(jié)點社團外度Zout生成20個隨機網(wǎng)絡(luò)，算法在每個網(wǎng)絡(luò)上均運行30次)，當(dāng)Zout較小時，網(wǎng)絡(luò)社團結(jié)構(gòu)明顯，模塊度較高，此時各算法識別效果相差不大. 隨著Zout增加，模塊度較低，網(wǎng)絡(luò)社團結(jié)構(gòu)逐漸不明顯，各算法識別效果都下降. 當(dāng)Zout較大時,新算法的識別能力要優(yōu)于其他算法. 優(yōu)化類算法采用直接尋優(yōu)的方式尋找社團劃分，對網(wǎng)絡(luò)拓撲變化不敏感. 在社團結(jié)構(gòu)不明顯的情況下，BBOSW算法識別效果優(yōu)于或近似于測試的其他算法.

圖5 GN網(wǎng)絡(luò)識別效果

3 科學(xué)家合作網(wǎng)絡(luò)上的社團結(jié)構(gòu)識別

為了驗證BBOSW在實際網(wǎng)絡(luò)中的效果，將算法應(yīng)用到一個具有1 589個節(jié)點，2 742條邊的科學(xué)家合作網(wǎng)絡(luò)(netscience network)上. 該網(wǎng)絡(luò)描述了復(fù)雜網(wǎng)絡(luò)科學(xué)家之間的合作關(guān)系[8]. 其中，每位學(xué)者都被抽象為一個節(jié)點，若是兩位學(xué)者之間有過合作關(guān)系，則這兩個節(jié)點之間存在一條連邊.

科學(xué)家合作網(wǎng)絡(luò)是一個具有較大規(guī)模的非連通網(wǎng)絡(luò)，其包含多個連通片及大量孤立節(jié)點，這些復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)特性為社團結(jié)構(gòu)的探測與識別提出了嚴(yán)峻的挑戰(zhàn). 將不同算法應(yīng)用于該網(wǎng)絡(luò). MST算法需要利用連通網(wǎng)絡(luò)的最小生成樹結(jié)構(gòu)分析網(wǎng)絡(luò)社團特征，而非連通網(wǎng)絡(luò)無法生成該算法所需的最小生成樹. 因此該算法應(yīng)用范圍僅局限于連通網(wǎng)絡(luò)，其無法應(yīng)用于科學(xué)家合作網(wǎng)絡(luò). GA-net算法使用Locus-based初始化方法，然而該方法無法完成孤立節(jié)點的初始化. 因為上述局限性，GA-net算法亦無法解決科學(xué)家合作網(wǎng)絡(luò)的社團結(jié)構(gòu)識別問題. FN算法采用局部貪婪優(yōu)化策略. 該算法在迭代過程中需要遍歷所有使模塊度上升的可能. 科學(xué)家合作網(wǎng)絡(luò)包含的多連通片及大量孤立節(jié)點使得算法探測到的社團個數(shù)長期維持在較高水平，因此需要合并的社團數(shù)目無法快速下降，從而導(dǎo)致算法運行效率很低，在超過24 h后依然無法完成運算(CPU運行主頻2.99 GHz，運行內(nèi)存4.0 GB)，因此FN算法無法有效識別復(fù)雜的包含多連通片及大量孤立節(jié)點的較大規(guī)模非連通網(wǎng)絡(luò)的社團結(jié)構(gòu). 對于社團結(jié)構(gòu)未知的較大規(guī)?，F(xiàn)實網(wǎng)絡(luò)(比如科學(xué)家合作網(wǎng)絡(luò))，Louvain算法應(yīng)選擇初始聚合的網(wǎng)絡(luò)社團結(jié)構(gòu)作為算法的運行結(jié)果[33]. 將確定性Louvain算法應(yīng)用于科學(xué)家合作網(wǎng)絡(luò)得到的網(wǎng)絡(luò)社團結(jié)構(gòu)對應(yīng)的模塊度為0.875. BBOSW算法是隨機算法，受隨機波動影響. 經(jīng)過10次重復(fù)實驗，BBOSW算法得到的平均模塊度為0.867，標(biāo)準(zhǔn)差為0.005，最佳模塊度為0.879. 綜上所述，盡管現(xiàn)實世界中的科學(xué)家合作網(wǎng)絡(luò)所具有的多連通片及大量孤立節(jié)點特性使得社團結(jié)構(gòu)探測非常困難，BBOSW算法和Louvain算法仍然能夠?qū)ζ溥M行有效且高質(zhì)量的社團結(jié)構(gòu)識別，兩種算法得到的模塊度相似.

根據(jù)隨機選取的BBOSW單次實驗結(jié)果繪制出科學(xué)家合作網(wǎng)絡(luò)拓撲及其社團劃分見圖6, 其對應(yīng)的模塊度為0.865. BBOSW算法將網(wǎng)絡(luò)劃分成44個社團. 選擇22和23號社團分析拓撲結(jié)構(gòu)(分別包含21個節(jié)點和7個節(jié)點)，在查閱相關(guān)節(jié)點對應(yīng)的學(xué)者具體情況(22號社團對應(yīng)節(jié)點標(biāo)號646、1 430～1 449，MANSFIELD T等所在課題組；23號社團對應(yīng)節(jié)點標(biāo)號1515、1505～1510，SALAFF J等所在的研究小組)后，發(fā)現(xiàn)社團內(nèi)部的研究人員分別處于同一研究小組. 22號社團學(xué)者的研究方向主要是生物和復(fù)雜網(wǎng)絡(luò)的結(jié)合(發(fā)表多項關(guān)于蛋白質(zhì)網(wǎng)絡(luò)特性的研究成果)，23號社團學(xué)者主要研究方向為社會網(wǎng)絡(luò)，其社團內(nèi)部的學(xué)者互相之間合作緊密. 新算法識別到的社團為現(xiàn)實世界中存在的研究小組，表明新算法可以有效進行社團探測與識別.

圖6 由網(wǎng)絡(luò)科學(xué)家構(gòu)成的合作網(wǎng)絡(luò)的劃分實驗結(jié)果

4 結(jié) 論

1)利用小世界效應(yīng)加速優(yōu)化算法，提出了一種新的社團識別算法. 該算法利用BBO方法具有較強全局搜索能力的特點，初始化一個隨機解空間，利用遷移和變異操作來更新個體，保證解的多樣性，直接在潛在解中尋找最大化模塊度的社團劃分.

2)結(jié)合小世界效應(yīng)，利用具有小世界效應(yīng)的拓撲網(wǎng)絡(luò)具有較快信息傳播速度的特點，建模棲息地之間遷移的過程，在保證解的多樣性的情況下，來加快算法收斂的過程.

3)使用現(xiàn)實網(wǎng)絡(luò)以及人工合成網(wǎng)絡(luò)測試算法效果，并與主流算法進行比較. 實驗結(jié)果表明所提出的算法精度較高，尤其對于社團結(jié)構(gòu)較為模糊的網(wǎng)絡(luò)，識別效果較好.

4)將來的工作是利用小世界效應(yīng)的性質(zhì)來加速其他群體智能算法，將這種新策略擴展至其他算法中.