A Two-Stage Multi-Objective Evolutionary Algorithm for Community Detection in Complex Networks

Abstract

Community detection is a crucial research direction in the analysis of complex networks and has been shown to be an NP-hard problem (a problem that is at least as hard as the hardest problems in nondeterministic polynomial time). Multi-objective evolutionary algorithms (MOEAs) have demonstrated promising performance in community detection. Given that distinct crossover operators are suitable for various stages of algorithm evolution, we propose a two-stage algorithm that uses an individual similarity parameter to divide the algorithm into two stages. We employ appropriate crossover operators for each stage to achieve optimal performance. Additionally, a repair operation is applied to boundary-independent nodes during the second phase of the algorithm, resulting in improved community partitioning results. We assessed the effectiveness of the algorithm by measuring its performance on a synthetic network and four real-world network datasets. Compared to four existing competing methods, our algorithm achieves better accuracy and stability.

Keywords

• multi-objective optimization
• community detection
• complex network
• evolutionary algorithms