CROSS-DISCIPLINARY PHYSICS AND RELATED AREAS OF SCIENCE AND TECHNOLOGY |
|
|
|
|
A New Definition of Modularity for Community Detection in Complex Networks |
YE Zhen-Qing1,2, ZHANG Ke3, HU Song-Nian1, YU Jun1,2** |
1James D. Watson Institute of Genome Sciences, College of Life Sciences, Zhejiang University, Hangzhou 310058 2CAS Key Laboratory of Genome Sciences and Information, Beijing Institute Genomics, Chinese Academy of Sciences, Beijing 100029 3Medical Systems Biology Research Center, Tsinghua University School of Medicine, Beijing 100084 |
|
Cite this article: |
YE Zhen-Qing, ZHANG Ke, HU Song-Nian et al 2012 Chin. Phys. Lett. 29 098901 |
|
|
Abstract We propose a new definition of modularity, i.e. the Qd function, for network analysis, which takes the edge density and topological structure of modules into account and is different from the original strategy of simply calculating the number of edges (the definition of modularity Q introduced by Newman and Girvan). Armed with this novel quality function Qd, we implement an adaptive clustering algorithm for process optimization, and apply our strategy to several synthetic and real-world networks. The results of our exercises demonstrate a better performance in extracting accurate community ingredients from complex networks.
|
|
Received: 18 November 2011
Published: 01 October 2012
|
|
PACS: |
89.75.Hc
|
(Networks and genealogical trees)
|
|
02.10.Ox
|
(Combinatorics; graph theory)
|
|
|
|
|
[1] Strogatz S H 2001 Nature 410 268 [2] Albert R and Barabási A L 2002 Rev. Mod. Phys. 74 47 [3] Mason O and Verwoerd M 2007 IET Syst. Biol. 1(2) 89 [4] Newman M E J 2008 Phys. Today 61 33 [5] Newman M E J 2004 Eur. Phys. J. B 38 321 [6] Fortunato S 2010 Phys. Rep. 486 75 [7] Palla G, Derenyi I, Farkas I and Vicsek T 2005 Nature 435 814 [8] Girvan M and Newman M E J 2002 Proc. Natl. Acad. Sci. USA 99 7821 [9] Guimera R and Amaral L A N 2005 Nature 433 895 [10] Reichardt J and Bornholdt S 2006 Phys. Rev. E 74 016110 [11] Rosvall M and Bergstrom C T 2008 Proc. Natl. Acad. Sci. USA 105 1118 [12] Rosvall M and Bergstrom C T 2007 Proc. Natl. Acad. Sci. USA 104 7327 [13] Newman M E J 2006 Phys. Rev. E 74 036104 [14] Mason A P, Jukka-Pekka O and Perter J M 2009 arXiv:0902.3788 [15] Newman M E J and Grivan M 2004 Phys. Rev. E 69 026113 [16] Newman M E J 2006 Proc. Natl. Acad. Sci. USA 103 8577 [17] Newman M E J 2004 Phys. Rev. E 69 066133 [18] Danon L, Diaz-Guilera A, Duch J and Arenas A 2005 J. Stat. Mech. P09008 [19] Duch J and Arenas A 2005 Phys. Rev. E 72 027104 [20] Hastings M 2006 Phys. Rev. E 74 035102 [21] Raghavan U N, Albert R, Kumara S 2007 Phys. Rev. E 76 036106 [22] Ye Z, Hu S and Yu J 2008 Phys. Rev. E 78 046115 [23] Schuetz P and Caflisch A 2008 Phys. Rev. E 77 046112 [24] Barber M J and Clark J W 2009 Phys. Rev. E 80 026129 [25] Fortunato S and Barthelemy M 2007 Proc. Natl. Acad. Sci. USA 104 36 [26] Kumpula J M, Saramaki J, Kaski K and Kertesz J 2007 Eur. Phys. J. B 56 41 [27] Ruan J and Zhang W 2008 Phys. Rev. E 77 016104 [28] Arenas A, Fernandez A and Gomes S 2008 New J. Phys. 10 053039 [29] Fronczak A, Fronczak P and Holyst J A 2004 Phys. Rev. E 70 056110 [30] Lancichinetti A, Fortunato S and Radicchi F 2008 Phys. Rev. E 78 046110 [31] Lancichinetti A and Fortunato S 2009 Phys. Rev. E 80 056117 [32] Lancichinetti A and Fortunato S 2011 Phys. Rev. E 84 066122 |
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|