基于改進(jìn)鯨魚(yú)算法的社區(qū)發(fā)現(xiàn)

劉紫娟，張啟文，任靜強(qiáng)，田文艷

（1.山西工程職業(yè)學(xué)院，山西 太原 030000；2.中國(guó)移動(dòng)通信集團(tuán)山西有限公司太原分公司，山西 太原 030000；3.太原科技大學(xué)，山西 太原 030000）

0 引 言

鯨魚(yú)算法[1]最先用于解決連續(xù)優(yōu)化問(wèn)題，本文針對(duì)復(fù)雜網(wǎng)絡(luò)應(yīng)用環(huán)境的離散化特性，對(duì)鯨魚(yú)算法的連續(xù)位置進(jìn)行離散化處理，提出了一種用于求解復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)的改進(jìn)離散鯨魚(yú)算法（Improved Discrete Whale Optimization Algorithm, IDWOA）。

1 原 理

在求解鯨魚(yú)算法的優(yōu)化問(wèn)題時(shí)，每個(gè)鯨魚(yú)都代表一個(gè)所求問(wèn)題的候選解，通過(guò)模塊度值來(lái)判斷鯨魚(yú)所處位置的好壞。鯨魚(yú)算法（Whale Optimization Algorithm, WOA）的數(shù)學(xué)模型表示如下：

但WOA模型并不適用于求解離散問(wèn)題，可以將WOA算法進(jìn)行離散化，使其適用于社區(qū)發(fā)現(xiàn)的應(yīng)用背景。

通過(guò)分析發(fā)現(xiàn)，WOA要適用于求解社區(qū)發(fā)現(xiàn)問(wèn)題，其對(duì)應(yīng)的鯨魚(yú)位置的每一個(gè)維度都應(yīng)該是整數(shù)。因此，在每次位置更新后進(jìn)行一次四舍五入的取整運(yùn)算，由此得到離散的鯨魚(yú)算法（DWOA）。

1.1 算法的編碼方式

對(duì)于網(wǎng)絡(luò)編碼而言，一種傳統(tǒng)也最直觀有效的編碼方式是基于字符的編碼。本文用鯨魚(yú)的位置編碼表示對(duì)應(yīng)節(jié)點(diǎn)的社區(qū)編號(hào)，基于字符的編碼過(guò)程如圖1所示。

圖1 基于字符的編碼示意圖

1.2 種群初始化

本文采用改進(jìn)的標(biāo)簽傳播方法[2]進(jìn)行初始化，同時(shí)用度和聚集系數(shù)[3]來(lái)評(píng)價(jià)節(jié)點(diǎn)的重要性[4]。該方法不僅易于計(jì)算，同時(shí)兼顧了節(jié)點(diǎn)的全局和局部影響。

本文對(duì)IDWOA算法采用分段初始化策略，即在整個(gè)種群中選取5%的個(gè)體進(jìn)行有序標(biāo)簽傳播，其余95%的個(gè)體仍然由LPA算法對(duì)其進(jìn)行初始化。這樣既豐富了種群的多樣性，也提高了初始解的質(zhì)量，使得算法性能大幅度提升。

1.3 位置更新操作

在連續(xù)求解問(wèn)題上，鯨魚(yú)更新位置的公式見(jiàn)式（1），新的鯨魚(yú)位置會(huì)充分利用原來(lái)的位置和最優(yōu)位置進(jìn)行更新。

為提高模塊度值[5]所采取的策略：

（1）慣性權(quán)重的引入

將慣性權(quán)重ω引入，使算法能夠快速收斂于全局最優(yōu)解，見(jiàn)式（3）：

式中：ωmax=0.08；ωmin=0.01。

式（1）加慣性權(quán)重ω后變?yōu)橄率剑?/p>

（2）單路交叉的融入

本文選用Tasgin等提出的單路交叉方式[6]。該策略以種群中的任一個(gè)體作為目標(biāo)個(gè)體xj，從當(dāng)前種群中隨機(jī)選擇另一個(gè)體作為源個(gè)體xi。

當(dāng)p<0.5，|A|<1時(shí)，采用式（5）更新此時(shí)的鯨魚(yú)位置；當(dāng)|A|>1時(shí)，采用單路交叉策略進(jìn)行更新；當(dāng)p≥0.5時(shí)，使用式（2）更新位置。

在位置更新的過(guò)程中，慣性權(quán)重的引入使得算法搜索局部最優(yōu)的能力得到了顯著提升；單路交叉的引入，在提高算法全局搜索能力的同時(shí)，極大地拓寬了算法尋優(yōu)搜索的范圍，而且豐富了種群的多樣性。因此將以上方法用于離散鯨魚(yú)算法的改進(jìn)有利于求得該算法在復(fù)雜網(wǎng)絡(luò)下的最優(yōu)解。

1.4 克隆選擇

在算法計(jì)算過(guò)程中，為提升計(jì)算效率，本文在算法中引入了免疫克隆選擇算子。即將算法計(jì)算過(guò)程中得到的所有最優(yōu)個(gè)體依次放入集合Pb中，然后對(duì)其克隆并選擇。

將集合Pb中的全部個(gè)體按適應(yīng)度從大到小進(jìn)行排序，并取前20%的個(gè)體組建臨時(shí)種群Ptmp，然后，對(duì)Ptmp中的個(gè)體進(jìn)行克隆擴(kuò)充，克隆數(shù)目由式（6）決定：

在個(gè)體中隨機(jī)選擇θ∈[2, n/2]個(gè)節(jié)點(diǎn)，將它們歸為一個(gè)種群PC，并隨機(jī)分配一個(gè)標(biāo)簽；計(jì)算種群PC的適應(yīng)度值，并與Ptmp比較，保留適應(yīng)度大的個(gè)體。

2 仿真驗(yàn)證

本實(shí)驗(yàn)首先對(duì)6個(gè)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集進(jìn)行計(jì)算，并與其他算法進(jìn)行比較；然后通過(guò)人工合成網(wǎng)絡(luò)對(duì)IDWOA與DWOA進(jìn)行綜合測(cè)試；最后以Karate網(wǎng)絡(luò)和Dolphin網(wǎng)絡(luò)為例，通過(guò)Gephi軟件對(duì)IDWOA劃分的社區(qū)結(jié)構(gòu)進(jìn)行可視化展示。

2.1 真實(shí)世界網(wǎng)絡(luò)實(shí)驗(yàn)與分析

（1）離散鯨魚(yú)算法（DWOA）與改進(jìn)離散鯨魚(yú)算法（IDWOA）用于社區(qū)發(fā)現(xiàn)的性能比較

首先考察DWOA與IDWOA在6組真實(shí)網(wǎng)絡(luò)數(shù)據(jù)下的性能比較，其結(jié)果如圖2所示。

圖2 IDWOA和DWOA的性能對(duì)比

由圖2可以看出，離散鯨魚(yú)算法在達(dá)到收斂時(shí)所需要的時(shí)間很短，但它所能達(dá)到的模塊度值也很小，而當(dāng)網(wǎng)絡(luò)規(guī)模很大時(shí)模塊度值仍舊非常小，尤其是Email網(wǎng)絡(luò)，模塊度值僅為0.048。說(shuō)明離散鯨魚(yú)算法在處理較小規(guī)模網(wǎng)絡(luò)時(shí)有效，而處理較大規(guī)模網(wǎng)絡(luò)時(shí)效果不理想。

改進(jìn)的離散鯨魚(yú)算法雖然在時(shí)間上的消耗相比原始算法更多，但是收斂值相比原始算法更好，說(shuō)明提出的改進(jìn)算法對(duì)于真實(shí)網(wǎng)絡(luò)是有效的。

（2）IDWOA與IGA和IDDE的性能比較

考察改進(jìn)IDWOA與IGA[7]和差分進(jìn)化算法IDDE[8]6個(gè)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)下的性能對(duì)比實(shí)驗(yàn)，表1給出了運(yùn)行3種算法30次，算法終止時(shí)刻模塊度函數(shù)值的平均值以及運(yùn)行時(shí)間的平均值。

分析表1可知，從運(yùn)行時(shí)間的角度來(lái)看，當(dāng)IDWOA與IDDE達(dá)到相同模塊度時(shí)，IDWOA耗費(fèi)的時(shí)間相比IDDE更少。

表1 IDWOA和其他算法性能對(duì)比

