搜索

x

留言板

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

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

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

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

引用本文:
Citation:

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

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

Analysis of community evaluation criterion and discovery algorithm of weighted complex network

Lü Tian-Yang, Xie Wen-Yan, Zheng Wei-Min, Piao Xiu-Feng
PDF
导出引用
  • 节点的聚集现象是复杂网络的重要特性. 以往研究主要发现无权复杂网络中的社团, 较少涉及加权网络的社团发现. 由于加权网络的复杂性远高于无权网络, 一般认为加权网络的社团发现是一个较难的问题. 本文基于统一的数据基础, 从社团评价指标的有效性和现有算法的效果两个角度开展研究. 首先, 总结了加权网络三种常见的社团评估指标, 并在社团大小、密度和局域特点均不同的模拟数据集上分析指标的有效性; 其次, 针对5个数据集, 分析现有的3种加权复杂网络社团发现算法的效果. 研究表明: 上述指标无论在评价最基本的社团结构, 还是在分析结构复杂的社团时都有较大缺欠; 现有的加权网络社团发现算法的泛化能力不强.
    The clustering of nodes is an important feature of complex network. Previous researches mainly focus on community discovery in unweighted network, with little attention paid to the weighted network because of the complexity of weighted network. The community discovery of the weighted network is believed to be a much more difficult task. In this paper, we perform a study on the effectivenesses of community evaluation criterion and the performances of the existing discovery algorithms. First, we summarize three classical community evaluation criterions of weighted network, and analyze their effectivenesses according to a simulated noisy dataset, which has different community sizes, densities and local characteristics. Second, we adopt five datasets to compare the performances of three typical community discovery algorithms. The study shows that the existing criterions encounter difficulties in evaluating the basic community structure and in evaluating the weighted community with complex structure, and the generalization ability of the typical community discovery algorithm of weighted network is unsatisfactory.
    • 基金项目: 国家科技支撑计划(批准号: 2009BAH42B02, 2012BAH08B02)、国家自然科学基金(批准号: 60903080)、中央高校基本科研业务费专项资金(批准号: HEUCFZ100603)和黑龙江省教育厅科学技术研究(批准号: 12513050)资助的课题.
    • Funds: Project supported by the National Basic Research Program of China (Grant Nos. 2009BAH42B02, 2012BAH08B02), the National Natural Science Foundation of China (Grant No. 60903080), the Fundamental Research Funds for the Central Universities, China (Grant No. HEUCF100603) and the Scientific Research Fund of Heilongjiang Provincial Education Department, China (Grant No. 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] 阮逸润, 老松杨, 汤俊, 白亮, 郭延明. 基于引力方法的复杂网络节点重要度评估方法. 物理学报, 2022, 0(0): 0-0. doi: 10.7498/aps.71.20220565
    [2] 徐明, 许传云, 曹克非. 度相关性对无向网络可控性的影响. 物理学报, 2017, 66(2): 028901. doi: 10.7498/aps.66.028901
    [3] 阮逸润, 老松杨, 王竣德, 白亮, 陈立栋. 基于领域相似度的复杂网络节点重要度评估算法. 物理学报, 2017, 66(3): 038902. doi: 10.7498/aps.66.038902
    [4] 胡耀光, 王圣军, 金涛, 屈世显. 度关联无标度网络上的有倾向随机行走. 物理学报, 2015, 64(2): 028901. doi: 10.7498/aps.64.028901
    [5] 闵磊, 刘智, 唐向阳, 陈矛, 刘三(女牙). 基于扩展度的复杂网络传播影响力评估算法. 物理学报, 2015, 64(8): 088901. doi: 10.7498/aps.64.088901
    [6] 胡庆成, 张勇, 许信辉, 邢春晓, 陈池, 陈信欢. 一种新的复杂网络影响力最大化发现方法. 物理学报, 2015, 64(19): 190101. doi: 10.7498/aps.64.190101
    [7] 欧阳博, 金心宇, 夏永祥, 蒋路茸, 吴端坡. 疾病传播与级联失效相互作用的研究:度不相关网络中疾病扩散条件的分析. 物理学报, 2014, 63(21): 218902. doi: 10.7498/aps.63.218902
    [8] 侯凤贞, 戴加飞, 刘新峰, 黄晓林. 基于网络连接度指标的脑梗死患者脑电信号相同步分析. 物理学报, 2014, 63(4): 040506. doi: 10.7498/aps.63.040506
    [9] 段东立, 战仁军. 基于相继故障信息的网络节点重要度演化机理分析. 物理学报, 2014, 63(6): 068902. doi: 10.7498/aps.63.068902
    [10] 王兴元, 赵仲祥. 基于节点间依赖度的社团结构划分方法. 物理学报, 2014, 63(17): 178901. doi: 10.7498/aps.63.178901
    [11] 李雨珊, 吕翎, 刘烨, 刘硕, 闫兵兵, 常欢, 周佳楠. 复杂网络时空混沌同步的Backstepping设计. 物理学报, 2013, 62(2): 020513. doi: 10.7498/aps.62.020513
    [12] 余晓平, 裴韬. 手机通话网络度特征分析. 物理学报, 2013, 62(20): 208901. doi: 10.7498/aps.62.208901
    [13] 胡庆成, 尹龑燊, 马鹏斐, 高旸, 张勇, 邢春晓. 一种新的网络传播中最有影响力的节点发现方法 . 物理学报, 2013, 62(14): 140101. doi: 10.7498/aps.62.140101
    [14] 丁益民, 丁卓, 杨昌平. 基于社团结构的城市地铁网络模型研究. 物理学报, 2013, 62(9): 098901. doi: 10.7498/aps.62.098901
    [15] 周漩, 张凤鸣, 李克武, 惠晓滨, 吴虎胜. 利用重要度评价矩阵确定复杂网络关键节点. 物理学报, 2012, 61(5): 050201. doi: 10.7498/aps.61.050201
    [16] 袁超, 柴毅. 基于簇相似度的网络社团结构探测算法. 物理学报, 2012, 61(21): 218901. doi: 10.7498/aps.61.218901
    [17] 张聪, 沈惠璋, 李峰, 杨何群. 复杂网络中社团结构发现的多分辨率密度模块度. 物理学报, 2012, 61(14): 148902. doi: 10.7498/aps.61.148902
    [18] 闫小勇, 王明生. 增长速度对合作网络参与者节点度分布的影响. 物理学报, 2010, 59(2): 851-858. doi: 10.7498/aps.59.851
    [19] 高忠科, 金宁德. 两相流流型复杂网络社团结构及其统计特性. 物理学报, 2008, 57(11): 6909-6920. doi: 10.7498/aps.57.6909
    [20] 许 丹, 李 翔, 汪小帆. 复杂网络病毒传播的局域控制研究. 物理学报, 2007, 56(3): 1313-1317. doi: 10.7498/aps.56.1313
计量
  • 文章访问数:  4651
  • PDF下载量:  4199
  • 被引次数: 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)

目录

    /

    返回文章
    返回