Improving temporal smoothness and snapshot quality in dynamic network community discovery using NOME algorithm

Abstract

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.

Keywords

• Community discovery
• Dynamic networks
• Evolutionary clustering
• Node occupancy assignment