Abstract：The algorithms of detecting community in complex networks now have lots of disadvantages such as high complexity and ignorance of accurate overlapping nodes. This paper proposes a highly efficient, rapid and accurate community detection algorithm. Based on greedy algorithm, the community is divided by establishing the modularity matrix and adopting the data structure. Considering the edges between local communities, the overlapping community structure is accurately dug by computing the partition density. We evaluate our methods using both synthetic benchmarks and real-world networks, demonstrating the effectiveness of our approach. Our method runs in essentially linear time.
任成磊, 韩定定, 蒲鹏, 张嘉诚. 利用堆数据结构实现邻域重叠社团结构挖掘[J]. 复杂系统与复杂性科学, 2016, 13(1): 102-106.
REN Chenglei, HAN Dingding, PU Peng, ZHANG Jiacheng. Finding Overlapping Community in Network by Using Modularity and Partition Density[J]. Complex Systems and Complexity Science, 2016, 13(1): 102-106.
[1] Girvan M, Newman M E J. Community structure in social and biological networks[J].Proceedings of the National Academy of Sciences, 2002, 99(12): 7821-7826. [2] Adamic L A, Adar E. Friends and neighbors on the web[J].Social Networks, 2003, 25(3): 211-230. [3] Holme P, Huss M, Jeong H. Subnetwork hierarchies of biochemical pathways[J].Bioinformatics, 2003, 19(4): 532-538. [4] Newman M E J. The structure and function of complex networks[J].SIAM Review, 2003, 45(2): 167-256. [5] Guimera R, Amaral L A N. Functional cartography of complex metabolic networks[J].Nature, 2005, 433(7028): 895-900. [6] Flake G W, Lawrence S, Giles C L, et al. Self-organization and identification of web communities[J].Computer, 2002, 35(3): 66-70. [7] Kernighan B W, Lin S. An efficient heuristic procedure for partitioning graphs[J].Bell System Technical Journal, 1970, 49(2): 291-307. [8] Newman M E J, Girvan M. Finding and evaluating community structure in networks[J].Physical Review E, 2004, 69(2): 026113. [9] Clauset A, Newman M E J, Moore C. Finding community structure in very large networks[J].Physical Review E, 2004, 70(6): 066111. [10] Newman M E J. Finding community structure in networks using the eigenvectors of matrices[J].Physical Review E, 2006, 74(3): 036104. [11] Zhang X S, Li Z, Wang R S, et al. A combinatorial model and algorithm for globally searching community structure in complex networks[J].Journal of Combinatorial Optimization, 2012, 23(4): 425-442. [12] Palla G, Derényi I, Farkas I, et al. Uncovering the overlapping community structure of complex networks in nature and society[J].Nature, 2005, 435(7043): 814-818. [13] 杨欢,韩定定. 完全子图的邻域重叠社团结构探测[J].现代电子技术, 2012, 35(18):122-126. Yang H, Han D D. Improvement of neighbourhood overlapping community detection algorithm based on complete subgraph[J].Modern Electronics Technique, 2012, 35(18):122-126. [14] Ahn Y Y, Bagrow J P, Lehmann S. Link communities reveal multiscale complexity in networks, 2010[J].Nature, 466: 761. [15] Zhang Z Y, Wang Y, Ahn Y Y. Overlapping community detection in complex networks using symmetric binary matrix factorization[J].Physical Review E, 2013, 87(6): 062803. [16] Zachary W W. An information flow model for conflict and fission in small groups[J].Journal of Anthropological Research, 1977: 452-473. [17] Lusseau D, Schneider K, Boisseau O J, et al. The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations[J].Behavioral Ecology and Sociobiology, 2003, 54(4): 396-405.
