###
Journal of Software:2019.30(4):1045-1061

基于节点向量表达的复杂网络社团划分算法
韩忠明,刘雯,李梦琪,郑晨烨,谭旭升,段大高
(北京工商大学 计算机与信息工程学院, 北京 100048;食品安全大数据技术北京市重点实验室, 北京 100048)
Community Detection Algorithm Based on Node Embedding Vector Representation
HAN Zhong-Ming,LIU Wen,LI Meng-Qi,ZHENG Chen-Ye,TAN Xu-Sheng,DUAN Da-Gao
(School of Computer and Information Engineering, Beijing Technology and Business University, Beijing 100048, China;Beijing Key Laboratory of Big Data Technology for Food Safety, Beijing 100048, China)
Abstract
Chart / table
Reference
Similar Articles
Article :Browse 340   Download 449
Received:October 09, 2016    Revised:June 09, 2017
> 中文摘要: 社团结构划分对复杂网络研究在理论和实践上都非常重要.借鉴分布式词向量理论,提出一种基于节点向量表达的复杂网络社团划分方法(CDNEV).为了构建网络节点的分布式向量,提出启发式随机游走模型.利用节点启发式随机游走得到的节点序列作为上下文,采用SkipGram模型学习节点的分布式向量.选择局部度中心节点作为K-Means算法的聚类中心点,然后用K-Means算法进行聚类,最终得到社团结构.在真实和模拟两种网络上做了丰富的实验,与主流的全局社团划分算法和局部社团划分算法作了比较.在真实网络上CDNEV算法的F1指标比其他算法平均提高19%;在模拟网络上,F1指标则可以提高15%.实验结果表明,相对其他算法,CDNEV算法的精度和效率都较高.
Abstract:Community detection is very important in theoretical and practical for complex research. According to the principle of distributed word vector, a community detection algorithm based on node embedding vector (CDNEV) is proposed in this study. In order to construct the distributed vector of network nodes, a heuristic random walk model is put forward. The node sequence obtained by the heuristic random walk model is used as the context for nodes, and the distributed vector of nodes is learned by SkipGram model. Based on the distributed vector of nodes that are selected from the local node as the center of the K-Means clustering algorithm center, all nodes in a network are clustered with K-Means algorithm, and the community structure are conclude by clustering result. Based on real complex networks and artificial networks used in other state-of-the-art algorithms, comprehensive experiments are conducted. For comparison purpose, typical community detection algorithms are selected to be evaluated. On real networks, the F1 value of CDNEV algorithm is increased 19% on average. The F1 value can be increased by 15% on artificial networks. Experimental results demonstrate that both accuracy and efficiency of CDNEV algorithm outperform other state-of-the-art algorithms.
文章编号:     中图分类号:    文献标志码:
基金项目:国家自然科学基金(61170112,61532006);北京市自然科学基金(4172016,KZ201410011014) 国家自然科学基金(61170112,61532006);北京市自然科学基金(4172016,KZ201410011014)
Foundation items:National Natural Science Foundation of China (61170112, 61532006); Natural Science Foundation of Beijing, China (4172016, KZ201410011014)
Reference text:

韩忠明,刘雯,李梦琪,郑晨烨,谭旭升,段大高.基于节点向量表达的复杂网络社团划分算法.软件学报,2019,30(4):1045-1061

HAN Zhong-Ming,LIU Wen,LI Meng-Qi,ZHENG Chen-Ye,TAN Xu-Sheng,DUAN Da-Gao.Community Detection Algorithm Based on Node Embedding Vector Representation.Journal of Software,2019,30(4):1045-1061