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

doi:10.3778/j.issn.1673-9418.2106011

摘要/Abstract

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

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

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

李浩, 杨海潇, 张兰, 黄欣, 王海宁, 康雁. 改进离散蜉蝣算法的多目标动态网络社区发现[J]. 计算机科学与探索, 2023, 17(4): 942-952.

LI Hao, YANG Haixiao, ZHANG Lan, HUANG Xin, WANG Haining, KANG Yan. Improved Discrete Mayfly Algorithm for Multi-objective Dynamic Network Commu-nity Detection[J]. Journal of Frontiers of Computer Science and Technology, 2023, 17(4): 942-952.

参考文献

[1] 刘紫娟. 智能算法下的复杂网络社区发现研究[D]. 重庆: 重庆大学, 2017.
LIU Z J. Research on community discovery in complex networks based on intelligence algorithm[D]. Chongqing: Chongqing University, 2017.
[2] 端祥宇, 袁冠, 孟凡荣. 动态社区发现方法研究综述[J]. 计算机科学与探索, 2021, 15(4): 612-630.
DUAN X Y, YUAN G, MENG F R. Dynamic community detection: a survey[J]. Journal of Frontiers of Computer Sci-ence and Technology, 2021, 15(4): 612-630.
[3] 高阳, 张宏莉. 动态网络社区发现综述[J]. 智能计算机与应用, 2020, 10(1): 197-199.
GAO Y, ZHANG H L. Community detection in dynamic networks: a survey[J]. Intelligent Computer and Applications, 2020, 10(1): 197-199.
[4] 李赫, 印莹, 李源, 等. 基于多目标演化聚类的大规模动态网络社区检测[J]. 计算机研究与发展, 2019, 56(2): 281-292.
LI H, YIN Y, LI Y, et al. Large-scale dynamic network com-munity detection by multi-objective evolutionary clustering[J]. Journal of Computer Research and Development, 2019, 56(2): 281-292.
[5] LI X M, WU B, GUO Q, et al. Dynamic community detec-tion algorithm based on incremental identification[C]//Procee-dings of the 2015 IEEE International Conference on Data Mining, Atlantic City, Nov 14-17, 2015. Washington: IEEE Computer Society, 2015: 900-907.
[6] MA X K, DONG D. Evolutionary nonnegative matrix facto-rization algorithms for community detection in dynamic net-works[J]. IEEE Transactions on Knowledge & Data Enginee-ring, 2017, 29(5): 1045-1058.
[7] WANG P Z, GAO L, MA X K. Dynamic community detec-tion based on network structural perturbation and topolo-gical similarity[J]. Journal of Statistical Mechanics Theory & Experiment, 2017, 1(1): 013401.
[8] CHAKRABARTI D, KUMAR R, TOMKINS A. Evolutionary clustering[C]//Proceedings of the 12th ACM SIGKDD Inter-national Conference on Knowledge Discovery and Data Mining, Philadelphia, Aug 20-23, 2006. New York: ACM, 2006: 554-560.
[9] LIN Y R, CHI Y, ZHU S H, et al. FacetNet: a framework for analyzing communities and their evolutions in dynamic net-works[C]//Proceedings of the 17th International Conference on World Wide Web, Beijing, Apr 21-25, 2008. New York:ACM, 2008: 685-694.
[10] KIM M S, HAN J W. A particle-and-density based evolu-tionary clustering method for dynamic networks[J]. Procee-dings of the VLDB Endowment, 2009, 2(1): 622-633.
[11] GONG M G, ZHANG L J, MA J J, et al. Community detec-tion in dynamic social networks based on multiobjective immune algorithm[J]. Journal of Computer Science and Technology, 2012, 27(3): 455-467.
[12] FOLINO F, PIZZUTI C. An evolutionary multiobjective app-roach for community discovery in dynamic networks[J]. IEEE Transactions on Knowledge and Data Engineering, 2014, 26(8): 1838-1852.
[13] ZHOU X, ZHAO X H, LIU Y H. A multiobjective discrete bat algorithm for community detection in dynamic networks[J]. Applied Intelligence, 2018, 48(9): 3081-3093.
[14] LIU F Z, WU J, XUE S, et al. Detecting the evolving community structure in dynamic social networks[J]. World Wide Web, 2019, 18: 715-733.
[15] ZENG X X, WANG W, CHEN C, et al. A consensus com-munity-based particle swarm optimization for dynamic com-munity detection[J]. IEEE Transactions on Cybernetics, 2020, 50(6): 2502-2513.
[16] ZERVOUDAKIS K, TSAFARAKIS S. A mayfly optimization algorithm[J]. Computers & Industrial Engineering, 2020, 145: 106559.
[17] EBERHART R, KENNEDY J. A new optimizer using par-ticle swarm theory[C]//Proceedings of the 6th International Symposium on Micro Machine and Human Science, Nagoya, Oct 4-6, 1995. Piscataway: IEEE, 1995: 39-43.
[18] GREFENSTETTE J J. Genetic algorithms and machine learning[J]. Machine Learning, 1988, 3(2): 95-99.
[19] YANG X S. Firefly algorithms for multimodal optimization[C]//LNCS 5792: Proceedings of the 5th International Sympo-sium on Stochastic Algorithms: Foundations and Applica-tions, Sapporo, Oct 26-28, 2009. Berlin, Heidelberg: Springer, 2009: 169-178.
[20] NEWMAN M. Modularity and community structure in net-works[J]. Proceedings of the National Academy of Sciences of the United States of America, 2006, 103(23): 8577-8582.
[21] LEON D, ALBERT D, JORDI D, et al. Comparing commu-nity structure identification[J]. Journal of Statistical Mecha-nics: Theory and Experiment, 2005: 09008.
[22] JENSEN M T. Reducing the run-time complexity of multi-objective EAs: the NSGA-II and other algorithms[J]. IEEE Transactions on Evolutionary Computation, 2003, 7(5): 503-515.
[23] LI Y, LIU G, LAO S Y. A genetic algorithm for community detection in complex networks[J]. Journal of Central South University, 2013, 20(5): 1269-1276.
[24] GONG M G, CAI Q, LI Y Y, et al. An improved memetic algorithm for community detection in complex networks[C]//Proceedings of the 2012 IEEE Congress on Evolutionary Computation, Brisbane, Jun 10-15, 2012. Piscataway: IEEE, 2012: 1-8.
[25] GONG M, CAI Q, CHEN X, et al. Complex network clus-tering by multiobjective discrete particle swarm optimiza-tion based on decomposition[J]. IEEE Transactions on Evo-lutionary Computation, 2014, 18(1): 82-97.
[26] GREENE D, DOYLE D, CUNNINGHAM P. Tracking the evolution of communities in dynamic social networks[C]//Proceedings of the 2010 International Conference on Adva-nces in Social Networks Analysis and Mining, Odense, Aug 9-11, 2010. Washington: IEEE Computer Society, 2010: 176-183.