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

劉紫娟，張啟文，任靜強，田文艷

（1.山西工程職業(yè)學院，山西 太原 030000；2.中國移動通信集團山西有限公司太原分公司，山西 太原 030000；3.太原科技大學，山西 太原 030000）

0 引 言

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

1 原 理

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

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

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

1.1 算法的編碼方式

對于網絡編碼而言，一種傳統(tǒng)也最直觀有效的編碼方式是基于字符的編碼。本文用鯨魚的位置編碼表示對應節(jié)點的社區(qū)編號，基于字符的編碼過程如圖1所示。

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

1.2 種群初始化

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

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

1.3 位置更新操作

在連續(xù)求解問題上，鯨魚更新位置的公式見式（1），新的鯨魚位置會充分利用原來的位置和最優(yōu)位置進行更新。

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

（1）慣性權重的引入

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

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

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

（2）單路交叉的融入

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

當p<0.5，|A|<1時，采用式（5）更新此時的鯨魚位置；當|A|>1時，采用單路交叉策略進行更新；當p≥0.5時，使用式（2）更新位置。

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

1.4 克隆選擇

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

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

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

2 仿真驗證

本實驗首先對6個真實網絡數(shù)據(jù)集進行計算，并與其他算法進行比較；然后通過人工合成網絡對IDWOA與DWOA進行綜合測試；最后以Karate網絡和Dolphin網絡為例，通過Gephi軟件對IDWOA劃分的社區(qū)結構進行可視化展示。

2.1 真實世界網絡實驗與分析

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

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

圖2 IDWOA和DWOA的性能對比

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

改進的離散鯨魚算法雖然在時間上的消耗相比原始算法更多，但是收斂值相比原始算法更好，說明提出的改進算法對于真實網絡是有效的。

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

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

分析表1可知，從運行時間的角度來看，當IDWOA與IDDE達到相同模塊度時，IDWOA耗費的時間相比IDDE更少。

表1 IDWOA和其他算法性能對比

從模塊度值的角度來看，當網絡規(guī)模較小時，IDWOA算法的模塊度值比IGA約高0.01；當網絡規(guī)模較大時，更能體現(xiàn)IDWOA算法的優(yōu)勢，尤其對于Email而言，IDWOA相比IGA提高了0.059。

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

2.2 可視化實驗與分析

在進行可視化[8]實驗的過程中，本文將Gephi軟件作為工具。本小節(jié)實驗用它對已知社區(qū)結構的Karate和Dolphin網絡進行可視化展示。

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

圖3 Karate網絡可視化結果

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

圖4 網絡可視化效果

3 結 語

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