Journal of Software:2017.28(7):1773-1789

(电子科技大学 计算机科学与技术学院, 四川 成都 611731;上海交通大学 电子信息与电气工程学院, 上海 200240;电子科技大学 信息与软件工程学院, 四川 成都 611731)
Evolutionary Community Detection in Dynamic Networks
NIU Xin-Zheng,SI Wei-Yu,SHE Kun
(School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu 611731, China;School of Electronic Information and Electrical Engineering, Shanghai Jiaotong University, Shanghai 200240, China;School of Information and Software Engineering, University of Electronic Science and Technology of China, Chengdu 611731, China)
Chart / table
Similar Articles
Article :Browse 1692   Download 1749
Received:August 24, 2015    Revised:March 18, 2016
> 中文摘要: 社团的数目和时间平滑性的平衡因子一直是基于进化聚类的动态网络社团发现算法的最大的问题.提出一种基于标签的多目标优化的动态网络社团发现算法(LDMGA).借鉴多目标遗传算法思想,将进化聚类思想转换为多目标遗传算法优化问题,在保证当前时刻的聚类质量的同时,又能使当前聚类结果与前一时刻网络结构保持一致.该算法在初始化过程中加入标签传播算法,提高了初始个体的聚类质量.提出基于标签的变异算法,增强了算法的聚类效果和算法的收敛速度.同时,多目标遗传算法和标签算法的结合使算法可扩展性更强,运行时间随着节点或者边数目的增加呈线性增长.将该算法与目前的优秀算法在仿真数据集和真实数据集上进行对比实验,结果表明,该算法既有良好的聚类效果,又有良好的扩展性.
Abstract: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.
文章编号:     中图分类号:    文献标志码:
基金项目:国家自然科学基金(61300192);国家科技支撑计划(2013BAH33F02);中央高校基本科研业务费(ZYGX2014J052);四川省科技支撑计划(2015GZ0096) 国家自然科学基金(61300192);国家科技支撑计划(2013BAH33F02);中央高校基本科研业务费(ZYGX2014J052);四川省科技支撑计划(2015GZ0096)
Foundation items:National Natural Science Foundation of China (61300192); National Key Technology Research and Development Program of the Ministry of Science and Technology of China (2013BAH33F02); Fundamental Research Funds for the Central Universities (ZYGX2014J052); Science and Technology Support Program of Sichuan, China (2015GZ0096)
Reference text:


NIU Xin-Zheng,SI Wei-Yu,SHE Kun.Evolutionary Community Detection in Dynamic Networks.Journal of Software,2017,28(7):1773-1789