首先定义了节点动态连接度这一概念,然后介绍了基于节点动态连接度的网络社团划分算法,之后再对其中相关参数的取值范围和社团划分结果之间的关系进行了分析,并以Zachary网络为例验证了分析结论。在此基础上,以dolphins、polbooks和football 3个实际网络为对象,进行了社团划分实验,证明了本算法可通过动态调整参数实现对不同网络的社团划分。最后将实验结果与其他几种常见的社团划分算法结果进行了比较,证明了算法的优势,并对算法中需要注意的一些问题进行了说明。
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.
[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.
