| CROSS-DISCIPLINARY PHYSICS AND RELATED AREAS OF SCIENCE AND TECHNOLOGY |
|
|
|
|
Community Detection by Neighborhood Similarity |
| LIU Xu,XIE Zheng,YI Dong-Yun** |
| Department of Mathematics and Systems Science, College of Science, National University of Defense Technology, Changsha 410073 |
|
| Cite this article: |
|
LIU Xu, XIE Zheng, YI Dong-Yun 2012 Chin. Phys. Lett. 29 048902 |
|
|
|
|
Abstract Detection of the community structure in a network is important for understanding the structure and dynamics of the network. By exploring the neighborhood of vertices, a local similarity metric is proposed, which can be quickly computed. The resulting similarity matrix retains the same support as the adjacency matrix. Based on local similarity, an agglomerative hierarchical clustering algorithm is proposed for community detection. The algorithm is implemented by an efficient max-heap data structure and runs in nearly linear time, thus is capable of dealing with large sparse networks with tens of thousands of nodes. Experiments on synthesized and real-world networks demonstrate that our method is efficient to detect community structures, and the proposed metric is the most suitable one among all the tested similarity indices.
|
|
|
Received: 18 September 2011
Published: 04 April 2012
|
|
| PACS: |
89.75.Hc
|
(Networks and genealogical trees)
|
| |
89.75.Fb
|
(Structures and organization in complex systems)
|
| |
89.75.-k
|
(Complex systems)
|
|
|
|
|
|
| [1] Albert R and Barabasi A L 2002 Rev. Mod. Phys. 74 47[2] Boccaletti S, Latora V, Moreno Y, Chavez M and Hwang D U 2006 Phys. Rep. 424 175[3] Fortunato S 2010 Phys. Rep. 486 75[4] Shang M S, Chen D B and Zhou T 2010 Chin. Phys. Lett. 27 058901[5] Palla G, Barabasi A L and Vicsek T 2007 Nature 446 664[6] Cohen R, Erez K, Ben Avraham D and Havlin S 2000 Phys. Rev. Lett. 85 4626[7] Pastor Satorras R and Vespignani A 2001 Phys. Rev. Lett. 86 3200[8] Yan G, Fu Z Q, Ren J and Wang W X 2007 Phys. Rev. E 75 016108[9] Zhou Y Z, Liu Z H and Zhou J 2007 Chin. Phys. Lett. 24 581[10] Wang R, Chi L P and Cai X 2008 Chin. Phys. Lett. 25 1502[11] Shao J, Havlin S and Stanley H 2009 Phys. Rev. Lett. 103 018701[12] Chang H, Su B B, Liu C P, Gao M, Di Z R and He D R 2008 Int. J. Mod. Phys. C 19 1537[13] Zhou T, Zhao M, Chen G, Yan G, and Wang B H 2007 Phys. Lett. A 368 431[14] Wang X F and Chen G 2002 IEEE Trans. Circ. Systems I 49 54[15] Newman M E J and Girvan M 2004 Phys. Rev. E 69 026113[16] Fortunato S and Barthelemy M 2007 Proc. Natl. Acad. Sci. U. S.A. 104 36[17] Good B H, De Montjoye Y A and Clauset A 2010 Phys. Rev. E 81 046106[18] Arenas A, Diaz Guilera A and Perez Vicente C J 2006 Phys. Rev. Lett. 96 114102[19] Clauset A, Newman M E J and Moore C 2004 Phys. Rev. E 70 066111[20] Raghavan U N, Albert R and Kumara S 2007 Phys. Rev. E 76 036106[21] Newman M E J 2006 Phys. Rev. E 74 036104[22] Lancichinetti A and Radicchi F 2008 Phys. Rev. E 78 046110[23] Zachary W W 1977 J. Anth. Res. 33 452[24] Lusseau D 2007 Evolutionary Ecology 21 357[25] Girvan M and Newman M E J 2002 Proc. Natl. Acad. Sci. U. S.A. 99 7821[26] Gleiser P M and Danon L 2003 Adv. Comput. Sys. 6 565[27] Duch J and Arenas A 2005 Phys. Rev. E 72 027104[28] Guimera R, Danon L, Diaz Guilera A, Giralt F and Arenas A 2003 Phys. Rev. E 68 065103[29] Adamic L A and Glance N 2005 LinkKDD (New York: ACM DL Digital Library) 36[30] Jeong H, Mason S P, Barabasi A L and Oltvai Z N 2001 Nature 411 41[31] Watts D J and Strogatz S H 1998 Nature 393 440[32] Newman M E J 2001 Proc. Natl. Acad. Sci. U. S.A. 98 404[33] Boguna M, Pastor Satorras R, Daz Guilera A and Arenas A 2004 Phys. Rev. E 70 056122[34] Salton G and McGill M J 1986 Introduction to Modern Information Retrieval (New York: McGraw Hill, Inc.)[35] Hamers L, Hemeryck Y, Herweyers G, Janssen M, Keters H, Rousseau R and Vanhoutte A 1989 Infor. Proc. Man. 25 315[36] Zhou T, Lü L Y and Zhang Y C 2009 Eurphys. J. B 71 623[37] Lü L Y and Zhou T 2011 Physica A 390 1150[38] Leicht E A, Holme P and Newman M E J 2006 Phys. Rev. E 73 026120[39] Fouss F, Pirotte A, Renders J M and Saerens M 2007 IEEE Trans. Knowl. Data Engin. 19 355[40] Katz L 1953 Psychometrika 18 39[41] Danon L, Diaz Guilera A, Duch J and Arenas A 2005 J. Stat. Mech. 2005 P09008 |
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
