基于免疫遗传算法的复杂网络社区发现

Community detection in complex networks based on immune genetic algorithm

针对大部分基于智能优化算法的社区发现方法存在的种群退化、寻优能力不强、计算过程复杂、需要先验知识等问题,提出了一种基于免疫遗传算法(GA)的复杂网络社区发现方法。算法将改进的字符编码和相应的遗传算子相结合,在不需要先验知识的情况下可自动获得最优社区数和社区划分方案;将免疫原理引入遗传算法的选择操作中,保持了群体多样性,改善了遗传算法所固有的退化现象;在初始化种群及交叉和变异算子中利用网络拓扑结构的局部信息,有效缩小了搜索空间,增强了寻优能力。计算机生成网络和真实网络上的仿真实验结果表明算法可自动获取最优社区数和社区划分方案并具有较高的精度,说明算法具有可行性和有效性。

As many of the community detection methods based on intelligent optimization algorithms suffer from degeneracy, unsatisfactory optimization ability, complex computational process, requiring priori knowledge, etc., a community detection method in complex networks based on immune Genetic Algorithm （GA） was proposed. The algorithm combined the improved character encoding with the corresponding genetic operator, and automatically acquired the opt!real community number and the community detection solution without the priori knowledge. Immune principle was introduced into selection operation of GA, which maintained the diversity of individuals, and therefore improved the intrinsic degeneracy of GA. By utilizing the local information of the network topology structure in initialization population, crossover operation and mutation operation, the search space was compressed and the optimization ability was improved. The simulation results on both computer-generated networks and real-world networks show that the algorithm acquires the optimal community number and the community detection solution, and has a higher accuracy. This indicates the algorithm is feasible and valid for community deteetion in complex networks.