搜索

x

留言板

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

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

基于加权K-阶传播数的节点重要性

黄丽亚 汤平川 霍宥良 郑义 成谢锋

引用本文:
Citation:

基于加权K-阶传播数的节点重要性

黄丽亚, 汤平川, 霍宥良, 郑义, 成谢锋

Node importance based on the weighted K-order propagation number algorithm

Huang Li-Ya, Tang Ping-Chuan, Huo You-Liang, Zheng Yi, Cheng Xie-Feng
PDF
HTML
导出引用
  • 节点重要性对于分析网络结构具有重要意义. 为了充分刻画网络全局和局部特性, 本研究基于网络拓扑结构对疾病传播过程进行了抽象, 分别设置各个节点为传染源, 在经历传播时长K后, 将网络中已感染节点的数量定义为K-阶传播数, 最终基于不同K值下的K-阶传播数得到节点重要性结果. 对Watts-Strogatz小世界网络和海豚网络的仿真实验表明, 加权K-阶传播数法对节点重要性的评估较其他方法更为合理, 能够细致地刻画小世界网络中长程连接对信息传输的影响, 提高海豚网络中对社区交流起关键作用的节点的重视程度. 本文利用蓄意攻击策略对美国西部电网、芝加哥公路网络、网络科学家合著网络以及小鼠神经纤维束网络进行了研究, 即依照节点重要性由高到低的排序依次攻击网络. 结果显示, 相较于其他方法, 基于加权K-阶传播数法仅需移除少量重要节点便可实现对网络结构的充分破坏.
    The measurement of node importance is significant for analyzing a network structure. To comprehensively reflect the global and local network features, in this paper we abstract the propagating process of epidemic diseases based on the network topology structure, and then respectively sets each node as an infection source. After a certain dissemination time K, the number of infected nodes in the network is defined as the K-order propagation number, and the weighted sum of K-order propagation numbers under different values of K is taken as the important index of nodes. The simulation experiments of Watts-Strogatz small-world networks and a dolphin network show that the weighted K-order propagation number algorithm is more effective than the traditional method in evaluating the importance of nodes. For the Watts-Strogatz small-world networks, it can reflect the influence of long-distance connections on information transmission in detail. For the dolphin network, the weighted K-order propagation number algorithm significantly raises the profile of those nodes which play a key role in the information communication between different dolphin communities. In addition, in this paper we use a deliberate attacking method to analyze the western power grid of the United States, the road transportation network of the Chicago region, the co-authorship network in network science and the axonal tracts’ network between neurons of mouse. According to the specific order of the node importance from high to low, network nodes are attacked in turn, that is, all edges of the attacked nodes are removed. The analysis results of network parameters such as the network efficiency and the node number of the maximum sub-graph changing with the attacking times show that comparing with other evaluation indices of node importance such as degree, Ren method, Chen method, eigenvector method, Katz index, PageRank, CI method and K-shell, the weighted K-order propagation number algorithm focuses much on destroying the major structure, and all of the above four networks will break down if only a small number of important nodes are attacked. For example, after attacking only 100 nodes, the network efficiency of the western power grid of the United States is down by 90%, and after attacking 200 nodes, the network scale of the maximum sub-graph is nearly 3% of the original network.
      通信作者: 黄丽亚, huangly@njupt.edu.cn
    • 基金项目: 国家自然科学基金(批准号: 71671093, 61271334)资助的课题.
      Corresponding author: Huang Li-Ya, huangly@njupt.edu.cn
    • Funds: Project supported by the National Natural Science Foundation of China (Grant Nos. 71671093, 61271334).
    [1]

    周漩, 张凤鸣, 周卫平, 邹伟, 杨帆 2012 物理学报 61 190201Google Scholar

    Zhou X, Zhang F M, Zhou W P, Zhou W, Yang F 2012 Acta Phys. Sin. 61 190201Google Scholar

    [2]

    周涛, 柏文洁, 汪秉宏, 刘之景, 严钢 2005 物理 34 31Google Scholar

    Zhou T, Bai W J, Wang B H, Liu Z J, Yan G 2005 Physics 34 31Google Scholar

    [3]

    Liu J G, Wang Z T, Dang Y Z 2005 Mod. Phys. Lett. B 19 785Google Scholar

    [4]

    汪小帆, 李翔, 陈关荣 2006 复杂网络理论及其应用 (北京: 清华大学出版社) 第8页

    Wang X F, Li X, Chen G R 2006 Complex Network Theory and Application (Beijing: Tsinghua University Press) p8 (in Chinese)

    [5]

    Dunne J A, Williams R J, Martinez N D 2002 Ecol. Lett. 5 558Google Scholar

    [6]

    Samant K, Bhattacharyya S 2004 Proceedings of the 37th Annual Hawaii International Conference on System Sciences Washington, USA, January 5–8, 2004 p289

    [7]

    Newman M E J, Forrest S, Balthrop A 2002 Phys. Rev. E 66 035101

    [8]

    Jeong H, Mason S, Barabasi A L 2001 Nature 411 41Google Scholar

    [9]

    任卓明, 邵凤, 刘建国, 郭强, 汪秉宏 2013 物理学报 62 128901Google Scholar

    Ren Z M, Shao F, Liu J G, Guo Q, Wang B H 2013 Acta Phys. Sin. 62 128901Google Scholar

    [10]

    Chen D B, Lü L Y, Shang M S, Zhang Y C, Zhou T 2012 Physica A 391 1777Google Scholar

    [11]

    Freeman L C 1977 Sociometry 40 35Google Scholar

    [12]

    Sabidussi G 1966 Psyehometrika 31 581Google Scholar

    [13]

    Bavelas A 1950 J. Acoustical Soc. Amer. 22 725Google Scholar

    [14]

    Stephenson K, Zelen M 1989 Soc. Netw. 1 11

    [15]

    Borgatti S P 2005 Soc. Netw. 27 55Google Scholar

    [16]

    Katz L 1953 Psychometrika 18 39Google Scholar

    [17]

    Zhang J, Xu X K, Li P, Zhang K, Small M 2011 Chaos 21 016107Google Scholar

    [18]

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

    [19]

    Zeng A, Zhang C J 2013 Phys. Lett. A 377 1031Google Scholar

    [20]

    Bryan K, Leise T 2006 SIAM Rev. 48 569Google Scholar

    [21]

    Lü L Y, Zhang Y C, Yeung C H, Zhou T 2011 PLoS One 6 e 2120 2

    [22]

    Zhong L F, Liu Q H, Wang W, Cai S M 2018 Physica A 511 78Google Scholar

    [23]

    Allen L J S 1994 Math. Biosci. 124 83Google Scholar

    [24]

    黄丽亚, 霍宥良, 王青, 成谢锋 2019 物理学报 68 018901Google Scholar

    Huang L Y, Huo Y L, Wang Q, Cheng X F 2019 Acta Phys. Sin. 68 018901Google Scholar

    [25]

    Watts D J, Strogatz S H 1998 Nature 393 440Google Scholar

    [26]

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

    [27]

    Lusseau D, Newman M E J 2004 Proc. Biol. Sci. 271 477Google Scholar

    [28]

    Eash R W, Chon K S, Lee Y J, Boyce D E 1983 Transport. Res. Rec. 994 30

    [29]

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

    [30]

    Ryan A R, Nesreen K A 2015 Proceedings of the Twenty-Ninth AAAI Conference on Artificial Austin, Texas, January 25–30, 2015 p4292

    [31]

    李鹏翔, 任玉晴, 席酉民 2004 系统工程 22 13Google Scholar

    Li P X, Ren Y Q, Xi Y M 2004 Syst. Eng. 22 13Google Scholar

    [32]

    赫南, 李德毅, 淦文燕, 朱熙 2007 计算机科学 34 1Google Scholar

    He N, Li D Y, Gan W Y, Zhu X 2007 Comput. Sci. 34 1Google Scholar

    [33]

    赵志远, 孟相如, 孙瑞男 2018 计算机工程 44 62Google Scholar

    Zhao Z Y, Meng X R, Sun R N 2018 Comput. Eng. 44 62Google Scholar

  • 图 1  随机生成的100节点WS小世界网络 (a) 网络结构; (b) 边31-33被改连至边31-72; (c) 边95-96被改连至边95-53

    Fig. 1.  A random WS small-world network with 100 nodes: (a) Network structure; (b) the edge 31-33 is rescheduled to the edge 31-72; (c) the edge 95-96 is rescheduled to the edge 95-53.

    图 2  基于加权K-阶传播数法的WS小世界网络节点重要性结果 (a) K-阶结构熵; (b) 权重系数; (c) 节点重要性

    Fig. 2.  Node importance of the WS small-world network based on the weighted K-order propagation number algorithm: (a) The K-order structure entropy; (b) the weight coefficient; (c) the importance of nodes.

    图 3  基于若干传统算法的WS小世界网络节点重要性评价结果 (a) 度中心性; (b) Ren法; (c) Chen法; (d) 介数中心性; (e) 特征向量法; (f) Katz指标法; (g) PageRank算法; (h) CI法

    Fig. 3.  Node importance of the WS small-world network based on some traditional algorithms: (a) Degree centrality; (b) Ren method; (c) Chen method; (d) betweenness centrality; (e) eigenvector method; (f) Katz index; (g) PageRank; (h) CI method.

    图 4  基于加权K-阶传播数法的海豚网络节点重要性结果 (a) K-阶结构熵; (b) 权重系数; (c) 节点重要性

    Fig. 4.  Node importance of the dolphin network based on the weighted K-order propagation number algorithm: (a) The K-order structure entropy; (b) the weight coefficient; (c) the importance of nodes.

    图 5  K-阶结构熵 (a) 美国西部电网; (b) 芝加哥公路网络; (c) 科学家合作网络; (d) 小鼠神经纤维束网络

    Fig. 5.  The K-order structure entropy: (a) The western power grid of the United States; (b) the road transportation network of the Chicago region; (c) the co-authorship network in network science; (d) the axonal tracts network between neurons of mouse.

    图 6  网络效率下降率ε随攻击次数的变化情况 (a) 美国西部电网; (b) 芝加哥公路网络; (c) 网络科学家合著网络; (d) 小鼠神经纤维束网络

    Fig. 6.  Change of the network efficiency decrease rate ε with attacking times: (a) The western power grid of the United States; (b) the road transportation network of the Chicago region; (c) the co-authorship network in network science; (d) the axonal tracts network between neurons of mouse.

    图 7  最大子图节点数γ随攻击次数的变化情况 (a) 美国西部电网; (b) 芝加哥公路网络; (c) 网络科学家合著网络; (d) 小鼠神经纤维束网络

    Fig. 7.  Change of the node number of the maximum sub-graph ε with attacking times: (a) The western power grid of the United States; (b) the road transportation network of the Chicago region; (c) the co-authorship network in network science; (d) the axonal tracts network between neurons of mouse.

    表 1  WS小世界网络以及同规模随机网络的网络参数

    Table 1.  Network features of the WS small-world network and random networks.

    网络类型节点数边数平均聚类
    系数
    特征路径
    长度
    WS小世界网络1002000.4868.4891
    随机网络1002000.02543.4158
    下载: 导出CSV

    表 2  海豚网节点重要性排序结果

    Table 2.  Node importance ordering result of the dolphin network.

    节点重要性加权K-阶传播数法Ren法Chen法介数中心性法特征向量法Katz指标法PageRank算法CI法
    11515153715151515
    2383838238381838
    34646464146465246
    42134343834345834
    5415151851523841
    63441411830304630
    73721172152413452
    83030225517213021
    95252195241511451
    10514430582239219
    11239214019192139
    123919252939173917
    131937393025221022
    144422524444444144
    15918441521255525
    下载: 导出CSV
  • [1]

    周漩, 张凤鸣, 周卫平, 邹伟, 杨帆 2012 物理学报 61 190201Google Scholar

    Zhou X, Zhang F M, Zhou W P, Zhou W, Yang F 2012 Acta Phys. Sin. 61 190201Google Scholar

    [2]

    周涛, 柏文洁, 汪秉宏, 刘之景, 严钢 2005 物理 34 31Google Scholar

    Zhou T, Bai W J, Wang B H, Liu Z J, Yan G 2005 Physics 34 31Google Scholar

    [3]

    Liu J G, Wang Z T, Dang Y Z 2005 Mod. Phys. Lett. B 19 785Google Scholar

    [4]

    汪小帆, 李翔, 陈关荣 2006 复杂网络理论及其应用 (北京: 清华大学出版社) 第8页

    Wang X F, Li X, Chen G R 2006 Complex Network Theory and Application (Beijing: Tsinghua University Press) p8 (in Chinese)

    [5]

    Dunne J A, Williams R J, Martinez N D 2002 Ecol. Lett. 5 558Google Scholar

    [6]

    Samant K, Bhattacharyya S 2004 Proceedings of the 37th Annual Hawaii International Conference on System Sciences Washington, USA, January 5–8, 2004 p289

    [7]

    Newman M E J, Forrest S, Balthrop A 2002 Phys. Rev. E 66 035101

    [8]

    Jeong H, Mason S, Barabasi A L 2001 Nature 411 41Google Scholar

    [9]

    任卓明, 邵凤, 刘建国, 郭强, 汪秉宏 2013 物理学报 62 128901Google Scholar

    Ren Z M, Shao F, Liu J G, Guo Q, Wang B H 2013 Acta Phys. Sin. 62 128901Google Scholar

    [10]

    Chen D B, Lü L Y, Shang M S, Zhang Y C, Zhou T 2012 Physica A 391 1777Google Scholar

    [11]

    Freeman L C 1977 Sociometry 40 35Google Scholar

    [12]

    Sabidussi G 1966 Psyehometrika 31 581Google Scholar

    [13]

    Bavelas A 1950 J. Acoustical Soc. Amer. 22 725Google Scholar

    [14]

    Stephenson K, Zelen M 1989 Soc. Netw. 1 11

    [15]

    Borgatti S P 2005 Soc. Netw. 27 55Google Scholar

    [16]

    Katz L 1953 Psychometrika 18 39Google Scholar

    [17]

    Zhang J, Xu X K, Li P, Zhang K, Small M 2011 Chaos 21 016107Google Scholar

    [18]

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

    [19]

    Zeng A, Zhang C J 2013 Phys. Lett. A 377 1031Google Scholar

    [20]

    Bryan K, Leise T 2006 SIAM Rev. 48 569Google Scholar

    [21]

    Lü L Y, Zhang Y C, Yeung C H, Zhou T 2011 PLoS One 6 e 2120 2

    [22]

    Zhong L F, Liu Q H, Wang W, Cai S M 2018 Physica A 511 78Google Scholar

    [23]

    Allen L J S 1994 Math. Biosci. 124 83Google Scholar

    [24]

    黄丽亚, 霍宥良, 王青, 成谢锋 2019 物理学报 68 018901Google Scholar

    Huang L Y, Huo Y L, Wang Q, Cheng X F 2019 Acta Phys. Sin. 68 018901Google Scholar

    [25]

    Watts D J, Strogatz S H 1998 Nature 393 440Google Scholar

    [26]

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

    [27]

    Lusseau D, Newman M E J 2004 Proc. Biol. Sci. 271 477Google Scholar

    [28]

    Eash R W, Chon K S, Lee Y J, Boyce D E 1983 Transport. Res. Rec. 994 30

    [29]

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

    [30]

    Ryan A R, Nesreen K A 2015 Proceedings of the Twenty-Ninth AAAI Conference on Artificial Austin, Texas, January 25–30, 2015 p4292

    [31]

    李鹏翔, 任玉晴, 席酉民 2004 系统工程 22 13Google Scholar

    Li P X, Ren Y Q, Xi Y M 2004 Syst. Eng. 22 13Google Scholar

    [32]

    赫南, 李德毅, 淦文燕, 朱熙 2007 计算机科学 34 1Google Scholar

    He N, Li D Y, Gan W Y, Zhu X 2007 Comput. Sci. 34 1Google Scholar

    [33]

    赵志远, 孟相如, 孙瑞男 2018 计算机工程 44 62Google Scholar

    Zhao Z Y, Meng X R, Sun R N 2018 Comput. Eng. 44 62Google Scholar

  • [1] 李江, 刘影, 王伟, 周涛. 识别高阶网络传播中最有影响力的节点. 物理学报, 2024, 73(4): 048901. doi: 10.7498/aps.73.20231416
    [2] 汪亭亭, 梁宗文, 张若曦. 基于信息熵与迭代因子的复杂网络节点重要性评价方法. 物理学报, 2023, 72(4): 048901. doi: 10.7498/aps.72.20221878
    [3] 阮逸润, 老松杨, 汤俊, 白亮, 郭延明. 基于引力方法的复杂网络节点重要度评估方法. 物理学报, 2022, 71(17): 176401. doi: 10.7498/aps.71.20220565
    [4] 杨松青, 蒋沅, 童天驰, 严玉为, 淦各升. 基于Tsallis熵的复杂网络节点重要性评估方法. 物理学报, 2021, 70(21): 216401. doi: 10.7498/aps.70.20210979
    [5] 孔江涛, 黄健, 龚建兴, 李尔玉. 基于复杂网络动力学模型的无向加权网络节点重要性评估. 物理学报, 2018, 67(9): 098901. doi: 10.7498/aps.67.20172295
    [6] 苏臻, 高超, 李向华. 节点中心性对复杂网络传播模式的影响分析. 物理学报, 2017, 66(12): 120201. doi: 10.7498/aps.66.120201
    [7] 王雨, 郭进利. 基于多重影响力矩阵的有向加权网络节点重要性评估方法. 物理学报, 2017, 66(5): 050201. doi: 10.7498/aps.66.050201
    [8] 阮逸润, 老松杨, 王竣德, 白亮, 陈立栋. 基于领域相似度的复杂网络节点重要度评估算法. 物理学报, 2017, 66(3): 038902. doi: 10.7498/aps.66.038902
    [9] 韩忠明, 陈炎, 李梦琪, 刘雯, 杨伟杰. 一种有效的基于三角结构的复杂网络节点影响力度量模型. 物理学报, 2016, 65(16): 168901. doi: 10.7498/aps.65.168901
    [10] 王超, 刘骋远, 胡元萍, 刘志宏, 马建峰. 社交网络中信息传播的稳定性研究. 物理学报, 2014, 63(18): 180501. doi: 10.7498/aps.63.180501
    [11] 胡庆成, 尹龑燊, 马鹏斐, 高旸, 张勇, 邢春晓. 一种新的网络传播中最有影响力的节点发现方法. 物理学报, 2013, 62(14): 140101. doi: 10.7498/aps.62.140101
    [12] 苑卫国, 刘云, 程军军, 熊菲. 微博双向关注网络节点中心性及传播 影响力的分析. 物理学报, 2013, 62(3): 038901. doi: 10.7498/aps.62.038901
    [13] 任卓明, 刘建国, 邵凤, 胡兆龙, 郭强. 复杂网络中最小K-核节点的传播能力分析. 物理学报, 2013, 62(10): 108902. doi: 10.7498/aps.62.108902
    [14] 任卓明, 邵凤, 刘建国, 郭强, 汪秉宏. 基于度与集聚系数的网络节点重要性度量方法研究. 物理学报, 2013, 62(12): 128901. doi: 10.7498/aps.62.128901
    [15] 刘建国, 任卓明, 郭强, 汪秉宏. 复杂网络中节点重要性排序的研究进展. 物理学报, 2013, 62(17): 178901. doi: 10.7498/aps.62.178901
    [16] 于会, 刘尊, 李勇军. 基于多属性决策的复杂网络节点重要性综合评价方法. 物理学报, 2013, 62(2): 020204. doi: 10.7498/aps.62.020204
    [17] 周漩, 张凤鸣, 李克武, 惠晓滨, 吴虎胜. 利用重要度评价矩阵确定复杂网络关键节点. 物理学报, 2012, 61(5): 050201. doi: 10.7498/aps.61.050201
    [18] 熊菲, 刘云, 司夏萌, 丁飞. 基于Web 2.0的边与节点同时增长网络模型. 物理学报, 2010, 59(10): 6889-6895. doi: 10.7498/aps.59.6889
    [19] 许 丹, 李 翔, 汪小帆. 复杂网络病毒传播的局域控制研究. 物理学报, 2007, 56(3): 1313-1317. doi: 10.7498/aps.56.1313
    [20] 李 季, 汪秉宏, 蒋品群, 周 涛, 王文旭. 节点数加速增长的复杂网络生长模型. 物理学报, 2006, 55(8): 4051-4057. doi: 10.7498/aps.55.4051
计量
  • 文章访问数:  7125
  • PDF下载量:  108
  • 被引次数: 0
出版历程
  • 收稿日期:  2019-01-16
  • 修回日期:  2019-04-05
  • 上网日期:  2019-06-01
  • 刊出日期:  2019-06-20

/

返回文章
返回