|本期目录/Table of Contents|

[1]张燕平,汪 洋,赵 姝,等.基于覆盖的社团发现算法[J].南京大学学报(自然科学),2013,49(5):539-545.
 Zhang Yan-Ping,Wang Yang,et al. Community detection algorithm base on cover[J].Journal of Nanjing University(Natural Sciences),2013,49(5):539-545.
点击复制

基于覆盖的社团发现算法()
     

《南京大学学报(自然科学)》[ISSN:0469-5097/CN:32-1169/N]

卷:
49
期数:
2013年第5期
页码:
539-545
栏目:
出版日期:
2013-09-30

文章信息/Info

Title:
 Community detection algorithm base on cover
作者:
张燕平12汪  洋12赵  姝12 段  震12**
1. 安徽大学计算机科学与技术学院,合肥,230601;
2. 安徽大学计算智能与信号处理教育部重点实验室,合肥,230601
Author(s):
 Zhang Yan-Ping1 2 Wang Yang12 Zhao Shu12 Duan Zhen12
 1. School of Computer Science and Technology, Anhui University, Hefei, 230039, China;
2. Computer Science and Technology Institute, Key Laboratory of Intelligent Computing and
Signal Processing of Ministry of Education, Anhui University, Hefei, 230601, China
关键词:
复杂网络社团发现覆 
Keywords:
 complex networks community detection cover
分类号:
-
DOI:
-
文献标志码:
-
摘要:
社团结构是复杂网络普遍存在的拓扑特性之一,发现复杂网络中的社团结构是复杂网络研究的基础性问题,近年来受到广泛关注,涌现出一批新颖的算法,但时间复杂度和准确率仍然是大规模复杂网络社团结构分析算法面临的两个主要问题。提出一种新的基于覆盖的社团发现算法,该算法的时间复杂度低,得到的社团结构准确率高,并且有效避免了一些经典算法无法识别小于一定粒度社团的问题。首先,以每个节点为中心构造覆盖,并提取其中的一部分覆盖以达到一定的覆盖率;其次,对提取的覆盖进行合并处理;最后,对重复覆盖和未覆盖到的节点做邻居节点投票划分。算法的时间复杂度为 ,实验部分测试了算法的准确率,并同标签传播算法(Label Propagation Algorithm, LPA)和Newman快速算法(NFA)作了比较。测试结果显示了本文算法的有效性,在已知社团结构的Zachary数据集上得到与实际完全一致的结果,在未知结构数据集上的Q值也高出LPA算法。
Abstract:
 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 for 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 . The new algorithm is compared with the Label Propagation Algorithm (LPA) and Newman Fast Algorithm (NFA). The experimental results demonstrate the 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 dataset with the unknown community structure.

参考文献/References:

[1] Luo Z G, Jiang X Z. New progresson community detection in complex networks. Journal of National University of Defense Technology, 2011; 33(1): 47~52. (骆志刚,蒋晓舟. 复杂网络社团发现算法研究新进展. 国防科技大学学报, 2011; 33(1): 47~52).
[2] Kemighan B W LS. An efficient heuristic procedure for partitioning graphs. Bell System Technical Journal, 1970, 49(2): 291~307.
[3] Girvan M, Newman M E. Community structure in social and biological networks. Proceedings of the National Academy of Sciences of the United States of America, 2002, 99(12): 7821~7826.
[4] Newman M, Girvan M. Finding and evaluating community structure in networks. Physical Review E, 2004, 69(2):026113-1.
[5] Newman M E J. Fast algorithm for detecting community structure in networks. Physical Review E, 2004; 69(6): 5.
[6] Clauset A. Finding local community structure in networks. Physical Review E, 2005, 72(2): 1~7.
[7] Schuetz P, Caflisch A. Multistep greedy algorithm identifies community structure in real-world and computer-generated networks. Physical Review E, 2008, 78(2):1~17 .
[8] Fortunato S, Barthelemy M. Resolution limit in community detection. Proceedings of the National Academy of Sciences of the United States of America, 2007, 104(1): 36~41.
[9] Rosvall M, Bergstrom CT. An information-theoretic framework for resolving community structure in complex networks. Proceedings of the National Academy of Sciences of the United States of America, 2007, 104(18): 7327~7331.
[10] Xie Z, Wang X F. An overview of algorithms for analyzing community structure in complex networks. Journal of Complex Systems And Complexity Science, 2005; 2(3): 1~12.(解  ?,汪小帆. 复杂网络中的社团结构分析算法研究综述. 复杂系统与复杂性科学. 2005; 2(3): 1~12).
[11] Raghavan U, Albert R, Kumara S. Near linear time algorithm to detect community structures in large-scale networks. Physical Review E, 2007; 76(3): 036106-1.
[12] Michele C G R. DEMON: A local-first discovery method for overlapping communities. ACM SIGKDD, 2012, 615~623.
[13] Agarwal G, Kempe D. Modularity-maximizing graph communities via mathematical programming. European Physical Journal B, 2008, 66(3): 409~418.
[14] Bruno A S S, John H. On the separability of structural classes of communities. ACM SIGKDD, 2012, 624~632.
[15] David F. Gleich C S. Vertex neighborhoods, low conductance cuts, and good seeds for local community methods. ACM SIGKDD, 2012, 597~605.
[16] Wu M L, Sun Q S. Image retrieval based on visual attention and fuzzy regions growing. Journal of Nanjing University (Natural Sciences), 2013, 49(1): 101~108.(吴梦麟,孙权森. 基于视觉注意和模糊区域生长的图像检索. 南京大学学报(自然科学), 2013, 49(1): 101~108).
[17] Gao S B, Zhou J B, Yan Y Y. A new superpixel based spectral clustering for image segmentation. Journal of Nanjing University (Natural Sciences), 2013, 49(2): 169~175.(高尚兵,周静波,严云洋.一种新的基于超像素的谱聚类图像分割算法. 南京大学学报(自然科学), 2013, 49(2): 169~175).
[18] Newman M E J. Modularity and community structure in networks. Proceedings of the National Academy of Sciences of the United States of America, 2006, 103(23): 8577~8582.
[19] Papadopoulos S, Kompatsiaris Y, Vakali A, et al. Community detection in social media. Data Mining and Knowledge Discovery, 2011, 24(3): 515~554.
[20] Yu Zhang D Y Y. Overlapping community detection via bounded nonnegative matrix tri-factorization.  ACM SIGKDD, 2012, 606~614.

相似文献/References:

备注/Memo

备注/Memo:
 国家自然科学基金(61175046,61073117),安徽省自然科学基金(11040606M145),安徽大学博士科研启动经费项目(33190057)
更新日期/Last Update: 2014-01-21