DOI: 10.11817/j.issn.1672-7207.2018.01.015

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

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

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

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

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

中图分类号：TP31        文献标志码：A         文章编号：1672-7207(2018)01-0109-09

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)

Abstract: 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 modularity Q was employed 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.

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

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

1 蝙蝠算法

1.1 蝙蝠算法的仿生学原理

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

1.2 BA数学模型

1.2.1 蝙蝠的运动

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

         (1)

式中：为第i只蝙蝠搜索猎物时的发射频率；和分别为脉冲频率的最小值和最大值；为服从0~1均匀分布的随机因子。

蝙蝠搜索猎物时的速度更新公式由下式决定：

          (2)

式中：和分别为第i只蝙蝠在t和t+1时刻的飞行速度；为第i只蝙蝠t时刻的空间位置；为当前搜索过程中蝙蝠群体中的最佳位置；下标d为空间位置维度索引。

蝙蝠的位置更新为

               (3)

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

             (4)

式中：为比例因子，它是在[-1, 1]区间上的随机数；为在第t次迭代中，所有蝙蝠响度的平均值。从式(4)可看出：比例因子代表随机游走的方向和强度。

1.2.2 发射脉冲和响度

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

           (5)

                (6)

式中：为最大脉冲频数；为脉冲响度减弱系数；为脉冲频数增加系数。事实上，类似于模拟退火算法中的冷却系数，对于任意0＜＜1和＞0，当迭代次数时，都有，。脉冲响度和频数在最优位置发生变化时才会更新，这种情况说明蝙蝠正在向目标靠近。

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

1) 初始化参数设置。包括种群NP、搜索脉冲频率范围、最大响度、最大脉冲频度、脉冲响度衰减系数、频度增加系数、迭代终止条件和随机初始化蝙蝠位置；

2) 计算当前种群适应度，找出处于蝙蝠的最佳位置；

3) 根据式(1)初始化搜索脉冲频率f_i，根据式(2)和(3)更新蝙蝠速度和空间位置；

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

5) 生成随机数r₂，当r₁＞A_i且＞时(F为适应度函数)，接受最优解，并使用式(5)和(6)更新响度和频数；

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

2 自适应进化蝙蝠算法

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

2.1 适应度函数

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

        (7)

式中：和为网络中的节点；n为网络节点总数；m为网络总边数；为图的邻接矩阵元素；和分别为节点和的度；和分别为节点和所在的社区编号，当和同属于1个社区时，，反之，。Q越接近于1，网络的社区结构越明显。实际网络中，Q一般在0.3~0.7的范围内，当Q＜0.3时表明网络几乎没有社区结构。

2.2 编码方式与初始化

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

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

Fig. 1  Schematic illustration of codec based on character

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

2.3 更新操作

2.3.1 速度更新

本文算法丢弃脉冲频率^[22]，将蝙蝠的速度转化为遗传算法中变异概率，实现了蝙蝠算法和遗传算法的融合，具体过程如下：第i只蝙蝠速度由当前位置和最优蝙蝠的位置决定，如下式所示。

            (8)

操作符表示异或，，其中是二进制变量，只能取0或1。假设蝙蝠处于2种极端情况：当蝙蝠完全搜索不到目标时，则，此时蝙蝠搜索位置需要全维更新；而在理想情况下，蝙蝠已经在目标位置，则，此时不需要更新。蝙蝠的寻优过程就是速度和位置不断变化的过程，速度代表了蝙蝠当前位置是否处于最优位置的概率，随着算法逐步趋于收敛，需要更新的速度越来越少，说明越来越接近目标位置，需要调整的位置也在减少，于是，利用速度和迭代次数的关系构造函数表示蝙蝠当前位置处于最佳位置的概率：

    (9)

式中：t为当前迭代次数；M_g为最大迭代次数。由式(9)可知：在算法初期需要更新的位置较多，迭代次数较小，而很大，因此，比较小，说明蝙蝠位置距离最佳位置较远，而算法后期则恰恰相反，t变大，减小，导致很大，说明蝙蝠越来越接近目标位置。

2.3.2 位置更新

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

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

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

2) 变异算子。变异算子体现了算法的局部开发能力。传统的变异算子采用随机变异策略，这会导致算法寻优能力退化。SEBA采用局部搜索定向变异方法^[16]，每发生一次变异蝙蝠都在向最优位置靠近。蝙蝠发生变异的概率，越小表示蝙蝠当前位置距离最佳位置较远，而蝙蝠发生变异的概率就越大，于是巧妙地将蝙蝠速度更新引入到变异算子中，实现了蝙蝠的自适应进化。

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

