小世界效應(yīng)加速生物地理學(xué)優(yōu)化的社團(tuán)識(shí)別算法

楊 波, 程維政, 朱 超

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

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

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

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

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

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

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

1 BBOSW

1.1 算法初始化

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

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

(1)

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

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

圖1 棲息地向量初始化

1.2 HSI函數(shù)選擇

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

(2)

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

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

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

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

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

(3)

(4)

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

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

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

圖3 遷移操作

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

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

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

圖4 棲息地信息交換模型

1.4 變異策略

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

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)

變異率的計(jì)算公式為

(6)

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

1.5 精英個(gè)體保留策略

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

E=αH.

(7)

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

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

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

2 實(shí)驗(yàn)及分析

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

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

(8)

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

2.1 參數(shù)選擇

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

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

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

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

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

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

表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 算法平均收斂時(shí)間比較

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

2.3 人工合成網(wǎng)絡(luò)實(shí)驗(yàn)

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

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

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

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

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

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

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

4 結(jié) 論

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

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

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

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