融入武裝部隊的鯨魚優(yōu)化算法用于社區(qū)發(fā)現(xiàn)

摘 要：針對于鯨魚優(yōu)化算法（WOA）多樣性不足、兩搜索階段信息交流效率低、不平衡的問題，這里借用武裝部隊協(xié)同作戰(zhàn)機理，提出一種新的WOA用于社區(qū)發(fā)現(xiàn)。為解決包圍捕食階段多樣性不足的問題，引入“鄰居潛力”學(xué)習(xí)模型，提高WOA的全局搜索能力和學(xué)習(xí)廣度；為解決兩捕食階段信息交流效率的低問題，提出鯨魚指揮官領(lǐng)導(dǎo)的氣泡網(wǎng)捕食，確保搜索信息能有效利用；為解決兩種捕食機制不平衡的問題，采用改進的學(xué)習(xí)自動機引導(dǎo)鯨魚種群向有希望區(qū)域移動。同時，考慮到復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)是離散問題，提出了一種基于拓?fù)涮匦缘男戮幋a離散演化規(guī)則。最后，通過真實數(shù)據(jù)集測試并與其他算法比較，結(jié)果表明，該算法相較于對比算法具有更優(yōu)的尋優(yōu)能力，驗證了算法的有效性。

關(guān)鍵詞：復(fù)雜網(wǎng)絡(luò)； 社區(qū)發(fā)現(xiàn)； 群體智能； 鯨魚優(yōu)化； 部隊協(xié)同

中圖分類號：TP391文獻標(biāo)志碼： A文章編號：1001－3695（2024）04－019－1086－08

doi：10.19734/j.issn.1001－3695.2023.08.0368

Whale optimization algorithm incorporating armed forcescollaboration for community discovery

Zhang Qiwen， Guan Dingkun

Abstract： Aiming at the problems of insufficient diversity of whale optimization algorithm（WOA）， inefficient and unbalanced information exchange between the two search phases， this paper proposed an improved WOA based on the armed forces collaborative warfare mechanism for community discovery. In order to solve the problem of insufficient diversity in the encircling predation stage， this paper developed a “neighbor potential” learning model to improve the global search capability and learn breadth of WOA. To solve the problem of inefficient information exchange during the two－predation phase， this paper proposed bubble net predation based on whale commanders， which could ensure effective utilization of search information. To address the imbalance between the two predation mechanisms， this paper proposed an improved learning automaton， which could guide whale populations toward promising areas. Meanwhile， because community discovery in complex networks is a discrete problem， this paper proposed a new coded discrete evolution rule based on topological properties. Finally， this paper tested the proposed algorithms on real data sets and compared them with other algorithms， and simulation experiments show that the proposed algorithm has better optimization ability than the comparison algorithm， verifying the effectiveness of the improved strategy.

Key words：complex networks; community discovery; swarm intelligence; whale optimization; force collaboration

0 引言

在復(fù)雜網(wǎng)絡(luò)中，準(zhǔn)確識別社區(qū)結(jié)構(gòu)能夠挖掘出其中重要的結(jié)構(gòu)信息和潛藏的內(nèi)容。社區(qū)發(fā)現(xiàn)在流行病的傳播控制［1］、微博的個性化推薦［2］以及蛋白質(zhì)網(wǎng)絡(luò)的挖掘［3］等多個領(lǐng)域中扮演著重要的角色，因此其具有重要意義和廣泛的應(yīng)用前景。

在過去幾年中，許多不同的社區(qū)發(fā)現(xiàn)方法被提出。常見的算法有基于標(biāo)簽傳播的方法，如Raghavan等人［4］提出的基于標(biāo)簽傳播的社區(qū)發(fā)現(xiàn)方法；基于圖分解、分裂的算法，如聚類（GN）算法［5］、譜方法［6］;基于深度學(xué)習(xí)的方法，如楊亮等人［7］將拉普拉斯矩陣替換模塊度矩陣進行訓(xùn)練得到社區(qū)劃分；基于優(yōu)化的方法，如Newman等人［8］定義了模塊度函數(shù)，用于評價社區(qū)劃分?；趦?yōu)化的方法是通過優(yōu)化目標(biāo)函數(shù)得到社區(qū)劃分，但是實現(xiàn)最優(yōu)目標(biāo)往往是NP難問題［9］，利用智能優(yōu)化算法選擇合適的啟發(fā)式規(guī)則可以取得較好的近似優(yōu)化結(jié)果。

