搜索

x

留言板

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

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

复杂网络中社团结构发现的多分辨率密度模块度

张聪 沈惠璋 李峰 杨何群

引用本文:
Citation:

复杂网络中社团结构发现的多分辨率密度模块度

张聪, 沈惠璋, 李峰, 杨何群

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

Zhang Cong, Shen Hui-Zhang, Li Feng, Yang He-Qun
PDF
导出引用
  • 现实中的许多复杂网络呈现出明显的模块性或社团性.模块度是衡量社团结构划分优劣的效益函数, 它也通常被用作社团结构探测的目标函数,但最为广泛使用的Newman-Girvan模块度却存在着分辨率限制问题,多分辨率模块度也不能克服误合并社团和误分裂社团同时存在的缺陷. 本文在网络密度的基础上提出了多分辨率的密度模块度函数, 通过实验和分析证实了该函数能够使社团结构的误划分率显著降低, 而且能够体现出网络社团结构是一个有机整体,不是各个社团的简单相加.
    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.
    • 基金项目: 国家自然科学基金(批准号: 71071096, 71001068)资助的课题.
    • 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] 阮逸润, 老松杨, 汤俊, 白亮, 郭延明. 基于引力方法的复杂网络节点重要度评估方法. 物理学报, 2022, 71(17): 176401. doi: 10.7498/aps.71.20220565
    [2] 阮逸润, 老松杨, 王竣德, 白亮, 陈立栋. 基于领域相似度的复杂网络节点重要度评估算法. 物理学报, 2017, 66(3): 038902. doi: 10.7498/aps.66.038902
    [3] 韩忠明, 吴杨, 谭旭升, 段大高, 杨伟杰. 面向结构洞的复杂网络关键节点排序. 物理学报, 2015, 64(5): 058902. doi: 10.7498/aps.64.058902
    [4] 苏晓萍, 宋玉蓉. 利用邻域“结构洞”寻找社会网络中最具影响力节点. 物理学报, 2015, 64(2): 020101. doi: 10.7498/aps.64.020101
    [5] 袁铭. 带有层级结构的复杂网络级联失效模型. 物理学报, 2014, 63(22): 220501. doi: 10.7498/aps.63.220501
    [6] 王兴元, 赵仲祥. 基于节点间依赖度的社团结构划分方法. 物理学报, 2014, 63(17): 178901. doi: 10.7498/aps.63.178901
    [7] 丁益民, 丁卓, 杨昌平. 基于社团结构的城市地铁网络模型研究. 物理学报, 2013, 62(9): 098901. doi: 10.7498/aps.62.098901
    [8] 刘金良. 具有随机节点结构的复杂网络同步研究. 物理学报, 2013, 62(4): 040503. doi: 10.7498/aps.62.040503
    [9] 杨浦, 郑志刚. 基于动力学同步的复杂网络结构识别速度研究. 物理学报, 2012, 61(12): 120508. doi: 10.7498/aps.61.120508
    [10] 吕翎, 柳爽, 张新, 朱佳博, 沈娜, 商锦玉. 节点结构互异的复杂网络的时空混沌反同步. 物理学报, 2012, 61(9): 090504. doi: 10.7498/aps.61.090504
    [11] 周漩, 张凤鸣, 李克武, 惠晓滨, 吴虎胜. 利用重要度评价矩阵确定复杂网络关键节点. 物理学报, 2012, 61(5): 050201. doi: 10.7498/aps.61.050201
    [12] 高忠科, 金宁德, 杨丹, 翟路生, 杜萌. 多元时间序列复杂网络流型动力学分析. 物理学报, 2012, 61(12): 120510. doi: 10.7498/aps.61.120510
    [13] 吕天阳, 谢文艳, 郑纬民, 朴秀峰. 加权复杂网络社团的评价指标及其发现算法分析. 物理学报, 2012, 61(21): 210511. doi: 10.7498/aps.61.210511
    [14] 袁超, 柴毅. 基于簇相似度的网络社团结构探测算法. 物理学报, 2012, 61(21): 218901. doi: 10.7498/aps.61.218901
    [15] 崔爱香, 傅彦, 尚明生, 陈端兵, 周涛. 复杂网络局部结构的涌现:共同邻居驱动网络演化. 物理学报, 2011, 60(3): 038901. doi: 10.7498/aps.60.038901
    [16] 邵斐, 蒋国平. 基于社团结构的负载传输优化策略研究. 物理学报, 2011, 60(7): 078902. doi: 10.7498/aps.60.078902
    [17] 沈毅, 徐焕良. 加权网络权重自相似评判函数及其社团结构检测. 物理学报, 2010, 59(9): 6022-6028. doi: 10.7498/aps.59.6022
    [18] 王高峡, 沈轶. 网络的模块矩阵及其社团结构指标. 物理学报, 2010, 59(2): 842-850. doi: 10.7498/aps.59.842
    [19] 吕翎, 张超. 一类节点结构互异的复杂网络的混沌同步. 物理学报, 2009, 58(3): 1462-1466. doi: 10.7498/aps.58.1462
    [20] 高忠科, 金宁德. 两相流流型复杂网络社团结构及其统计特性. 物理学报, 2008, 57(11): 6909-6920. doi: 10.7498/aps.57.6909
计量
  • 文章访问数:  5200
  • PDF下载量:  1626
  • 被引次数: 0
出版历程
  • 收稿日期:  2011-09-07
  • 修回日期:  2011-12-07
  • 刊出日期:  2012-07-05

复杂网络中社团结构发现的多分辨率密度模块度

  • 1. 上海交通大学安泰经济与管理学院, 上海 200052;
  • 2. 上海市卫星遥感与测量应用中心, 上海 201199
    基金项目: 国家自然科学基金(批准号: 71071096, 71001068)资助的课题.

摘要: 现实中的许多复杂网络呈现出明显的模块性或社团性.模块度是衡量社团结构划分优劣的效益函数, 它也通常被用作社团结构探测的目标函数,但最为广泛使用的Newman-Girvan模块度却存在着分辨率限制问题,多分辨率模块度也不能克服误合并社团和误分裂社团同时存在的缺陷. 本文在网络密度的基础上提出了多分辨率的密度模块度函数, 通过实验和分析证实了该函数能够使社团结构的误划分率显著降低, 而且能够体现出网络社团结构是一个有机整体,不是各个社团的简单相加.

English Abstract

参考文献 (35)

目录

    /

    返回文章
    返回