搜索

x

留言板

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

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

基于簇相似度的网络社团结构探测算法

袁超 柴毅

引用本文:
Citation:

基于簇相似度的网络社团结构探测算法

袁超, 柴毅

Group similarity based algorithm for network community structure detection

Yuan Chao, Chai Yi
PDF
导出引用
  • 社团结构对复杂系统的结构特性和动力学特性有重要影响. 提出了一个度量社团相似度的模型, 称为簇相似度. 该模型能够度量两个社团的相似度大小, 为研究社团间的作用机制提供帮助. 而且基于该模型, 设计了一个社团划分算法. 算法采用层次聚类的思想, 每次合并两个相似度最大的社团, 并通过一个评价函数选择最优社团划分. 数值实验以及与CNM, GN, EigenMod等主流算法做比较, 表明本算法的精度和效率都比较高, 尤其对于边密度较高的网络, 性能非常理想.
    Community structure has an important influence on the structural and dynamic characteristics of the complex system. In the present study, a group similarity model is proposed for the measurement of similarity between two communities. So it can help us understand the mechanism of inter action between these communities. Moreover, based on this model, a hierarchical clustering based algorithm for network community structure detection is put forward. By this algorithm, one pair of communities with the largest similarity is merged in each iteration. And then an evaluation function is adopted for choosing the optimal partition. The algorithm gives a higher performance than many state-of-the-art community detection algorithms when tested on a series of real-world and synthetic networks. Especially, it performs better when the edge density of the network is high.
    • 基金项目: 国家自然科学基金(批准号: 60974090)和高等学校博士学科点专项科研基金(批准号: 200806110016)资助的课题.
    • Funds: Project supported by the National Natural Science Foundation of China (Grant No. 60974090) and the Specialized Research Fund for the Doctoral Program of Higher Education of China (Grant No. 200806110016).
    [1]

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

    [2]

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

    [3]

    Newman M E J 2004 Phys. Rev. E 69 066133

    [4]

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

    [5]

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

    [6]

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

    [7]

    Kernighan W, Lin S 1970 Bell. Syst. Tech. J. 49 291

    [8]

    Raghavan U N, Albert R, Kumara S 2007 Phys. Rev. E 76 036106

    [9]

    Luo Z G, Ding F, Jiang X Z, Shi J L 2011 Guofang Keji Daxue Xuebao 33 47 (in Chinese) [骆志刚, 丁凡, 蒋晓舟, 石金龙 2011 国防科技大学学报 33 47]

    [10]

    Ma X, Gao L 2011 J. Stat. Mech.-Theory Exp. 5 P05012

    [11]

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

    [12]

    Stanoev A, Smilkov D, Kocarev L 2011 Phys. Rev. E 84 046102

    [13]

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

    [14]

    Li W, Yang J Y, Hadden W C 2009 Europhys. Lett. 88 68007

    [15]

    Pan Y, Li D H, Liu J G, Liang J Z 2010 Physica A 389 2849

    [16]

    Palla G, Derenyi I, Farkas I, Vicsek T 2005 Nature 435 814

    [17]

    Sun P G, Gao L, Han S S 2011 Inform. Sciences 181 1060

    [18]

    Lancichinetti A, Fortunato S, Kertész J 2009 New J. Phys. 11 033015

    [19]

    Newman M E J, Leicht E A 2007 Proc. Natl. Acad. Sci. USA 104 9564

    [20]

    Ahn Y Y, Bagrow J P, Lehmann S 2010 Nature 466 761

    [21]

    Mucha P J 2010 Science 328 876

    [22]

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

    [23]

    Ahlgren P, Jarneving B, Rousseau R 2003 J. Am. Soc. Inf. Sci. Tech. 54 550

    [24]

    Bhattacharyya A 1946 SANKHYA 7 401

    [25]

    Egghe L, Rousseau R 2006 Inform. Process. Manag. 42 106

    [26]

    Lusseau D, Schneider K, Boisseau O J, Haase P, Slooten E, Dawson S M 2003 Behav. Ecol. Sociobiol. 54 396

    [27]

    Knuth D E 1993 The Stanford Graph Base: A Platform for Combinatorial Computing (1st Edn.) (New Jersey: Addison-Wesley Professional) p4

    [28]

    Clauset A, Newman M E J, Moore C 2004 Phys. Rev. E 70 066111

    [29]

    Newman M E J 2006 Proc. Natl. Acad. Sci. USA 103 8577

  • [1]

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

    [2]

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

    [3]

    Newman M E J 2004 Phys. Rev. E 69 066133

    [4]

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

    [5]

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

    [6]

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

    [7]

    Kernighan W, Lin S 1970 Bell. Syst. Tech. J. 49 291

    [8]

    Raghavan U N, Albert R, Kumara S 2007 Phys. Rev. E 76 036106

    [9]

    Luo Z G, Ding F, Jiang X Z, Shi J L 2011 Guofang Keji Daxue Xuebao 33 47 (in Chinese) [骆志刚, 丁凡, 蒋晓舟, 石金龙 2011 国防科技大学学报 33 47]

    [10]

    Ma X, Gao L 2011 J. Stat. Mech.-Theory Exp. 5 P05012

    [11]

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

    [12]

    Stanoev A, Smilkov D, Kocarev L 2011 Phys. Rev. E 84 046102

    [13]

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

    [14]

    Li W, Yang J Y, Hadden W C 2009 Europhys. Lett. 88 68007

    [15]

    Pan Y, Li D H, Liu J G, Liang J Z 2010 Physica A 389 2849

    [16]

    Palla G, Derenyi I, Farkas I, Vicsek T 2005 Nature 435 814

    [17]

    Sun P G, Gao L, Han S S 2011 Inform. Sciences 181 1060

    [18]

    Lancichinetti A, Fortunato S, Kertész J 2009 New J. Phys. 11 033015

    [19]

    Newman M E J, Leicht E A 2007 Proc. Natl. Acad. Sci. USA 104 9564

    [20]

    Ahn Y Y, Bagrow J P, Lehmann S 2010 Nature 466 761

    [21]

    Mucha P J 2010 Science 328 876

    [22]

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

    [23]

    Ahlgren P, Jarneving B, Rousseau R 2003 J. Am. Soc. Inf. Sci. Tech. 54 550

    [24]

    Bhattacharyya A 1946 SANKHYA 7 401

    [25]

    Egghe L, Rousseau R 2006 Inform. Process. Manag. 42 106

    [26]

    Lusseau D, Schneider K, Boisseau O J, Haase P, Slooten E, Dawson S M 2003 Behav. Ecol. Sociobiol. 54 396

    [27]

    Knuth D E 1993 The Stanford Graph Base: A Platform for Combinatorial Computing (1st Edn.) (New Jersey: Addison-Wesley Professional) p4

    [28]

    Clauset A, Newman M E J, Moore C 2004 Phys. Rev. E 70 066111

    [29]

    Newman M E J 2006 Proc. Natl. Acad. Sci. USA 103 8577

  • [1] 阮逸润, 老松杨, 汤俊, 白亮, 郭延明. 基于引力方法的复杂网络节点重要度评估方法. 物理学报, 2022, 0(0): 0-0. 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(17): 178901. doi: 10.7498/aps.63.178901
    [6] 丁益民, 丁卓, 杨昌平. 基于社团结构的城市地铁网络模型研究. 物理学报, 2013, 62(9): 098901. doi: 10.7498/aps.62.098901
    [7] 刘金良. 具有随机节点结构的复杂网络同步研究. 物理学报, 2013, 62(4): 040503. doi: 10.7498/aps.62.040503
    [8] 柳爽, 吕翎, 李钢. 一类不确定复杂网络的滑模追踪同步. 物理学报, 2012, 61(16): 160507. doi: 10.7498/aps.61.160507
    [9] 吕翎, 柳爽, 张新, 朱佳博, 沈娜, 商锦玉. 节点结构互异的复杂网络的时空混沌反同步. 物理学报, 2012, 61(9): 090504. doi: 10.7498/aps.61.090504
    [10] 周漩, 张凤鸣, 李克武, 惠晓滨, 吴虎胜. 利用重要度评价矩阵确定复杂网络关键节点. 物理学报, 2012, 61(5): 050201. doi: 10.7498/aps.61.050201
    [11] 吕天阳, 谢文艳, 郑纬民, 朴秀峰. 加权复杂网络社团的评价指标及其发现算法分析. 物理学报, 2012, 61(21): 210511. doi: 10.7498/aps.61.210511
    [12] 高忠科, 金宁德, 杨丹, 翟路生, 杜萌. 多元时间序列复杂网络流型动力学分析. 物理学报, 2012, 61(12): 120510. doi: 10.7498/aps.61.120510
    [13] 张聪, 沈惠璋, 李峰, 杨何群. 复杂网络中社团结构发现的多分辨率密度模块度. 物理学报, 2012, 61(14): 148902. doi: 10.7498/aps.61.148902
    [14] 崔爱香, 傅彦, 尚明生, 陈端兵, 周涛. 复杂网络局部结构的涌现:共同邻居驱动网络演化. 物理学报, 2011, 60(3): 038901. doi: 10.7498/aps.60.038901
    [15] 邵斐, 蒋国平. 基于社团结构的负载传输优化策略研究. 物理学报, 2011, 60(7): 078902. doi: 10.7498/aps.60.078902
    [16] 王高峡, 沈轶. 网络的模块矩阵及其社团结构指标. 物理学报, 2010, 59(2): 842-850. doi: 10.7498/aps.59.842
    [17] 沈毅, 徐焕良. 加权网络权重自相似评判函数及其社团结构检测. 物理学报, 2010, 59(9): 6022-6028. doi: 10.7498/aps.59.6022
    [18] 吕翎, 张超. 一类节点结构互异的复杂网络的混沌同步. 物理学报, 2009, 58(3): 1462-1466. doi: 10.7498/aps.58.1462
    [19] 高忠科, 金宁德. 两相流流型复杂网络社团结构及其统计特性. 物理学报, 2008, 57(11): 6909-6920. doi: 10.7498/aps.57.6909
    [20] 张军峰, 胡寿松. 基于一种新型聚类算法的RBF神经网络混沌时间序列预测. 物理学报, 2007, 56(2): 713-719. doi: 10.7498/aps.56.713
计量
  • 文章访问数:  3921
  • PDF下载量:  908
  • 被引次数: 0
出版历程
  • 收稿日期:  2012-03-11
  • 修回日期:  2012-05-03
  • 刊出日期:  2012-11-05

基于簇相似度的网络社团结构探测算法

  • 1. 重庆大学自动化学院, 重庆 400030
    基金项目: 国家自然科学基金(批准号: 60974090)和高等学校博士学科点专项科研基金(批准号: 200806110016)资助的课题.

摘要: 社团结构对复杂系统的结构特性和动力学特性有重要影响. 提出了一个度量社团相似度的模型, 称为簇相似度. 该模型能够度量两个社团的相似度大小, 为研究社团间的作用机制提供帮助. 而且基于该模型, 设计了一个社团划分算法. 算法采用层次聚类的思想, 每次合并两个相似度最大的社团, 并通过一个评价函数选择最优社团划分. 数值实验以及与CNM, GN, EigenMod等主流算法做比较, 表明本算法的精度和效率都比较高, 尤其对于边密度较高的网络, 性能非常理想.

English Abstract

参考文献 (29)

目录

    /

    返回文章
    返回