從模塊度值的角度來(lái)看，當(dāng)網(wǎng)絡(luò)規(guī)模較小時(shí)，IDWOA算法的模塊度值比IGA約高0.01；當(dāng)網(wǎng)絡(luò)規(guī)模較大時(shí)，更能體現(xiàn)IDWOA算法的優(yōu)勢(shì)，尤其對(duì)于Email而言，IDWOA相比IGA提高了0.059。

綜上所述，IDWOA算法在處理大規(guī)模網(wǎng)絡(luò)數(shù)據(jù)集方面，具有兼顧適應(yīng)度精度和快速收斂的特性，總體性能優(yōu)于IGA算法與IDDE算法。

2.2 可視化實(shí)驗(yàn)與分析

在進(jìn)行可視化[8]實(shí)驗(yàn)的過(guò)程中，本文將Gephi軟件作為工具。本小節(jié)實(shí)驗(yàn)用它對(duì)已知社區(qū)結(jié)構(gòu)的Karate和Dolphin網(wǎng)絡(luò)進(jìn)行可視化展示。

Karate數(shù)據(jù)集[9]由Zachary在20世紀(jì)70年代提出，用來(lái)研究復(fù)雜網(wǎng)絡(luò)的信息流。在Karate網(wǎng)絡(luò)上，圖3（a）展示的是真實(shí)網(wǎng)絡(luò)中的社區(qū)劃分，該模塊度值已知，為0.371 5。圖3（b）所示為隨機(jī)運(yùn)行一次IGA，得到的Q=0.402 0。從圖中可以看出，圖中紅色部分只與節(jié)點(diǎn)1連接，可以看做教練的忠實(shí)盟友。此外，節(jié)點(diǎn)9在參考劃分中屬于教練派，但是可以看出他與經(jīng)理派的連邊要多于教練派，因此該算法將其劃為經(jīng)理派社區(qū)。IGA對(duì)節(jié)點(diǎn)9進(jìn)行了更為合理的劃分。圖3（c）所示為隨機(jī)運(yùn)行IDWOA一次，得到的值Q=0.419 8，從圖中可以看出，該算法將節(jié)點(diǎn)9也進(jìn)行了合理劃分，并且在標(biāo)準(zhǔn)劃分基礎(chǔ)上對(duì)2個(gè)派別進(jìn)行了更為細(xì)致的劃分，將俱樂(lè)部?jī)?nèi)部成員聯(lián)系更為緊密的小團(tuán)體也發(fā)掘出來(lái)，得到4個(gè)社區(qū)，得到的社區(qū)結(jié)構(gòu)更準(zhǔn)確。

圖3 Karate網(wǎng)絡(luò)可視化結(jié)果

Dolphin數(shù)據(jù)集[10]是Lusseau等在研究海豚群體生活習(xí)性過(guò)程中構(gòu)建的動(dòng)物社區(qū)網(wǎng)絡(luò)。在海豚網(wǎng)絡(luò)上，圖4（a）展示的是真實(shí)網(wǎng)絡(luò)中的社區(qū)劃分，其模塊度值為0.372 2。圖4（b）展示的是隨機(jī)運(yùn)行IGA一次，得到Q=0.519 0，該算法將雌性海豚劃分為3類。圖4（c）展示的是隨機(jī)運(yùn)行一次IDWOA，求得Q=0.529 0，改進(jìn)的鯨魚(yú)算法不僅能夠保持原有劃分，還未出現(xiàn)錯(cuò)劃性別的情況，而且還能夠根據(jù)海豚間的交流程度將雌性海豚社區(qū)細(xì)化為4個(gè)小社區(qū)，這樣的劃分使得社區(qū)內(nèi)部比社區(qū)之間的相互交流更為頻繁，也更能展現(xiàn)IDWOA算法的有效性。

圖4 網(wǎng)絡(luò)可視化效果

3 結(jié) 語(yǔ)

本文對(duì)社區(qū)發(fā)現(xiàn)這一場(chǎng)景提出IDOWA算法來(lái)適應(yīng)復(fù)雜網(wǎng)絡(luò)應(yīng)用的離散化。通過(guò)6組網(wǎng)絡(luò)數(shù)據(jù)集的仿真計(jì)算，證明IDWOA算法比DWOA算法、IGA算法、IDDE算法更有效。最后，本文以直觀的方式給出IDWOA算法、IGA算法、IDDE算法的Karate網(wǎng)絡(luò)和Dolphin網(wǎng)絡(luò)的可視化效果圖。