目前，基于智能優(yōu)化算法的社區(qū)發(fā)現(xiàn)方法主要分為兩大類，第一類基于進化算法的社區(qū)發(fā)現(xiàn)方法。如Behera等人［10］提出了一種基于遺傳算法的社區(qū)發(fā)現(xiàn)算法（GA－BCD），利用網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)計算節(jié)點間的相似性指數(shù)，并構(gòu)建相似度矩陣，從而設(shè)計新的目標(biāo)函數(shù)。雖然以此作為評價指標(biāo)在社區(qū)劃分上取得了一定效果，但基于模塊化的特性，結(jié)果不穩(wěn)定且易陷入局部最優(yōu)。Zhang等人［11］設(shè)計了拉馬克學(xué)習(xí)規(guī)則，建立了拉馬克遺傳算法的框架，并在社區(qū)劃分結(jié)果中證明了其良好的收斂性能和局部搜索能力。Zhou等人［12］提出了一種基于蟻群的重疊社區(qū)發(fā)現(xiàn)算法（AntCBO），借用螞蟻在信息素引導(dǎo)下行走的思想，提出一種在螞蟻運動指導(dǎo)下更新每個節(jié)點中存儲的標(biāo)簽列表的策略，實驗表明，在重疊社區(qū)發(fā)現(xiàn)方面，該算法取得了出色效果。因此，雖然進化算法在部分網(wǎng)絡(luò)上取得較好效果，但是它們?nèi)源嬖谝恍┤秉c，如收斂速度慢且受到分辨率限制等問題的制約。第二類是基于群體智能優(yōu)化算法的社區(qū)發(fā)現(xiàn)方法。群智能優(yōu)化算法由于其穩(wěn)定、搜索能力強和可解釋性強的優(yōu)點，近來也成為了社區(qū)發(fā)現(xiàn)領(lǐng)域研究的熱點。如Liu等人［13］將果蠅優(yōu)化算法應(yīng)用于社區(qū)發(fā)現(xiàn)，提出了一種新的多種群果蠅優(yōu)化社區(qū)發(fā)現(xiàn)算法（CDMFOA），該算法通過引入多種群策略，提高了全局并行搜索能力，同時引入爬山搜索策略來解決過早收斂的問題。鯨魚優(yōu)化算法（WOA）是近年來提出并迅速蓬勃發(fā)展的一種新算法，該算法以模擬鯨魚覓食行為為基礎(chǔ)，憑借其強大的全局搜索能力，在解決社區(qū)發(fā)現(xiàn)等優(yōu)化問題上作出了巨大的貢獻。如Feng等人［14］通過模擬座頭鯨的狩獵行為，巧妙地結(jié)合了社團網(wǎng)絡(luò)的強內(nèi)聚和弱耦合的拓?fù)浣Y(jié)構(gòu)特征，提出了一種新的離散化搜索策略的社區(qū)發(fā)現(xiàn)算法（EP－WOCD），同時，他們引入了進化種群動力學(xué)機理，來動態(tài)調(diào)整鯨魚種群的大小，以解決時間復(fù)雜度高的問題。Zhang等人［15］提出了一種基于標(biāo)簽傳播的收縮包圍操作社區(qū)發(fā)現(xiàn)算法（WOCDA），將當(dāng)前節(jié)點的標(biāo)簽更新為其最近鄰節(jié)點的標(biāo)簽，然后通過單向交叉算子建立螺旋更新操作以確保社區(qū)的良好連接，為了獲得高質(zhì)量的初始解，提出了基于標(biāo)簽擴散和傳播的初始化策略。Nadimi－shahraki等人［16］提出了基于饑餓搜索的鯨魚優(yōu)化算法（DMFO－CD）用于社區(qū)劃分，將饑餓的概念與座頭鯨的覓食策略相結(jié)合，在改進的算法中，WOA探測能力低、收斂速度慢和陷入局部解等問題得到了緩解。

雖然以往研究者使用WOA在社區(qū)發(fā)現(xiàn)方面已經(jīng)取得了較好的成果，但是WOA在搜索過程中存在多樣性下降、信息交流效率低的問題。因此在本文中，借用武裝部隊協(xié)同作戰(zhàn)的機理，提出了一種新的WOA用于社區(qū)劃分。針對包圍捕食階段多樣性不足的問題，提出“鄰居潛力”學(xué)習(xí)模型，用于提高WOA的全局搜索能力，增加學(xué)習(xí)的廣度；針對兩捕食階段信息交流效率低導(dǎo)致搜索性能低的問題，提出了鯨魚指揮官領(lǐng)導(dǎo)的氣泡網(wǎng)捕食，以確保搜索信息得到有效利用；針對兩種捕食機制不平衡的問題，采用一種改進的學(xué)習(xí)自動機來自適應(yīng)引導(dǎo)鯨魚部隊向有希望的區(qū)域移動， 同時，考慮到復(fù)雜網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)是離散問題， 提出了一種基于拓?fù)浣Y(jié)構(gòu)的新編碼離散演化規(guī)則。

1 基礎(chǔ)知識介紹

1.1 鯨魚優(yōu)化算法

鯨魚的捕食行為主要分為三類：包圍捕食、螺旋氣泡網(wǎng)捕食［17］和隨機搜索獵物。其數(shù)學(xué)模型如下：

a）包圍捕食。

在該階段中，座頭鯨識別獵物的位置并包圍。起初以當(dāng)前最優(yōu)作為獵物位置，其他座頭鯨根據(jù)它更新公式為

其中：M為網(wǎng)絡(luò)中邊的總數(shù)； A ij代表網(wǎng)絡(luò)的鄰接矩陣；Ki代表節(jié)點i的度，當(dāng)節(jié)點i和j屬于同一個社區(qū)時，δ（Ci，Cj）取1，否則取0。模塊度Q在［0，1］，Q的值越大，說明網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)越明顯，因此衡量社區(qū)的最優(yōu)劃分，就是尋找Q值最大化的一種劃分方式。

2 融入武裝部隊的離散WOA用于社區(qū)發(fā)現(xiàn)

新版《中國人民解放軍軍語》對“協(xié)同”進行了如下定義［19］：各作戰(zhàn)力量共同遂行任務(wù)時，在行動上協(xié)調(diào)配合。本研究將武裝部隊的協(xié)同作戰(zhàn)機理融入WOA。其中，WOA的包圍捕食和氣泡網(wǎng)捕食對應(yīng)于偵查部隊和特種部隊的作戰(zhàn)機理，基于此，在兩個捕食階段進行建模，以實現(xiàn)協(xié)同捕食的目的。

