Cai Lei, Zhou Jincheng, Wang Dan
State Key Laboratory of Public Big Data, College of Computer Science and Technology, Guizhou University, Guiyang, China.
Key Laboratory of Complex Systems and Intelligent Optimization of Guizhou Province, School of Computer and Information, Qiannan Normal University for Nationalities, Duyun, China.
PeerJ Comput Sci. 2023 Jul 18;9:e1477. doi: 10.7717/peerj-cs.1477. eCollection 2023.
The goal of dynamic community discovery is to quickly and accurately mine the network structure for individuals with similar attributes for classification. Correct classification can effectively help us screen out more desired results, and it also reveals the laws of dynamic network changes. We propose a dynamic community discovery algorithm, NOME, based on node occupancy assignment and multi-objective evolutionary clustering. NOME adopts the multi-objective evolutionary algorithm MOEA/D framework based on decomposition, which can simultaneously decompose the two objective functions of modularization and normalized mutual information into multiple single-objective problems. In this algorithm, we use a Physarum-based network model to initialize populations, and each population represents a group of community-divided solutions. The evolution of the population uses the crossover and mutation operations of the genome matrix. To make the population in the evolution process closer to a better community division result, we develop a new strategy for node occupancy assignment and cooperate with mutation operators, aiming at the boundary nodes in the connection between the community and the connection between communities, by calculating the comparison node. The occupancy rate of the community with the neighbor node, the node is assigned to the community with the highest occupancy rate, and the authenticity of the community division is improved. In addition, to select high-quality final solutions from candidate solutions, we use a rationalized selection strategy from the external population size to obtain better time costs through smaller snapshot quality loss. Finally, comparative experiments with other representative dynamic community detection algorithms on synthetic and real datasets show that our proposed method has a better balance between snapshot quality and time cost.
动态社区发现的目标是快速准确地挖掘具有相似属性的个体的网络结构以进行分类。正确的分类可以有效地帮助我们筛选出更理想的结果，同时也揭示了动态网络变化的规律。我们提出了一种基于节点占用分配和多目标进化聚类的动态社区发现算法NOME。NOME采用基于分解的多目标进化算法MOEA/D框架，该框架可以将模块化和归一化互信息这两个目标函数同时分解为多个单目标问题。在该算法中，我们使用基于黏菌的网络模型初始化种群，每个种群代表一组社区划分解决方案。种群的进化使用基因组矩阵的交叉和变异操作。为了使进化过程中的种群更接近更好的社区划分结果，我们针对社区之间连接中的边界节点，通过计算比较节点，开发了一种新的节点占用分配策略并与变异算子配合，根据社区与邻居节点的占用率，将节点分配到占用率最高的社区，提高社区划分的真实性。此外，为了从候选解中选择高质量的最终解，我们从外部种群规模采用一种合理化的选择策略，以通过较小的快照质量损失获得更好的时间成本。最后，在合成数据集和真实数据集上与其他有代表性的动态社区检测算法进行的对比实验表明，我们提出的方法在快照质量和时间成本之间具有更好的平衡。
