ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2019, Vol. 56 ›› Issue (2): 281-292.doi: 10.7544/issn1000-1239.2019.20170751

• 人工智能 • 上一篇    下一篇

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

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

  1. (东北大学计算机科学与工程学院 沈阳 110819) (15040107713@163.com)
  • 出版日期: 2019-02-01
  • 基金资助: 
    国家自然科学基金项目(61772124,61332014);中央高校基本科研业务费专项资金(N150404008,N150402002)

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

Li He, Yin Ying, Li Yuan, Zhao Yuhai, Wang Guoren   

  1. (College of Computer Science and Engineering, Northeastern University, Shenyang 110819)
  • Online: 2019-02-01

摘要: 动态网络社区检测能揭示社区结构随时间演变的规律,是目前网络社区研究领域的热点之一.基于演化聚类的方法被广泛采用,但存在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.

Key words: dynamic network community detection, evolutionary clustering, multi-objective optimi-zation, random walk, particle swarm algorithm

中图分类号: