PDF(685 KB)
Modularity for community structure in complex networks based on spectral method
ZHANG Cong, SHEN Hui-zhang
Systems Engineering - Theory & Practice ›› 2013, Vol. 33 ›› Issue (5) : 1231-1239.
PDF(685 KB)
PDF(685 KB)
Modularity for community structure in complex networks based on spectral method
In reality many complex networks present community structures obviously. Modularity function can evaluate the partitions of network community structure quantitatively. But the most popular NG's modularity may fail to identify communities smaller than a scale. In this paper, we proposed two modularities for community structure in complex network based on spectral method. The improvement performance modularity not only can apply in the weighted network, but also can overcome the resolution limit of NG's modularity partly. The cohesion modularity take the internal cohesion as the weight basis, and it essentially avoid the resolution limit of NG's modularity and performance modularity. Finally the proposed function has been tested on three networks, including the artificial networks and two classical real-world networks. Computational results demonstrate that the proposed modularities are feasible and effective by comparing with NG's modularity.
complex networks / community structure / modularity / spectral method {{custom_keyword}} /
[1] Fortunato S. Community detection in graphs[J]. Physics Reports, 2010, 486: 75-174.
[2] Porter M A, Onnela J P, Mucha P J. Communities in networks[J]. Notices of the AMS, 2009, 56(9): 1082-1097.
[3] 汪小帆, 李翔, 陈关荣. 复杂网络理论及其应用[M]. 北京: 清华大学出版社, 2006: 162-191.Wang X F, Li X, Chen G R. Complex networks theory and application[M]. Beijing: Tsinghua University Press, 2006: 162-191.
[4] Newman M E J. Modularity and community structure in networks[J]. Proceedings of the National Academy of Sciences of the USA, 2006, 103(23): 8577-8582.
[5] 王林, 戴贯中. 复杂网络的Scale-free性、Scale-free现象及其控制[M]. 北京: 科学出版社, 2009: 1-10, 67-101. Wang L, Dai G Z. Scale-free feature, phenomena & control in complex networks[M]. Beijing: Science Press, 2009: 1-10, 67-101.
[6] Girvan M, Newman M E J. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences of the USA, 2002, 99(12): 7821-7826.
[7] Fortunato S, Barthélemy M. Resolution limit in community detection[J]. Proceedings of the National Academy of Sciences of the USA, 2007, 104(1): 36-41.
[8] Radicchi F, Castellano C, Cecconi F, et al. Defining and identifying communities in networks[J]. Proceedings of the National Academy of Sciences of the USA, 2004, 101(9): 2658-2663.
[9] 汪小帆, 刘亚冰. 复杂网络中的社团结构算法综述[J]. 电子科技大学学报, 2009, 38(5): 537-543. Wang X F, Liu Y B. Overview of algorithms for detecting community structure in complex networks[J]. Journal of University of Electronic Science and Technology of China, 2009, 38(5): 537-543.
[10] Newman M E J. Random graphs with clustering[J]. Physical Review Letters, 2009, 103: 058701.
[11] Shen H, Cheng X, Cai K, et al. Detect overlapping and hierarchical community structure in networks[J]. Physica A, 2009, 388: 1706-1712.
[12] Pothen A, Simon H, Liou K P. Partitioning sparse matrices with eigenvectors of graphs[J]. SIAM Journal of Matrix Analysis and Appllications, 1990, 11(3): 430-452.
[13] Capocci A, Servedio V D P, Caldarelli G, et al. Detecting communities in large networks[J]. Physica A, 2005, 352: 669-676.
[14] Newman M E J. Finding community structure in networks using the eigenvectors of matrices[J]. Physical Review E, 2006, 74(3): 036104.
[15] Zhang S, Wang R S, Zhang X S. Identification of overlapping community structure in complex networks using fuzzy c-means clustering[J]. Physica A, 2007, 374: 483-490.
[16] Newman M E J, Girvan M. Finding and evaluating community structure in networks[J]. Physical Review E, 2004, 69(2): 026113.
[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 of the USA, 2007, 104(18): 7327-7331.
[18] Muff S, Rao F, Caflisch A. Local modularity measure for network clusterizations[J]. Physical Review E, 2005, 72(5): 056107.
[19] Lancichinetti A, Fortunato S. Limits of modularity maximization in community detection[J]. Physical Review E, 2011, 84(6): 066122.
[20] Li Z, Zhang S, Wang R S, et al. Quantitative function for community detection[J]. Physical Review E, 2008, 77(3): 036109.
[21] Brandes U, Gaertler M, Wagner D. Engineering graph clustering: Models and experimental evaluation[J]. ACM Journal of Experimental Algorithmics, 2008, 12: No.1.1.
[22] Kannan R, Vempala S, Vetta A. On clusterings: Good, bad and spectral[J]. Journal of the ACM, 2004, 51(3): 497-515.
[23] Bai Z, Demmel J, Dongarra J, et al. Templates for the solution of algebraic eigenvalue problems: A practical guide[M]. SIAM, Philadelphia, PA, 2000.
PDF(685 KB)
/
| 〈 |
|
〉 |
