信息网络安全

信息网络安全 ›› 2017, Vol. 17 ›› Issue (9): 138-142.doi: 10.3969/j.issn.1671-1122.2017.09.032

• • 上一篇    下一篇

基于改进MCMC方法的重叠社区发现算法

付顺顺, 顾益军(), 张大瀚, 孟凡鹏   

  1. 中国人民公安大学信息技术与网络安全学院,北京 100038
  • 收稿日期:2017-08-01 出版日期:2017-09-20 发布日期:2020-05-12
  • 作者简介:

    作者简介： 付顺顺（1989—）,男,河南,硕士研究生,主要研究方向为网络管控、数据挖掘;顾益军（1968—）,男,江苏,副教授,博士,主要研究方向为网络管控、数据挖掘;张大瀚（1991—） ,男,辽宁,硕士研究生,主要研究方向为网络管控、数据挖掘;孟凡鹏（1992—）,男,江苏,硕士研究生,主要研究方向为网络管控、数据挖掘。

Overlapping Community Detection Algorithm Based on Improved MCMC Method

Shunshun FU, Yijun GU(), Dahan ZHANG, Fanpeng MENG   

  1. College of Information Technology and Network Security, People’s Public Security University of China, Beijing 100038, China
  • Received:2017-08-01 Online:2017-09-20 Published:2020-05-12

RichHTML

2

PDF (PC)

124

摘要：

文章对基于社区隶属模型AGM的重叠社区发现算法的特点及机理进行了分析,针对算法在求解过程中存在的易陷入局部最优的问题加以改进。在原有的MCMC采样方法上引入模拟回火（ST）策略和补充搜索过程,实现了待求参数的快速更新并且逐渐逼近理想中的全局最优解。在四种网络中的实验表明,改进之后的算法结果比原算法均有所提高,其中在平均聚类系数较高的DBLP科学合著网络中的实验效果提升了14%。改进之后的算法能够提高采样效率,从而提高社区发现的精确性和可靠性。

关键词: 复杂网络, 重叠社区, MCMC方法, 极大似然

Abstract:

This paper analyzes the characteristics and mechanism of the overlapping community detection algorithm based on Community-Affiliation Graph Model AGM. The aim of this paper is to improve the partial optimization problem .In the original MCMC sampling method, the simulated annealing (ST) strategy and the supplementary search process were introduced to realize the fast updating of the parameters to be obtained and to approximate the global optimal solution. Experiments in four networks show that the results of the improved algorithm are improved compared with the original algorithm, and the experimental results in the DBLP scientific co-network with higher average clustering coefficient are improved by 14%. The improved algorithm can improve the efficiency of sampling and improve the accuracy and reliability of community detection.

Key words: complex network, overlapping community, MCMC method, maximal likelihood

中图分类号: