计算机工程 ›› 2009, Vol. 35 ›› Issue (1): 117-119.doi: 10.3969/j.issn.1000-3428.2009.01.039

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

基于相对密度的社团结构探测算法

王立敏1,2,高学东1,宫 雨3,马红权4   

  1. (1. 北京科技大学经济管理学院,北京 100083;2. 北京科技大学中国教育经济信息网管理中心,北京 100083;3. 中国石油大学工商管理学院,北京 102249;4. 钢铁研究总院,北京 100081)
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2009-01-05 发布日期:2009-01-05

Community Structure Detection Algorithm Based on Relative Density

WANG Li-min1,2, GAO Xue-dong1, GONG Yu3, MA Hong-quan4   

  1. (1. School of Economics and Management, University of Science and Technology Beijing, Beijing 100083; 2. Management Center of China Education Economy Information Net, University of Science and Technology Beijing, Beijing 100083; 3. School of Business Administration, China University of Petroleum Beijing, Beijing 102249; 4. Central Iron & Steel Research Institute, Beijing 100081)
  • Received:1900-01-01 Revised:1900-01-01 Online:2009-01-05 Published:2009-01-05

摘要: 社团结构发现方法已经成为复杂网络的一个研究热点。在分析目前一些典型的社团探测算法的基础上,该文提出基于相对密度的社团结构划分方法,该方法可以有效地解决SCAN算法中对参数值过于敏感、参数值难以设置以及高密度社团完全被相连的低密度所包含等问题。把该算法应用到已知社团结构的计算机生成网络中,并与SCAN算法的划分结果进行比较。实验结果表明,该算法是有效可行的。

关键词: 相对密度, 社团结构, 网络, 探测算法

Abstract: The detection of community structure becomes the current hot research topic in the area of complex networks. The paper analyzes typical algorithms of present community structure discovery. A new method of detecting community structure is proposed, which is based on relative density. The method efficiently resolves these problems that parameters are very sensitive and are too difficult for user to determine. The method is applied to synthetic networks and compared with the SCAN algorithm. Experimental results show the feasibility and effectiveness of the proposed approach.

Key words: relative density, community structure, network, detection algorithm

中图分类号: