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. 刘琳岚，唐家威，朱文俊. 基于特征相似性的机会网络链路预测. 工程科学与技术. 2025(02): 12-21 . 
百度学术
2. 邬剑升，李玉珩. 基于共同邻居惩罚的复杂网络链路预测方法. 计算机测量与控制. 2023(03): 71-75+139 . 百度学术
3. 王子健，薛家玥，杨鹏飞，李艺茹，相洁. 基于对抗生成网络的时序脑功能网络预测方法. 太原理工大学学报. 2023(05): 830-837 . 百度学术
4. 康驻关，金福生，王国仁. 基于Motif聚集系数与时序划分的高阶链接预测方法. 软件学报. 2021(03): 712-725 . 百度学术
5. 高雅娟，王玉峰. 融合多维特征的ISP网络拓扑匹配优化仿真. 计算机仿真. 2021(02): 278-281+286 . 百度学术
6. 顾秋阳，吴宝，池仁勇. 基于高阶路径相似度的复杂网络链路预测方法. 通信学报. 2021(07): 61-69 . 百度学术
7. 王瑾. 动态有向网络中的时序链路预测问题研究. 粘接. 2021(09): 106-109 . 百度学术
其他类型引用(8)
计量
- 文章访问数: 1399
- HTML全文浏览量: 0
- PDF下载量: 583
- 被引次数: 15
下载:
