自适应进化蝙蝠算法下的复杂网络社区发现

唐朝伟，李彦，段青言，杨险峰，胡佩，陈冠豪



自适应进化蝙蝠算法下的复杂网络社区发现

唐朝伟，李彦，段青言，杨险峰，胡佩，陈冠豪

(重庆大学通信工程学院，重庆，400030)

针对现有智能优化算法解决复杂网络社区发现问题存在求解适应度函数精度低、算法收敛速度慢等不足，在基本蝙蝠算法框架下，结合遗传算法的思想，提出一种自适应进化蝙蝠算法。首先，算法以模块度函数作为适应度函数，采用基于字符的编码方式，利用标签传播方法初始化种群；然后，将蝙蝠个体的速度转化为变异概率，使用交叉变异算子更新位置，从而实现蝙蝠的自适应进化；最后，在计算机生成网络和真实网络环境下进行仿真实验。研究结果表明：与用于社区发现的其他智能算法相比，该算法具有收敛速度快、求解精度高的优点，更适合大规模网络下的社区发现。

复杂网络；社区发现；模块度；蝙蝠算法；自适应进化

复杂系统可以建模成复杂网络进行分析，社区可以视为系统中具有某些特定属性或功能的子系统。很多复杂网络都存在社区结构，研究复杂网络的社区结构有着重要的理论意义。首先，通过社区结构，可挖掘节点群体的共同特征和属性，有助于分析整体与部分的关系；再者，在基于现有网络信息的基础上可预测相似节点的功能，节点之间潜在的连接可能性[1]；最后，可以探索社区结构对网络传播、同步、稳定性等动力学特性的影响[2]，且根据社区划分出的网络结构更清晰，可视化效果更直观。社区发现的目的是挖掘网络中的社区结构，社区发现的研究思路层出不穷，算法原理和性能指标各有差异，从算法求解策略的角度出发，社区发现的算法大体分为基于图分割的算 法[3−4]、聚类算法[5−8]、基于网络动力学特性的算 法[9−11]和基于目标函数的优化算法[12−16]等。其中，基于模块度函数(Modularity)的优化算法是目前较为普遍的算法之一。模块度函数(用表示)是NEWMAN与GIRVAN提出的定量评价社区结构优劣的度量指标[5]，从而将复杂网络的社区发现问题转化为模块度函数的优化问题，越大，网络的社区结构越明显。模块度函数的优化是一个NP-complete问题，相比于传统优化算法，智能优化算法对目标函数的要求更为宽松，可以在有限的时间内找到较好的解，因此研究者们更倾向于利用智能优化算法解决社区发现问题。GUIMERA等[14]于2005年提出基于模拟退火的模块度优化算法，该算法有良好的聚类效果，但运行效率低下，需做进一步研究；TASGIN[15]针对社区发现问题提出单路交叉算子，将遗传算法应用于本领域；LI等[17]使用基于二进制矩阵编码的遗传算法，虽然这种编码便于进行交叉操作，但是编解码复杂，算法时间复杂度为(3)，且需要进行编码修正；张英杰等[18]在离散差分进化算法中加入免疫克隆算子，提高了算法的局部开发能力，增加了算法的鲁棒性；ZHOU 等[19]提出一种离散粒子群算法，对速度更新重新定义并应用在符号网络的社区发现。模块度函数存在分辨率受限的问题，即在大规模网络中存在较小社区的情况下这类方法的效果不佳。冷作福[20]使用surprise函数作为社区评价指标，并提出一种基于贪婪思想的局部优化surprise函数的社区发现算法。上述智能算法均可以解决复杂网络社区发现问题，基本思路为：根据求解问题选择适应度函数和编码方式，设置算法参数，最后采用不同的寻优算子不断逼近最优解。然而，在算法求解精度和运行效率方面还有提升空间。2010年由YANG[21]提出一种新型群智能优化算法——蝙蝠算法，对比遗传算法，粒子群算法等，该算法具有计算量小，收敛速度快的特点。本文作者在蝙蝠算法的框架下，结合遗传算法，提出自适应进化蝙蝠算法，将其应用于复杂网络社区发现领域。首先，使用基于字符的编码方式，采用标签传播的方式初始化；然后，将蝙蝠算法中的速度转换为变异概率，利用交叉变异算子更新蝙蝠位置，均衡全局搜索和局部开发能力，并且实现蝙蝠的自适应进化。

1 蝙蝠算法

1.1 蝙蝠算法的仿生学原理

蝙蝠算法(bat algorithm，BA)模拟蝙蝠在黑暗环境中捕食行为特征，以微蝙蝠的回声定位特性为基础，根据发射超声波的脉冲频率进行指向性飞行。在搜索过程中，发射脉冲的频数较低而响度大，随着目标范围的缩小，蝙蝠会增加发射脉冲的频数，从而增加获取目标的信息量，最终精确定位到目标所在位置。

1.2 BA数学模型

1.2.1 蝙蝠的运动

蝙蝠算法包含3个要素，即搜索脉冲频率、发射脉冲响度和频数。蝙蝠算法中蝙蝠是种群中的个体，同时对应解空间中的一个解。在第次迭代中，蝙蝠搜寻猎物时使用的频率为

在局部搜索部分，蝙蝠个体的位置是随机游走在当前种群最优解周围，更新如下：

1.2.2 发射脉冲和响度

蝙蝠算法的局部搜索能力依赖于响度和脉冲频数。一旦蝙蝠发现猎物，发射脉冲信号的响度就会减弱，但频数则会逐渐增大。蝙蝠的脉冲频数和响度更新公式如下：

综上所述，蝙蝠算法步骤如下。

4) 生成随机数1，若1＞r，则使用最优蝙蝠的位置随机扰动式(4)代替当前个体位置；

6) 判断算法是否达到终止条件，若未达到，则重复步骤2)~6)。

2 自适应进化蝙蝠算法

本文对原始蝙蝠算法进行改进，提出自适应进化蝙蝠算法(self-adaptive evolution bat algorithm，SEBA)用于解决社区发现问题。下面将介绍利用改进的蝙蝠算法求解复杂网络中的社区发现问题。

2.1 适应度函数

模块度函数具有求解简单，易于理解的特点，因此，SEBA采用模块度函数作为适应度函数，其数学表达式如下：

2.2 编码方式与初始化

SEBA采用基于字符的编码方式，这种编码简单明了，易于操作。基于字符的编码是用蝙蝠的空间位置直接表示对应节点的社区编号，这是一种最传统也是最直观有效的编码方式。基于字符的编解码过程如图1所示，图1(a)所示为网络拓扑图，假设网络中节点的编码(Code)如图1(b)所示，因为位置维度索引(Index)1，4，5和7的编码都是1，所以它们同属一个社区，如图1(c)中红色节点所示。同理可得节点2，3和6是一个社区。

(a) 网络示意图；(b) 基于字符的编码； (c) 网络社区结构示意图

好的初始化策略不仅可以减小搜索空间，缩短算法运行时间，还能保证种群的多样性。因此，本文采用标签传播的方法初始化种群[16]。

2.3 更新操作

2.3.1 速度更新

2.3.2 位置更新

本文将遗传算法中的交叉算子和变异算子引入到SEBA中，交叉算子用于提升探索能力，变异算子用于局部开发，通过交叉变异运算更新蝙蝠的位置。

1) 交叉算子。首先，传统的交叉算子如单点交叉、多点交叉、均匀交叉只关注基因本身，因此忽略了基因之间的相互关系。再者，本文算法采用基于字符的编码方式，每一个基因表示节点所在社区标号，也就是说这些基因之间是存在联系的，一旦随意交换基因，就会割裂基因之间的关系，改变社区结构，最终使得求解的适应度函数变小，导致寻优过程倒退。因此，传统的交叉算法不能应用于本文算法中。

针对上述问题，本文在TASGIN等[15]提出单路交叉的基础上使用双路交叉算子。具体的策略如下：随机选择2个染色体，分别作为交叉的源染色体和目标染色体。然后随机从源染色体选择1个节点，获取其所在社区成员和社区标号，接着在目标染色体中寻找中的成员，并将其社区标号改为。单路交叉可以形象地比作一种社区集体搬迁的行为，加入到新环境后社区成员之间的联系依然存在，双路交叉不仅保持这种社区关系，而且增加了种群多样性，扩宽了蝙蝠寻优搜索范围。双路交叉的操作如表1，假设存在2个染色体A和B，随机选择某节点4，取源染色体A中节点4的社区标号(=4)，找出其所在社区的其他节点(节点3)，将染色体B中的对应节点(节点3，节点4)的社区标号改为，从而生成新染色体C1交换源染色体和目标染色体，相同操作生成新染色体C2，根据模块度选择C1或者C2作为双路交叉的最终结果。

变异算子的具体操作步骤流程如下。

④ 选择对局部函数贡献度大的标签作为第维的标签值。更新公式见式(10)~(12)。

表1 双路交叉示意说明

2.3.3 随机扰动

(a) 网络示意图；(b) 随机扰动示意图

2.4 算法流程图

综上所述，自适应进化蝙蝠算法的流程如图3 所示。

2.5 时间复杂度分析

3 实验与分析

为了验证自适应进化蝙蝠算法的性能，选择计算机合成网络和7种现实网络两类实验环境，并与免疫离散差分进化(IDDE)算法[18]和改进的遗传算法(IGA)[23]进行对比实验测试。实验均在Inter(R) Core(TM) i7−3770处理器，主频3.4 GHz，内存4 G，操作系统Windows 7的台式机下运行。

图3 SEBA流程图

3.1 计算机合成网络测试

计算NM首先需要定义混淆矩阵，矩阵行号代表参考社区结构，列号代表算法实验发现社区结构，p表示划分在标准社区和发现社区中共同存在的节点数。NM取值范围是[0,1]，NM越大，表明算法划分的结果越接近参考网络的社区结构，表示为

SEBA快速收敛特性分析：蝙蝠算法更新速度选择的参照标准为当前最佳蝙蝠位置，所以蝙蝠位置更易接近极值点；双路交叉算子起全局搜索作用，变异算子进行局部开发，保证算法求解精度；蝙蝠位置的更新有一部分依靠当前最佳位置随机扰动产生，即每只蝙蝠都在最佳位置附近飞行，因此压缩了搜索空间，更易找到最优解或次优解。随着计算机和信息技术的迅猛发展和普及应用，网络规模呈爆炸性增加，SEBA在保证一定求解精度的同时能够快速收敛，比其他对比算法更加具有应用优势。

1—SEBA；2—IGA；3—IDDE。

3.2 真实网络数据集

本文选用Karate，Dolphin，Book，Football，Jazz，E-mail以及Science共7个真实网络数据集进行仿真实验，其中Karate，Dolphin，Book，Football和Jazz网络规模较小，具体描述见表2。

表2 真实网络数据集信息

各算法适应度随迭代次数变化如图5所示。从图5可知：当网络规模较小时(Karate，Dolphin，Book，Football和Jazz)，本文SEBA与对比算法求解的相当，但是收敛速度要比其他算法的快，如图5中曲线1所示。当网络规模增大时(如E-mail和Science)，自适应进化蝙蝠算法快速收敛的优势明显，且在Science网络中求解的显著比其他2种算法的高。

(a) Karate; (b) Dolphin; (c) Book; (d) Football; (e) Jazz; (f) E-mail; (g) Science

通过网络可视化手段考察本文自适应进化蝙蝠算法的性能。Karate网络和Dolphin网络的可视化结果分别如图6和图7所示。

Karate数据集是20世纪70年代由ZACHARY[25]用来进行复杂网络信息流研究。他通过近3年的时间观察某大学空手道俱乐部的业务和人员交往情况，该俱乐部有4位老师分工管理，其中1名教练和经理在授课费用方面存在分歧，随着日积月累，最终爆发矛盾冲突，俱乐部分裂为2部分，如图6(a)所示，其中根据节点度值排序位列前三的是：节点34，节点1和节点33。而节点1和节点33恰恰代表发生冲突的教练和经理，作为网络的重要连通节点，他们的离开导致整个网络分裂，很好地解释了空手道俱乐部一分为二的原因。在空手道网络随机运行SEBA 1次，求得=0.419 8，NM=0.618 7，社区划分结果如图6(b)所示。从图6可以看出：SEBA在标准划分的基础上对2个派别进行更细致的划分，得到4个社区。图6(b)中最右边社区完全只与节点1连接，可以看作教练的忠实盟友。此外，节点9在参考划分中属于教练派，但是可以看出他与经理派的连边要多于教练派，因此本算法将其划为经理派的社区内。

Dolphin数据集是LUSSEAU[26]研究海豚群体生活习性构建的动物社区网络，该网络共有62个节点，159条边，根据海豚性别可以把网络划分出2个社区，如图7(a)所示。

(a) 参考社区结构；(b) SEBA结果

(a) 参考社区结构；(b) SEBA结果

随机抽取SEBA运行1次，求得=0.528 5，NM=0.644 1，社区划分结果如图7(b)所示。本文算法依然保持了原有划分，并未出现错划性别的情况，值得注意的是，根据海豚间的交流程度，还将雌性海豚社区细化为4个小社区，社区内部明显比社区之间交流更为频繁，因此，海豚网络具有一定的层次结构。

4 结论

1) 针对社区发现场景，本文从遗传算法中的交叉编译和变异算子中得到启发，对蝙蝠算法进行改进，提出了自适应进化蝙蝠算法。该算法摒弃原始蝙蝠算法速度和位置更新思想，引入进化过程，通过交叉变异算子计算位置更新，利用速度更新的快慢提供变异概率值，自适应进行变异操作。

2) SEBA具有收敛速度快、求解精度高的特点，比IGA和IDDE等算法具有更优的性能，在大规模网络能够更高效地进行社区发现。

[1] FAN L, WU W, LU Z, et al. Influence diffusion, community detection, and link prediction in social network analysis[J]. Springer Proceedings in Mathematics and Statistics, 2013, 51(1): 305−325.

[2] SUN H J, GAO Z Y. Dynamical behaviors of epidemics on scale-free networks with community structure[J]. Physica A: Statistical Mechanics and its Applications, 2007, 381(1): 491−496.

[3] KERNIGHAN B W, LIN S. An efficient heuristic procedure for partitioning graphs[J]. Bell system technical journal, 1970, 49(2): 291−307.

[4] SUARIS P R, KEDEM G. An algorithm for quadrisection and its application to standard cell placement[J]. IEEE Transactions on Circuits and Systems, 1988, 35(3): 294−303.

[5] NEWMANM M E J, Girvan M. Finding and evaluating community structure in networks[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2004, 69(2): 026113−026127.

[6] CLAUSET A, NEWMAN M E, MOORE C. Finding community structure in very large networks[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2004, 70(6): 264−277.

[7] NEWMAN M E J. Fast algorithm for detecting community structure in networks[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2004, 69(6): 066133-1−066133-5.

[8] NEWMAN M E J. Modularity and community structure in networks[J]. Proceedings of the national academy of sciences, 2006, 103(23): 8577−8582.

[9] XING Y, MENG F, ZHOU Y, et al. A node influence based label propagation algorithm for community detection in networks[J]. The Scientific World Journal, 2014, 2014(5): 1−13.

[10] DONGEN S V. Graph clustering by flow simulation[D]. Netherlands: University of Utrecht. Department of Mathematics and Computer Science, 2000: 57−160.

[11] ROSVALL M, BERGSTROM C T. Maps of random walks on complex networks reveal community structure[J]. Proceedings of the National Academy of Sciences, 2008, 105(4): 1118−1123.

[12] CAI Q, GONG M, MA L, et al. Greedy discrete particle swarm optimization for large-scale social network clustering[J]. Information Sciences, 2015, 9(410): 503−516.

[13] HE D, LIU J, LIU D, et al. Ant colony optimization for community detection in large-scale complex networks[C]// International Conference on Natural Computation. Shanghai, China, 2011: 1151−1155.

[14] GUIMERA R, AMARAL L A N. Functional cartography of complex metabolic networks[J]. Nature, 2005, 433(7028): 895−900.

[15] TASGIN M, HERDAGDELEN A, BINGOL H. Community detection in complex networks using genetic algorithms[J]. EprintarXiv, 2006, 2005(1): 1−6.

[16] 金弟, 刘杰, 杨博, 等. 局部搜索与遗传算法结合的大规模复杂网络社区探测[J]. 自动化学报, 2011, 37(7): 873−882. JIN Di, LIU Jie, YANG Bo, et al. Genetic algorithm with local search for community detection in large-scale complex networks[J]. Acta Automatica Sinica, 2011, 37(7): 873−882.

[17] LI Y, LIU G, LAO S. A genetic algorithm for community detection in complex networks[J]. Journal of Central South University, 2013, 20(5): 1269−1276.

[18] 张英杰, 龚中汉, 陈乾坤. 基于免疫离散差分进化算法的复杂网络社区发现[J]. 自动化学报, 2015, 41(4): 749−757. ZHANG Yingjie, GONG Zhonghan, CHEN Qiankun. Community detection in complex networks using immune discrete differential evolution algorithm[J]. Acta Automatica Sinica, 2015, 41(4): 749−757.

[19] ZHOU D, WANG X. A Neighborhood-impact based community detection algorithm via discrete PSO[J]. Mathematical Problems in Engineering, 2016(4): 1−15.

[20] 冷作福. 基于贪婪优化技术的网络社区发现算法研究[J]. 电子学报, 2014, 42(4): 723−729. LENG Zuofu. Community detection in complex networks based on greedy optimization[J]. Acta Electronic Sinica, 2014, 42(4): 723−729.

[21] YANG X S. A new metaheuristic bat-inspired algorithm[C]// Nature Inspired Cooperative Strategies for Optimization (NICSO2010), Berlin, Heidelberg: Springer, 2010: 65−74.

[22] OSABA E, YANG X S, DIAZ F, et al. An improved discrete bat algorithm for symmetric and asymmetric Traveling Salesman Problems[J]. Engineering Applications of Artificial Intelligence, 2016, 48: 59−71.

[23] 邓琨, 张健沛, 杨静.利用改进遗传算法进行复杂网络社团发现[J]. 哈尔滨工程大学学报, 2013, 34(11): 1438−1444. DENG Kun, ZHANG Jianpei, YANG Jing. Community detection in complex networks using an improved genetic algorithm[J]. Journal of Harbin Engineering University, 2013, 34(11): 1438−1444.

[24] LANCICHINETTI A, FORTUNATO S, RADICCHI F. Benchmark graphs for testing community detection algorithms[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2008, 78(4): 561−570.

[25] ZACHARY W W. An information flow model for conflict and fission in small groups[J]. Journal of Anthropological Research, 1977, 33(4): 452−473.

[26] LUSSEAU D. The emergent properties of a dolphin social network[J]. Proceedings Biological Sciences, 2003, 270(Suppl 2): s186−s188.

(编辑 杨幼平)

Research on community detection in complex networks based on self-adaptive evolution bat algorithm

TANG Chaowei, LI Yan, DUAN Qingyan, YANG Xianfeng, HU Pei, CHEN Guanhao

(School of Communication Engineering, Chongqing University, Chongqing 400030, China)

To solve the problem of low accuracy and slow convergence speed in the community detection of the complex networks, an improved bat algorithm called self-adaptive evolution bat algorithm (SEBA) was proposed by combining the idea of location update and speed update which exists in genetic algorithm. Firstly, network modularitywasemployed as objective function and label propagation method was applied to initialize the population based on the character encoding; then the speed of bat individuals is turned into mutation probability and crossover operator was used to update location information to achieve the self-adaptive evolutionary of bat. Finally, the proposed SEBA was tested on both benchmark networks and real networks in order to compare with other competitive community detection algorithms. The results show that the proposed algorithm significantly accelerates the convergence speed and increases accuracy in the presence of large-scale network structure.

complex network; community detection; modularity; bat algorithm; self-adaptive; evolution

TP31

A

1672−7207(2018)01−0109−09

10.11817/j.issn.1672-7207.2018.01.015

2017−01−12；

2017−03−19

重庆市科委社会民生专项(cstc2013shmszx0500)；重庆市教委科学技术研究项目(KJ1729405)；佛山市经济科技发展专项(2015) (Project(cstc2013shmszx0500) supported by a research grant from Chongqing Science & Technology Commission; Project(KJ1729405) supported by a Scientific and Technological Research Program from Chongqing Municipal Education Commission; Project(2015) supported by Foshan Economic and Information Bureau)

唐朝伟，博士(后)，研究员，从事模式识别，智能信息处理，物联网与大数据分析等研究；E-mail: cwtang@cqu.edu.cn