基于当前复杂网络中社团划分算法普遍存在算法复杂度过高以及重叠节点挖掘不准确的局限性,提出了一种高效、快速、准确的社团划分算法。基于贪婪算法,建立最大模块度矩阵,并采用堆数据结构,划分非邻域重叠社团。通过分析局部网络的连边情况,计算邻域社团的划分密度,以准确挖掘社团间的重叠节点。新算法经过仿真分析和实证研究表明,算法复杂度降到近线性。
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.
[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.
