Detecting communities in complex networks can shed light on the essential characteristics and functions of the modeled phenomena. This topic has attracted researchers of various fields from both academia and industry. Among the different methods implemented for community detection, Genetic Algorithms (GA) have become popular recently. Considering the drawbacks of the currently used locus-based and solution-vector-based encodings to represent the individuals, in this paper, we propose (1) a new node similarity-based encoding method to represent a network partition as an individual named MST-based. Then, we propose (2) a new Adaptive Genetic Algorithm for Community Detection, along with (3) a new initial population generation function, and (4) a new adaptive mutation function called sine-based mutation function. Using the proposed method, we combine similarity-based and modularity-optimization-based approaches to find the communities of complex networks in an evolutionary framework. Besides the fact that the proposed representation scheme can avoid meaningless mutations or disconnected communities, we show that the new initial population generation function, and the new adaptive mutation function, can improve the convergence time of the algorithm. Experiments and statistical tests verify the effectiveness of the proposed method compared with several classic and state-of-the-art algorithms.
翻译:在复杂的网络中检测社区可以揭示模型现象的基本特点和功能。这个专题吸引了学术界和工业界各领域的研究人员。在社区检测的不同方法中,遗传变异器(GA)最近变得流行。考虑到目前使用的基于地基的编码和基于溶解的矢量-矢量-基于编码的缺点,以代表个人,我们在本文件中提议:(1) 一种新的基于节点的类似编码方法,以代表一个名为MST的个体的网络分割。然后,我们提议(2) 一个新的适应性遗传值,与(3) 新的初始人口生成功能一起,用于社区探测,(4) 新的适应性突变功能,称为基于正弦化的突变功能。我们使用拟议的方法,将基于类似性和基于模块的基于矢量-优化的方法结合起来,以在进化框架内找到复杂的网络群落。除了拟议的代表性计划可以避免毫无意义的突变或断开社区外,我们还表明,新的初始人口生成功能和新的适应性变异功能可以改进算法的趋同时间。实验和统计性测试数项典型方法的效益。