Abstract：This paper gives the definition of node’s dynamic connection degree at first, and then introduces the algorithm of finding the community structure by the node’s dynamic connection degree. After that, it analyzes the range of parameter’s value in node’s connection degree and proves it by experimenting on the Zachary network. On this basis, it experiments on three real networks which are dolphins, polbooks and football. The result proves that this algorithm can find different network’s community structure correctly by adjust its parameter’s value. At last, it compares the result with some other common algorithms’ and illustrates some matters that need attention.
贾珺, 胡晓峰, 贺筱媛. 基于节点动态连接度的网络社团划分算法[J]. 复杂系统与复杂性科学, 2016, 13(4): 56-61.
JIA Jun, HU Xiaofeng, HE Xiaoyuan. Finding Community Structure in Networks Using Node’s Dynamic Connection Degree[J]. Complex Systems and Complexity Science, 2016, 13(4): 56-61.
[1] Wasserman S, Faust K. Social Network Analysis: Methods and Applications[M].Cambridge:Cambridge University Press, 1994. [2] Radicchi F, Castellano C, Cecconi F, et al, Defining and identifying communities in networks[J].Proc Natl Acad Sci,2004,101(9):2658-2663. [3] 骆志刚,丁凡,蒋晓舟,等.复杂网络社团发现算法研究新进展[J].国防科技大学学报, 2011,33(1):47-52. Luo Zhigang, Ding Fan, Jiang Xiaozhou, et al. New progress on community detection in complex networks[J].Journal of National University of Defense Technology, 2011, 33(1): 47-52. [4] Kernighan B W, Lin S. An efficient heuristic procedure for partitioning graphs[J].Bell system technical journal, 1970, 49(2): 291-307. [5] Pothen A, Simon H D, Liou K P. Partitioning sparse matrices with eigenvectors of graphs[J].SIAM Journal on Matrix Analysis and Applications, 1990, 11(3): 430-452. [6] Capocci A, Servedio V D P, Caldarelli G, et al. Detecting communities in large networks[J].Physica A: Statistical Mechanics and Its Applications, 2005, 352(2): 669-676. [7] Newman M E J. Finding community structure in networks using the eigenvectors of matrices[J].Physical Review E, 2006, 74(3): 036104. [8] Newman M E J. Fast algorithm for detecting community structure in networks[J].Physical Review E, 2004, 69(6): 066133. [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] 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. [11] Newman M E J, Girvan M. Finding and evaluating community structure in networks[J].Physical Review E, 2004, 69(2): 026113. [12] Fortunato S, Latora V, Marchiori M. Method to find community structures based on information centrality[J].Phys Rev E, 2004, 70(5): 056104. [13] Pan Y, Li D H, Liu J G, et al. Detecting community structure in complex networks via node similarity[J].Physica A: Statistical Mechanics and Its Applications, 2010, 389(14): 2849-2857. [14] 袁超, 柴毅. 基于簇相似度的网络社团结构探测算法[J].物理学报, 2012, 61(21): 539-547. Yuan Chao, Chai Yi. Group similarity based algorithm for network community structure detection[J].Acta Phys Sin, 2012,61(21):539-547. [15] 王兴元,赵仲祥.基于节点间依赖度的社团结构划分方法[J].物理学报, 2014, 63(17): 178901. Wang Xingyuan, Zhao Zhongxiang. Partitioning community structure in complex network based on node dependent degree[J].Acta Phys Sin,2014,63(17): 178901. [16] Zhanga J, Zhanga G, Yanga J, et al. Local community detection algorithm based on hierarchical clustering[J].Journal of Information & Computational Science 2015,12(7):2805-2813. [17] Rosvall M, Bergstrom C T. An information-theoretic framework for resolving community structure in complex networks[J].Proceedings of the National Academy of Sciences, 2007, 104(18): 7327-7331. [18] Deng K, Zhang J P, Yang J. An efficient multi-objective community detection algorithm in complex networks[J].Tehniki vjesnik, 2015, 22(2):319-328. [19] Zachary W W. An information flow model for conflict and fission in small groups[J].Journal of Anthropological Research, 1977,33(4): 452-473. [20] 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.
