Multi-objective evolutionary clustering for large-scale dynamic community detection

The research of dynamic community detection is becoming increasingly popular since it can disclose how the community structures change over time in dynamic networks. Evolutionary clustering is often utilized for the goal and has achieved some success, however, still has some major drawbacks: (1) The absence of error correction may lead to the result-drifting problem and the error accumulation problem; (2) The NP-hardness of modularity based community detection makes it low efficiency to get an exact solution. In this paper, an efficient and effective multi-objective method, namely DYN-MODPSO, is proposed, and where the traditional evolutionary clustering framework and the particle swarm algorithm are modified and enhanced, respectively. The main contributions include that: (1) A novel strategy, namely the recent future reference, is devised for the initial clustering result correction to make the dynamic community detection more effective; (2) The traditional particle swarm algorithm is improved and integrated with the evolutionary clustering framework by profitably exploiting the proposed strategy; (3) The deredundant random walk based population initialization is proposed to diversify the individuals in a quality-guaranteed way. Furthermore, the multi-individual crossover operator and the improved interference operator are carefully designed to keep the solution from local optimization. Extensive experiments conducted on the real and the synthetic dynamic networks manifest that the proposed DYN-MODPSO outperforms the competitors in terms of both effectiveness and efficiency. (C) 2020 Elsevier Inc. All rights reserved.

Automated summary

The paper proposes an efficient and effective multi-objective method, DYN-MODPSO, which addresses the issues in dynamic community detection by enhancing the traditional evolutionary clustering framework and particle swarm algorithm. The novel strategy and carefully designed operators contribute to the method's superior performance on both real and synthetic dynamic networks, outperforming competitors in terms of effectiveness and efficiency.