计算机工程 ›› 2010, Vol. 36 ›› Issue (1): 25-26,2.doi: 10.3969/j.issn.1000-3428.2010.01.009

• 博士论文 • 上一篇    下一篇

基于最大节点接近度的局部社团结构探测算法

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

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

Algorithm for Detecting Local Community Structure Based on Maximal Closeness Degree of Vertex

WANG Li-min1,2, GAO Xue-dong1, MA Hong-quan3   

  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. Central Iron & Steel Research Institute, Beijing 100081)
  • Received:1900-01-01 Revised:1900-01-01 Online:2010-01-05 Published:2010-01-05

摘要: 针对复杂网络社团结构挖掘算法复杂度高的问题,提出一种基于最大节点接近度的局部社团结构挖掘算法。该算法的时间复杂度为O(kd)。为验证该方法计算的准确性和计算的速度,与一种经典的挖掘局部社团结构方法——Clauset算法进行比较。实验结果表明,该算法抽取的社团结构与Clauset算法相比基本一致,但在性能上有明显提高。

关键词: 复杂网络, 局部社团结构, 节点接近度

Abstract: This paper presents an algorithm for detecting local community structure based on maximal closeness degree of vertex for resolving the time complexity problems of finding local community structure in complex networks. The algorithm runs in time O(kd) for general graphs. In order to determine the precision and speed of the method, it is compared with the classical local community identification approaches, namely Clauset algorithm. Experimental results shows that the algorithm is as effective as Clauset algorithm on the whole, and the algorithm is much faster than Clauset algorithm.

Key words: complex networks, local community structure, closeness degree of vertex

中图分类号: