Search

Article

x

留言板

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

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

Multi-resolution density modularity for finding community structure in complex networks

Zhang Cong Shen Hui-Zhang Li Feng Yang He-Qun

Multi-resolution density modularity for finding community structure in complex networks

Zhang Cong, Shen Hui-Zhang, Li Feng, Yang He-Qun
PDF
Get Citation

(PLEASE TRANSLATE TO ENGLISH

BY GOOGLE TRANSLATE IF NEEDED.)

  • In reality many complex networks present modules or community structures obviously. Modularity is a benefit function used in quantifying the quality of a division of a network into communities. And it usually can be used as a basis for optimization methods of detecting community structure in networks. But the most popular modularity which is proposed by M. E. J. Newman and M. Girvan has the resolution limit in community detection. Multi-resolution modularity cannot overcome the misclassifications caused by merging and splitting the communities either. In this paper, we propose a multi-resolution density modularity based on the network density. The proposed function is tested on the artificial networks. Computational results show that it can reduce the rate of misclassification considerably. And the systematicness of the community structures can be demonstrated by the multi-resolution density modularity.
    • Funds: Project supported by the National Natural Science Foundation of China (Grant Nos. 71071096, 71001068).
    [1]

    Wang X F, Li X, Chen G R 2006 Complex Networks Theory and its Application (Beijing: Tsinghua University Press) (in Chinese) [汪小帆, 李翔, 陈关荣 2006 复杂网络理论及其应用 (北京:清华大学出版社)]

    [2]

    He D R, Lin Z H, Wang B H 2008 Complex System and Complex Networks (Beijing: Higher Education Press) (in Chinese) [何大韧, 刘宗华, 汪秉宏 2008 复杂系统与复杂网络 (北京: 高等教育出版社)]

    [3]

    Wang L, Dai G Z 2009 Scale-free Feature, Phenomena and Control in Complex Networks (Beijing: Science Press) (in Chinese) [王林, 戴贯中 2009 复杂网络的Scale-free性、Scale-free现象及其控制 (北京: 科学出版社)]

    [4]

    Zhang P P, He Y, Zhou T, Su B B, Chang H, Zhou Y P, Wang B H, He D R 2006 Acta Phys. Sin. 55 60 (in Chinese) [张培培, 何阅, 周涛, 苏蓓蓓, 常慧, 周月平, 汪秉宏, 何大韧 2006 物理学报 55 60]

    [5]

    Liu H K, Zhou T 2007 Acta Phys. Sin. 56 106 (in Chinese) [刘宏鲲, 周涛 2007 物理学报 56 106]

    [6]

    Xu D, Li X, Wang X F 2007 Acta Phys. Sin. 56 1313 (in Chinese) [许丹, 李翔, 汪小帆 2007 物理学报 56 1313]

    [7]

    Albert R, Jeong H, Barabasi A L 1999 Nature 401 130

    [8]

    Andrei B, Ravi K, Farzin M, Prabhakar R, Sridhar R, Raymie S, Andrew T, Janet W 2000 Comput. Netw. 33 309

    [9]

    Williams R J, Martinez N D 2000 Nature 404 180

    [10]

    Amaral L A N, Scala A, Barthelemy M, Stanley H E 2000 Proc. Natl. Acad. Sci. USA 97 11149

    [11]

    Gleiser P, Danon L 2003 Adv. Complex Syst. 6 565

    [12]

    Fortunato S 2010 Phys. Rep. 486 75

    [13]

    Girvan M, Newman M E J 2002 Proc. Natl. Acad. Sci. USA 99 7821

    [14]

    Newman M E J 2009 Phys. Rev. Lett. 103 058701

    [15]

    Newman M E J 2004 Eur. Phys. J. B 38 321

    [16]

    Sales-Pardo M, Guimera R, Moreira A A, Amaral L A N 2007 Proc. Natl. Acad. Sci. USA 104 15224

    [17]

    Blondel V D, Guillaume J L, Lambiotte R, Lefebvre E 2008 J. Stat. Mech. 2008 10008

    [18]

    Shen H, Cheng X, Cai K, Hu M B 2009 Physica A 388 1706

    [19]

    Zhang S, Wang R S, Zhang X S 2007 Physica A 374 483

    [20]

    Zhang S Wang R S, Zhang X S 2007 Phys. Rev. E 76 046103

    [21]

    Gao Z K, Jin N D 2008 Acta Phys. Sin. 57 6909 (in Chinese) [高忠科, 金宁德 2008 物理学报 57 6909]

    [22]

    Wang J W, Rong L L 2009 Acta Phys. Sin. 58 3714 (in Chinese) [王建伟, 荣莉莉 2009 物理学报 58 3714]

    [23]

    Shen Y, Xu H L 2010 Acta Phys. Sin. 59 6022 (in Chinese) [沈毅, 徐焕良 2010 物理学报 59 6022]

    [24]

    Wang G X, Shen Y 2010 Acta Phys. Sin. 59 842 (in Chinese) [王高峡, 沈轶 2010 物理学报 59 842]

    [25]

    Shao F, Jiang G P 2011 Acta Phys. Sin. 60 078902 (in Chinese) [邵斐, 蒋国平 2011 物理学报 60 078902]

    [26]

    Newman M E J, Girvan M 2004 Phys. Rev. E 69 026113

    [27]

    Fortunato S, Barthélemy M 2007 Proc. Natl. Acad. Sci. USA 104 36

    [28]

    Rosvall M, Bergstrom C T 2007 Proc. Natl. Acad. Sci. USA 104 7327

    [29]

    Muff S, Rao F, Caflisch A 2005 Phys. Rev. E 72 056107

    [30]

    Li Z, Zhang S, Wang R S 2008 Phys. Rev. E 77 036109

    [31]

    Radicchi F, Castellano C, Cecconi F, Loreto V, Parisi D 2004 Proc. Natl. Acad. Sci. USA 101 2658

    [32]

    Reichardt J, Bornholdt S 2006 Phys. Rev. E 74 016110

    [33]

    Arenas A, Fernández A, Gómez S 2008 New J. Phys. 10 053039

    [34]

    Lancichinetti A, Fortunato S 2011 arXiv: 1107. 1155v1 [physics. soc-ph]

    [35]

    Lancichinetti A, Fortunato S, Radicchi F 2008 Phys. Rev. E 78 046110

  • [1]

    Wang X F, Li X, Chen G R 2006 Complex Networks Theory and its Application (Beijing: Tsinghua University Press) (in Chinese) [汪小帆, 李翔, 陈关荣 2006 复杂网络理论及其应用 (北京:清华大学出版社)]

    [2]

    He D R, Lin Z H, Wang B H 2008 Complex System and Complex Networks (Beijing: Higher Education Press) (in Chinese) [何大韧, 刘宗华, 汪秉宏 2008 复杂系统与复杂网络 (北京: 高等教育出版社)]

    [3]

    Wang L, Dai G Z 2009 Scale-free Feature, Phenomena and Control in Complex Networks (Beijing: Science Press) (in Chinese) [王林, 戴贯中 2009 复杂网络的Scale-free性、Scale-free现象及其控制 (北京: 科学出版社)]

    [4]

    Zhang P P, He Y, Zhou T, Su B B, Chang H, Zhou Y P, Wang B H, He D R 2006 Acta Phys. Sin. 55 60 (in Chinese) [张培培, 何阅, 周涛, 苏蓓蓓, 常慧, 周月平, 汪秉宏, 何大韧 2006 物理学报 55 60]

    [5]

    Liu H K, Zhou T 2007 Acta Phys. Sin. 56 106 (in Chinese) [刘宏鲲, 周涛 2007 物理学报 56 106]

    [6]

    Xu D, Li X, Wang X F 2007 Acta Phys. Sin. 56 1313 (in Chinese) [许丹, 李翔, 汪小帆 2007 物理学报 56 1313]

    [7]

    Albert R, Jeong H, Barabasi A L 1999 Nature 401 130

    [8]

    Andrei B, Ravi K, Farzin M, Prabhakar R, Sridhar R, Raymie S, Andrew T, Janet W 2000 Comput. Netw. 33 309

    [9]

    Williams R J, Martinez N D 2000 Nature 404 180

    [10]

    Amaral L A N, Scala A, Barthelemy M, Stanley H E 2000 Proc. Natl. Acad. Sci. USA 97 11149

    [11]

    Gleiser P, Danon L 2003 Adv. Complex Syst. 6 565

    [12]

    Fortunato S 2010 Phys. Rep. 486 75

    [13]

    Girvan M, Newman M E J 2002 Proc. Natl. Acad. Sci. USA 99 7821

    [14]

    Newman M E J 2009 Phys. Rev. Lett. 103 058701

    [15]

    Newman M E J 2004 Eur. Phys. J. B 38 321

    [16]

    Sales-Pardo M, Guimera R, Moreira A A, Amaral L A N 2007 Proc. Natl. Acad. Sci. USA 104 15224

    [17]

    Blondel V D, Guillaume J L, Lambiotte R, Lefebvre E 2008 J. Stat. Mech. 2008 10008

    [18]

    Shen H, Cheng X, Cai K, Hu M B 2009 Physica A 388 1706

    [19]

    Zhang S, Wang R S, Zhang X S 2007 Physica A 374 483

    [20]

    Zhang S Wang R S, Zhang X S 2007 Phys. Rev. E 76 046103

    [21]

    Gao Z K, Jin N D 2008 Acta Phys. Sin. 57 6909 (in Chinese) [高忠科, 金宁德 2008 物理学报 57 6909]

    [22]

    Wang J W, Rong L L 2009 Acta Phys. Sin. 58 3714 (in Chinese) [王建伟, 荣莉莉 2009 物理学报 58 3714]

    [23]

    Shen Y, Xu H L 2010 Acta Phys. Sin. 59 6022 (in Chinese) [沈毅, 徐焕良 2010 物理学报 59 6022]

    [24]

    Wang G X, Shen Y 2010 Acta Phys. Sin. 59 842 (in Chinese) [王高峡, 沈轶 2010 物理学报 59 842]

    [25]

    Shao F, Jiang G P 2011 Acta Phys. Sin. 60 078902 (in Chinese) [邵斐, 蒋国平 2011 物理学报 60 078902]

    [26]

    Newman M E J, Girvan M 2004 Phys. Rev. E 69 026113

    [27]

    Fortunato S, Barthélemy M 2007 Proc. Natl. Acad. Sci. USA 104 36

    [28]

    Rosvall M, Bergstrom C T 2007 Proc. Natl. Acad. Sci. USA 104 7327

    [29]

    Muff S, Rao F, Caflisch A 2005 Phys. Rev. E 72 056107

    [30]

    Li Z, Zhang S, Wang R S 2008 Phys. Rev. E 77 036109

    [31]

    Radicchi F, Castellano C, Cecconi F, Loreto V, Parisi D 2004 Proc. Natl. Acad. Sci. USA 101 2658

    [32]

    Reichardt J, Bornholdt S 2006 Phys. Rev. E 74 016110

    [33]

    Arenas A, Fernández A, Gómez S 2008 New J. Phys. 10 053039

    [34]

    Lancichinetti A, Fortunato S 2011 arXiv: 1107. 1155v1 [physics. soc-ph]

    [35]

    Lancichinetti A, Fortunato S, Radicchi F 2008 Phys. Rev. E 78 046110

  • [1] Yuan Chao, Chai Yi. Group similarity based algorithm for network community structure detection. Acta Physica Sinica, 2012, 61(21): 218901. doi: 10.7498/aps.61.218901
    [2] Wang Gao-Xia, Shen Yi. Modularity matrix of networks and the measure of community structure. Acta Physica Sinica, 2010, 59(2): 842-850. doi: 10.7498/aps.59.842
    [3] Lü Tian-Yang, Xie Wen-Yan, Zheng Wei-Min, Piao Xiu-Feng. Analysis of community evaluation criterion and discovery algorithm of weighted complex network. Acta Physica Sinica, 2012, 61(21): 210511. doi: 10.7498/aps.61.210511
    [4] Wang Xing-Yuan, Zhao Zhong-Xiang. Partitioning community structure in complex networks based on node dependent degree. Acta Physica Sinica, 2014, 63(17): 178901. doi: 10.7498/aps.63.178901
    [5] Su Xiao-Ping, Song Yu-Rong. Leveraging neighborhood “structural holes” to identifying key spreaders in social networks. Acta Physica Sinica, 2015, 64(2): 020101. doi: 10.7498/aps.64.020101
    [6] Shen Yi, Xu Huan-Liang. The evaluation function of weight similarity and its application in community detection in weighted networks. Acta Physica Sinica, 2010, 59(9): 6022-6028. doi: 10.7498/aps.59.6022
    [7] 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. Acta Physica Sinica, 2012, 61(12): 120510. doi: 10.7498/aps.61.120510
    [8] Shao Fei, Jiang Guo-Ping. Optimal traffic routing strategy based on community structure. Acta Physica Sinica, 2011, 60(7): 078902. doi: 10.7498/aps.60.078902
    [9] Gao Zhong-Ke, Jin Ning-De. Complex network community structure of two-phase flow pattern and its statistical characteristics. Acta Physica Sinica, 2008, 57(11): 6909-6920. doi: 10.7498/aps.57.6909
    [10] Cui Ai-Xiang, Fu Yan, Shang Ming-Sheng, Chen Duan-Bing, Zhou Tao. Emergence of local structures in complex network:common neighborhood drives the network evolution. Acta Physica Sinica, 2011, 60(3): 038901. doi: 10.7498/aps.60.038901
    [11] Zhou Xuan, Zhang Feng-Ming, Li Ke-Wu, Hui Xiao-Bin, Wu Hu-Sheng. Finding vital node by node importance evaluation matrix in complex networks. Acta Physica Sinica, 2012, 61(5): 050201. doi: 10.7498/aps.61.050201
    [12] Lü Ling, Zhang Chao. Chaos synchronization of a complex network with different nodes. Acta Physica Sinica, 2009, 58(3): 1462-1466. doi: 10.7498/aps.58.1462
    [13] LÜ Ling, Liu Shuang, Zhang Xin, Zhu Jia-Bo, Shen Na, Shang Jin-Yu. Spatiotemporal chaos anti-synchronization of a complex network with different nodes. Acta Physica Sinica, 2012, 61(9): 090504. doi: 10.7498/aps.61.090504
    [14] Liu Jin-Liang. Research on synchronization of complex networks with random nodes. Acta Physica Sinica, 2013, 62(4): 040503. doi: 10.7498/aps.62.040503
    [15] Han Zhong-Ming, Wu Yang, Tan Xu-Sheng, Duan Da-Gao, Yang Wei-Jie. Ranking key nodes in complex networks by considering structural holes. Acta Physica Sinica, 2015, 64(5): 058902. doi: 10.7498/aps.64.058902
    [16] Ruan Yi-Run, Lao Song-Yang, Wang Jun-De, Bai Liang, Chen Li-Dong. Node importance measurement based on neighborhood similarity in complex network. Acta Physica Sinica, 2017, 66(3): 038902. doi: 10.7498/aps.66.038902
    [17] Ding Yi-Min, Ding Zhuo, Yang Chang-Ping. The network model of urban subway networks with community structure. Acta Physica Sinica, 2013, 62(9): 098901. doi: 10.7498/aps.62.098901
    [18] Yang Pu, Zheng Zhi-Gang. Analysis the convergency speed of estimating the network topology based on the dynamical synchronization. Acta Physica Sinica, 2012, 61(12): 120508. doi: 10.7498/aps.61.120508
    [19] Yuan Ming. A cascading failure model of complex network with hierarchy structure. Acta Physica Sinica, 2014, 63(22): 220501. doi: 10.7498/aps.63.220501
    [20] Han Zhong-Ming, Chen Yan, Li Meng-Qi, Liu Wen, Yang Wei-Jie. An efficient node influence metric based on triangle in complex networks. Acta Physica Sinica, 2016, 65(16): 168901. doi: 10.7498/aps.65.168901
  • Citation:
Metrics
  • Abstract views:  2924
  • PDF Downloads:  1604
  • Cited By: 0
Publishing process
  • Received Date:  07 September 2011
  • Accepted Date:  07 December 2011
  • Published Online:  05 July 2012

Multi-resolution density modularity for finding community structure in complex networks

  • 1. Antai College of Economics and Management, Shanghai Jiaotong University, Shanghai 200052, China;
  • 2. Shanghai Center for Satellite Remote Sensing and Measurement Application, Shanghai 201199, China
Fund Project:  Project supported by the National Natural Science Foundation of China (Grant Nos. 71071096, 71001068).

Abstract: In reality many complex networks present modules or community structures obviously. Modularity is a benefit function used in quantifying the quality of a division of a network into communities. And it usually can be used as a basis for optimization methods of detecting community structure in networks. But the most popular modularity which is proposed by M. E. J. Newman and M. Girvan has the resolution limit in community detection. Multi-resolution modularity cannot overcome the misclassifications caused by merging and splitting the communities either. In this paper, we propose a multi-resolution density modularity based on the network density. The proposed function is tested on the artificial networks. Computational results show that it can reduce the rate of misclassification considerably. And the systematicness of the community structures can be demonstrated by the multi-resolution density modularity.

Reference (35)

Catalog

    /

    返回文章
    返回