2.1 社區(qū)的編碼和初始化

常見的編碼方法有鄰節(jié)點編碼［14］和標(biāo)簽編碼［20］兩種方式。在本研究中，為了增加初始種群的多樣性，采用鄰節(jié)點編碼。初始化利用節(jié)點的連接關(guān)系進行初始化，相較于隨機初始化產(chǎn)生的種群，這樣的初始化能夠得到一個高質(zhì)量的初始種群。基于鄰居節(jié)點初始化是指每個基因i所對應(yīng)的基因值只能是節(jié)點Vi的鄰居節(jié)點集中某個鄰居節(jié)點編號。也就是說，如果第j個基因位的取值為j，那么節(jié)點Vi和節(jié)點Vj在真實網(wǎng)絡(luò)中一定存在連邊。在基于鄰居節(jié)點初始化策略以后，此時所有基因值表示的是節(jié)點之間的連接關(guān)系。

2.2 基于“偵查部隊”的離散化包圍捕食

在本節(jié)中，致力于解決WOA在包圍捕食階段存在的學(xué)習(xí)對象單一、多樣性不足的問題。這種情況往往會導(dǎo)致陷入局部最優(yōu)解，進而影響社區(qū)劃分的準(zhǔn)確度。因此，目標(biāo)是通過借鑒偵查部隊的作戰(zhàn)機理，設(shè)計一種“鄰居潛力”個體以增加學(xué)習(xí)的多樣性。具體實施時，根據(jù)網(wǎng)絡(luò)節(jié)點和連邊的拓?fù)浣Y(jié)構(gòu)特征對“鄰居潛力”進行建模。這樣設(shè)計的理由在于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)能夠準(zhǔn)確地反映節(jié)點間的實際連接關(guān)系，從而實現(xiàn)更準(zhǔn)確高效的社區(qū)劃分。同時考慮到復(fù)雜網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)是離散問題，提出了一種基于拓?fù)浣Y(jié)構(gòu)的新編碼離散演化規(guī)則。

1）鄰居潛力的定義

在武裝部隊中，偵查部隊是掌握偵察技巧與技能的專業(yè)部隊，他們需要緊密地合作，共同收集情報并執(zhí)行任務(wù)，通過協(xié)作以實現(xiàn)既定目標(biāo)。類似地，鯨魚在包圍捕食中通過群體的合作來圍困獵物，以提高捕食成功率。偵查部隊進行搜索時，為了擴大搜索范圍，通常會在可疑目標(biāo)點鄰近的區(qū)域進行搜索，而基本W(wǎng)OA在包圍捕食階段學(xué)習(xí)對象單一、多樣性不足，容易陷入局部最優(yōu)。因此，結(jié)合偵察部隊在可疑目標(biāo)點區(qū)域內(nèi)探索的原理進行建模，將最優(yōu)個體的 “鄰居潛力”作為學(xué)習(xí)對象，與最優(yōu)個體的Q值相近的個體定義為其鄰居。為了衡量鄰居的潛力值，采用鄰居個體與最優(yōu)個體之間的漢明距離［21］，物理意義是鄰居個體接近最優(yōu)個體的最少變換次數(shù)。同時，為了結(jié)合社團網(wǎng)絡(luò)的結(jié)構(gòu)特征，將節(jié)點連邊距離也作為衡量條件，引入曼哈頓距離［22］基于拓?fù)涞挠嬎惴椒ǎx鄰居潛力如下：

其中：xij是第i個鯨魚個體的第j個基因位，xie同理；當(dāng)D=1時，隨機選取該節(jié)點的其他鄰居xie替換當(dāng)前xij，否則不作替換。

2.3 基于“特種部隊”的氣泡網(wǎng)捕食

在本節(jié)中，著力于解決WOA中存在的兩個捕食階段信息交流效率低、搜索性能不高的問題，進而影響社區(qū)劃分的效率。本文的目標(biāo)是借鑒特種部隊作戰(zhàn)的機理，提出鯨魚指揮官作為信息交流的橋梁，將包圍捕食階段搜索中的有用信息傳遞給氣泡網(wǎng)捕食階段，從而提高這兩個階段間的信息交流效率。具體實施時，根據(jù)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)特征和編解碼性質(zhì)，對鯨魚指揮官進行建模。選擇這種設(shè)計的理由在于，通過選擇三個較優(yōu)的個體，能夠獲得高質(zhì)量的網(wǎng)絡(luò)子集，充分利用了網(wǎng)絡(luò)節(jié)點拓?fù)湫畔⒑完P(guān)聯(lián)關(guān)系等先驗知識。這樣做有利于加強兩個捕食階段的信息交流效率，同時也能加速氣泡網(wǎng)捕食階段算法的收斂速度。

1）鯨魚指揮官的選取

在武裝部隊中，特種部隊是通過情報，專門從事精確打擊的部隊，特種兵在作戰(zhàn)中常常利用各種技術(shù)和策略來建立網(wǎng)絡(luò)，從而將敵方目標(biāo)圍剿其中?；趥刹椴筷牭陌鼑妒橙缢惴?所示。

式（14）中，b為限定螺旋形狀的螺旋系數(shù)，為區(qū)間［-1，1］的隨機數(shù)。同時基于離散網(wǎng)絡(luò)的拓?fù)涮卣?，提出了一種新的局部社區(qū)加強策略，對于氣泡網(wǎng)捕食階段的個體，如果其通過基于鯨魚指揮官的搜索后適應(yīng)度值變差，對比該個體迭代前后的基因位，將不同的基因值替換為其他鄰居編號。算法2描述了基于特種部隊的氣泡網(wǎng)捕食算法框架。

2.4 基于“學(xué)習(xí)自動機”的自適應(yīng)選擇操作

基本的WOA算法在選擇包圍捕食或氣泡網(wǎng)捕食時，使用概率P值進行隨機選擇，缺乏對當(dāng)前拓?fù)浣Y(jié)構(gòu)和搜索信息的更好利用，無法實現(xiàn)兩個捕食階段的平衡。然而，在實際作戰(zhàn)過程中，各個武裝力量協(xié)同合作，共同搜索敵人的位置，一旦發(fā)現(xiàn)敵人，其他武裝力量會迅速增援發(fā)現(xiàn)敵人的部隊，以加快搜索速度。因此，基于此機理引入改進的學(xué)習(xí)自動機引導(dǎo)鯨魚種群向更加有希望的方向增員，通過自適應(yīng)選擇動作，達到平衡兩搜索階段的目的。Hashemi等人［24］提出的學(xué)習(xí)自動機（LA）可以用四個元素〈α，β，γ，P〉為表示，它通過這四個元素的組合進行連續(xù)反饋并調(diào)整，以找到最優(yōu)解，其中α、β、γ和P分別表示動作集、強化過程、響應(yīng)集和概率集。用于更新概率向量 p 的機制可以如式（15）和（16）所示。

其中：a和b分別表示［0，1］內(nèi)的獎勵和懲罰參數(shù)。學(xué)習(xí)自動機具體的實現(xiàn)過程是：從具有概率集 P 的動作集α中選擇一個動作，然后通過響應(yīng)集γ對獲得的數(shù)據(jù)進行增強，生成增強信號β。在LA－DSWOA中，將鯨魚部隊中的兩種搜索策略，即包圍捕食和氣泡網(wǎng)捕食，合并到LA的動作集α中，然后，在動作集α進化后評估鯨魚的性能，這個過程是LA的強化過程。緊接著，將每個進化前后鯨魚的Q值進行比較，并將響應(yīng)存儲在LA的響應(yīng)集γ中。最后，由于搜索策略在兩個動作集α中的執(zhí)行具有一定的概率，兩種搜索策略的概率通過響應(yīng)集γ存儲在概率集 P 中。所以通過這種自適應(yīng)的方法引導(dǎo)鯨魚種群向有希望的方向增員，流程如圖3所示。

在該算法中，使用兩個動作來更有效地找到最優(yōu)解，即包圍捕食和氣泡網(wǎng)捕食策略，其中LA只執(zhí)行一個動作。基于動作α，產(chǎn)生強化信號γ，基于環(huán)境的反饋值通過式（17）來計算，算法3描述了LA－DSWOA算法框架。

算法3 求解社區(qū)發(fā)現(xiàn)的LA－DSWOA算法框架

1 輸入：網(wǎng)絡(luò)G=（V，E）；最大迭代次數(shù)T；種群大小N；適應(yīng)度函數(shù)Q;

2 鯨魚個體初始化←基于鄰節(jié)點編碼（xij，N（xij））;

3 計算個體適應(yīng)度選出最優(yōu)的三個Xa、Xb和Xc；

4 初始化概率向量 P ←0.5；

5 開始迭代令，t=0；

6 while tlt;T

7計算每個鯨魚個體的適應(yīng)度f（xi）；

8根據(jù)概率向量 P 選擇動作α；

9for each Xi∈N do

10 根據(jù)向量 P 選擇動作α;

11 if α=包圍捕食 then

12基于式（8）更新Xi;

13 else

14基于式（14）更新Xi，并局部增強;

15if f（Xi（t+1））gt;f（Xi（t）） then

16 Xi（t）←Xi（t+1）;

17else

18 xi←局部增強;

19 γ←根據(jù)式（17）生成響應(yīng)γ;

20 根據(jù)式（15）（16）更新概率向量 P ;

21 Xbest←根據(jù)適應(yīng)度選擇最佳個體;

22 Xgbest←（Xbest，X）歷史最優(yōu)X進行比較;

23 t←t+1;

24 輸出：最佳個體Xgbest。

3 仿真實驗及其結(jié)果分析

在本章中，為了驗證算法的性能，將LA－DSWOA在真實網(wǎng)絡(luò)數(shù)據(jù)集和人工合成網(wǎng)絡(luò)數(shù)據(jù)集上進行實驗，并將結(jié)果與近幾年基于群體智能優(yōu)化的社區(qū)發(fā)現(xiàn)算法在相同的網(wǎng)絡(luò)數(shù)據(jù)集上進行比較，同時分析了算法復(fù)雜度。

3.1 復(fù)雜度分析

