-
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(cn2/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.
-
Keywords:
- weight similarity /
- weighted networks /
- community structure /
- spectral algorithm
[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] 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
计量
- 文章访问数: 8089
- PDF下载量: 1320
- 被引次数: 0