搜索

x

留言板

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

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

一种基于离散数据从局部到全局的网络重构算法

徐翔 朱承 朱先强

引用本文:
Citation:

一种基于离散数据从局部到全局的网络重构算法

徐翔, 朱承, 朱先强

Discrete data based local-to-global network reconstruction algorithm

Xu Xiang, Zhu Cheng, Zhu Xian-Qiang
PDF
HTML
导出引用
  • 网络的结构和功能彼此相互影响, 网络上的功能往往体现为网络上的动力学过程, 网络上的动力学过程通过网络中的行为表象数据进行体现. 因此, 根据网络上可观测的相关数据对网络结构进行重构将成为可能. 本文拟解决如何根据网络上可观测的离散数据还原网络拓扑结构的问题, 提出了在网络局部利用每一条离散数据对应节点的相似程度来推测节点间发生连边的可能性, 通过多条离散数据重构网络各个局部拓扑并将由多条数据得到的局部拓扑进行叠加, 最终重构出整个网络的全局拓扑结构的算法. 为了验证算法的可行性与准确性, 在小世界、无标度和随机网络中进行了网络重构实验, 通过在三种不同类型及不同规模的网络中进行网络重构实验可以看出, 网络重构算法在不同类型网络中的表现也不同, 且网络的平均度值也会影响网络重构算法对数据的要求. 为了验证算法的适用性, 对三个实际网络进行了网络重构实验, 结果显示算法能够适用实际较大规模网络的重构. 该算法具有很好的适用性和准确度, 适合不同类型网络的拓扑结构重构场景.
    The structure and the function of network interact with each other. The function of network is often reflected as the dynamic process on the network. The dynamic process on the network is reflected by the behavior data in the network. Therefore, it is possible to reconstruct the network structure according to the observed data. This paper aims to solve the problem of how to restore the network topology according to the observable discrete data on the network. In this paper, an algorithm to infer the possibility of edge connection between nodes is proposed by using the similarity degree of each node corresponding to each discrete datum, and by reconstructing each local topology of the network through multiple discrete data, and by superposing the local topology obtained from multiple data, the global topology of the whole network is reconstructed finally. The data in the network are generated by SIR (Susceptible Infective Removed) model with infection probability of 0.2 and recovery probability of 1. Each time, a single node is selected as the infected node, and the final infection state of the network is counted as a network datum. In order to verify the feasibility and accuracy of the algorithm, the network reconfiguration experiments are carried out in small world, scale-free and random networks. Through the network reconstruction experiments in the networks of three different types and different scales, we can see that the performances of network reconstruction algorithm in different types of networks are different, and the average degree of network will affect the requirements for data of the network reconstruction algorithm. In order to verify the applicability of the algorithm, network reconstruction experiments are carried out on three practical networks. The results show that the algorithm can be applied to the reconstruction of large-scale networks. In order to show the accuracy of the algorithm more intuitively, we analyze the network reconstruction error after each network reconstruction experiment. The experiment shows that with the gradual increase of network data, the network reconstruction error gradually decreases and finally approaches to 0. In a nutshell, the algorithm we proposed in this work has good applicability and accuracy, and is suitable for different types of network topology reconstructions.
      通信作者: 朱承, zhucheng@nudt.edu.cn
    • 基金项目: 国家自然科学基金(批准号: 71571186, 61703416)和湖南省研究生创新基金(批准号: CX20190041)资助的课题
      Corresponding author: Zhu Cheng, zhucheng@nudt.edu.cn
    • Funds: Project supported by the National Natural Science Foundation of China (Grant Nos. 71571186, 61703416) and the Postgraduate Innovation Project of Hunan Province, China (Grant No. CX20190041)
    [1]

    Martinez N D 1991 Ecol. Monogr. 61 367Google Scholar

    [2]

    Oh S W, Harris J A, Ng L 2014 Nature 508 207Google Scholar

    [3]

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

    [4]

    Faloutsos M, Faloutsos P, Faloutsos C 1999 Sigcomm. Comput. Commun. Rev. 29 251Google Scholar

    [5]

    Scott J 1994 Sociology 22 109

    [6]

    丁香园新型冠状病毒肺炎数据 https://ncov.dxy.cn/ncovh5/view/pneumonia?from=timeline&isappinstalled=0 [2020-11-16]

    Ding Xiang Yuan COVID-19 data https://ncov.dxy.cn/ncovh5/view/pneumonia?from=timeline&isappinstalled=0. [2020-11-16] (in Chinese)

    [7]

    Bongard J, Lipson H 2007 Proc. Natl. Acad. Sci. U.S.A. 104 9943Google Scholar

    [8]

    Sugihara G, May R, Ye H 2012 Science 338 496Google Scholar

    [9]

    Marbach D, Costello J C, Küffner R 2012 Nat. Methods 9 796Google Scholar

    [10]

    Wang W X, Lai Y C, Grebogi C 2016 Phys. Rep. 644 1Google Scholar

    [11]

    Casadiego J, Nitzan M, Hallerberg S, Timme M 2017 Nat. Commun. 8 1Google Scholar

    [12]

    Nitzan M, Casadiego J, Timme M 2017 Sci. Adv. 3 e1600396Google Scholar

    [13]

    Zhao H, Li L, Peng H, Xiao J, Yang Y, Zheng M 2017 Neurocomputing 219 5

    [14]

    Granger C W 1969 Econometrica 37 424Google Scholar

    [15]

    Runge J, Bathiany S, Bollt E 2019 Nat. Commun. 10 1Google Scholar

    [16]

    Maziarz M 2015 J. Phil. Econ. 8 86

    [17]

    Zhou D, Xiao Y, Zhang Y, Xu Z, Cai D 2013 Phys. Rev. Lett. 111 054102Google Scholar

    [18]

    Wang W X, Yang R, Lai Y C 2011 EPL 94 48006Google Scholar

    [19]

    Shen Z, Wang W X, Fan Y, Di Z, Lai Y C 2014 Nat. Commun. 5 1

    [20]

    Li L, Xu D, Peng H, Kurths J, Yang Y 2017 Sci. Rep. 7 1Google Scholar

    [21]

    Zhang Z, Chen Y, Mi Y, Hu G 2019 Phys. Rev. E 99 042311

    [22]

    Hempel S, Koseska A, Kurths J, Nikoloski Z 2011 Phys. Rev. Lett. 107 3214

    [23]

    Akaike H 1973 Information Theory and an Extension of the Maximum Likelihood Principle (New York: Springer) pp199−213

    [24]

    Donges J F, Zou Y, Marwan N, Kurths J 2009 EPL 87 48007Google Scholar

    [25]

    Stetter O, Battaglia D, Soriano J, Geisel T 2012 PloS Comput. Biol. 8 e1002653Google Scholar

    [26]

    Sun J, Bollt E M 2014 Physica D 267 49Google Scholar

    [27]

    Sun J, Taylor D, Bollt E M 2015 SIAM J. Appl. Dyn. Syst. 14 73Google Scholar

    [28]

    Sharma P, Bucci D J, Brahma S K, Varshney P K 2019 IEEE T. Netw. Sci. Eng. 7 562

    [29]

    张海峰, 王文旭 2020 物理学报 69 088906

    Zhang H F, Wang W X 2020 Acta Phys. Sin. 69 088906

    [30]

    张朝阳, 陈阳, 弭元元, 胡岗 2020 中国科学: 物理学 力学 天文学 1 3

    Zhang Z Y, Chen Y, Mi Y Y, Hu G 2020 Sci. Sin.: Phys. Mech. Astron. 1 3

    [31]

    Ma C, Zhang H F, Lai Y C 2017 Phys. Rev. E 96 022320

    [32]

    Wagner A 2000 Nat. Genet. 24 355Google Scholar

    [33]

    Levnajić Z 2012 arXiv: 1209.0219

    [34]

    Eagle N, Pentland A S, Lazer D 2009 Proc. Natl. Acad. Sci. U.S.A. 106 15274Google Scholar

    [35]

    Lü L, Jin C H, Zhou T 2009 Phys. Rev. E 80 046122Google Scholar

    [36]

    Clauset A, Moore C, Newman M E 2008 Nature 453 98Google Scholar

    [37]

    Taskar B, Wong M F, Abbeel P, Koller D 2004 NIPS 16 659

    [38]

    Liu W, Lü L 2010 EPL 89 58007Google Scholar

    [39]

    Ma C, Chen H S, Li X, Lai Y C, Zhang H F 2020 SIAM J. Appl. Dyn. Syst. 19 1Google Scholar

    [40]

    Pastor-Satorras R, Castellano C, Van Mieghem P, Vespignani A 2015 Rev. Mod. Phys. 87 120

    [41]

    Zhang H F, Xu F, Bao Z K, Ma C 2018 IEEE T. Circuits-I 66 4

    [42]

    Hempel S, Koseska A, Kurths J, Nikoloski Z 2011 Phys. Rev. Lett. 107 054101Google Scholar

    [43]

    Han X, Shen Z, Wang W X, Di Z 2015 Phys. Rev. Lett. 114 028701Google Scholar

    [44]

    Barabási A L, Albert R 1999 Science 286 509Google Scholar

    [45]

    Erdős P, Rényi A 1960 Publ. Math. Inst. Hung. Acad. Sci. 5 17

  • 图 1  网络初始二值数据矩阵

    Fig. 1.  Initial binary data matrix of the network.

    图 2  节点1和节点2的相同感染源数量

    Fig. 2.  The same number of infection sources in node 1 and node 2.

    图 3  子图重构过程

    Fig. 3.  Subgraph reconstruction process.

    图 4  子图叠加过程

    Fig. 4.  Subgraph superposition process.

    图 5  不同规模的WS小世界网络重构实验效果

    Fig. 5.  Experimental results of WS small world network reconstruction with different scales.

    图 6  不同规模的WS小世界网络重构误差分析

    Fig. 6.  Error analysis of WS small world network reconstruction with different scales.

    图 7  WS小世界网络不同平均度值对网络重构实验效果的影响

    Fig. 7.  Influence of different average degrees of WS small world network on network reconstruction experiment.

    图 8  不同规模的BA无标度网络重构实验效果

    Fig. 8.  Experimental results of BA scale-free network reconstruction with different scales.

    图 9  不同规模的BA小世界网络重构误差分析

    Fig. 9.  Error analysis of BA scale-free network reconstruction with different scales.

    图 10  BA无标度网络不同平均度值对网络重构实验效果的影响

    Fig. 10.  The influence of different average degree values of BA scale-free network on network reconstruction experiment.

    图 11  不同规模的ER随机网络重构实验效果

    Fig. 11.  Experimental results of ER random network reconstruction with different scales.

    图 12  不同规模的ER小世界网络重构误差分析

    Fig. 12.  Error analysis of ER random network reconstruction with different scales.

    图 13  ER随机网络不同平均度值对网络重构实验效果的影响

    Fig. 13.  Influence of different average degree of ER random network on network reconstruction experiment.

    图 14  三种不同网络在相同数据下的重构效果对比

    Fig. 14.  Comparison of reconstruction effects of three different networks under the same data.

    图 15  三个实际网络重构实验效果

    Fig. 15.  Experimental results of three practical network reconstruction.

    图 16  三个实际网络重构误差分析

    Fig. 16.  Error analysis of three practical network reconstruction.

    表 1  三类网络的基本拓扑特征

    Table 1.  Basic topological features of the three types of networks.

    WS networksNE$ \langle k\rangle $C$ \langle l\rangle $
    WS10010020040.0993.61
    WS20020040040.0784.17
    WS30030060040.0574.51
    WS40040080040.0524.74
    WS500500100040.0824.96
    WS600600120040.0625.12
    WS700700140040.0715.25
    WS800800160040.0795.43
    WS900900180040.0685.48
    WS10001000200040.0685.58
    BA networksNE$ \langle k\rangle $C$ \langle l\rangle $
    BA1001001963.920.1553.11
    BA2002003963.960.0753.41
    BA3003005963.970.0733.53
    BA4004007963.980.0683.62
    BA5005009963.980.0373.81
    BA60060011963.980.0443.77
    BA70070013963.980.0343.95
    BA80080015963.990.0233.93
    BA90090017963.990.0204.06
    BA1000100019963.990.0274.14
    ER networksNE$ \langle k\rangle $C$ \langle l\rangle $
    ER1001004879.740.1172.249
    ER200200205620.560.1032.004
    ER300300457930.650.1031.936
    ER400400793639.680.0991.917
    ER5005001228449.140.0981.909
    下载: 导出CSV

    表 2  三个实际网络的基本拓扑特征

    Table 2.  Basic topological characteristics of three practical networks.

    实际网络NE$\langle k \rangle$C$ \langle l \rangle $
    Euroroad117414172.4140.02018.371
    Minnesota264233032.5000.01735.349
    Power Grid494165942.6690.10718.989
    下载: 导出CSV
  • [1]

    Martinez N D 1991 Ecol. Monogr. 61 367Google Scholar

    [2]

    Oh S W, Harris J A, Ng L 2014 Nature 508 207Google Scholar

    [3]

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

    [4]

    Faloutsos M, Faloutsos P, Faloutsos C 1999 Sigcomm. Comput. Commun. Rev. 29 251Google Scholar

    [5]

    Scott J 1994 Sociology 22 109

    [6]

    丁香园新型冠状病毒肺炎数据 https://ncov.dxy.cn/ncovh5/view/pneumonia?from=timeline&isappinstalled=0 [2020-11-16]

    Ding Xiang Yuan COVID-19 data https://ncov.dxy.cn/ncovh5/view/pneumonia?from=timeline&isappinstalled=0. [2020-11-16] (in Chinese)

    [7]

    Bongard J, Lipson H 2007 Proc. Natl. Acad. Sci. U.S.A. 104 9943Google Scholar

    [8]

    Sugihara G, May R, Ye H 2012 Science 338 496Google Scholar

    [9]

    Marbach D, Costello J C, Küffner R 2012 Nat. Methods 9 796Google Scholar

    [10]

    Wang W X, Lai Y C, Grebogi C 2016 Phys. Rep. 644 1Google Scholar

    [11]

    Casadiego J, Nitzan M, Hallerberg S, Timme M 2017 Nat. Commun. 8 1Google Scholar

    [12]

    Nitzan M, Casadiego J, Timme M 2017 Sci. Adv. 3 e1600396Google Scholar

    [13]

    Zhao H, Li L, Peng H, Xiao J, Yang Y, Zheng M 2017 Neurocomputing 219 5

    [14]

    Granger C W 1969 Econometrica 37 424Google Scholar

    [15]

    Runge J, Bathiany S, Bollt E 2019 Nat. Commun. 10 1Google Scholar

    [16]

    Maziarz M 2015 J. Phil. Econ. 8 86

    [17]

    Zhou D, Xiao Y, Zhang Y, Xu Z, Cai D 2013 Phys. Rev. Lett. 111 054102Google Scholar

    [18]

    Wang W X, Yang R, Lai Y C 2011 EPL 94 48006Google Scholar

    [19]

    Shen Z, Wang W X, Fan Y, Di Z, Lai Y C 2014 Nat. Commun. 5 1

    [20]

    Li L, Xu D, Peng H, Kurths J, Yang Y 2017 Sci. Rep. 7 1Google Scholar

    [21]

    Zhang Z, Chen Y, Mi Y, Hu G 2019 Phys. Rev. E 99 042311

    [22]

    Hempel S, Koseska A, Kurths J, Nikoloski Z 2011 Phys. Rev. Lett. 107 3214

    [23]

    Akaike H 1973 Information Theory and an Extension of the Maximum Likelihood Principle (New York: Springer) pp199−213

    [24]

    Donges J F, Zou Y, Marwan N, Kurths J 2009 EPL 87 48007Google Scholar

    [25]

    Stetter O, Battaglia D, Soriano J, Geisel T 2012 PloS Comput. Biol. 8 e1002653Google Scholar

    [26]

    Sun J, Bollt E M 2014 Physica D 267 49Google Scholar

    [27]

    Sun J, Taylor D, Bollt E M 2015 SIAM J. Appl. Dyn. Syst. 14 73Google Scholar

    [28]

    Sharma P, Bucci D J, Brahma S K, Varshney P K 2019 IEEE T. Netw. Sci. Eng. 7 562

    [29]

    张海峰, 王文旭 2020 物理学报 69 088906

    Zhang H F, Wang W X 2020 Acta Phys. Sin. 69 088906

    [30]

    张朝阳, 陈阳, 弭元元, 胡岗 2020 中国科学: 物理学 力学 天文学 1 3

    Zhang Z Y, Chen Y, Mi Y Y, Hu G 2020 Sci. Sin.: Phys. Mech. Astron. 1 3

    [31]

    Ma C, Zhang H F, Lai Y C 2017 Phys. Rev. E 96 022320

    [32]

    Wagner A 2000 Nat. Genet. 24 355Google Scholar

    [33]

    Levnajić Z 2012 arXiv: 1209.0219

    [34]

    Eagle N, Pentland A S, Lazer D 2009 Proc. Natl. Acad. Sci. U.S.A. 106 15274Google Scholar

    [35]

    Lü L, Jin C H, Zhou T 2009 Phys. Rev. E 80 046122Google Scholar

    [36]

    Clauset A, Moore C, Newman M E 2008 Nature 453 98Google Scholar

    [37]

    Taskar B, Wong M F, Abbeel P, Koller D 2004 NIPS 16 659

    [38]

    Liu W, Lü L 2010 EPL 89 58007Google Scholar

    [39]

    Ma C, Chen H S, Li X, Lai Y C, Zhang H F 2020 SIAM J. Appl. Dyn. Syst. 19 1Google Scholar

    [40]

    Pastor-Satorras R, Castellano C, Van Mieghem P, Vespignani A 2015 Rev. Mod. Phys. 87 120

    [41]

    Zhang H F, Xu F, Bao Z K, Ma C 2018 IEEE T. Circuits-I 66 4

    [42]

    Hempel S, Koseska A, Kurths J, Nikoloski Z 2011 Phys. Rev. Lett. 107 054101Google Scholar

    [43]

    Han X, Shen Z, Wang W X, Di Z 2015 Phys. Rev. Lett. 114 028701Google Scholar

    [44]

    Barabási A L, Albert R 1999 Science 286 509Google Scholar

    [45]

    Erdős P, Rényi A 1960 Publ. Math. Inst. Hung. Acad. Sci. 5 17

  • [1] 张海峰, 王文旭. 复杂系统重构. 物理学报, 2020, 69(8): 088906. doi: 10.7498/aps.69.20200001
    [2] 孔江涛, 黄健, 龚建兴, 李尔玉. 基于复杂网络动力学模型的无向加权网络节点重要性评估. 物理学报, 2018, 67(9): 098901. doi: 10.7498/aps.67.20172295
    [3] 李钊, 郭燕慧, 徐国爱, 胡正名. 复杂网络中带有应急恢复机理的级联动力学分析. 物理学报, 2014, 63(15): 158901. doi: 10.7498/aps.63.158901
    [4] 李雨珊, 吕翎, 刘烨, 刘硕, 闫兵兵, 常欢, 周佳楠. 复杂网络时空混沌同步的Backstepping设计. 物理学报, 2013, 62(2): 020513. doi: 10.7498/aps.62.020513
    [5] 王辉, 韩江洪, 邓林, 程克勤. 基于移动社交网络的谣言传播动力学研究. 物理学报, 2013, 62(11): 110505. doi: 10.7498/aps.62.110505
    [6] 熊熙, 胡勇. 基于社交网络的观点传播动力学研究. 物理学报, 2012, 61(15): 150509. doi: 10.7498/aps.61.150509
    [7] 杨浦, 郑志刚. 基于动力学同步的复杂网络结构识别速度研究. 物理学报, 2012, 61(12): 120508. doi: 10.7498/aps.61.120508
    [8] 高忠科, 金宁德, 杨丹, 翟路生, 杜萌. 多元时间序列复杂网络流型动力学分析. 物理学报, 2012, 61(12): 120510. doi: 10.7498/aps.61.120510
    [9] 崔爱香, 傅彦, 尚明生, 陈端兵, 周涛. 复杂网络局部结构的涌现:共同邻居驱动网络演化. 物理学报, 2011, 60(3): 038901. doi: 10.7498/aps.60.038901
    [10] 李树彬, 吴建军, 高自友, 林勇, 傅白白. 基于复杂网络的交通拥堵与传播动力学分析. 物理学报, 2011, 60(5): 050701. doi: 10.7498/aps.60.050701
    [11] 陈卫东, 徐华, 郭琦. 国际石油价格复杂网络的动力学拓扑性质. 物理学报, 2010, 59(7): 4514-4523. doi: 10.7498/aps.59.4514
    [12] 陈华良, 刘忠信, 陈增强, 袁著祉. 复杂网络的一种加权路由策略研究. 物理学报, 2009, 58(9): 6068-6073. doi: 10.7498/aps.58.6068
    [13] 李涛, 裴文江, 王少平. 无标度复杂网络负载传输优化策略. 物理学报, 2009, 58(9): 5903-5910. doi: 10.7498/aps.58.5903
    [14] 吕翎, 张超. 一类节点结构互异的复杂网络的混沌同步. 物理学报, 2009, 58(3): 1462-1466. doi: 10.7498/aps.58.1462
    [15] 王丹, 于灏, 井元伟, 姜囡, 张嗣瀛. 基于感知流量算法的复杂网络拥塞问题研究. 物理学报, 2009, 58(10): 6802-6808. doi: 10.7498/aps.58.6802
    [16] 许 丹, 李 翔, 汪小帆. 复杂网络病毒传播的局域控制研究. 物理学报, 2007, 56(3): 1313-1317. doi: 10.7498/aps.56.1313
    [17] 翁文国, 倪顺江, 申世飞, 袁宏永. 复杂网络上灾害蔓延动力学研究. 物理学报, 2007, 56(4): 1938-1943. doi: 10.7498/aps.56.1938
    [18] 李 季, 汪秉宏, 蒋品群, 周 涛, 王文旭. 节点数加速增长的复杂网络生长模型. 物理学报, 2006, 55(8): 4051-4057. doi: 10.7498/aps.55.4051
    [19] 李剑锋, 张红东, 邱 枫, 杨玉良. 模拟囊泡形变动力学的新方法离散空间变分法. 物理学报, 2005, 54(9): 4000-4005. doi: 10.7498/aps.54.4000
    [20] 王宏霞, 何 晨. 细胞神经网络的动力学行为. 物理学报, 2003, 52(10): 2409-2414. doi: 10.7498/aps.52.2409
计量
  • 文章访问数:  3936
  • PDF下载量:  97
  • 被引次数: 0
出版历程
  • 收稿日期:  2020-10-22
  • 修回日期:  2020-11-15
  • 上网日期:  2021-04-21
  • 刊出日期:  2021-04-20

/

返回文章
返回