ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2017, Vol. 54 ›› Issue (11): 2611-2619.doi: 10.7544/issn1000-1239.2017.20160741

• 信息处理 • 上一篇    下一篇

基于HMM的动态社会网络社团发现算法

伊鹏1,周桥1,门浩崧2   

  1. 1(国家数字交换系统工程技术研究中心 郑州 450001); 2(中华人民共和国科学技术部信息中心 北京 100000) (15238363586@139.com)
  • 出版日期: 2017-11-01
  • 基金资助: 
    国家“八六三”高技术研究发展计划基金项目(2015AA016102)

Dynamic Social Network Community Detection Algorithm Based on Hidden Markov Model

Yi Peng1, Zhou Qiao1, Men Haosong2   

  1. 1(National Digital Switching System Engineering & Technology Research & Development Center, Zhengzhou 450001); 2(Department of Information, Ministry of Science & Technology of the People's Republic of China, Beijing 100000)
  • Online: 2017-11-01

摘要: 随着互联网的不断发展,大多数社会网络已逐渐显示出动态特性,动态社会网络社团分析对理解现实生活中社会网络结构和功能具有非常重要的意义.针对动态社会网络中的社团发现问题,提出一种基于隐Markov模型(hidden Markov model, HMM)的HMM_DC算法.该算法考虑到社会网络的动态特性,结合历史信息,将社团发现转化为求解隐马尔可夫模型中的最优状态序列问题,将网络中的社团结构和节点信息分别采用状态链和观察链表示,在无须指定额外参数的情况下实现动态网络的社团结构发现.最后,利用该算法和其他算法对VAST数据集、ENRON数据集和Facebook social network数据集进行实验仿真.仿真结果表明:该算法能够快速、准确地发现真实动态网络中的社团,其模块度Q值和互信息NMI值有很大提升.

关键词: 动态社会网络, 隐Markov模型, 最优状态序列, 社团结构, 社团发现

Abstract: With the continuous development of the Internet, most social networks have gradually demonstrated dynamic characteristics, and dynamic analysis of social network community has a very important significance on the understanding of the structure and function of social networks in real life. The HMM_DC algorithm (hidden Markov model based on dynamic community detection) is proposed according to the HMM (hidden Markov model) to detect the community in dynamic social network. Firstly, the algorithm transforms the community detection problem to get the optimal status chain in hidden Markov model considering the history information and characteristics in dynamic social networks. And the algorithm uses the observed chain and status chain to represent the community structure and node information, and can identify the community structure without extra information. Finally, this algorithm and three other algorithms are used to make comparable simulation experiments with VAST data set, ENRON data set and Facebook social network data set. Experimental results show that HMM_DC algorithm performs effectively and accurately in identifying the community structure in the dynamic social network and the value of Q and NMI can be raised greatly compared with other three algorithms.

Key words: dynamic social network, hidden Markov model (HMM), optimal status chain, community structure, community detection

中图分类号: