搜索

文章查询

x

留言板

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

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

加权复杂网络社团的评价指标及其发现算法分析

吕天阳 谢文艳 郑纬民 朴秀峰

加权复杂网络社团的评价指标及其发现算法分析

吕天阳, 谢文艳, 郑纬民, 朴秀峰
PDF
导出引用
导出核心图
  • 节点的聚集现象是复杂网络的重要特性. 以往研究主要发现无权复杂网络中的社团, 较少涉及加权网络的社团发现. 由于加权网络的复杂性远高于无权网络, 一般认为加权网络的社团发现是一个较难的问题. 本文基于统一的数据基础, 从社团评价指标的有效性和现有算法的效果两个角度开展研究. 首先, 总结了加权网络三种常见的社团评估指标, 并在社团大小、密度和局域特点均不同的模拟数据集上分析指标的有效性; 其次, 针对5个数据集, 分析现有的3种加权复杂网络社团发现算法的效果. 研究表明: 上述指标无论在评价最基本的社团结构, 还是在分析结构复杂的社团时都有较大缺欠; 现有的加权网络社团发现算法的泛化能力不强.
    • 基金项目: 国家科技支撑计划(批准号: 2009BAH42B02, 2012BAH08B02)、国家自然科学基金(批准号: 60903080)、中央高校基本科研业务费专项资金(批准号: HEUCFZ100603)和黑龙江省教育厅科学技术研究(批准号: 12513050)资助的课题.
    [1]

    Watts D J, Strogatz S H 1998 Nature 393 440

    [2]

    Barabási A L, Albert R, Jeong H, Bianconi G 2000 Science 287 2115

    [3]

    Granovetter M 1973 Am. J. Soc. 78 1360

    [4]

    Barabasi A L, Albert R 1999 Science 286 509

    [5]

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

    [6]

    Yang B, Liu D Y, Liu J M, Jin D, Ma H B 2009 J. Software 20 54 (in Chinese) [杨博, 刘大有, Liu Jiming, 金弟, 马海宾 2009 软件学报 20 54]

    [7]

    Cheng X Q, Shen H W 2011 Complex Syst. Complexity Sci. 8 57 (in Chinese) [程学旗, 沈华伟 2011 复杂系统与复杂性科学 8 57]

    [8]

    Barrat A, Barthélemy M, Vespignani A 2004 Phys. Rev. E 70 066149

    [9]

    Antoniou I E, Tsompa E T 2008 Dis. Dyn. Nat. Soc. 2008 194

    [10]

    Tian L, Di Z R, Yao H 2011 Acta Phys. Sin. 60 028901 (in Chinese) [田柳, 狄增如, 姚虹 2011 物理学报 60 028901]

    [11]

    Newman M E J 2004 Phys. Rev. E 70 056131

    [12]

    Li X J, Zhang P, Di Z R, Fan Y 2008 Complex Sys. Complexity Sci. 5 19 (in Chinese) [李晓佳, 张鹏, 狄增如, 樊瑛 2008 复杂系统与复杂性科学 5 19]

    [13]

    Wang X F, Li X, Chen G R 2006 Complex Network Theory and Its Application (1st Edn.) (Beijing: Tsinghua University Press) p10 (in Chinese) [汪小帆, 李翔, 陈关荣 2006 复杂网络理论及其应用 (第一版) (北京: 清华大学出版社) 第10页]

    [14]

    Zhang B, Horvath S 2005 Stat. Appl. Genet. Mol. 4 1128

    [15]

    Onnela J-P, Saramäki J, Kertész J, Kaski K 2005 Phys. Rev. E 71 065103

    [16]

    Barrat A, Barthelemy M, Pastor-Satorras R, Vespignani A 2004 PNAS (USA) 101 3747

    [17]

    Holme P, Park S M, Kim B J, Edling C R 2007 Physica 373 821

    [18]

    Kalna G, Higham D J 2006 SNANSE pp45-50

    [19]

    Lopez-Fernandez L, Robles G, Gonzalez-Barahona J M 2004 Proc. of the 1st Intl. Workshop on MSR pp101-105

    [20]

    Serrano M A, Boguñá M, Pastor-Satorras R 2006 Phys. Rev. E 74 055101

    [21]

    Filippo R, Claudio C, Federico C, Vittorio L, Domenico P 2004 PNAS 101 2658

    [22]

    Lü T Y, Huang S B, Wu P, Jia Y R 2010 Proc. SKG pp211-218

    [23]

    Knuth D E 1993 The Stanford Graph Base: A Platform for Combinatorial Computing (1st Ed.) (Indianapolis: Addison-Wesley Professional) pp15

    [24]

    Newman M E J 2006 Phys. Rev. E 74 036104

    [25]

    Kevin D, Steven C 2004 NDPLS 8 259

  • [1]

    Watts D J, Strogatz S H 1998 Nature 393 440

    [2]

    Barabási A L, Albert R, Jeong H, Bianconi G 2000 Science 287 2115

    [3]

    Granovetter M 1973 Am. J. Soc. 78 1360

    [4]

    Barabasi A L, Albert R 1999 Science 286 509

    [5]

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

    [6]

    Yang B, Liu D Y, Liu J M, Jin D, Ma H B 2009 J. Software 20 54 (in Chinese) [杨博, 刘大有, Liu Jiming, 金弟, 马海宾 2009 软件学报 20 54]

    [7]

    Cheng X Q, Shen H W 2011 Complex Syst. Complexity Sci. 8 57 (in Chinese) [程学旗, 沈华伟 2011 复杂系统与复杂性科学 8 57]

    [8]

    Barrat A, Barthélemy M, Vespignani A 2004 Phys. Rev. E 70 066149

    [9]

    Antoniou I E, Tsompa E T 2008 Dis. Dyn. Nat. Soc. 2008 194

    [10]

    Tian L, Di Z R, Yao H 2011 Acta Phys. Sin. 60 028901 (in Chinese) [田柳, 狄增如, 姚虹 2011 物理学报 60 028901]

    [11]

    Newman M E J 2004 Phys. Rev. E 70 056131

    [12]

    Li X J, Zhang P, Di Z R, Fan Y 2008 Complex Sys. Complexity Sci. 5 19 (in Chinese) [李晓佳, 张鹏, 狄增如, 樊瑛 2008 复杂系统与复杂性科学 5 19]

    [13]

    Wang X F, Li X, Chen G R 2006 Complex Network Theory and Its Application (1st Edn.) (Beijing: Tsinghua University Press) p10 (in Chinese) [汪小帆, 李翔, 陈关荣 2006 复杂网络理论及其应用 (第一版) (北京: 清华大学出版社) 第10页]

    [14]

    Zhang B, Horvath S 2005 Stat. Appl. Genet. Mol. 4 1128

    [15]

    Onnela J-P, Saramäki J, Kertész J, Kaski K 2005 Phys. Rev. E 71 065103

    [16]

    Barrat A, Barthelemy M, Pastor-Satorras R, Vespignani A 2004 PNAS (USA) 101 3747

    [17]

    Holme P, Park S M, Kim B J, Edling C R 2007 Physica 373 821

    [18]

    Kalna G, Higham D J 2006 SNANSE pp45-50

    [19]

    Lopez-Fernandez L, Robles G, Gonzalez-Barahona J M 2004 Proc. of the 1st Intl. Workshop on MSR pp101-105

    [20]

    Serrano M A, Boguñá M, Pastor-Satorras R 2006 Phys. Rev. E 74 055101

    [21]

    Filippo R, Claudio C, Federico C, Vittorio L, Domenico P 2004 PNAS 101 2658

    [22]

    Lü T Y, Huang S B, Wu P, Jia Y R 2010 Proc. SKG pp211-218

    [23]

    Knuth D E 1993 The Stanford Graph Base: A Platform for Combinatorial Computing (1st Ed.) (Indianapolis: Addison-Wesley Professional) pp15

    [24]

    Newman M E J 2006 Phys. Rev. E 74 036104

    [25]

    Kevin D, Steven C 2004 NDPLS 8 259

  • [1] 张聪, 沈惠璋, 李峰, 杨何群. 复杂网络中社团结构发现的多分辨率密度模块度. 物理学报, 2012, 61(14): 148902. doi: 10.7498/aps.61.148902
    [2] 袁超, 柴毅. 基于簇相似度的网络社团结构探测算法. 物理学报, 2012, 61(21): 218901. doi: 10.7498/aps.61.218901
    [3] 周漩, 张凤鸣, 李克武, 惠晓滨, 吴虎胜. 利用重要度评价矩阵确定复杂网络关键节点. 物理学报, 2012, 61(5): 050201. doi: 10.7498/aps.61.050201
    [4] 胡庆成, 张勇, 许信辉, 邢春晓, 陈池, 陈信欢. 一种新的复杂网络影响力最大化发现方法. 物理学报, 2015, 64(19): 190101. doi: 10.7498/aps.64.190101
    [5] 高忠科, 金宁德. 两相流流型复杂网络社团结构及其统计特性. 物理学报, 2008, 57(11): 6909-6920. doi: 10.7498/aps.57.6909
    [6] 阮逸润, 老松杨, 王竣德, 白亮, 陈立栋. 基于领域相似度的复杂网络节点重要度评估算法. 物理学报, 2017, 66(3): 038902. doi: 10.7498/aps.66.038902
    [7] 闵磊, 刘智, 唐向阳, 陈矛, 刘三(女牙). 基于扩展度的复杂网络传播影响力评估算法. 物理学报, 2015, 64(8): 088901. doi: 10.7498/aps.64.088901
    [8] 王兴元, 赵仲祥. 基于节点间依赖度的社团结构划分方法. 物理学报, 2014, 63(17): 178901. doi: 10.7498/aps.63.178901
    [9] 丁益民, 丁卓, 杨昌平. 基于社团结构的城市地铁网络模型研究. 物理学报, 2013, 62(9): 098901. doi: 10.7498/aps.62.098901
    [10] 胡庆成, 尹龑燊, 马鹏斐, 高旸, 张勇, 邢春晓. 一种新的网络传播中最有影响力的节点发现方法 . 物理学报, 2013, 62(14): 140101. doi: 10.7498/aps.62.140101
    [11] 余晓平, 裴韬. 手机通话网络度特征分析. 物理学报, 2013, 62(20): 208901. doi: 10.7498/aps.62.208901
    [12] 胡耀光, 王圣军, 金涛, 屈世显. 度关联无标度网络上的有倾向随机行走. 物理学报, 2015, 64(2): 028901. doi: 10.7498/aps.64.028901
    [13] 闫小勇, 王明生. 增长速度对合作网络参与者节点度分布的影响. 物理学报, 2010, 59(2): 851-858. doi: 10.7498/aps.59.851
    [14] 段东立, 战仁军. 基于相继故障信息的网络节点重要度演化机理分析. 物理学报, 2014, 63(6): 068902. doi: 10.7498/aps.63.068902
    [15] 徐明, 许传云, 曹克非. 度相关性对无向网络可控性的影响. 物理学报, 2017, 66(2): 028901. doi: 10.7498/aps.66.028901
    [16] 侯凤贞, 戴加飞, 刘新峰, 黄晓林. 基于网络连接度指标的脑梗死患者脑电信号相同步分析. 物理学报, 2014, 63(4): 040506. doi: 10.7498/aps.63.040506
    [17] 欧阳博, 金心宇, 夏永祥, 蒋路茸, 吴端坡. 疾病传播与级联失效相互作用的研究:度不相关网络中疾病扩散条件的分析. 物理学报, 2014, 63(21): 218902. doi: 10.7498/aps.63.218902
    [18] 许 丹, 李 翔, 汪小帆. 复杂网络病毒传播的局域控制研究. 物理学报, 2007, 56(3): 1313-1317. doi: 10.7498/aps.56.1313
    [19] 李雨珊, 吕翎, 刘烨, 刘硕, 闫兵兵, 常欢, 周佳楠. 复杂网络时空混沌同步的Backstepping设计. 物理学报, 2013, 62(2): 020513. doi: 10.7498/aps.62.020513
    [20] 崔爱香, 傅彦, 尚明生, 陈端兵, 周涛. 复杂网络局部结构的涌现:共同邻居驱动网络演化. 物理学报, 2011, 60(3): 038901. doi: 10.7498/aps.60.038901
  • 引用本文:
    Citation:
计量
  • 文章访问数:  2112
  • PDF下载量:  4169
  • 被引次数: 0
出版历程
  • 收稿日期:  2012-03-31
  • 修回日期:  2012-05-07
  • 刊出日期:  2012-11-05

加权复杂网络社团的评价指标及其发现算法分析

  • 1. 清华大学计算机科学与技术系, 北京 100084;
  • 2. 审计署审计科研所, 北京 100830;
  • 3. 哈尔滨工程大学计算机科学与技术学院, 哈尔滨 150001
    基金项目: 

    国家科技支撑计划(批准号: 2009BAH42B02, 2012BAH08B02)、国家自然科学基金(批准号: 60903080)、中央高校基本科研业务费专项资金(批准号: HEUCFZ100603)和黑龙江省教育厅科学技术研究(批准号: 12513050)资助的课题.

摘要: 节点的聚集现象是复杂网络的重要特性. 以往研究主要发现无权复杂网络中的社团, 较少涉及加权网络的社团发现. 由于加权网络的复杂性远高于无权网络, 一般认为加权网络的社团发现是一个较难的问题. 本文基于统一的数据基础, 从社团评价指标的有效性和现有算法的效果两个角度开展研究. 首先, 总结了加权网络三种常见的社团评估指标, 并在社团大小、密度和局域特点均不同的模拟数据集上分析指标的有效性; 其次, 针对5个数据集, 分析现有的3种加权复杂网络社团发现算法的效果. 研究表明: 上述指标无论在评价最基本的社团结构, 还是在分析结构复杂的社团时都有较大缺欠; 现有的加权网络社团发现算法的泛化能力不强.

English Abstract

参考文献 (25)

目录

    /

    返回文章
    返回