Journal of Frontiers of Computer Science and Technology ›› 2023, Vol. 17 ›› Issue (4): 942-952.DOI: 10.3778/j.issn.1673-9418.2106011

• Artificial Intelligence·Pattern Recognition • Previous Articles     Next Articles

Improved Discrete Mayfly Algorithm for Multi-objective Dynamic Network Commu-nity Detection

LI Hao, YANG Haixiao, ZHANG Lan, HUANG Xin, WANG Haining, KANG Yan   

  1. School of Software, Yunnan University, Kunming 650504, China
  • Online:2023-04-01 Published:2023-04-01

改进离散蜉蝣算法的多目标动态网络社区发现

李浩,杨海潇,张兰,黄欣,王海宁,康雁   

  1. 云南大学 软件学院,昆明 650504

Abstract: Dynamic network community detection can detect community structure changing with time, and its research is of great significance. In order to effectively solve the problem of dynamic network community detection, mayfly algorithm is innovatively introduced into community detection and a multi-objective discrete mayfly algo-rithm (MODMA) for dynamic network community detection is proposed in this paper. Firstly, population generation via label propagation and label diffusion algorithm are combined to initialize the mayfly population in the initia-lization stage, which is beneficial to improving the complementarity and diversity of initial solutions. Secondly, the mayfly individual update strategy is designed by discrete operation to further fully search the global space. Then, an improved crossover operation combined with two mutation strategies is proposed to speed up population evolution. Finally, the local search strategy based on boundary points is carried out for the optimal solution, so that the algorithm can avoid falling into local optimum and improve the optimization search ability and convergence ability. In the process of solving the algorithm, non-dominated sorting and crowding distance sorting mechanisms are used to retain high-quality solutions. A large number of experimental results based on synthetic networks and real net-works show that the MODMA algorithm has higher accuracy than the comparison algorithms.

Key words: dynamic network community detection, mayfly algorithm, multi-objective optimization, initialization

摘要: 动态网络社区发现能检测出随时间不断变化的社区结构,其研究具有重要意义。为了有效地解决动态网络社区发现问题,将蜉蝣算法引入社区发现,提出了一种多目标离散蜉蝣算法的动态网络社区发现方法(MODMA)。首先,在初始化阶段结合基于种群的标签传播算法和标签扩散算法对蜉蝣种群进行初始化,有利于提高初始解的互补性和多样性;其次,将蜉蝣个体更新策略进行离散化,进一步充分搜索全局空间;然后,提出改进的交叉操作并结合两种变异策略,加快种群的进化速度;最后,对最优解进行基于边界点的局部搜索,避免算法陷入局部最优,提高寻优搜索能力和收敛能力。在算法求解过程中,使用非支配排序和拥挤度距离排序机制保留优质解。大量基于合成网络和真实网络的实验结果表明,MODMA算法与对比算法相比具有更高的求解精度。

关键词: 动态网络社区发现, 蜉蝣算法, 多目标优化, 初始化