The evaluation function of weight similarity and its application in community detection in weighted networks
Shen Yi, Xu Huan-Liang
College of Information Science and Technology,Nanjing Agricultural University,Nanjing 210095,China
Abstract An evaluation function of weight similarity in weighted network is proposed,and a spectral algorithm for detecting community structure based on the function is presented. The results show that the algorithm can divide the weighted network into several groups within each of them the edges weights distribute uniformly but at random between them. The algorithm is analyzed by constructing random weighted networks with known community structure. Compared with WEO and WGN,the algorithm has high accuracy when the threshold coefficient takes small values. For a network with n nodes and c communities,the computation complexity of the algorithm is O (cn 2 /2). By setting different threshold coefficients,a special hierarchical organization which describes the various steady connections between nodes in groups can be discovered by the algorithm. It is different from the conventional concept of community detection in weighted networks which divides the weighted network into several groups in which the edges weights are relatively larger than those in-between them,such that it extracts the information about the structure of weighted networks from another perspective.
Key words ：
weight similarity
weighted networks
community structure
spectral algorithm
Received: 2010-12-17
Published: 2010-09-15
Cite this article:
Shen Yi,Xu Huan-Liang. The evaluation function of weight similarity and its application in community detection in weighted networks. Acta Phys. Sin., 2010, 59(9): 6022-6028.
URL:
http://wulixb.iphy.ac.cn/CN/Y2010/V59/I9/6022
[1] Watts D J,Strogatz S H 1998 Nature 393 440
[2] Albert R,Jeong H,Barabási A L 1999 Nature 401 130
[3] Wang G Z,Cao Y J,Bao Z J,Han Z X 2009 Acta Phys. Sin. 58 3597 (in Chinese) [王光增、曹一家、包哲静、韩祯祥 2009 物理学报 58 3597]
[4] Zhang L,Liu Y 2008 Acta Phys. Sin. 57 5419 (in Chinese) [张 立、刘 云 2008 物理学报 57 5419]
[5] Newman M E J 2002 Proc. Natl. Acad. Sci. U.S.A. 99 7821
[6] Newman M E J,Barabási A L,Watts D J 2006 The Structure and Dynamics of Networks (Princeton:Princeton University Press)
[7] Shen Y,Pei W J,Wang K,Li T,Wang S P 2008 Physica A 387 6663
[8] Danon L,Duch J,Guilera A D,Arenas A 2005 J. Stat. Mech. p09008
[9] Holme P,Huss M,Jeong H 2003 Bioinformatics 19 532
[10] Guimerà R,Amaral L A N 2005 Nature 433 895
[11] Colizza V,Barrat A M,Vespignani A 2006 Proc. Natl. Acad. Sci. U.S.A. 103 2015
[12] Ni S J,Weng W G,Fan W C 2009 Acta Phys. Sin. 58 3707 (in Chinese) [倪顺江、翁文国、范维澄 2009 物理学报 58 3707]
[13] Ma X J,Wang Y,Zheng Z G 2009 Acta Phys. Sin. 58 4426 (in Chinese) [马晓娟、王 延、郑志刚 2009 物理学报 58 4426]
[14] Lü L,Zhang C 2009 Acta Phys. Sin. 58 1462 (in Chinese) [吕 翎、张 超 2009 物理学报 58 1462]
[15] Song Q S,Feng Z R,Li R H 2009 Acta Phys. Sin. 58 5057 (in Chinese) [宋青松、冯祖仁、李人厚 2009 物理学报 58 5057]
[16] Shen Y,Pei W J,Wang K,Wang S P 2009 Chin. Phys. B 18 3783
[17] Zhang Z,Fu Z Q,Yan G 2009 Chin. Phys. B 18 2209
[18] Wang J W,Rong L L 2009 Acta Phys. Sin. 58 3714 (in Chinese) [王建伟、荣莉莉 2009 物理学报 58 3714]
[19] Ouyang M,Fei Q,Yu M H 2008 Acta Phys. Sin. 57 6763 (in Chinese) [欧阳敏、费 奇、余明晖 2008 物理学报 57 6763]
[20] Xu Q X,Xu X J 2009 Chin. Phys. B 18 933
[21] Nelson A A 2007 Phys. Rev. E 76 036101
[22] Newman M E J 2004 Phys. Rev. E 70 056131
[23] Duch J,Arenas A 2005 Phys. Rev. E 72 027104
[24] Fan Y,Li M,Zhang P,Wu J S,Di Z R 2006 Physica A 370 869
[25] Newman M E J,Girvan M 2004 Phys. Rev. E 69 026113
[26] Lancichinetti A,Fortunato S,2009 Phys. Rev. E 80 056117
[27] Newman M E J 2006 Phys. Rev. E 74 036104
[28] Roger G,Marta S P,Luís A,Nunes A 2004 Phys. Rev. E 70 025101
[29] Newman M E J 2004 Phys. Rev. E 69 066133
[30] Frank K A 1996 Soc. Networks 18 93
[31] Danon L,Díaz-Guilera A,Duch J,Arenas A 2006 J. Stat. Mech. p11010
[32] Newman M E J 2006 Proc. Natl. Acad. Sci. U.S.A. 103 8577
[1]
Gao Zhong Ke,Yang Dan,Zhai Lu Sheng, and Du Meng. Complex networks from multivariate time series for characterizing nonlinear dynamics underlying two-phase flow patterns
[2]
Zhang Cong,Shen Hui-zhang,Li Feng,Yang He-Qun. Multi-resolution density modularity for finding community structure in complex networks
[3]
Gao Zhong-Ke, Jin Ning-De, Yang Dan, Zhai Lu-Sheng, Du Meng. Complex networks from multivariate time series for characterizing nonlinear dynamics of two-phase flow patterns
[4]
Shao Fei, Jiang Guo-Ping. Optimal traffic routing strategy based on community structure
[5]
Lü Ling, Meng Le, Guo Li, Zou Jia-Rui, Yang Ming. Projective synchronization of a weighted network in a laser spatiotemporal chaos model
[6]
Tian Liu, Di Zeng-Ru, Yao Hong. Effect of distribution of weight on the efficiency of weighted networks
[7]
Wang Gao-Xia, Shen Yi. Modularity matrix of networks and the measure of community structure
[8]
Li Yan, Lü Ling, Luan Ling. Lag synchronization of spatiotemporal chaos in a weighted network with ring connection
[9]
Pan Zao-Feng, Wang Xiao-Fan. A weighted scale-free network model with large-scale tunable clustering
[10]
. On Weightd Scale-free Network Model with Tunable Clustering and Congesstion
2010, Vol. 59 