① 待变异的蝙蝠位置为，依次对维度d更新，若随机数小于变异概率，则进入步骤②)；

② 计算变异节点v_d的局部函数，寻找其邻居节点标签集合L_d，；

③ 对于，将标签j赋值给x_d，计算对应局部函数；

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

，重复执行步骤②~④。

           (10)

       (11)

         (12)

式中：为同属一个社区j的节点集合；为节点v_d的邻居节点的社区标签集。式(10)定义局部函数，式(11)表示粒子位置第d维分量用j代替(或者说，节点v_d的标签更改为j)后求解，式(12)表示依次将节点d的标签依次更换为其邻居节点的标签，并求解对应，取使最大的标签作为。

表1  双路交叉示意说明

Table 1  Schematic illustration of two-way cross operation

2.3.3 随机扰动

蝙蝠算法的随机扰动模拟蝙蝠在觅食过程中协同工作机制，种群共享最优位置信息，个体根据最佳位置调整自己的飞行路线，以提高捕食效率。SEBA设计的随机扰动算子如图2所示，假设节点1为扰动点，其社区标签为4。寻找节点1的所有邻居节点2，4，5和7，如图2中箭头所示，将它们的标签设置为4。设置比例因子，依次遍历所有节点，若随机数rand大于，则对节点进行扰动操作。

图2  随机扰动算子示意图

Fig. 2  Schematic illustration of disturbing operation

2.4 算法流程图

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

2.5 时间复杂度分析

设网络的节点数为n，对应于蝙蝠算法搜索空间维度，则计算模块度函数的时间复杂度为O(n²)。SEBA初始化阶段采用标签传播策略，其时间复杂度为，其中表示网络的平均度。算法迭代1次需要进行N_P次交叉变异操作和一次寻找最佳蝙蝠位置操作，时间复杂度为

      (13)

式中：为平均变异概率；为平均社区。故SEBA时间复杂度为

     (14)

3  实验与分析

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

SEBA参数设置为：种群NP=100，迭代次数M_g=50，最大响度A⁰=0.95，最大频数r⁰=0.95，响度衰减系数0.95，频度增加系数0.5。

图3  SEBA流程图

Fig. 3  SEBA flow chart

3.1 计算机合成网络测试

LFR(lancichinetti-fortunato-radicchi)基准网络^[24]是当前社区发现研究中最为常用的计算机合成数据集，该网络模拟现实网络节点之间连接服从幂律分布的特性，产生的社区也服从幂律分布。LFR基准网络主要包括以下参数：网络中节点个数n，节点的平均度；节点最大度k_max；最小社区包含的节点的数量c_min；最大社区包含节点数量c_max；节点与社区外部节点连接概率参数，当＞0.5时，社区中节点与外部的连接近乎一致，网络的社区结构变得模糊，故不属于本文研究场景范围。本文使用LFR网络模型的参数为：n=128，=16，k_max=16，c_min=32，c_max=32，以0.05为步长从0依次递增到0.5。由于社区结构已知，因此采用标准化互信息NMI(Normalized mutual information)作为评价指标。

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

   (15)

式中：B_E和B_F分别为矩阵B的行数和列数；为第i行元素之和；为第j列元素之和；n为网络节点总数。

为了不失一般性，将各算法独立运行30次，最终统计平均得到I_NM随着概率参数μ变化的曲线如图4所示。由图4可以看出：当＜0.4时，3种算法划分的社区结果与参考社区完全一致；当=0.4时，IGA性能出现下降，而IDDE算法和SEBA直至=0.5时I_NM才出现下降，且IDDE算法下降幅度明显比SEBA算法的高。可见本文提出的自适应进化蝙蝠算法在LFR网络测试中的稳定性比IGA的优，其准确性比IGA和IDDE算法的优。

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

图4  合成网络上SEBA与IGA和IDDE算法性能比较

Fig. 4  Comparing SEBA with IGA and IDDE algorithm on composed network

3.2 真实网络数据集

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

表2  真实网络数据集信息

Table 2  Information of real network data sets

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

图5  真实网络SEBA与IGA和IDDE算法性能比较

Fig. 5  Comparing SEBA with IGA and IDDE algorithm on real networks

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

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

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

图6  Karate网络可视化结果

Fig. 6  Visualization results of Karate network

图7  Dolphin网络可视化结果

Fig. 7  Visualization results of Dolphin network

随机抽取SEBA运行1次，求得Q=0.528 5，I_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.

(编辑  杨幼平)

收稿日期：2017-01-12；修回日期：2017-03-19

基金项目(Foundation item)：重庆市科委社会民生专项(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