-
网络的结构和功能彼此相互影响, 网络上的功能往往体现为网络上的动力学过程, 网络上的动力学过程通过网络中的行为表象数据进行体现. 因此, 根据网络上可观测的相关数据对网络结构进行重构将成为可能. 本文拟解决如何根据网络上可观测的离散数据还原网络拓扑结构的问题, 提出了在网络局部利用每一条离散数据对应节点的相似程度来推测节点间发生连边的可能性, 通过多条离散数据重构网络各个局部拓扑并将由多条数据得到的局部拓扑进行叠加, 最终重构出整个网络的全局拓扑结构的算法. 为了验证算法的可行性与准确性, 在小世界、无标度和随机网络中进行了网络重构实验, 通过在三种不同类型及不同规模的网络中进行网络重构实验可以看出, 网络重构算法在不同类型网络中的表现也不同, 且网络的平均度值也会影响网络重构算法对数据的要求. 为了验证算法的适用性, 对三个实际网络进行了网络重构实验, 结果显示算法能够适用实际较大规模网络的重构. 该算法具有很好的适用性和准确度, 适合不同类型网络的拓扑结构重构场景.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.
-
Keywords:
- network reconstruction/
- complex networks/
- dynamics/
- discrete data
[1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] -
WS networks N E $ \langle k\rangle $ C $ \langle l\rangle $ WS100 100 200 4 0.099 3.61 WS200 200 400 4 0.078 4.17 WS300 300 600 4 0.057 4.51 WS400 400 800 4 0.052 4.74 WS500 500 1000 4 0.082 4.96 WS600 600 1200 4 0.062 5.12 WS700 700 1400 4 0.071 5.25 WS800 800 1600 4 0.079 5.43 WS900 900 1800 4 0.068 5.48 WS1000 1000 2000 4 0.068 5.58 BA networks N E $ \langle k\rangle $ C $ \langle l\rangle $ BA100 100 196 3.92 0.155 3.11 BA200 200 396 3.96 0.075 3.41 BA300 300 596 3.97 0.073 3.53 BA400 400 796 3.98 0.068 3.62 BA500 500 996 3.98 0.037 3.81 BA600 600 1196 3.98 0.044 3.77 BA700 700 1396 3.98 0.034 3.95 BA800 800 1596 3.99 0.023 3.93 BA900 900 1796 3.99 0.020 4.06 BA1000 1000 1996 3.99 0.027 4.14 ER networks N E $ \langle k\rangle $ C $ \langle l\rangle $ ER100 100 487 9.74 0.117 2.249 ER200 200 2056 20.56 0.103 2.004 ER300 300 4579 30.65 0.103 1.936 ER400 400 7936 39.68 0.099 1.917 ER500 500 12284 49.14 0.098 1.909 实际网络 N E $\langle k \rangle$ C $ \langle l \rangle $ Euroroad 1174 1417 2.414 0.020 18.371 Minnesota 2642 3303 2.500 0.017 35.349 Power Grid 4941 6594 2.669 0.107 18.989 -
[1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45]
计量
- 文章访问数:5318
- PDF下载量:116
- 被引次数:0