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

Abstract 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, which, 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 de-redundant 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.