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

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

中圖分類號(hào)：TP391文獻(xiàn)標(biāo)志碼： A文章編號(hào)：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)確識(shí)別社區(qū)結(jié)構(gòu)能夠挖掘出其中重要的結(jié)構(gòu)信息和潛藏的內(nèi)容。社區(qū)發(fā)現(xiàn)在流行病的傳播控制［1］、微博的個(gè)性化推薦［2］以及蛋白質(zhì)網(wǎng)絡(luò)的挖掘［3］等多個(gè)領(lǐng)域中扮演著重要的角色，因此其具有重要意義和廣泛的應(yīng)用前景。

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

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

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

1 基礎(chǔ)知識(shí)介紹

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

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

a）包圍捕食。

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

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

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

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

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

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

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

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

1）鄰居潛力的定義

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

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

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

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

1）鯨魚指揮官的選取

在武裝部隊(duì)中，特種部隊(duì)是通過(guò)情報(bào)，專門從事精確打擊的部隊(duì)，特種兵在作戰(zhàn)中常常利用各種技術(shù)和策略來(lái)建立網(wǎng)絡(luò)，從而將敵方目標(biāo)圍剿其中。基于偵查部隊(duì)的包圍捕食如算法1所示。

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

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

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

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

在該算法中，使用兩個(gè)動(dòng)作來(lái)更有效地找到最優(yōu)解，即包圍捕食和氣泡網(wǎng)捕食策略，其中LA只執(zhí)行一個(gè)動(dòng)作?；趧?dòng)作α，產(chǎn)生強(qiáng)化信號(hào)γ，基于環(huán)境的反饋值通過(guò)式（17）來(lái)計(jì)算，算法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 鯨魚個(gè)體初始化←基于鄰節(jié)點(diǎn)編碼（xij，N（xij））;

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

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

5 開始迭代令，t=0；

6 while tlt;T

7計(jì)算每個(gè)鯨魚個(gè)體的適應(yīng)度f(wàn)（xi）；

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

9for each Xi∈N do

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

11 if α=包圍捕食 then

12基于式（8）更新Xi;

13 else

14基于式（14）更新Xi，并局部增強(qiáng);

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

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

17else

18 xi←局部增強(qiáng);

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

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

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

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

23 t←t+1;

24 輸出：最佳個(gè)體Xgbest。

3 仿真實(shí)驗(yàn)及其結(jié)果分析

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

3.1 復(fù)雜度分析

首先分析本文算法的時(shí)間復(fù)雜度。N為鯨魚種群規(guī)模，n為網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)，D為平均節(jié)點(diǎn)度（基于適應(yīng)度函數(shù)Q公式），最大迭代次數(shù)為Tmax，基于算法3進(jìn)行展開計(jì)算。首先個(gè)體鄰節(jié)點(diǎn)初始化需要時(shí)間復(fù)雜度為O（N·nD）（第2行），個(gè)體適應(yīng)度計(jì)算，通過(guò)插入排序選出三個(gè)較優(yōu)個(gè)體時(shí)間復(fù)雜度（N+N2+3）（第3行），初始化P與t均為O（1），整個(gè)while循環(huán)中每個(gè)鯨魚個(gè)體都要計(jì)算適應(yīng)度O（Tmax·N·nD）。包圍捕食，距離計(jì)算需要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行）的時(shí)間復(fù)雜度，其中m表示常數(shù)。 綜上，while循環(huán)總的時(shí)間復(fù)雜度為O（Tmax （N·nD+N（n log n+n+nD+m）））），最后根據(jù)適應(yīng)度選出最佳個(gè) 體Xgbest時(shí)間復(fù)雜度為O（n·D+N）（第21、22行），因此總的時(shí)間復(fù)雜度為O（Tmax（N·nD+N（n log n+n+nD+m）））+O（N+N2+3）+O（n·D+N）+O（1），因此在最壞情況下，LA－DSWOA的時(shí)間復(fù)雜度為O（N·n（Tmax （log n+D）+D）+N2）。

