计算机应用 ›› 2015, Vol. 35 ›› Issue (5): 1213-1217.DOI: 10.11772/j.issn.1001-9081.2015.05.1213

• 网络与通信 • 上一篇    下一篇

基于节点相似性度量的社团结构划分方法

梁宗文1,2, 杨帆1, 李建平1   

  1. 1. 电子科技大学 计算机科学与工程学院, 成都 611731;
    2. Department of Electrical and Computer Engineering, Rutgers, The State University of New Jersey, Piscataway 08854, USA
  • 收稿日期:2014-12-08 修回日期:2014-12-29 出版日期:2015-05-10 发布日期:2015-05-14
  • 通讯作者: 梁宗文
  • 作者简介:梁宗文(1985-),男,四川广元人,博士研究生,主要研究方向:网络信息流控制、大数据、网络安全; 杨帆(1987-),男,四川简阳人,博士研究生,主要研究方向:生物特征识别、图像处理; 李建平(1964-),男,湖南祁阳人,教授,博士,主要研究方向:小波分析、生物特征识别、信息安全.
  • 基金资助:

    国家自然科学基金资助项目(61370073);国家建设高水平大学留学项目(201306070037).

Community structure detection based on node similarity in complex networks

LIANG Zongwen1,2, YANG Fan1, LI Jianping1   

  1. 1. School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu Sichuan 611731, China;
    2. Department of Electrical and Computer Engineering, Rutgers, The State University of New Jersey, Piscataway New Jersey 08854, USA
  • Received:2014-12-08 Revised:2014-12-29 Online:2015-05-10 Published:2015-05-14

摘要:

针对复杂网络结构划分过程复杂、准确性差的问题,定义了节点全局和局部相似性衡量指标,并构建节点的相似性矩阵,提出一种基于节点相似性度量的社团结构划分算法.其基本思路是将节点(或社团)按相似性合并条件划分到同一个社团中,如果合并后的节点(或社团)仍然满足相似性合并条件,则继续合并,直到所有节点都得到准确的社团划分.实验结果表明,所提算法能成功正确地划分出真实网络中的社团结构, 性能比标签传播算法(LPA)、GN(Girvan-Newman)、CNM(Clauset-Newman-Moore)等算法优秀,能有效提高结果的准确性和鲁棒性.

关键词: 节点相似性, 社团划分, 社团结构, 复杂网络

Abstract:

Concerning the problem that finding community structure in complex network is very complex, a community discovery algorithm based on node similarity was proposed. The basic idea of this algorithm was that node pairs with higher similarity had more posibility to be grouped into the same community. Integrating local and global similarity, it constructed a similarity matrix which each element represents the similarity of a pair of nodes, then merged nodes which have the most similarity to the same community. The experimental results show that the proposed algorithm can get the correct community structure of networks, and achieve better performance than Label Propagation Algorithm (LPA), GN (Girvan-Newman) and CNM (Clauset-Newman-Moore) algorithms in community detection.

Key words: node similarity, community detection, community structure, complex network

中图分类号: