主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2018-2019年专刊出版计划 微信服务介绍 最新一期:2018年第8期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
牛新征,司伟钰,佘堃.基于进化聚类的动态网络社团发现.软件学报,2017,28(7):1773-1789
基于进化聚类的动态网络社团发现
Evolutionary Community Detection in Dynamic Networks
投稿时间:2015-08-24  修订日期:2016-03-18
DOI:10.13328/j.cnki.jos.005114
中文关键词:  进化聚类  标签传播  动态网络  社团发现
英文关键词:evolutionary clustering  label propagation  dynamic network  community discovery
基金项目:国家自然科学基金(61300192);国家科技支撑计划(2013BAH33F02);中央高校基本科研业务费(ZYGX2014J052);四川省科技支撑计划(2015GZ0096)
作者单位E-mail
牛新征 电子科技大学 计算机科学与技术学院, 四川 成都 611731 xinzhengniu@uestc.edu.cn 
司伟钰 上海交通大学 电子信息与电气工程学院, 上海 200240  
佘堃 电子科技大学 信息与软件工程学院, 四川 成都 611731  
摘要点击次数: 979
全文下载次数: 792
中文摘要:
      社团的数目和时间平滑性的平衡因子一直是基于进化聚类的动态网络社团发现算法的最大的问题.提出一种基于标签的多目标优化的动态网络社团发现算法(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.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利