其次，分析空間復(fù)雜度，仍以算法3為主。首先，初始化需要O（N·n）（第2行），根據(jù)適應(yīng)度進(jìn)行插入排序需要O（1）（第3行），“鄰居潛力”挖掘?qū)ψ顑?yōu)和九個(gè)鄰居解碼需要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)個(gè)體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］提出，通過(guò)調(diào)整LFR參數(shù)生成人工網(wǎng)絡(luò)，使用這種方法生成的網(wǎng)絡(luò)可以很好地體現(xiàn)社區(qū)結(jié)構(gòu)，網(wǎng)絡(luò)中有一個(gè)表示節(jié)點(diǎn)與其所屬社區(qū)之外的網(wǎng)絡(luò)中其他節(jié)點(diǎn)的連接率的參數(shù)μ，μ越大，網(wǎng)絡(luò)的模塊化程度越低，越不容易區(qū)分社區(qū)結(jié)構(gòu)。

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

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

3.3 評(píng)價(jià)指標(biāo)

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

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

圖5為不同μ值下50次迭代的NMI收斂圖。由圖可以看出，當(dāng)μ值為0.2、0.4和0.5時(shí)，各算法的NMI均勻變化并呈現(xiàn)一定的收斂性，而在μ值為0.6下時(shí)，結(jié)構(gòu)較復(fù)雜網(wǎng)絡(luò)中NMI的波動(dòng)較大，同時(shí)LA－DSWOA的性能略高于其他算法，在μ值為0.4和0.5時(shí)，其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ù)雜時(shí)，其對(duì)網(wǎng)絡(luò)規(guī)模敏感，當(dāng)μ值為0.2時(shí)網(wǎng)絡(luò)結(jié)構(gòu)簡(jiǎn)單，50次迭代中LA－DSWOA和IHHOOBL的NMI均收斂于0.98。0.4和0.5時(shí)均收斂于0.94，當(dāng)μ值為0.6時(shí)網(wǎng)絡(luò)結(jié)構(gòu)較復(fù)雜，IHHOOBL的性能急劇下降，而LA－DAWOA仍能保持一定的收斂性。

2）真實(shí)網(wǎng)絡(luò)實(shí)驗(yàn)結(jié)果

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

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

在netscience、polblogs和power三個(gè)大型網(wǎng)絡(luò)上，由于其復(fù)雜的網(wǎng)絡(luò)結(jié)構(gòu)，很多算法都沒(méi)能很好地劃分社區(qū)結(jié)構(gòu)。對(duì)比Qmax和Qavg，LA－DSWOA在polblogs網(wǎng)絡(luò)中的Qmax=0.4252，除了IHHOOBL算法外，高于其他算法，同時(shí)LA－DSWOA在power網(wǎng)絡(luò)上，Qmax=0.9110，Qavg=0.9081，除了SFBFO算法與其相近外，均優(yōu)于其他對(duì)比算法，說(shuō)明在該網(wǎng)絡(luò)上獲得了更好的社區(qū)劃分結(jié)構(gòu)的同時(shí)，具有更好的穩(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上劃分的效果不佳。而在其余兩個(gè)大型網(wǎng)絡(luò)上，LA－DSWOA在50次獨(dú)立運(yùn)行的過(guò)程中仍然能取得不錯(cuò)的效果，因此LA－DSWOA得到的社區(qū)劃分能夠更接近網(wǎng)絡(luò)的真實(shí)社區(qū)結(jié)構(gòu)。

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

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

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

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

4 結(jié)束語(yǔ)

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

參考文獻(xiàn)：

［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è)［C］//第25屆國(guó)際人工智能聯(lián)合會(huì)議論文集. 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］楊魯. 《中國(guó)人民解放軍軍語(yǔ)》編纂的歷程、特色和創(chuàng)新［J］. 語(yǔ)言戰(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基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目（62162040，62063021）

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