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
摘要: 针对复杂网络社团结构挖掘算法复杂度高的问题,提出一种基于最大节点接近度的局部社团结构挖掘算法。该算法的时间复杂度为O(kd)。为验证该方法计算的准确性和计算的速度,与一种经典的挖掘局部社团结构方法——Clauset算法进行比较。实验结果表明,该算法抽取的社团结构与Clauset算法相比基本一致,但在性能上有明显提高。
关键词:
复杂网络,
局部社团结构,
节点接近度
CLC Number:
WANG Li-min; GAO Xue-dong; MA Hong-quan. Algorithm for Detecting Local Community Structure Based on Maximal Closeness Degree of Vertex[J]. Computer Engineering, 2010, 36(1): 25-26,2.
王立敏;高学东;马红权. 基于最大节点接近度的局部社团结构探测算法[J]. 计算机工程, 2010, 36(1): 25-26,2.