基于面向复杂网络的社区发现算法分析

刘亚琼 王鲁

摘 要：结合复杂网络的社区发现问题，本文提出了经过改进的自适应蝙蝠算法，以适应复杂网络的动态增长、海量特性，解决社区发现问题。从分析结果来看，该算法可以获得较高的社区发现效率。

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

中图分类号：O157.5 文献标识码：A 文章编号：2096-4706（2018）02-0126-02

Analysis of Community Detection Based on Complex Networks

LIU Yaqiong，WANG Lu

（Shandong Agricultural University，Taian 271000，China）

Abstract：Combined with the problem of community discovery in complex networks，this paper proposes an improved adaptive bat algorithm to adapt to the dynamic growth and massive characteristics of complex networks，and solve community detection problems. From the analysis results，the algorithm can achieve high efficiency in community discovery.

Keywords：complex network；community detection；adaptive bat algorithm

0 引 言

伴隨着网络技术的快速发展，各种复杂的网络也随之出现。针对这些网络，还要利用算法进行社区的查找，以便更好地解答网络潜在结构问题。而采用传统的算法目前已经无法满足复杂网络的社区发现效率要求，因此还要加强对基于面向复杂网络的社区发现算法的研究。

1 复杂网络的社区发现研究

复杂网络不同于一般网络结构，其由结点和边组构成，结点为个体，连接结点的边可以表示为个体的复杂关系。在生活中，网络都是复杂且庞大的，通常拥有数十万乃至数百万结点。从属性上来看，这些网络具有强社区结构特性，即有相似或相同兴趣的个体容易聚集成群，群体中个体间的联系频繁、紧密。相反的，不同群体间个体联系减少。在对结点间联系的紧密度进行衡量时，可以利用聚类系数。

通常情况下，真实的网络都具有社区特性，较之随机网络拥有更高的平均聚类系数。针对复杂网络，社区发现为关键的分析路径，可以用于解决网络部分结点集合的查找问题。在发现的集合内部，各结点间联系紧密，集合外的结点联系相对松散。

通过对这些社区的行为结构进行分析，可以发现网络的结构特性，继而为实际问题的解答提供便利。在面向复杂网络的社区发现算法研究方面，目前得到广泛采用的为模块度函数[1]。利用该函数，可以利用定量评价社区结构优劣的度量指标进行问题的转化，从而利用模块度函数优化方法解决问题。采用该算法，得到的函数越大，网络社区结构越显著。但是相较于这一算法，利用智能优化算法可以在有限时间内完成最优解的查找。

2 基于面向复杂网络的社区发现算法

2.1 蝙蝠算法模型

相较于粒子群算法、遗传算法等智能优化算法，蝙蝠群算法拥有收敛速度快、计算量小等特点。在解决复杂网络的社区发现问题时，可以尝试采用该算法解决问题。采用该算法，是利用蝙蝠借助超声波捕食的原理，对蝙蝠回声定位行为特征进行模拟，将根据蝙蝠发射超声波的脉冲频数进行指向性搜索。由于脉冲频数较低，同时响度较大，所以在目标范围不断缩小的情况下，脉冲频数会增加，目标信息量也将得到大量获取，继而实现目标准确定位。

如式（1）所示：

（1）

xidt+1为游走在种群最优解周围的蝙蝠个体位置，vidt+1为第i只蝙蝠在t+1时刻的飞行速度，ε指的是比例因子，为[-1，1]上的随机数，? t指的是t次迭代中，为蝙蝠响度平均值。从式中可以看出比例因子随机游走的强度和方向。

蝙蝠在搜索的过程中，依靠响度和脉冲频数进行猎物查找，发现猎物后信号响度会减弱，频数则相对增大，如式（2）所示：

（2）

ri0指的是最大脉冲频数，α则为响度减弱系数，γ为频数增加系数。针对0<α<1和γ>0的情况，在迭代次数接近∞的情况下，存在Att无限趋近0，rit+1无限趋近ri0的情况。而只有在最优位置，脉冲响度和频数才能更新，因此可以说明蝙蝠接近目标。

按照算法步骤，需要先完成初始化参数设置，包含脉冲频率最大值fmax和最小值fmin，最大响度Ai0，最大脉冲频度，响度衰减系数、频度增加系数和迭代终止条件。而蝙蝠初始位置为Xi，（i=1，2，3，...，NP）；对当前种群适应度进行计算后，需完成最佳蝙蝠位置的查找，然后结合脉冲初始化频率对蝙蝠速度及位置进行更新，得到随机数r1；在随机数比ri大的情况下，可以利用最优蝙蝠尾椎随机扰动计算进行当前个体位置的替代，得到第二个随机数；在随机数比Ai大的情况下，同时F（Xi）比F（X*）大，可以接受最优解，进行响度和频数更新；最后，确认算法是否终止，未终止需要重复更新步骤。

2.2 算法改进分析

通过算法分析可以发现，采用蝙蝠算法的局部搜索能力与全局搜索能力无法得到自动平衡，所以会导致算法无法获得理想应用效果。针对这一问题，还要实现算法改进，得到自适应的蝙蝠算法。采用该算法，由于需要实现字符编码，因此还要利用标签传播方式完成初始化。通过将算法中的速度转化为变异概率，同时加强交叉变异算子的利用，则能使蝙蝠的位置得到更新，使全局搜索和局部开发能力得到均衡。具体来讲，就是要利用模块度函数作为适应度函数，利用蝙蝠空间位置X进行对应节点社区编号的直接表示。在编解码时，还要将网络中节点编码位置维度索引设定为1、2、3、4、5、6、7，对应编码为1、6、6、1、1、6、1。由此可知，编码为1的属于同一个社区，编码为6的属于一个社区。通过采取该种初始化策略，可以使搜索空间得到有效减小，并使算法的运行时间得到缩短，同时也能使种群的多样性得到保留[2]。

而蝙蝠寻优的过程，则是速度和尾椎不断更新的过程，可以利用速度进行蝙蝠处于最优位置概率的表示。在算法逐步收敛的情况下，可以更新的速度逐渐减小，可以证明蝙蝠接近目标。结合速度和迭代次数关系，可以对蝙蝠当前处于最佳位置的概率进行分析。

针对蝙蝠局部搜索能力不强的问题，还要引入变异算子进行局部开发。采用传统算法，在利用各基因进行节点所在社区标号表示时，各基因存在联系，随机交换基因将导致这种关系被割裂，造成求解寻优倒退[3]。

而采用双路交叉算子，可以进行2个染色体的随机选择，然后将其分别作为源染色体和目标染色体。从中进行1个节点的选择，并对其社区成员C和标号l进行获取，可以完成成员查找。

通过双路交叉，可以保持社区关系，并使蝙蝠搜索范围得到拓宽。从算法流程上来看，针对变异蝙蝠，需要依次进行维度d更新，在随机数比变异概率小的情况下，需要对变异节点vd的局部函数Fd（Xt）进行计算，得到邻居节点标签集合Ld，d属于{1，2，...，n}；在标签属于该集合的情况下，对标签j赋值xd，然后进行对应局部函数计算；完成对函数贡献度最大标签的选择，然后将其看成是d维度的标签值，进而进行上述数据更新。如式（3）所示，d维分量可以用j替代，从而进行函数求解，使xdt+1成为最大标签。

（3）

2.3 算法改进效果

在確认算法效果时，需要利用主频3.4GHz的Windows7的台式机操作系统进行算法运行，同时与改进遗传算法进行对比。将种群数设置为100，迭代次数和最大响度分别设定为50和0.95，最大频度设置为0.95，响度衰减系数和频度增加系数分别设为0.95和0.5。从结果来看，自适应蝙蝠算法的Q为0.95，改进遗传算法为0.92，二者的适应度相当，但是自适应蝙蝠算法的收敛速度更快，因此在复杂网络社区发现问题解答方面具有一定优势。

3 结 论

通过分析可以发现，现实生活中的网络多为复杂网络，针对这些网络进行社区发现问题的解决，采用传统算法已经无法满足要求。而采用改进的自适应蝙蝠算法，可以获得较高的适应度，并能加快算法收敛，因此可以使社区的发现效率得到明显提高，继而更好地满足网络社区查找需求。

参考文献：

[1] 金爽.复杂网络社区发现中标签传播算法的研究与应用 [J].信息与电脑（理论版），2018（3）：53-54.

[2] 楚杨杰，杨忠保，洪叶.局部扩展的遗传优化重叠社区发现方法 [J].计算机应用研究，2019（3）：1-2.

[3] 唐朝伟，李彦，段青言，等.自适应进化蝙蝠算法下的复杂网络社区发现 [J].中南大学学报（自然科学版），2018，49（1）：109-117.