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

Improved Discrete Mayfly Algorithm for Multi-objective Dynamic Network Community Detection

作　　者：李浩[1] 杨海潇 张兰 黄欣 王海宁 康雁[1] LI Hao;YANG Haixiao;ZHANG Lan;HUANG Xin;WANG Haining;KANG Yan(School of Software,Yunnan University,Kunming 650504,China)

机构地区：[1]云南大学软件学院,昆明650504

出　　处：《计算机科学与探索》2023年第4期942-952,共11页Journal of Frontiers of Computer Science and Technology

基　　金：国家自然科学基金(61762092);云南省软件工程重点实验室开放基金项目(2020SE303);云南省重大科技专项(202002AB080001);云南省科技厅重大专项(2019CLJY06,202002AD080047,202202AE090019,202202AD080007)。

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

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

分 类 号：TP391[自动化与计算机技术—计算机应用技术]