首先分析本文算法的時間復(fù)雜度。N為鯨魚種群規(guī)模，n為網(wǎng)絡(luò)節(jié)點總數(shù)，D為平均節(jié)點度（基于適應(yīng)度函數(shù)Q公式），最大迭代次數(shù)為Tmax，基于算法3進行展開計算。首先個體鄰節(jié)點初始化需要時間復(fù)雜度為O（N·nD）（第2行），個體適應(yīng)度計算，通過插入排序選出三個較優(yōu)個體時間復(fù)雜度（N+N2+3）（第3行），初始化P與t均為O（1），整個while循環(huán)中每個鯨魚個體都要計算適應(yīng)度O（Tmax·N·nD）。包圍捕食，距離計算需要O（N·n log n） （第11、12行），位置更新需要O（N· n）（算法1第7～10行），再一次更新適應(yīng)度值需要O（N·nD（算法1第11行）。由于兩種捕食使用相同的離散化規(guī)則，所以氣泡網(wǎng)捕食也為O（N（n·log n+n+nD）） （算法2），生成響應(yīng)和更新概率向量需要O（m）（第19、20行）的時間復(fù)雜度，其中m表示常數(shù)。 綜上，while循環(huán)總的時間復(fù)雜度為O（Tmax （N·nD+N（n log n+n+nD+m）））），最后根據(jù)適應(yīng)度選出最佳個 體Xgbest時間復(fù)雜度為O（n·D+N）（第21、22行），因此總的時間復(fù)雜度為O（Tmax（N·nD+N（n log n+n+nD+m）））+O（N+N2+3）+O（n·D+N）+O（1），因此在最壞情況下，LA－DSWOA的時間復(fù)雜度為O（N·n（Tmax （log n+D）+D）+N2）。

其次，分析空間復(fù)雜度，仍以算法3為主。首先，初始化需要O（N·n）（第2行），根據(jù)適應(yīng)度進行插入排序需要O（1）（第3行），“鄰居潛力”挖掘?qū)ψ顑?yōu)和九個鄰居解碼需要O（11n）（算法1第5～8行）， 包圍捕食距離D更新需要額外空間為O（2n2（N-2）），氣泡網(wǎng)捕食需要O（n2（N-1））（算法2第5～11行）， 生成鯨魚指揮官的編解碼需要O（3n+n）（算法1 第11～13行）的空間，最后保存當(dāng)前最優(yōu)個體Xgbest需要O（1）（ 第21、22行）的空間。綜上，總空間復(fù)雜度為：O（2n2（N-2））+O（n2（N-1））+O（11n）+O（N·n）+2O（1），因此最壞情況下空間復(fù)雜度為O（N·n+n3）。

3.2 數(shù)據(jù)集

3.2.1 人工合成網(wǎng)絡(luò)

人工合成網(wǎng)絡(luò)由Lancichinetti等人［25］提出，通過調(diào)整LFR參數(shù)生成人工網(wǎng)絡(luò)，使用這種方法生成的網(wǎng)絡(luò)可以很好地體現(xiàn)社區(qū)結(jié)構(gòu)，網(wǎng)絡(luò)中有一個表示節(jié)點與其所屬社區(qū)之外的網(wǎng)絡(luò)中其他節(jié)點的連接率的參數(shù)μ，μ越大，網(wǎng)絡(luò)的模塊化程度越低，越不容易區(qū)分社區(qū)結(jié)構(gòu)。

3.2.2 真實網(wǎng)絡(luò)

本文采用以下8個真實網(wǎng)絡(luò)測試，包含5個小型網(wǎng)絡(luò)和3個大型網(wǎng)絡(luò)，網(wǎng)絡(luò)的基本信息如表1所示。

3.3 評價指標(biāo)

標(biāo)準(zhǔn)化互信息（normalized mutual information，NMI）是Danon等人［26］提出的一種重要評價指標(biāo)，可以比較客觀地評價一個社區(qū)劃分與標(biāo)準(zhǔn)劃分之間相比的準(zhǔn)確度。NMI的值域是0到1，越大代表劃分越準(zhǔn)確。當(dāng)NMI=1時，表示算法得到的社區(qū)劃分結(jié)果與真實社區(qū)劃分結(jié)果完全一致。其公式定義如下：

如圖4所示，每個算法的NMI值都隨著μ的增大整體呈下降趨勢，可以看出，LA－DSWOA的精度始終大于其他對比算法，證明了本文設(shè)計的鄰居潛力和鯨魚指揮官的學(xué)習(xí)確實能提高算法的穩(wěn)定性和精度。當(dāng)μ＜0.4時，網(wǎng)絡(luò)結(jié)構(gòu)比較清晰，相比之下，所有算法都真實地反映網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)劃分；當(dāng)μ≥0.4時，網(wǎng)絡(luò)結(jié)構(gòu)逐漸趨于模糊，找出真實的社區(qū)結(jié)構(gòu)越發(fā)困難；當(dāng)μ≥0.5時，IHHOOBL性能下降很快，其主要原因是基于對立學(xué)習(xí)的更新策略在μ值較大時失去跳出局部最優(yōu)的能力；當(dāng)μ≥0.5時，EP－WOCD的精度也急劇下降，這是因為當(dāng)網(wǎng)絡(luò)模糊度增大的同時，其模塊性也急劇下降；當(dāng)μ≥0.6時，SDBFO、Propose和DMFO－CD算法的NMI值急速下降，反映出當(dāng)網(wǎng)絡(luò)的結(jié)構(gòu)變得模糊時，其他傳統(tǒng)的算法很難正確劃分社區(qū)，而LA－DSWOA仍能保持較好的精度，因此在網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)復(fù)雜、模糊時仍具有較好的社區(qū)劃分能力。

