社团结构是复杂网络普遍存在的拓扑特性之一，发现复杂网络中的社团结构是复杂网络研究的基础性问题，近年来受到广泛关注，涌现出一批新颖的算法，但时间复杂度和准确率仍然是大规模复杂网络社团结构分析算法面临的两个主要问题。提出一种新的基于覆盖的社团发现算法，该算法的时间复杂度低，得到的社团结构准确率高，并且有效避免了一些经典算法无法识别小于一定粒度社团的问题。首先，以每个节点为中心构造覆盖，并提取其中的一部分覆盖以达到一定的覆盖率；其次，对提取的覆盖进行合并处理；最后，对重复覆盖和未覆盖到的节点做邻居节点投票划分。算法的时间复杂度为 ，实验部分测试了算法的准确率，并同标签传播算法(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.
{{custom_sec.title}}
{{custom_sec.title}}
{{custom_sec.content}}
参考文献
[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.
{{custom_fnGroup.title_cn}}
脚注
{{custom_fn.content}}
基金
国家自然科学基金（61175046，61073117），安徽省自然科学基金(11040606M145)，安徽大学博士科研启动经费项目(33190057)
{{custom_fund}}
PDF(858046 KB)
