搜索

x

留言板

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

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

考虑边聚类与扩散特性的信息传播网络结构优化算法

杨李 宋玉蓉 李因伟

引用本文:
Citation:

考虑边聚类与扩散特性的信息传播网络结构优化算法

杨李, 宋玉蓉, 李因伟

Network structure optimization algorithm for information propagation considering edge clustering and diffusion characteristics

Yang Li, Song Yu-Rong, Li Yin-Wei
PDF
导出引用
  • 优化网络结构以促进信息在网络中传播一直是复杂网络研究的重点,网络中边的聚类特性和扩散特性对信息传播具有重要作用.K-truss分解算法是一种利用边的聚类特性识别网络关键节点的算法,然而K-truss算法会受到网络中局部聚类结果(即相互连接的假核结构)的影响,而这些假核结构里的节点对信息扩散能力通常较弱.为此,本文提出一种衡量边扩散特性的指标,研究发现一些位于网络边缘的边具有很好的扩散性,但这类边的聚类很低,并不利于信息传播.通过同时考虑边的聚类特性和扩散特性之间的制约关系,提出一种信息传播网络结构优化算法.为了验证所提算法的有效性,使用该算法对四个真实的网络进行结构优化,并使用经典的独立级联模型来验证网络结构优化前后信息传播的有效范围.结果表明:使用提出的算法优化后的网络拓扑可以有效提高信息传播范围;并且,优化后的网络其叶子节点数目降低、聚类系数降低以及平均路径长度降低.
    Optimizing network structure to promote information propagation has been a key issue in the research field of complex network, and both clustering and diffusion characteristics of edges in a network play a very important role in information propagation. K-truss decomposition is an algorithm for identifying the most influential nodes in the network. We find that K-truss decomposition only considers edge clustering characteristics, without considering the diffusion characteristics, so it is easily affected by the local clustering structure in the network, such as core-like groups. There are mutually closely connected the core-like groups in the network, but the correlation between the core-like groups and the other parts of the network is less, so the information is easy to spread in the core-like groups, but not in the other parts of the network, nor over the whole network. For the reason, we propose an index to measure the edge diffusion characteristics in a network, and it is found that the diffusion characteristics of some edges in the periphery of the network are relatively high, but the clustering characteristics of these edges are relatively low, so they are not beneficial for rapid information propagation. In this paper, by considering the relationship between the clustering characteristics and diffusion characteristics of the edges, we propose a novel network structure optimization algorithm for information propagation. By measuring the comprehensive ability strength of the clustering characteristics and the diffusion characteristics of the edges, we can filter out the edges whose comprehensive ability is poor in the network, then determine whether the edges should be optimized according to the relative relationship between the clustering characteristics and the diffusion characteristics of the edges. To prove the effectiveness of the proposed algorithm, it is carried out to optimize the structures of four real networks, and verify the effective range of information propagation before and after the optimization of network structure from the classical independent cascade model. The results show that the network topology optimized by the proposed algorithm can effectively increase the range of information propagation. Moreover, the number of leaf nodes in the optimized network is reduced, and the clustering coefficient and the average path length are also reduced.
      通信作者: 宋玉蓉, songyr@njupt.edu.cn
    • 基金项目: 国家自然科学基金(批准号:61672298,61373136)和教育部人文社科规划基金项目(批准号:17YJAZH071,15YJAZH016)资助的课题.
      Corresponding author: Song Yu-Rong, songyr@njupt.edu.cn
    • Funds: Project supported by the National Natural Science Foundation of China (Grant Nos. 61672298, 61373136) and the Ministry of Education Research in the Humanities and Social Sciences Planning Fund of China (Grant Nos. 17YJAZH071, 15YJAZH016).
    [1]

    Barabasi A L, Albert R 1999 Science 286 509

    [2]

    Watts D J, Strogatz S H 1998 Nature 393 409

    [3]

    Pastor-Satorras R, Vespignani A 2001 Phys. Rev. Lett. 86 3200

    [4]

    Wu Z, Menichetti G, Rahmede C, Bianconi G 2015 Sci. Rep. 5 10073

    [5]

    Serrano A B, Gómez-Gardeñes J, Andrade R F S 2017 Phys. Rev. E 95 052312

    [6]

    Pastor-Satorras R, Vespignani A 2001 Phys. Rev. E 63 066117

    [7]

    Coupechoux E, Lelarge M 2014 Adv. Appl. Probab. 46 985

    [8]

    L L, Chen D B, Zhou T 2011 New J. Phys. 13 123005

    [9]

    Sydney A, Scoglio C, Gruenbacher D 2013 Appl. Math. Comput. 219 5465

    [10]

    Liu C, Zhang Z K 2014 Commun. Nonlinear Sci. 19 896

    [11]

    Peng G S, Tan S Y, Wu J, Holme P 2016 Sci. Rep. 6 37317

    [12]

    Zhang Z K, Liu C, Zhan X X, Xin L, Zhang C X, Zhang Y C 2016 Phys. Rep. 65 1

    [13]

    Liu C, Zhan X X, Zhang Z K, Sun G Q, Hui P M 2015 New J. Phys. 17 113045

    [14]

    Zhan X X, Liu C, Zhou G, Zhang Z, Sun G Q 2018 Appl. Math. Comput. 332 437

    [15]

    Zhan X X, Liu C, Sun G Q, Zhang Z K 2018 Chaos Soliton. Fract. 108 196

    [16]

    Grady D, Thiemann C, Brockmann D 2012 Nat. Commun. 3 864

    [17]

    Yang C L, Tang K S 2011 Chin. Phys. B 20 128901

    [18]

    L L, Chen D, Ren X L, Zhang Q M, Zhang Y C, Zhou T 2016 Phys. Rep. 650 1

    [19]

    Malliaros F D, Rossi M E G, Vazirgiannis M 2016 Sci. Rep. 6 19307

    [20]

    Kitsak M, Gallos L K, Havlin S, Liljeros F, Muchnik L, Stanley H E, Makse H A 2010 Nat. Phys. 6 888

    [21]

    Liu Y, Tang M, Zhou T, Do Y 2015 Sci. Rep. 5 9602

    [22]

    Liu Y, Tang M, Do Y, Hui P M 2017 Phys. Rev. E 96 022323

    [23]

    Wang J, Cheng J 2012 Proc. VLDB Endow. 5 812

    [24]

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

    [25]

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

    [26]

    Guimerà R, Danon L, Díaz-Guilera A, Giralt F, Arenas A 2003 Phys. Rev. E 68 065103

    [27]

    Goldenberg J, Libai B, Muller E 2001 Market. Lett. 12 211

    [28]

    Chen W, Wang Y, Yang S 2009 ACM SIGKDD International Conference on Knowledge Discovery and Data Mining 2009 p199

  • [1]

    Barabasi A L, Albert R 1999 Science 286 509

    [2]

    Watts D J, Strogatz S H 1998 Nature 393 409

    [3]

    Pastor-Satorras R, Vespignani A 2001 Phys. Rev. Lett. 86 3200

    [4]

    Wu Z, Menichetti G, Rahmede C, Bianconi G 2015 Sci. Rep. 5 10073

    [5]

    Serrano A B, Gómez-Gardeñes J, Andrade R F S 2017 Phys. Rev. E 95 052312

    [6]

    Pastor-Satorras R, Vespignani A 2001 Phys. Rev. E 63 066117

    [7]

    Coupechoux E, Lelarge M 2014 Adv. Appl. Probab. 46 985

    [8]

    L L, Chen D B, Zhou T 2011 New J. Phys. 13 123005

    [9]

    Sydney A, Scoglio C, Gruenbacher D 2013 Appl. Math. Comput. 219 5465

    [10]

    Liu C, Zhang Z K 2014 Commun. Nonlinear Sci. 19 896

    [11]

    Peng G S, Tan S Y, Wu J, Holme P 2016 Sci. Rep. 6 37317

    [12]

    Zhang Z K, Liu C, Zhan X X, Xin L, Zhang C X, Zhang Y C 2016 Phys. Rep. 65 1

    [13]

    Liu C, Zhan X X, Zhang Z K, Sun G Q, Hui P M 2015 New J. Phys. 17 113045

    [14]

    Zhan X X, Liu C, Zhou G, Zhang Z, Sun G Q 2018 Appl. Math. Comput. 332 437

    [15]

    Zhan X X, Liu C, Sun G Q, Zhang Z K 2018 Chaos Soliton. Fract. 108 196

    [16]

    Grady D, Thiemann C, Brockmann D 2012 Nat. Commun. 3 864

    [17]

    Yang C L, Tang K S 2011 Chin. Phys. B 20 128901

    [18]

    L L, Chen D, Ren X L, Zhang Q M, Zhang Y C, Zhou T 2016 Phys. Rep. 650 1

    [19]

    Malliaros F D, Rossi M E G, Vazirgiannis M 2016 Sci. Rep. 6 19307

    [20]

    Kitsak M, Gallos L K, Havlin S, Liljeros F, Muchnik L, Stanley H E, Makse H A 2010 Nat. Phys. 6 888

    [21]

    Liu Y, Tang M, Zhou T, Do Y 2015 Sci. Rep. 5 9602

    [22]

    Liu Y, Tang M, Do Y, Hui P M 2017 Phys. Rev. E 96 022323

    [23]

    Wang J, Cheng J 2012 Proc. VLDB Endow. 5 812

    [24]

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

    [25]

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

    [26]

    Guimerà R, Danon L, Díaz-Guilera A, Giralt F, Arenas A 2003 Phys. Rev. E 68 065103

    [27]

    Goldenberg J, Libai B, Muller E 2001 Market. Lett. 12 211

    [28]

    Chen W, Wang Y, Yang S 2009 ACM SIGKDD International Conference on Knowledge Discovery and Data Mining 2009 p199

  • [1] 马晓萍, 杨宏国, 李昌锋, 刘有继, 朴红光. 切边纳米铁磁盘对中磁涡旋旋性的磁场调控. 物理学报, 2021, 70(10): 107502. doi: 10.7498/aps.70.20201995
    [2] 赵国涛, 王立夫, 关博飞. 一类影响网络能控性的边集研究. 物理学报, 2021, 70(14): 148902. doi: 10.7498/aps.70.20201831
    [3] 吴健, 韩文, 程珍珍, 杨彬, 孙利利, 王迪, 朱程鹏, 张勇, 耿明昕, 景龑. 基于流体模型的碳纳米管电离式传感器的结构优化方法. 物理学报, 2021, 70(9): 090701. doi: 10.7498/aps.70.20201828
    [4] 李鑫, 赵城利, 刘阳洋. 有限步传播范围期望指标判别节点传播影响力. 物理学报, 2020, 69(2): 028901. doi: 10.7498/aps.69.20191313
    [5] 肖云鹏, 李松阳, 刘宴兵. 一种基于社交影响力和平均场理论的信息传播动力学模型. 物理学报, 2017, 66(3): 030501. doi: 10.7498/aps.66.030501
    [6] 邓海游, 贾亚, 张阳. 蛋白质结构预测. 物理学报, 2016, 65(17): 178701. doi: 10.7498/aps.65.178701
    [7] 胡庆成, 张勇, 许信辉, 邢春晓, 陈池, 陈信欢. 一种新的复杂网络影响力最大化发现方法. 物理学报, 2015, 64(19): 190101. doi: 10.7498/aps.64.190101
    [8] 王金龙, 刘方爱, 朱振方. 一种基于用户相对权重的在线社交网络信息传播模型. 物理学报, 2015, 64(5): 050501. doi: 10.7498/aps.64.050501
    [9] 王小娟, 宋梅, 郭世泽, 杨子龙. 基于有向渗流理论的关联微博转发网络信息传播研究. 物理学报, 2015, 64(4): 044502. doi: 10.7498/aps.64.044502
    [10] 彭兴钊, 姚宏, 杜军, 丁超, 张志浩. 基于时滞耦合映像格子的多耦合边耦合网络级联抗毁性研究. 物理学报, 2014, 63(7): 078901. doi: 10.7498/aps.63.078901
    [11] 王文祥, 左冬冬, 封国林. 基于信息分配和扩散理论的东北地区干旱脆弱性特征分析. 物理学报, 2014, 63(22): 229201. doi: 10.7498/aps.63.229201
    [12] 刘树新, 季新生, 刘彩霞, 郭虹. 一种信息传播促进网络增长的网络演化模型. 物理学报, 2014, 63(15): 158902. doi: 10.7498/aps.63.158902
    [13] 苑卫国, 刘云, 程军军, 熊菲. 微博双向关注网络节点中心性及传播 影响力的分析. 物理学报, 2013, 62(3): 038901. doi: 10.7498/aps.62.038901
    [14] 张彦超, 刘云, 张海峰, 程辉, 熊菲. 基于在线社交网络的信息传播模型. 物理学报, 2011, 60(5): 050501. doi: 10.7498/aps.60.050501
    [15] 李明杰, 吴晔, 刘维清, 肖井华. 手机短信息传播过程和短信息寿命研究. 物理学报, 2009, 58(8): 5251-5258. doi: 10.7498/aps.58.5251
    [16] 郭进利. 新节点的边对网络无标度性影响. 物理学报, 2008, 57(2): 756-761. doi: 10.7498/aps.57.756
    [17] 刘廷禹, 张启仁, 庄松林. PbWO4晶体中铅空位相关的色心模型. 物理学报, 2005, 54(2): 863-867. doi: 10.7498/aps.54.863
    [18] 柯三黄, 王仁智, 黄美纯. 应变层半导体超晶格价带边不连续性的第一原理研究. 物理学报, 1994, 43(1): 103-109. doi: 10.7498/aps.43.103
    [19] 柯三黄, 王仁智, 黄美纯. 应变层超晶格InAs/InP界面的平均键能行为与价带边不连续性. 物理学报, 1993, 42(9): 1510-1514. doi: 10.7498/aps.42.1510
    [20] 潘士宏, 黄晖, 张存洲, R. N. SACKS. GaAs/Al0.23Ga0.77As双量子阱的带边不连续性和阱间耦合. 物理学报, 1992, 41(8): 1322-1329. doi: 10.7498/aps.41.1322
