计算机应用 ›› 2016, Vol. 36 ›› Issue (5): 1296-1301.DOI: 10.11772/j.issn.1001-9081.2016.05.1296

• 人工智能 • 上一篇    下一篇

改进的基于局部模块度的社团划分算法

王天宏1, 武星2, 兰旺森1   

  1. 1. 忻州师范学院 数学系, 山西 忻州 034000;
    2. 上海大学 计算机工程与科学学院, 上海 200072
  • 收稿日期:2015-10-02 修回日期:2016-01-14 出版日期:2016-05-10 发布日期:2016-05-09
  • 通讯作者: 王天宏
  • 作者简介:王天宏(1977-),男,山西忻州人,讲师,硕士,主要研究方向:复杂网络;武星(1980-),男,山西太原人,副教授,博士,主要研究方向:云计算、复杂网络、图像处理;兰旺森(1966-),男,山西静乐人,教授,主要研究方向:复杂网络。
  • 基金资助:
    忻州师范学院重点建设学科项目(2012)

Improved community detection algorithm based on local modularity

WANG Tianhong1, WU Xing2, LAN Wangsen1   

  1. 1. Department of Mathematics, Xinzhou Teachers University, Xinzhou Shanxi 034000, China;
    2. School of Computer Engineering and Science, Shanghai University, Shanghai 200072, China
  • Received:2015-10-02 Revised:2016-01-14 Online:2016-05-10 Published:2016-05-09
  • Supported by:
    This work is partially surported by Key Discipline Construction Project supported of Xinzhou Teachers University (2012), the Youth Foundation Project Supported of Xinzhou Teachers University (QN201521).

摘要: 针对大多复杂网络社团划分算法不能快速发现最优节点加入社团的问题,提出一种利用节点亲密度的局部社团划分算法。引入节点亲密度的概念量化社团与邻居节点的关系,按照节点亲密度由大到小选择节点加入社团,最后以局部模块度为指标终止局部社团扩展。在真实网络和人工仿真网络进行实验,并与基于信息压缩的随机游走算法等4种典型社团划分算法相比较,所提算法划分结果的综合评价指标(F1score)和标准化互信息(NMI)均好于比较算法。实验研究表明,所提算法具有较好的时间效率和准确度,适用于大规模网络社团划分。

关键词: 复杂网络, 社团划分, 节点亲密度, 模块度, 人工合成网络

Abstract: Focusing on the problem that the best neighbor nodes of the communities can not accurately be found in most local community detection algorithms, an improved local community detection algorithm was proposed based on local modularity. The concept of node intimacy was introduced to quantify the relationship between the community and the neighbor nodes by the algorithm, and the nodes were selected into the communities according to the node intimacy in descending order. In the end,the extension of the local community was terminated by the local modularity index. Compared with the four kinds of typical community detection algorithms such as the random walk algorithm based on information compression, the algorithm was applied in the real networks and the artificial simulation network. The comprehensive evaluation indexs (F1score) and Normalized Mutual Informations (NMI) of the results are better than comparison algorithms. The experiments show that the algorithm has better efficiency and accuracy, and is very suitable for community detection in a large scale network.

Key words: complex network, community detection, node intimacy, modularity, synthetic network

中图分类号: