• 中国精品科技期刊
  • CCF推荐A类中文期刊
  • 计算领域高质量科技期刊T1类
高级检索

基于多目标演化聚类的大规模动态网络社区检测

李赫, 印莹, 李源, 赵宇海, 王国仁

李赫, 印莹, 李源, 赵宇海, 王国仁. 基于多目标演化聚类的大规模动态网络社区检测[J]. 计算机研究与发展, 2019, 56(2): 281-292. DOI: 10.7544/issn1000-1239.2019.20170751
引用本文: 李赫, 印莹, 李源, 赵宇海, 王国仁. 基于多目标演化聚类的大规模动态网络社区检测[J]. 计算机研究与发展, 2019, 56(2): 281-292. DOI: 10.7544/issn1000-1239.2019.20170751
Li He, Yin Ying, Li Yuan, Zhao Yuhai, Wang Guoren. Large-Scale Dynamic Network Community Detection by Multi-Objective Evolutionary Clustering[J]. Journal of Computer Research and Development, 2019, 56(2): 281-292. DOI: 10.7544/issn1000-1239.2019.20170751
Citation: Li He, Yin Ying, Li Yuan, Zhao Yuhai, Wang Guoren. Large-Scale Dynamic Network Community Detection by Multi-Objective Evolutionary Clustering[J]. Journal of Computer Research and Development, 2019, 56(2): 281-292. DOI: 10.7544/issn1000-1239.2019.20170751

基于多目标演化聚类的大规模动态网络社区检测

基金项目: 国家自然科学基金项目(61772124,61332014);中央高校基本科研业务费专项资金(N150404008,N150402002)
详细信息
  • 中图分类号: TP391

Large-Scale Dynamic Network Community Detection by Multi-Objective Evolutionary Clustering

  • 摘要: 动态网络社区检测能揭示社区结构随时间演变的规律,是目前网络社区研究领域的热点之一.基于演化聚类的方法被广泛采用,但存在2个主要问题:1)缺乏结果校正机制,容易产生“结果漂移”和“误差累积”问题;2)问题的NP-难本质,导致基于模块度的精确社区结构检测在效率上存在很大问题.针对以上问题,通过对传统演化聚类框架和离散粒子群算法的改进及有效结合,提出一种高效且有效的多目标动态社区检测方法(multi-objective discrete particle swarm optimization for dynamic network, DYN-MODPSO),主要工作包括:1)提出基于最近未来参考策略的初始聚类结果校正方法,提高动态社区检测结果的有效性;2)改进传统粒子群算法,使其能与演化聚类框架有效结合;3)提出基于去冗余的随机游走初始群体生成方法,提高传统粒子群算法中的个体多样性并保证个体的初始精度;4)提出多个体交叉算子及改进的干扰算子,提高算法的局部搜索能力与收敛能力.大量基于真实和人工动态网络数据的实验结果证实,提出的方法在效率和有效性方面,显著优于同类比较算法.
    Abstract: Evolutionary clustering is often utilized for dynamic network community detection to uncover the evolution of community structure over time. However, it has the following main problems: 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 inefficient to get an exact solution. In this paper, an efficient and effective multi-objective method, namely DYN-MODPSO(multi-objective discrete particle swarm optimization for dynamic network), is proposed, where the traditional evolutionary clustering framework and the particle swarm algorithm are modified and enhanced, respectively. The main work of this article is as follows: 1) A novel strategy, namely the recently 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 modified so that it could be effectively integrated with the evolutionary clustering framework; 3) the de-redundancy random walk based initial population generation method is presented to improve the diversity and the initial precision of the individuals; 4) the multi-individual crossover operator and the improved interference operator are developed to enhance the local search and the convergence abilities of DYN-MODPSO. Extensive experiments conducted on the real and the synthetic dynamic networks show that the efficiency and the effectiveness of DYN-MODPSO are significantly better than those of the competitors.
  • 期刊类型引用(7)

    1. YU Yongbin,TANG Haowen,FENG Xiao,WANG Xiangxiang,HUANG Hang. Design of multilayer cellular neural network based on memristor crossbar and its application to edge detection. Journal of Systems Engineering and Electronics. 2023(03): 641-649 . 必应学术
    2. 杨海兰,祁永强,吴保磊,荣丹,洪妙英,王军. 动态环境下基于忆阻强化学习的移动机器人路径规划. 系统仿真学报. 2023(07): 1619-1633 . 百度学术
    3. 刘军,缪伟伟,吴玺,任福继. 约束重编程单元数量的忆阻器阵列闭环重映射算法. 计算机辅助设计与图形学学报. 2023(06): 970-978 . 百度学术
    4. 杨海兰,祁永强,荣丹. 仓储环境下基于忆阻强化学习的AGV路径规划. 计算机工程与应用. 2023(17): 318-327 . 百度学术
    5. 张晋博,丁传红. 基于神经网络的模数转换电路动态误差源识别系统设计. 现代电子技术. 2019(21): 53-57 . 百度学术
    6. 张粮,王宇,张小元,郭宇锋,连晓娟,肖建,童祎. 一种基于新型忆阻器的识别电路. 南京邮电大学学报(自然科学版). 2019(05): 34-40 . 百度学术
    7. 张小勇,杨立波,常浩,史俊斌,尚珍珍. 基于忆阻器的鉴相电路设计与分析. 太原师范学院学报(自然科学版). 2018(04): 65-68+87 . 百度学术

    其他类型引用(15)

计量
  • 文章访问数:  1393
  • HTML全文浏览量:  0
  • PDF下载量:  579
  • 被引次数: 22
出版历程
  • 发布日期:  2019-01-31

目录

    /

    返回文章
    返回