基于改进鲸鱼算法的社区发现

刘紫娟，张启文，任静强，田文艳

（1.山西工程职业学院，山西 太原 030000；2.中国移动通信集团山西有限公司太原分公司，山西 太原 030000；3.太原科技大学，山西 太原 030000）

0 引 言

鲸鱼算法[1]最先用于解决连续优化问题，本文针对复杂网络应用环境的离散化特性，对鲸鱼算法的连续位置进行离散化处理，提出了一种用于求解复杂网络社区发现的改进离散鲸鱼算法（Improved Discrete Whale Optimization Algorithm, IDWOA）。

1 原 理

在求解鲸鱼算法的优化问题时，每个鲸鱼都代表一个所求问题的候选解，通过模块度值来判断鲸鱼所处位置的好坏。鲸鱼算法（Whale Optimization Algorithm, WOA）的数学模型表示如下：

但WOA模型并不适用于求解离散问题，可以将WOA算法进行离散化，使其适用于社区发现的应用背景。

通过分析发现，WOA要适用于求解社区发现问题，其对应的鲸鱼位置的每一个维度都应该是整数。因此，在每次位置更新后进行一次四舍五入的取整运算，由此得到离散的鲸鱼算法（DWOA）。

1.1 算法的编码方式

对于网络编码而言，一种传统也最直观有效的编码方式是基于字符的编码。本文用鲸鱼的位置编码表示对应节点的社区编号，基于字符的编码过程如图1所示。

图1 基于字符的编码示意图

1.2 种群初始化

本文采用改进的标签传播方法[2]进行初始化，同时用度和聚集系数[3]来评价节点的重要性[4]。该方法不仅易于计算，同时兼顾了节点的全局和局部影响。

本文对IDWOA算法采用分段初始化策略，即在整个种群中选取5%的个体进行有序标签传播，其余95%的个体仍然由LPA算法对其进行初始化。这样既丰富了种群的多样性，也提高了初始解的质量，使得算法性能大幅度提升。

1.3 位置更新操作

在连续求解问题上，鲸鱼更新位置的公式见式（1），新的鲸鱼位置会充分利用原来的位置和最优位置进行更新。

为提高模块度值[5]所采取的策略：

（1）惯性权重的引入

将惯性权重ω引入，使算法能够快速收敛于全局最优解，见式（3）：

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

式（1）加惯性权重ω后变为下式：

（2）单路交叉的融入

本文选用Tasgin等提出的单路交叉方式[6]。该策略以种群中的任一个体作为目标个体xj，从当前种群中随机选择另一个体作为源个体xi。

当p<0.5，|A|<1时，采用式（5）更新此时的鲸鱼位置；当|A|>1时，采用单路交叉策略进行更新；当p≥0.5时，使用式（2）更新位置。

在位置更新的过程中，惯性权重的引入使得算法搜索局部最优的能力得到了显著提升；单路交叉的引入，在提高算法全局搜索能力的同时，极大地拓宽了算法寻优搜索的范围，而且丰富了种群的多样性。因此将以上方法用于离散鲸鱼算法的改进有利于求得该算法在复杂网络下的最优解。

1.4 克隆选择

在算法计算过程中，为提升计算效率，本文在算法中引入了免疫克隆选择算子。即将算法计算过程中得到的所有最优个体依次放入集合Pb中，然后对其克隆并选择。

将集合Pb中的全部个体按适应度从大到小进行排序，并取前20%的个体组建临时种群Ptmp，然后，对Ptmp中的个体进行克隆扩充，克隆数目由式（6）决定：

在个体中随机选择θ∈[2, n/2]个节点，将它们归为一个种群PC，并随机分配一个标签；计算种群PC的适应度值，并与Ptmp比较，保留适应度大的个体。

2 仿真验证

本实验首先对6个真实网络数据集进行计算，并与其他算法进行比较；然后通过人工合成网络对IDWOA与DWOA进行综合测试；最后以Karate网络和Dolphin网络为例，通过Gephi软件对IDWOA划分的社区结构进行可视化展示。

2.1 真实世界网络实验与分析

（1）离散鲸鱼算法（DWOA）与改进离散鲸鱼算法（IDWOA）用于社区发现的性能比较

首先考察DWOA与IDWOA在6组真实网络数据下的性能比较，其结果如图2所示。

图2 IDWOA和DWOA的性能对比

由图2可以看出，离散鲸鱼算法在达到收敛时所需要的时间很短，但它所能达到的模块度值也很小，而当网络规模很大时模块度值仍旧非常小，尤其是Email网络，模块度值仅为0.048。说明离散鲸鱼算法在处理较小规模网络时有效，而处理较大规模网络时效果不理想。

改进的离散鲸鱼算法虽然在时间上的消耗相比原始算法更多，但是收敛值相比原始算法更好，说明提出的改进算法对于真实网络是有效的。

（2）IDWOA与IGA和IDDE的性能比较

考察改进IDWOA与IGA[7]和差分进化算法IDDE[8]6个真实网络数据下的性能对比实验，表1给出了运行3种算法30次，算法终止时刻模块度函数值的平均值以及运行时间的平均值。

分析表1可知，从运行时间的角度来看，当IDWOA与IDDE达到相同模块度时，IDWOA耗费的时间相比IDDE更少。

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

从模块度值的角度来看，当网络规模较小时，IDWOA算法的模块度值比IGA约高0.01；当网络规模较大时，更能体现IDWOA算法的优势，尤其对于Email而言，IDWOA相比IGA提高了0.059。

综上所述，IDWOA算法在处理大规模网络数据集方面，具有兼顾适应度精度和快速收敛的特性，总体性能优于IGA算法与IDDE算法。

2.2 可视化实验与分析

在进行可视化[8]实验的过程中，本文将Gephi软件作为工具。本小节实验用它对已知社区结构的Karate和Dolphin网络进行可视化展示。

Karate数据集[9]由Zachary在20世纪70年代提出，用来研究复杂网络的信息流。在Karate网络上，图3（a）展示的是真实网络中的社区划分，该模块度值已知，为0.371 5。图3（b）所示为随机运行一次IGA，得到的Q=0.402 0。从图中可以看出，图中红色部分只与节点1连接，可以看做教练的忠实盟友。此外，节点9在参考划分中属于教练派，但是可以看出他与经理派的连边要多于教练派，因此该算法将其划为经理派社区。IGA对节点9进行了更为合理的划分。图3（c）所示为随机运行IDWOA一次，得到的值Q=0.419 8，从图中可以看出，该算法将节点9也进行了合理划分，并且在标准划分基础上对2个派别进行了更为细致的划分，将俱乐部内部成员联系更为紧密的小团体也发掘出来，得到4个社区，得到的社区结构更准确。

图3 Karate网络可视化结果

Dolphin数据集[10]是Lusseau等在研究海豚群体生活习性过程中构建的动物社区网络。在海豚网络上，图4（a）展示的是真实网络中的社区划分，其模块度值为0.372 2。图4（b）展示的是随机运行IGA一次，得到Q=0.519 0，该算法将雌性海豚划分为3类。图4（c）展示的是随机运行一次IDWOA，求得Q=0.529 0，改进的鲸鱼算法不仅能够保持原有划分，还未出现错划性别的情况，而且还能够根据海豚间的交流程度将雌性海豚社区细化为4个小社区，这样的划分使得社区内部比社区之间的相互交流更为频繁，也更能展现IDWOA算法的有效性。

图4 网络可视化效果

3 结 语

本文对社区发现这一场景提出IDOWA算法来适应复杂网络应用的离散化。通过6组网络数据集的仿真计算，证明IDWOA算法比DWOA算法、IGA算法、IDDE算法更有效。最后，本文以直观的方式给出IDWOA算法、IGA算法、IDDE算法的Karate网络和Dolphin网络的可视化效果图。