搜索

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): 120510. doi: 10.7498/aps.61.120510
    [8] 杨浦, 郑志刚. 基于动力学同步的复杂网络结构识别速度研究. 物理学报, 2012, 61(12): 120508. doi: 10.7498/aps.61.120508
    [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
计量
  • 文章访问数:  1452
  • PDF下载量:  57
  • 被引次数: 0
出版历程
  • 收稿日期:  2020-10-22
  • 修回日期:  2020-11-15
  • 上网日期:  2021-04-21
  • 刊出日期:  2021-04-20

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

  • 国防科技大学, 信息系统工程重点实验室, 长沙 410073
  • 通信作者: 朱承, zhucheng@nudt.edu.cn
    基金项目: 国家自然科学基金(批准号: 71571186, 61703416)和湖南省研究生创新基金(批准号: CX20190041)资助的课题

摘要: 网络的结构和功能彼此相互影响, 网络上的功能往往体现为网络上的动力学过程, 网络上的动力学过程通过网络中的行为表象数据进行体现. 因此, 根据网络上可观测的相关数据对网络结构进行重构将成为可能. 本文拟解决如何根据网络上可观测的离散数据还原网络拓扑结构的问题, 提出了在网络局部利用每一条离散数据对应节点的相似程度来推测节点间发生连边的可能性, 通过多条离散数据重构网络各个局部拓扑并将由多条数据得到的局部拓扑进行叠加, 最终重构出整个网络的全局拓扑结构的算法. 为了验证算法的可行性与准确性, 在小世界、无标度和随机网络中进行了网络重构实验, 通过在三种不同类型及不同规模的网络中进行网络重构实验可以看出, 网络重构算法在不同类型网络中的表现也不同, 且网络的平均度值也会影响网络重构算法对数据的要求. 为了验证算法的适用性, 对三个实际网络进行了网络重构实验, 结果显示算法能够适用实际较大规模网络的重构. 该算法具有很好的适用性和准确度, 适合不同类型网络的拓扑结构重构场景.

English Abstract

    • 网络作为复杂系统的抽象已经广泛存在于现实世界, 从生物界的食物网[1]到大脑中的脑网络[2]、现代社会中的电力网络[3]、Internet[4]、社交网络[5]等等. 网络中的节点代表系统中的实体要素, 网络中各节点间的连边表示系统中各实体之间的相互作用关系. 然而, 人们一般对现实中的复杂系统知之甚少, 不了解系统内部的相关结构, 例如, 生态系统中各个物种之间的相互影响关系以及大脑中各个部分之间的相互作用关系等. 虽然系统中各要素之间的作用关系较难获得, 但随着系统的逐渐演化, 与系统行为相关的演化数据会被保留下来. 例如, 在生态系统演化的过程中, 不同演化时期存在的物种种类和物种数量可以获得; 2019年末到2020年初爆发的新型冠状病毒在不同城市和国家的感染情况数据[6]也可以得到. 通过对系统演化过程中产生的相关数据进行分析和处理, 可以对系统中隐藏的结构和动态过程进行挖掘, 这类研究问题被称为动力学网络重构[7-12]. 在现实世界, 很多网络中的数据能够体现网络上的动态过程, 例如: 交通网络中的流量、车速, 社交网络中的点赞数、转发数等. 网络的结构具有自适应性质, 网络结构自适应辨识问题[13]对网络结构重构具有一定的帮助. 综上, 如何根据网络上可观测的相关数据对未知结构的网络进行拓扑重构是一个重要且有研究价值的问题.

      目前, 对网络拓扑进行重构的工作较为丰富, 包括格兰杰因果关系(Granger Causality)[14-17]方法, 通过因果推断来判断变量之间的关系, 该方法对成对变量具有较好的适用性, 变量数量达到三个或者以上时, 推断的结果可能会出现错误. 压缩感知(compress sensing)[10,18,19]方法通过将网络上的动力学过程转化成压缩感知方法能够处理的欠定线性系统, 利用可观测到的时间序列对网络的拓扑进行重构. 压缩感知被广泛应用于电子工程尤其是信号处理中, 用于获取和重构稀疏或可压缩的信号. 该方法的优势是通过获取少量的信号数据重构出原始信号. 除此之外, 相关性方法能够根据网络节点之间的相关性进行网络拓扑重构. 文献[20]针对网络噪音干扰问题提出了一种结合QR分解(QR decomposition)和压缩感知的方法对网络进行结构重构. 相关性方法在其他领域也有很多应用[21,22], 该方法的优点是简单快速, 适合大规模网络拓扑重构问题, 但对数据的数量和质量要求较高.

      在面对网络结构重构问题时, 一些工作基于信息论[23]进行研究. 与简单的利用相关系数作为节点相关性的依据相比, 与信息论相关的指标能更好地反映不同条件下节点之间的相关性程度. 常用的基于信息论的指标有互信息[24](mutual information)、传输熵[25](transfer entropy)和因果熵[26,27](causation entropy)等. 文献[28]利用传输熵对无线传感网的拓扑进行了推测, 但该网络的规模较小. 网络重构的方法还有很多, 文献[29,30]较为详细地综述了相关的方法.

      本文通过借鉴文献[31]中利用SIR模型产生网络数据的方法进行网络拓扑结构还原, 产生数据的具体方法将在第3节阐述. 通过利用产生的初始数据, 我们的贡献有以下几点: 第一, 与传统的利用相关性指标[32]进行节点相关性计算不同, 首先统计被相同感染节点同时感染的不同节点数量, 然后再统计任意两个节点同时被感染的数量, 综合考虑了疾病在节点间的传播过程以及网络中不同节点之间的相互作用, 更加全面地刻画了网络节点之间的相关性; 第二, 与基于时序数据网络重构[33,34]方法不同, 我们的方法只需要离散的数据, 即对数据之间的时间相关性没有要求, 较大程度降低了获取数据的难度; 第三, 使用了从局部到全局的结构重构方法, 充分利用了每条数据对网络结构的影响, 提高了网络拓扑重构的准确性且计算复杂度较低.

    • 网络重构问题根据对网络初始结构的了解程度可以分为两类: 一类为已知部分初始网络结构, 对剩余未知部分进行推理或预测, 这类问题一般被称为链路预测[35]问题; 另一类为对初始网络结构完全未知, 一般需要知道网络上的动力学过程或能够获取网络上的观测数据.

      针对网络结构部分已知的情况, 可以利用链路预测相关方法进行网络结构的重构, 典型的链路预测方法包括最大似然估计[36]和概率模型[37]等. 链路预测的思想是对给定的一个网络, 为网络中没有连边的节点对$ (x, y) $赋予一个得分值$ {S}_{xy} $, 对网络中所有没有连边的节点对的得分值按照从大到小排序, 排在最前面的节点对形成的连边概率最大. 链路预测的思想可以用于网络拓扑重构, 需要做的是尽可能保证每条链路预测准确性以及预测链路的完整性. 利用链路预测中的相似性[38]概念, 通过对相似节点进行判断从而获得相似节点间的连边关系.

      对网络进行重构有以下几点困难: 第一, 网络结构的复杂性, 实际中的很多网络具有节点数量多、连接关系复杂的结构特点; 第二, 网络各节点之间的交互关系一般为非线性; 第三, 关于网络动态过程的数据较难获得, 包括数据的数量和质量. 同时, 在获取网络数据过程中还会存在一定的干扰数据, 即噪声会对网络重构的精度产生影响; 第四, 实际存在的网络大多数为时序动态网络, 且存在双层甚至多层的结构, 因此如何对时序网络和多层网络结构进行重构[39]也是一个重要的问题.

    • 网络上的动力学过程有很多, 我们采取了经典的SIR疾病传播过程[40]来产生网络数据, 具体过程如下.

      在未知网络中任选一个节点作为感染节点, 设置疾病传播概率$ \beta =0.2 $, 节点恢复概率$ \mu =1 $, 一定时间之后, 统计网络中最终稳定状态下被感染节点的数量, 这一过程产生了网络的一条数据, 以此类推, 重复上述操作, 可以获得关于网络的多条数据信息. 文献[41]使用了和本文相似的数据形式, 不同的是该论文产生数据使用的动力学过程与本文不同, 且网络中节点的状态会以一定的概率相互转移, 即使用的是非终态数据.

      为了更加直观地表示网络数据并便于后续的相关计算, 将网络中被感染的节点状态设置为“1”, 未被感染的节点设置为“0”, 则可以得到网络初始二值数据矩阵, 数据格式如图1所示. 其中每一行代表不同的数据, 即不同的感染节点, 每一列表示网络中不同的节点. 从该数据矩阵可以看出, 不同数据之间相互独立, 不存在时间上的相关性, 即数据是离散的.

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

      Figure 1.  Initial binary data matrix of the network.

    • 为了更方便地介绍我们提出的基于离散数据的网络重构算法, 给出以下相关定义.

      定义1 二值数据矩阵

      给定一个图$ G=(V, E, S) $, V表示图中的节点集合, E表示图中的连边集合, S表示图中各节点的状态集合, 当节点j被第i次选取的感染源节点感染时, $ {S}_{ij}=1 $, 反之$ {S}_{ij}=0 $. 二值数据矩阵$ {{S}}_{M\times N}={{(S}_{ij})}_{M\times N} $, 其中M表示网络中数据的数量, N为网络节点数量.

      例如, 一个拥有16条数据8个节点的网络的二值数据矩阵可表示如下:

      ${{{S}}_{16 \times 8}} = \left[ {\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} 0\\ 1 \end{array}}&{\begin{array}{*{20}{c}} 0\\ 1 \end{array}}\\ {\begin{array}{*{20}{c}} 0\\ 1 \end{array}}&{\begin{array}{*{20}{c}} 0\\ 0 \end{array}} \end{array}}&{\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} 1\\ 1 \end{array}}&{\begin{array}{*{20}{c}} 0\\ 0 \end{array}}\\ {\begin{array}{*{20}{c}} 1\\ 1 \end{array}}&{\begin{array}{*{20}{c}} 1\\ 1 \end{array}} \end{array}}\\ {\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} 1\\ 0 \end{array}}&{\begin{array}{*{20}{c}} 0\\ 0 \end{array}}\\ {\begin{array}{*{20}{c}} 1\\ 0 \end{array}}&{\begin{array}{*{20}{c}} 0\\ 0 \end{array}} \end{array}}&{\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} 1\\ 1 \end{array}}&{\begin{array}{*{20}{c}} 0\\ 1 \end{array}}\\ {\begin{array}{*{20}{c}} 0\\ 1 \end{array}}&{\begin{array}{*{20}{c}} 1\\ 1 \end{array}} \end{array}} \end{array}}&{\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} 1\\ 1 \end{array}}&{\begin{array}{*{20}{c}} 0\\ 0 \end{array}}\\ {\begin{array}{*{20}{c}} 0\\ 0 \end{array}}&{\begin{array}{*{20}{c}} 1\\ 0 \end{array}} \end{array}}&{\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} 1\\ 0 \end{array}}&{\begin{array}{*{20}{c}} 1\\ 1 \end{array}}\\ {\begin{array}{*{20}{c}} 1\\ 1 \end{array}}&{\begin{array}{*{20}{c}} 1\\ 1 \end{array}} \end{array}}\\ {\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} 0\\ 0 \end{array}}&{\begin{array}{*{20}{c}} 1\\ 1 \end{array}}\\ {\begin{array}{*{20}{c}} 1\\ 0 \end{array}}&{\begin{array}{*{20}{c}} 0\\ 1 \end{array}} \end{array}}&{\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} 0\\ 0 \end{array}}&{\begin{array}{*{20}{c}} 0\\ 0 \end{array}}\\ {\begin{array}{*{20}{c}} 0\\ 1 \end{array}}&{\begin{array}{*{20}{c}} 1\\ 1 \end{array}} \end{array}} \end{array}}\\ {\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} 0\\ 1 \end{array}}&{\begin{array}{*{20}{c}} 0\\ 1 \end{array}}\\ {\begin{array}{*{20}{c}} 1\\ 0 \end{array}}&{\begin{array}{*{20}{c}} 1\\ 0 \end{array}} \end{array}}&{\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} 1\\ 1 \end{array}}&{\begin{array}{*{20}{c}} 0\\ 0 \end{array}}\\ {\begin{array}{*{20}{c}} 1\\ 0 \end{array}}&{\begin{array}{*{20}{c}} 0\\ 1 \end{array}} \end{array}}\\ {\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} 1\\ 1 \end{array}}&{\begin{array}{*{20}{c}} 0\\ 0 \end{array}}\\ {\begin{array}{*{20}{c}} 1\\ 1 \end{array}}&{\begin{array}{*{20}{c}} 0\\ 1 \end{array}} \end{array}}&{\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} 0\\ 1 \end{array}}&{\begin{array}{*{20}{c}} 1\\ 0 \end{array}}\\ {\begin{array}{*{20}{c}} 0\\ 0 \end{array}}&{\begin{array}{*{20}{c}} 1\\ 0 \end{array}} \end{array}} \end{array}}&{\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} 0\\ 0 \end{array}}&{\begin{array}{*{20}{c}} 1\\ 0 \end{array}}\\ {\begin{array}{*{20}{c}} 0\\ 0 \end{array}}&{\begin{array}{*{20}{c}} 1\\ 1 \end{array}} \end{array}}&{\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} 0\\ 1 \end{array}}&{\begin{array}{*{20}{c}} 1\\ 1 \end{array}}\\ {\begin{array}{*{20}{c}} 0\\ 1 \end{array}}&{\begin{array}{*{20}{c}} 1\\ 0 \end{array}} \end{array}}\\ {\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} 0\\ 0 \end{array}}&{\begin{array}{*{20}{c}} 0\\ 1 \end{array}}\\ {\begin{array}{*{20}{c}} 0\\ 1 \end{array}}&{\begin{array}{*{20}{c}} 1\\ 0 \end{array}} \end{array}}&{\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} 1\\ 0 \end{array}}&{\begin{array}{*{20}{c}} 0\\ 1 \end{array}}\\ {\begin{array}{*{20}{c}} 0\\ 1 \end{array}}&{\begin{array}{*{20}{c}} 0\\ 1 \end{array}} \end{array}} \end{array}} \end{array}} \right]$

      定义2 相同感染源数量

      给定一个图数据矩阵$ {{S}}_{M\times N} $, 定义网络中任意两节点的相同感染源数量为${n}_{kj}=\sum _{i=1}^{M}\times $$ {S}_{ik}{S}_{ij}, k\ne j$(当$ k=j $时规定$ {n}_{kj}=0 $), 其中$ {S}_{ik} $表示节点k在第i次选取感染源节点时的状态, $ {S}_{ij} $表示节点j在第i次选取感染源节点时的状态, M表示数据数量. 两节点的相同感染源数量越大, 则两节点间的相似性越高, 两节点间存在连边的概率越大, 反之亦然.例如, 图2$ {n}_{12}=4 $.

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

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

      定义3 相同感染源矩阵

      给定一个二值数据图$ G=(V, S) $和图数据矩阵$ {{S}}_{M\times N} $, 称${{A}}^{G}={\left({n}_{kj}\right)}_{N\times N},\; k\ne j$(当$ k=j $时规定$ {n}_{kj}=0 $)为相同感染源矩阵, $ {n}_{kj} $为节点k和节点j的相同感染源数量, N为二值数据图节点数量.

      例如, 图2所示数据矩阵对应的相同感染源矩阵为

      $ {{{A}}^G} = \left[ {\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} 0&4\\ 4&0 \end{array}}&{\begin{array}{*{20}{c}} 5&4\\ 3&0 \end{array}}\\ {\begin{array}{*{20}{c}} 5&3\\ 4&0 \end{array}}&{\begin{array}{*{20}{c}} 0&4\\ 4&0 \end{array}} \end{array}}&{\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} 3&4\\ 2&1 \end{array}}&{\begin{array}{*{20}{c}} 4&7\\ 2&4 \end{array}}\\ {\begin{array}{*{20}{c}} 2&7\\ 1&5 \end{array}}&{\begin{array}{*{20}{c}} 5&9\\ 5&4 \end{array}} \end{array}}\\ {\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} 3&2\\ 4&1 \end{array}}&{\begin{array}{*{20}{c}} 2&1\\ 7&5 \end{array}}\\ {\begin{array}{*{20}{c}} 4&2\\ 7&4 \end{array}}&{\begin{array}{*{20}{c}} 5&5\\ 9&4 \end{array}} \end{array}}&{\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} 0&0\\ 0&0 \end{array}}&{\begin{array}{*{20}{c}} 2&4\\ 3&5 \end{array}}\\ {\begin{array}{*{20}{c}} 2&3\\ 4&5 \end{array}}&{\begin{array}{*{20}{c}} 0&6\\ 6&0 \end{array}} \end{array}} \end{array}} \right].$

      定义4 二值数据子图

      给定一个二值数据图$ G=(V, S) $和图数据矩阵$ {{S}}_{M\times N} $, 针对任意数据i, 称节点集合${V}^{i}= $$ \left\{{v}_{j}\right|{S}_{ij}=1\}$中的节点构成的图为二值数据子图$ {G}^{i} $.

      例如, 由$ {{S}}_{16\times 8} $可以得到数据1对应的子图节点集合为

      $ {G}^{1}=\left({V}^{1},{S}^{1}\right)=\left(\left\{{v}_{3},{v}_{5},{v}_{7},{v}_{8}\right\},\left\{{1,1},{1,1}\right\}\right). $

      定义5 子图相同感染源矩阵

      给定一个二值数据子图$ {G}^{i} $, 称${{A}}^{i}={\left({n}_{kj}\right)}_{{N}_{i}\times {N}_{i}}, $$ k\ne j$(当$ k=j $时规定$ {n}_{kj}=0 $)为二值相同感染源矩阵, 其中$ k, j\in {V}^{i}, {N}_{i} $为第i次选取感染源节点时对应的二值数据子图节点数量.

      例如, 图2数据矩阵中数据1对应的子图相同感染源矩阵为

      ${{{A}}^1} = \left[ {\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} 0\\ 2 \end{array}}&{\begin{array}{*{20}{c}} 2\\ 0 \end{array}} \end{array}}&{\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} 5\\ 2 \end{array}}&{\begin{array}{*{20}{c}} 9\\ 4 \end{array}} \end{array}}\\ {\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} 5\\ 9 \end{array}}&{\begin{array}{*{20}{c}} 2\\ 4 \end{array}} \end{array}}&{\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} 0\\ 6 \end{array}}&{\begin{array}{*{20}{c}} 6\\ 0 \end{array}} \end{array}} \end{array}} \right].$

    • 给定任意数据i对应的子图相同感染源矩阵$ {{A}}^{i} $, 对矩阵中每一行进行最大共同数据数搜索, 对最大数据数处两节点进行连边, 得到重构子图${G}_{i} \!=\! ({V}^{i}, {E}^{i})$, ${E}^{i} \!=\! \bigcup\limits_{p, q\in {V}^{i}}\left\{\right(p, q\left)\right|{n}_{pq}= {\max}\left({n}_{pq}\right)\}$, 其中$ {V}^{i} $为子图节点集合, $ {E}^{i} $为子图连边集合, $ {n}_{pq} $为节点p和节点q的相同感染源数量; 当出现多个相同的最大共同数据数时, 依次选取其中的每个最大值对应的两节点进行连边, 对得到的不同子图进行度方差计算, 并将度方差值小的子网络作为最终子网的结构, 度方差计算公式为

      $ {\sigma }_{i}^{2}=\frac1{{N}_{i}}{\displaystyle\sum\limits_{j\in {V}^{i}}{({k}_{j}-{\bar{k}}_{i})}^{2}}, $

      其中$ {\sigma }_{i}^{2} $表示第i条数据对应子图的度方差值; $ {k}_{j} $表示子图中节点的度值; $ {\bar{k}}_{i} $表示子图的平均度值, $ {N}_{i} $为子图节点数量. 例如, 数据1对应的子图重构过程如图3所示.

      图  3  子图重构过程

      Figure 3.  Subgraph reconstruction process.

    • 对所有数据得到的重构子图$ {G}_{i} $进行叠加, 即对子图$ {G}_{i} $中的相同节点进行重叠, 最终得到图G的拓扑, 即$G=\left(V, E\right),\; V=\bigcup _{i=1}^{M}{V}^{i},\; E= \bigcup _{i=1}^{M}{E}^{i}$, 其中V表示图G的节点集合, E表示图G的连边集合, M表示数据数量, $ {E}^{i} $为第i条数据对应重构子图的连边集合, $ {V}^{i} $为第i条数据对应重构子图的节点集合, 子图叠加过程如图4所示. 对所有数据得到的子图进行叠加得到网络全局拓扑, 即得到网络的邻接矩阵A.

      图  4  子图叠加过程

      Figure 4.  Subgraph superposition process.

      子图叠加数学计算过程如下:

      $ \begin{split} {G}^{12}=\;&({(V}^{1}\cup {V}^{2}),{(E}^{1}\cup {E}^{2}))\\ =\;&(\left\{{3,5},{7,8}\right\}\cup \left\{{1,2},{3,5},8\right\},\{\left({1,2}\right),\\ &\left({1,8}\right),\left({3,8}\right),\left({5,8}\right)\}\cup \left\{\left({3,8}\right),\left({5,8}\right),\left({7,8}\right)\right\})\\ =\;&(\left\{{1,2},{3,5},{7,8}\right\},\{\left({1,2}\right),\left({1,8}\right),\\ &\left({3,8}\right),\left({5,8}\right),\left({7,8}\right)\}), \end{split} $

      网络重构算法流程如下所示:

      Algorithm Network Topology Reconstruction

      Input: Binary data matrix $ {{S}}_{M\times N} $

      1: ${n}_{kj}=\sum\nolimits_{i=1}^{M}{S}_{ik}{S}_{ij}$

      2: $ {{A}}^{{G}}={\left({n}_{kj}\right)}_{N\times N} $

      3: ${\rm{for}}\; i=1 \;{\rm{to}}\; M\;{\rm{do}}$

      4:  $ {V}^{i}=\left\{{v}_{j}\right|{S}_{ij}=1\} $

      5:  $ {G}^{i}\leftarrow {V}^{i} $

      6:  ${\rm{for}}\;{v}_{i}\;{\rm{in}}\;{G}^{i}$ ${\rm{do}}$

      7:    $ {{A}}^{i}={\left({n}_{kj}\right)}_{{N}_{i}\times {N}_{i}} $

      8:    if number of max($ {n}_{pq} $)=1

      9:  ${E}^{i}=\bigcup _{p, q\in {V}^{i}}\left\{\right(p, q\left)\right|{n}_{pq}= {\max}\left({n}_{pq}\right)\}$

      10:    else

      11:     ${E}^{i}=\bigcup _{p, q\in {V}^{i}}\left\{\left(p, q\right)|{\min}\left({\sigma }_{i}^{2}\right)\right\}$

      12:  ${\rm{end}}\;{\rm{for}}$

      13:  $ {G}_{i}=({V}^{i}, {E}^{i}) $

      14: ${\rm{end}}\;{\rm{for}}$

      15: $ V=\bigcup _{i=1}^{M}{V}^{i} $

      16: $ E=\bigcup _{i=1}^{M}{E}^{i} $

      17: $ G=\left(V, E\right) $

      Output: Network topology G

    • 采用真正例率(true positive rate, TPR)和假正例率(false positive rate, FPR)分别表示网络重构的准确率和误差, TPR指标越高, FPR指标越小则说明网络重构的效果越好[42-43]. TPR和FPR指标计算公式如下:

      $ {\rm{TPR}} = {{{\rm{TP}}}}/({{{\rm{TP}} + {\rm{FN}}}}), $

      $ {\rm{FPR}} = {{{\rm{FP}}}}/({{{\rm{TN}} + {\rm{FP}}}}), $

      其中TP(true positive), FP(false positive), TN(true negative)和FN(false negative)分别表示真正例数、假正例数、真反例数和假反例数.

    • 为了验证本文算法的适用性, 针对不同规模的WS小世界网络、BA无标度网络[44]和ER随机网络[45]进行了网络重构实验, 网络的相关拓扑属性如表1所列, 其中N表示网络节点数量, E表示网络连边数量, $ \langle k\rangle $表示网络的平均度, C表示网络的集聚系数, $ \langle l\rangle $表示网络的平均路径.

      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

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

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

    • 图5为不同规模的WS小世界网络重构实验效果. 由图5可以发现, 随着网络数据的增加, 不同节点规模的WS小世界网络重构效果也越来越好, 且最终都能够完全重构出网络的拓扑. 还可以发现, 随着网络规模的增加, 需要的网络数据量也随之增加, 但从最终达到平衡的数据数量来看, 需要的信息数量与网络节点呈线性变化, 即对网络数据数量的需求与网络节点数量是同一个数量级. 从对WS小世界网络的重构实验结果可以看出, 本文算法对网络拓扑还原具有较高的准确性, 能够适应不同规模的网络, 且对网络数据数量的要求不高.

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

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

      为更直观地反映算法的重构效果, 定义了多边重构误差$ {e}_{\rm{FP}} $和少边重构误差$ {e}_{\rm{FN}} $指标, 计算公式如下:

      $ {e}_{\rm{FP}}= {\rm{FP}}/{\rm{TP}}, $

      $ {e}_{\rm{FN}}= {\rm{FN}}/{\rm{TP}}. $

      图6所示, 在不同节点规模的WS小世界网络重构实验过程中, 随着实验数据的增加, 网络重构实验的多边重构误差$ {e}_{\rm{FP}} $和少边重构误差$ {e}_{\rm{FN}} $逐渐减小, 最终趋近于0, 该实验误差分析进一步说明了本文算法的准确性.

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

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

      为了研究网络平均度值对网络重构效果的影响, 对WS小世界网络, 分别对网络平均度值为4, 6和8(即$ \langle k\rangle $ = 4, $ \langle k\rangle $ = 6和$ \langle k\rangle $ = 8)的网络进行了网络重构实验, 实验结果如图7所示. 从图7可以看到, 随着网络平均度值的增加, 要达到相同的网络重构效果, 需要的网络数据量更多, 原因是网络的平均度值越大网络中各个节点的连边数量越多, 则网络整体的连边数量也随之增加, 所以需要更多的网络数据来重构网络. 从网络节点数量为200—600 (即WS200—WS600)的重构效果可以发现, 网络平均度值为$ \langle k\rangle $ = 6的重构效果在相同网络数据情况下的重构效果比网络平均度值为$ \langle k\rangle =4$ 的网络重构效果好, 原因可能是WS小世界网络具有较高的集聚性, 因此网络平均度值在一定范围内对网络数据的需求量较少, 即相同数量的网络数据能够很好地被节点及其邻居节点“利用”.

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

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

    • 图8可以看出, 与WS小世界网络类似, 随着网络数据的增加网络重构效果也越来越好. 图9展示了实验误差曲线, 总体上来说网络重构误差随着实验数据的增加逐渐减小. 从图10可以看出, 在相同网络数据的情况下, 网络平均度值越大, 网络的重构效果越差, 且平均度值越大网络重构需要的数据越大.

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

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

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

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

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

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

    • 图11展示了不同规模的ER随机网络重构效果, 相比同等规模的WS小世界和BA无标度网络, ER随机网络需要更多的网络数据. 图12展示了两种重构误差的变化情况, 可以发现, 两种重构误差变化的趋势基本一致, 误差随实验数据的增加逐渐减小. 除此之外, 对具有不同平均度值的ER随机网络进行网络重构实验, 发现网络重构的效果与网络的平均度值基本没有关系, 从图13可以发现三条曲线基本重合.

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

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

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

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

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

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

    • 为了更直观地比较不同网络重构效果, 同时对WS, BA和ER网络进行网络重构实验, 实验结果见图14. 从图14可以看出, 在相同网络数据下可以发现WS和BA网络的重构效果类似, ER网络则需要更多的网络数据.

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

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

    • 为了更好地说明本文算法的适用性, 选取了三个实际网络进行网络重构实验, 三个网络的具体属性数据如表2所列. 其中, Euroroad和Minnesota为公路网数据集, 相关数据可以在http://networkrepository.com/road.php上获取; Power Grid数据集由Duncan Watts和Steven Strogatz编制, 数据可在http://cdg.columbia.edu/cdg/datasets上获取.

      实际网络NE$\langle k \rangle$C$ \langle l \rangle $
      Euroroad117414172.4140.02018.371
      Minnesota264233032.5000.01735.349
      Power Grid494165942.6690.10718.989

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

      Table 2.  Basic topological characteristics of three practical networks.

      图15展示了三个实际网络的重构效果, 可以发现网络边数(节点)越多, 重构网络需要的数据越多, 随着使用数据的增加, 网络的重构效果也逐步提高. 图16展示了三个实际网络对应的重构误差变化曲线, 可以看出, 三个实际网络的重构误差随着数据量的增加都呈现下降趋势, 最终都趋近于0.

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

      Figure 15.  Experimental results of three practical network reconstruction.

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

      Figure 16.  Error analysis of three practical network reconstruction.

    • 针对网络结构完全未知, 网络上的动力学过程已知的网络结构重构问题, 提出了一种基于离散数据从局部到全局的网络重构算法. 通过在网络上模拟SIR疾病传播过程来产生网络数据, 利用产生的数据从局部还原到全局叠加, 最终重构出整个网络的拓扑. 我们提出的算法具有快速, 简单的优势, 且适用于不同网络类型. 为了验证算法的准确性和适用性, 在具有不同节点数量的WS, BA和ER网络上进行了仿真实验, 实验结果表明我们的方法能够准确地还原出不同规模大小的网络拓扑. 为了验算法的适用范围, 还对三个实际网络进行了重构实验, 由实验结果可以发现, 本文提出的算法同样可行. 目前我们研究的对象属于单层静态网络, 以后的工作可能会考虑如何对动态和多层网络进行拓扑重构.

参考文献 (45)

目录

    /

    返回文章
    返回