基于覆盖的社团发现算法  

Community detection algorithm base on cover

作　　者：张燕平[1,2] 汪洋[1,2] 赵姝[1,2] 段震[1,2] 高兆远[1,2] 

机构地区：[1]安徽大学计算机科学与技术学院,合肥230601 [2]安徽大学计算智能与信号处理教育部重点实验室,合肥230601

出　　处：《南京大学学报（自然科学版）》2013年第5期539-545,共7页Journal of Nanjing University（Natural Science）

基　　金：国家自然科学基金(61175046;61073117);安徽省自然科学基金(11040606M145);安徽大学博士科研启动经费项目(33190057)

摘　　要：社团结构是复杂网络普遍存在的拓扑特性之一,发现复杂网络中的社团结构是复杂网络研究的基础性问题,近年来受到广泛关注,涌现出一批新颖的算法,但时间复杂度和准确率仍然是大规模复杂网络社团结构分析算法面临的两个主要问题.提出一种新的基于覆盖的社团发现算法,该算法的时间复杂度低,得到的社团结构准确率高,并且有效避免了一些经典算法无法识别小于一定粒度社团的问题.首先,以每个节点为中心构造覆盖,并提取其中的一部分覆盖以达到一定的覆盖率;其次,对提取的覆盖进行合并处理;最后,对重复覆盖和未覆盖到的节点做邻居节点投票划分.算法的时间复杂度为O(n2),实验部分测试了算法的准确率,并同标签传播算法(Label Propagation Algorithm,LPA)和Newman快速算法(NFA)作了比较.测试结果显示了本文算法的有效性,在已知社团结构的Zachary数据集上得到与实际完全一致的结果,在未知结构数据集上的Q值也高出LPA算法.Community structure is one of the widespread topological characteristics in complex network, and determining community structure is the fundamental research of complex networks. In recent years, it received extensive attention and a group of novel algorithms emerged. However, the time complexity and accuracy are two major problems of the community structure analysis on the complex network. This paper proposes a new cover based community detection algorithm which has a low time complexity and high accuracy. In addition, the algorithm can effectively avoid the problem that classic algorithm can＇t recognize small communities. Firstly, it regards each node as the center to construct a cover,and extracts part of the cover in order to reach a certain criterion. Secondly,it merges the extracted cover. Finally, it partitions the node which is repeatedly covered or not covered by the neighbor node vote algorithm. The time complexity of the proposed algorithm is O（n^2 ）. The new algorithm is compared with the Label Propagation Algorithm（I.PA）and Newman Fast Algorithm（NFA）. The experimental results demonstrate lhe effectiveness of the proposed algorithm. The results is completely consistent with the actual community structure on the Zachary dataset with the known community structure, and the Q modularity surpasses LPA on the benchmark datasel with the unknown community structure.

关 键 词：复杂网络 社团发现 覆盖 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]