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

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

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

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.