计量
  • 文章访问数:  2731
  • PDF下载量:  68
  • 被引次数: 0
出版历程
  • 收稿日期:  2018-03-06
  • 修回日期:  2018-07-18
  • 刊出日期:  2018-10-05

考虑边聚类与扩散特性的信息传播网络结构优化算法

  • 1. 南京邮电大学自动化学院, 南京 210023;
  • 2. 江苏省物联网智能机器人工程实验室, 南京 210023;
  • 3. 南京邮电大学计算机学院, 南京 210023
  • 通信作者: 宋玉蓉, songyr@njupt.edu.cn
    基金项目: 国家自然科学基金(批准号:61672298,61373136)和教育部人文社科规划基金项目(批准号:17YJAZH071,15YJAZH016)资助的课题.

摘要: 优化网络结构以促进信息在网络中传播一直是复杂网络研究的重点,网络中边的聚类特性和扩散特性对信息传播具有重要作用.K-truss分解算法是一种利用边的聚类特性识别网络关键节点的算法,然而K-truss算法会受到网络中局部聚类结果(即相互连接的假核结构)的影响,而这些假核结构里的节点对信息扩散能力通常较弱.为此,本文提出一种衡量边扩散特性的指标,研究发现一些位于网络边缘的边具有很好的扩散性,但这类边的聚类很低,并不利于信息传播.通过同时考虑边的聚类特性和扩散特性之间的制约关系,提出一种信息传播网络结构优化算法.为了验证所提算法的有效性,使用该算法对四个真实的网络进行结构优化,并使用经典的独立级联模型来验证网络结构优化前后信息传播的有效范围.结果表明:使用提出的算法优化后的网络拓扑可以有效提高信息传播范围;并且,优化后的网络其叶子节点数目降低、聚类系数降低以及平均路径长度降低.

English Abstract

参考文献 (28)

目录

    /

    返回文章
    返回