基于进化聚类的动态网络社团发现

Evolutionary Community Detection in Dynamic Networks

社团的数目和时间平滑性的平衡因子一直是基于进化聚类的动态网络社团发现算法的最大的问题.提出一种基于标签的多目标优化的动态网络社团发现算法(LDMGA).借鉴多目标遗传算法思想,将进化聚类思想转换为多目标遗传算法优化问题,在保证当前时刻的聚类质量的同时,又能使当前聚类结果与前一时刻网络结构保持一致.该算法在初始化过程中加入标签传播算法,提高了初始个体的聚类质量.提出基于标签的变异算法,增强了算法的聚类效果和算法的收敛速度.同时,多目标遗传算法和标签算法的结合使算法可扩展性更强,运行时间随着节点或者边数目的增加呈线性增长.将该算法与目前的优秀算法在仿真数据集和真实数据集上进行对比实验,结果表明,该算法既有良好的聚类效果,又有良好的扩展性.

The number of communities and temporal smoothness are always the main limitations in the field of evolutionary community detection for dynamic networks. In this paper, a new multi-objective approach based on the label propagation algorithm （LDMGA） is proposed. Employing the idea of multi-objective genetic algorithm, the evolutionary clustering algorithm is transformed into a multi-objective optimization problem, which not only improves the clustering quality, but also minimizes clustering drift from one time step to the successive one. Population initialization based on the label propagation algorithm improves the clustering quality of initial individuals. In addition, applying the label propagation algorithm to the mutation progress enhances the quality of clustering and the convergence rate. At the same time, the combination of the multi-objective genetic algorithm and the label propagation algorithm makes the algorithm more scalable, and the running time increases linearly with the increase of the number of nodes or edges. The experiment on the synthesized datasets and real datasets shows that the proposed algorithm consistently provides good clustering quality and scalability.