Community detection algorithm based on signal adaptive transmission
TAN Chunni1, ZHANG Yumei2, ZHANG Jiatong3, WU Xiaojun1,2
1. School of Physics and Information Technology, Shaanxi Normal University, Xi'an Shaanxi 710119, China;
2. School of Computer Science, Shaanxi Normal University, Xi'an Shaanxi 710119, China;
3. School of Cultural Heritage, Northwest University, Xi'an Shaanxi 710127, China
In order to accurately detect the community structure of complex networks, a community detection algorithm based on signal adaptive transmission was proposed. First, the signal was adaptively passed on complex networks,thereby getting the vector affecting on the entire network of each node, then the topological structure of each node was translated into geometrical relationships of algebra vector space. Thus, according to the nature of the clustering, the community structure of the network was detected. In order to get the feasible spatial vectors, the optimum transfer number was determined, which reduced the searching space, and effectively strengthened the search capability of community detection.The proposed algorithm was tested on computer-generated network, Zachary network and American college football network. Compared with Girvan-Newman (GN) algorithm, spectral clustering algorithm,extremal optimization algorithm and signal transmission algorithm, the results show that the accuracy and precision of the proposed community division algorithm is feasible and effective.
[1] WANG X, LI X, CHEN G.Complex network theory and its applications [M]. Beijing: Tsinghua University Press, 2006:162-165.(汪小帆, 李翔, 陈关荣.复杂网络理论及其应用[M].北京:清华大学出版社, 2006:162-165.) [2] SHI C, CAI Y N, FU D, et al. A link clustering based overlap-ping community detection algorithm [J]. Data & Knowledge Engineering, 2013, 87: 394-404. [3] LI K, PANG Y. A unified community detection algorithm in complex network [J]. Neurocomputing, 2014, 130: 36-43. [4] GIRVAN M, NEWMAN M E J. Community structure in social and biological networks [J]. Proceedings of National Academy of Sciences, 2001, 99(12): 7821-7826. [5] DUCH J, ARENAS. A community detection in complex networks using extremal optimization [J].Physical Review E, 2005, 72(2): 027104. [6] WU F, HUBERMAN B A. Finding communities in linear time: a physics approach [J]. The European Physical Journal B, 2004, 38(2): 331-338. [7] DONETTI L, MUNOZ M A. Detecting network communities: a new systematic and efficient algorithm [J]. Journal of Statistical Mechanics: Theory and Experiment, 2004, 37(10): 10012. [8] HU Y, LI M, ZHANG P, et al.Community detection by signaling on complex networks [J].Physcial Review E: Statistical, Nonlinear and Soft Matter Physics, 2008, 78: 016115. [9] WASSERMAN S, FAUST K. Social network analysis: methods and applications [M]. Cambridge: Cambridge University Press, 1994:249-290. [10] YANG B, LIU J. Discovering global network communities based on local centralities [J]. ACM Transactions on the Web, 2008, 2(1): article 9. [11] NEWMAN M E J, GIRAN M. Finding and evaluating community structure in networks [J]. Physical Review E, 2004, 69(2):293-313. [12] ZHANG C, SHEN H. Modularity function for community structure based on natural density of networks [J]. Journal of University of Electronic Science and Technology of China, 2012, 41(2): 185-191.(张聪, 沈惠璋.网络自然密度社团结构模块度函数[J].电子科技大学学报, 2012, 41(2):185-191.) [13] ZACHARY W W. An information flow model for conflict and fission in small groups [J]. Journal of Anthropology Research, 1977, 33(4): 452-473. [14] XIE Z, WANG X. Review of the algorithm analysis research for community structure in complex networks [C]. Complex Systems and Complexity Science, 2005, 2(3): 1-12.(解, 汪小帆.复杂网络中的社团结构分析算法研究综述[J].复杂系统与复杂性科学, 2005, 2(3):1-12.)