圖5為不同μ值下50次迭代的NMI收斂圖。由圖可以看出，當(dāng)μ值為0.2、0.4和0.5時，各算法的NMI均勻變化并呈現(xiàn)一定的收斂性，而在μ值為0.6下時，結(jié)構(gòu)較復(fù)雜網(wǎng)絡(luò)中NMI的波動較大，同時LA－DSWOA的性能略高于其他算法，在μ值為0.4和0.5時，其NMI值均能收斂于0.9。而不考慮網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的算法WOCDA和SDBFO，隨著網(wǎng)絡(luò)規(guī)模的增加其性能迅速下降。IHHOOBL和DMFO－CD的精度隨著μ值的增加顯著變化，這意味著當(dāng)網(wǎng)絡(luò)結(jié)構(gòu)復(fù)雜時，其對網(wǎng)絡(luò)規(guī)模敏感，當(dāng)μ值為0.2時網(wǎng)絡(luò)結(jié)構(gòu)簡單，50次迭代中LA－DSWOA和IHHOOBL的NMI均收斂于0.98。0.4和0.5時均收斂于0.94，當(dāng)μ值為0.6時網(wǎng)絡(luò)結(jié)構(gòu)較復(fù)雜，IHHOOBL的性能急劇下降，而LA－DAWOA仍能保持一定的收斂性。

2）真實網(wǎng)絡(luò)實驗結(jié)果

為了進一步驗證LA－DSWOA的真實性和有效性，共選取八個真實網(wǎng)絡(luò)進行驗證，包括karate、football、dolphin、polbooks和lesmis五個小型網(wǎng)絡(luò)以及netscience、polblogs、power三個大型網(wǎng)絡(luò)。在每個網(wǎng)絡(luò)上獨立運行50次，使用Q和NMI作為評價指標(biāo)，每次運行結(jié)束后分別取最大值和平均值。

在五個小型網(wǎng)絡(luò)中，對比Qmax和Qavg，在表2中可以看出，在劃分karate網(wǎng)絡(luò)時，DMFO－CD、EP－WOCD、IHHOOBL、SDBFO和LA－DSWOA都具有相對較高的Qmax，因為karate結(jié)構(gòu)簡單，而IHHOOBL和LA－DSWOA具有相同的Qavg，所以對比其他算法更加穩(wěn)定。在劃分football網(wǎng)絡(luò)時，DMFO－CD和SDBOF的Qmax和Qavg都為0.605 0，優(yōu)于其他算法，同時LA－DSWOA的Qmax也為該值，相較穩(wěn)定性也更好。在劃分dolphin和polbooks網(wǎng)絡(luò)時，IHHOOBL和SDBFO均能分別取得較好的模塊值，而LA－DSWOA能夠始終保持這種好的模塊值，因此在穩(wěn)定性和性能方面更佳，WOCDA劃分效果不好，尤其是劃分Lesmis網(wǎng)絡(luò)時，整個網(wǎng)絡(luò)被劃分為一個社區(qū)，模塊性非常差。對比DMFO－CD、EP－WOCD、IHHOOBL和LA－DSWOA，在劃分四個小型網(wǎng)絡(luò)karate、football、dolphins和polbooks時，NMImax和NMIavg值均出現(xiàn)為1的結(jié)果，證明了算法得到的社區(qū)劃分結(jié)果與真實社區(qū)劃分結(jié)果完全一致。因此，在劃分五個小型網(wǎng)絡(luò)時，LA－DSWOA具有較好的穩(wěn)定性和準(zhǔn)確性。

在netscience、polblogs和power三個大型網(wǎng)絡(luò)上，由于其復(fù)雜的網(wǎng)絡(luò)結(jié)構(gòu)，很多算法都沒能很好地劃分社區(qū)結(jié)構(gòu)。對比Qmax和Qavg，LA－DSWOA在polblogs網(wǎng)絡(luò)中的Qmax=0.4252，除了IHHOOBL算法外，高于其他算法，同時LA－DSWOA在power網(wǎng)絡(luò)上，Qmax=0.9110，Qavg=0.9081，除了SFBFO算法與其相近外，均優(yōu)于其他對比算法，說明在該網(wǎng)絡(luò)上獲得了更好的社區(qū)劃分結(jié)構(gòu)的同時，具有更好的穩(wěn)定性。雖然在netscience網(wǎng)絡(luò)上，LA－DSWOA算法的劃分結(jié)果為Qmax=0.9473和Qavg=0.9261，而IHHOOBL的劃分結(jié)果為Qmax=0.9479和Qavg=0.9479，總體上IHHOOB值略高，但是劃分結(jié)果相差不大，而且IHHOOB不是每次都能在大型網(wǎng)絡(luò)上取得較好的模塊值，且power上劃分的效果不佳。而在其余兩個大型網(wǎng)絡(luò)上，LA－DSWOA在50次獨立運行的過程中仍然能取得不錯的效果，因此LA－DSWOA得到的社區(qū)劃分能夠更接近網(wǎng)絡(luò)的真實社區(qū)結(jié)構(gòu)。

總的來說，本文提出的LA－DSWOA劃分小型網(wǎng)絡(luò)karate、dolphins、polbooks和lesmis以及大型網(wǎng)絡(luò)polblogs和power具有較好的準(zhǔn)確性和穩(wěn)定性，能夠得到質(zhì)量較高的社區(qū)結(jié)構(gòu)，同時有較好的穩(wěn)定性。

為了驗證LA－DSWOA對社區(qū)的層級劃分能力和精度，能夠?qū)⒋笊鐓^(qū)中的小社區(qū)發(fā)現(xiàn)出來，將其應(yīng)用到三個網(wǎng)絡(luò)數(shù)據(jù)集，分別為karate、dolphins和football。在某次運行中選擇幾個代表性的解，利用Pajek軟件進行可視化，不同的顏色代表檢測到的不同社區(qū)。

如圖6（a）中，karate網(wǎng)絡(luò)被劃分為2個社區(qū)，對應(yīng)NMI=1，Q=0.3715，劃分與美國大學(xué)空手道俱樂部真實結(jié)構(gòu)完全吻合，一個在節(jié)點33（俱樂部教練）周圍，另一個在節(jié)點1（俱樂部經(jīng)理）周圍。圖6（b）中，karate網(wǎng)絡(luò)被劃分為4個社區(qū)，對應(yīng)NMI=0.8268，Q=0.4308，它是圖（a）的進一步劃分，社區(qū)內(nèi)部聯(lián)系更加緊密、模塊性更好。

圖7（a）中，dolphins網(wǎng)絡(luò)同樣被劃分為2個社區(qū)，對應(yīng)NMI=1，Q=0.3742，與真實網(wǎng)絡(luò)社區(qū)劃分一樣。圖7（b）中，以Q為目標(biāo)函數(shù)被劃分為5個社區(qū)對應(yīng)，NMI=0.5745，Q=0.5295，節(jié)點3、8、36、39和59之間連接緊密，被劃分為一個社區(qū)，0、2、10、20、28、30、42、44和47這9個節(jié)點獨立成一個社區(qū)，它們內(nèi)外部度之和的比遠大于1，因此內(nèi)部連接緊密。圖7中代表通過劃分的football網(wǎng)絡(luò)結(jié)構(gòu)，該網(wǎng)絡(luò)包含8個島節(jié)點（如節(jié)點36、28、90和110等），因此這個網(wǎng)絡(luò)被劃分時，很難獲得NMI=1的社區(qū)結(jié)構(gòu)。在圖8（a）中，LA－DSWOA正確劃分了football所有島節(jié)點，并準(zhǔn)確識別了12個社區(qū)結(jié)構(gòu)，對應(yīng)NMI=1，Q=0.5540。在圖8（b）中，football網(wǎng)絡(luò)被劃分為9個社區(qū)，對應(yīng)NMI=0.8613，Q=0.6050，同時，這9個社區(qū)比圖8（a）具有更強的內(nèi)部連接。

4 結(jié)束語

復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)被認(rèn)為是一個很有趣的問題，也是近年來研究的熱點，因為它在語言學(xué)、生物學(xué)、社會科學(xué)和化學(xué)等許多流行領(lǐng)域都有廣泛的應(yīng)用，許多算法都可以用于社區(qū)發(fā)現(xiàn)。本文提出一種融入武裝部隊WOA的社區(qū)發(fā)現(xiàn)方法，針對包圍捕食階段多樣性不足的問題，提出“鄰居潛力”學(xué)習(xí)模型，用于提高WOA的全局搜索能力；針對兩捕食階段信息交流效率低從而導(dǎo)致性能低的問題，提出了鯨魚指揮官領(lǐng)導(dǎo)的氣泡網(wǎng)捕食階段，以確保搜索信息得到有效利用；針對兩種捕食機制不平衡問題，采用一種改進的學(xué)習(xí)自動機來自適應(yīng)引導(dǎo)鯨魚部隊向有希望的區(qū)域移動。為了驗證LA－DSWOA的性能，將LA－DSWOA與其余六種算法進行比較，從真實網(wǎng)絡(luò)和人工網(wǎng)絡(luò)都可以看出：LA－DSWOA可以劃分出更好的社區(qū)結(jié)構(gòu)，并可以找到與實際社區(qū)接近的分區(qū)。本研究對象為靜態(tài)的非重疊網(wǎng)絡(luò)，未考慮到節(jié)點重疊的可能，因此在將來會考慮重疊因素。

參考文獻：

［1］Eisinger R W， Dieffenbach C W， Fauci A S. Role of implementation science： linking fundamental discovery science and innovation science to ending the HIV epidemic at the community level［J］.JAIDS Journal of Acquired Immune Deficiency Syndromes ， 2019， 82 ： S171－S172.

［2］Li Chaoyi， Zhang Yangsen. A personalized recommendation algorithm based on large－scale real micro－blog data［J］.Neural Computing and Applications ， 2020， 32 ： 11245－11252.

［3］Becker E， Robisson B， Chapple C E，et al.Multifunctional proteins revealed by overlapping clustering in protein interaction network［J］.Bioinformatics ， 2012， 28 （1）： 84－90.

［4］Raghavan U N， Albert R， Kumara S. Near linear time algorithm to detect community structures in large－scale networks［J］.Physical Review E ， 2007 ，76 （3）： 036106.

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

［6］White S， Smyth P. A spectral clustering approach to finding communities in graph［C］//Proc of SIAM International Conference on Data Mining. 2005：274－285.

