Search

Article

x

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

The evaluation function of weight similarity and its application in community detection in weighted networks

Shen Yi Xu Huan-Liang

Citation:

The evaluation function of weight similarity and its application in community detection in weighted networks

Shen Yi, Xu Huan-Liang
PDF
Get Citation

(PLEASE TRANSLATE TO ENGLISH

BY GOOGLE TRANSLATE IF NEEDED.)

  • 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.
    [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

Metrics
  • Abstract views:  7485
  • PDF Downloads:  1315
  • Cited By: 0
Publishing process
  • Received Date:  17 December 2010
  • Accepted Date:  24 January 2010
  • Published Online:  15 September 2010

/

返回文章
返回