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

来源：软件学报杂志2017年第7期北京时间：

作者：牛新征,司伟钰,佘堃

单位：牛新征，电子科技大学 计算机科学与技术学院, 四川 成都 61173111,司伟钰，上海交通大学 电子信息与电气工程学院, 上海 20024002,佘堃，电子科技大学 信息与软件工程学院, 四川 成都 61173103

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

关键词：进化聚类;标签传播;动态网络;社团发现

基金资助：国家自然科学基金（61300192）；国家科技支撑计划（2013BAH33F02）；中央高校基本科研业务费（ZYGX2014J052）；四川省科技支撑计划（2015GZ0096）