［7］楊亮， 曹曉春， 何東曉，等. 基于深度學(xué)習(xí)的模塊化社區(qū)檢測［C］//第25屆國際人工智能聯(lián)合會議論文集. 2016： 2252－2258. （Yang Liang， Cao Xiaochun， He Dongxiao，et al.Modularity based community detection with deep learning［C］// Proc of the 25th International Joint Conference on Artificial Intelligence. 2016： 2252－2258.）

［8］Newman M E J， Girvan M. Finding and evaluating community structure in networks［J］.Phys Rev E ， 2004， 69 ：026113.

［9］Aloise D， Deshpande Hansen P，et al.NP－h(huán)ardness of Euclidean sum－of－squares clustering［J］.Machine Learning，2009， 75 （2）： 245－248.

［10］Behera R K， Naik D， Rath S K，et al.Genetic algorithm－based community detection in large－scale social networks［J］.Neural Computing and Applications ， 2020， 32 ： 9649－9665.

［11］Zhang Qang， Liu Lijie. Whale optimization algorithm based on Lamarckian learning for global optimization problems［J］.IEEE Access，2019，7 ： 36642－36666.

［12］Zhou Xu， Liu Yanheng， Zhang Jindong， et al.An ant colony based algorithm for overlapping community detection in complex networks［J］.Physica A： Statistical Mechanics and its Applications ， 2015，427 ： 289－301.

［13］Liu Qiang， Zhou Bo， Li Shudong，et al.Community detection utilizing a novel multi－swarm fruit fly optimization algorithm with hill－climbing strategy［J］.Arabian Journal for Science and Enginee－ring，2016，41 ： 807－828.

［14］Feng Yunfei， Chen Hongmei， Li Tianrui， et al.A novel community detection method based on whale optimization algorithm with evolutionary population［J］.Applied Intelligence ， 2020， 50 ： 2503－2522.）

［15］Zhang Yun， Liu Yongguo， Li Jietinget al.WOCDA： a whale optimization based community detection algorithm［J］.Physica A： Statistical Mechanics and its Applications ， 2020， 539 ： 122937.

［16］Nadimi－Shahraki M H， Moeini E， Taghian S，et al.DMFO－CD： a discrete moth－flame optimization algorithm for community detection［J］.Algorithms，202 14 （11）： 314.

［17］Chakraborty S， Saha A K， Chakraborty R，et al.HSWOA： an ensemble of hunger games search and whale optimization algorithm for global optimization［J］.International Journal of Intelligent Systems，2022，37 （1）： 52－104.

［18］Mirjalili S， Lewis A. The whale optimization algorithm［J］.Advances in Engineering Software ， 2016，95 ：51－67.

［19］楊魯. 《中國人民解放軍軍語》編纂的歷程、特色和創(chuàng)新［J］. 語言戰(zhàn)略研究， 2022， 7 （6）： 25－33. （Yang Lu. The history， characteristics and innovations of the compilation of the military language of the Chinese people’s liberation army［J］.Language Strategy Research ， 2022， 7 （6）： 25－33.）

［20］Li Xiangjun， Wu Xiaoliang， Su Xu，et al.A novel complex network community detection approach using discrete particle swarm optimization with particle diversity and mutation［J］.Applied Soft Computing ， 2019，81 ： 105476.

［21］Li Jing， Song Lin， Yu Kai，et al.Quantum K－nearest neighbor classification algorithm based on Hamming distance［J］.Quantum Information Processing ， 2022， 21 （1）： 18.

［22］Suwanda R， Syahputra Z， Zamzami E M. Analysis of Euclidean distance and Manhattan distance in the K－means algorithm for variations number of centroid K［J］.Journal of Physics： Conference Series ， 2020， 1566 （1）： 012058.

［23］Wu Deng， Shang Shifan， Cai Xinget al.An improved differential evolution algorithm and its application in optimization problem［J］.Soft Computing ， 2021，25 ： 5277－5298.）

［24］Hashemi A B， Meybodi M R. A note on the learning automata based algorithms for adaptive parameter selection in PSO［J］.Applied Soft Computing，201 11 （1）： 689－705.

［25］Lancichinetti Fortunato S， Radicchi F. Benchmark graphs for testing community detection algorithms［J］.Physical Review E ， 2008， 78 （4）： 046110.

［26］Danon L， Diaz－Guilera Duch J，et al.Comparing community structureidentification［J］.Journal of Statistical Mechanics： Theory and Experiment ， 2005， 2005 （9）： P09008.

［27］Gharehchopogh F S. An improved Harris hawks optimization algorithm with multi－strategy for community detection in social network［J］.Journal of Bionic Engineering ， 2023， 20 （3）： 1175－1197.

［28］Yang Bo， Huang Xuelin， Cheng Weizheng，et al.Discrete bacterial foraging optimization for community detection in networks［J］.Future Generation Computer Systems ， 2022， 128 ： 192－204.）

［29］Shishavan S T， Gharehchopogh F S. An improved cuckoo search optimization algorithm with genetic algorithm for community detection in complex networks［J］.Multimedia Tools and Applications，2022， 81 （18）： 25205－25231.

收稿日期：2023－08－15；修回日期：2023－10－20基金項目：國家自然科學(xué)基金資助項目（62162040，62063021）

作者簡介：張其文（1975—），男，山西臨汾人，副教授，碩導(dǎo)，碩士，主要研究方向為模式識別與人工智能、機器學(xué)習(xí)；關(guān)定坤（1997—），男（通信作者），甘肅永登人，碩士研究生，主要研究方向為模式識別與人工智能（1790738867@qq.com）．