NCSS:一种快速有效的复杂网络社团划分算法  

NCSS:an effective and efficient complex network community detection algorithm

作　　者：韩忠明[1] 谭旭升 陈炎[1] 段大高[1] 

机构地区：[1]北京工商大学计算机与信息工程学院,北京100048

出　　处：《中国科学：信息科学》2016年第4期431-444,共14页Scientia Sinica(Informationis)

基　　金：国家自然科学基金项目(批准号:61170112);中央财政支持地方高校发展专项资金人才培养和创新团队建设项目(批准号:19005323132);教育部人文社会科学研究基金项目(批准号:13YJC860006)资助

摘　　要：划分复杂网络中的社团对研究复杂系统在理论和实践上都非常重要.全局社团划分算法划分结果相对准确,但计算量大;局部社团划分算法多数精度低、稳定性差.本文借鉴全局社团划分算法与局部社团划分算法的特点,提出了基于节点中心度和节点与社团间结构关系强度的社团划分算法(NCSS).NCSS算法基于全局信息找到核心节点,然后构建初始社团,从而有效摆脱了传统局部社团算法中初始节点随机选择的稳定性差的弊端.在社团扩张过程中,NCSS每次只需计算社团边缘节点和与其有联系的社团之间的结构关系强度,从而降低了算法时间复杂度.本文在真实网络和模拟基准网络上进行了大量实验,与主流的全局社团划分算法和局部社团划分算法作了比较.在真实网络上NCSS算法的精度比其他算法平均提高6%;在模拟基准网络上,精度则可以提高18%.Community Detection has significant theoretical and practical importance.Global community detection algorithms can achieve high precision,but with worst-case time complexity.Local community detection algorithms mostly have low precision with poor stability.In this paper,a NCSS algorithm is proposed based on node centrality and the structural strength between nodes and local communities in a complex network.The NCSS algorithm ranks core nodes based on global information about the complex network.It then creates initial communities,which can overcome the instability disadvantage of random initial nodes in other local community detection algorithms.During the community-expansion process,the NCSS algorithm calculates only the structural relationship strength between the margin node and related local communities,thus reducing time complexity.Comprehensive experiments are conducted based on different benchmark networks and real complex networks.Typical global community algorithms and local community detection algorithms are selected for comparison.On real networks,the precision of the NCSS algorithm is increased by 6% on average.On benchmark networks,the precision can be increased by as much as 18%.

关 键 词：复杂网络 社团结构 社团划分 核心节点 结构关系强度 

分 类 号：O157.5[理学—数学]