1.   引　言

网络作为复杂系统的抽象已经广泛存在于现实世界, 从生物界的食物网^[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]方法不同, 我们的方法只需要离散的数据, 即对数据之间的时间相关性没有要求, 较大程度降低了获取数据的难度; 第三, 使用了从局部到全局的结构重构方法, 充分利用了每条数据对网络结构的影响, 提高了网络拓扑重构的准确性且计算复杂度较低.

2.   网络重构问题描述

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

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

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

3.   基于离散数据的网络重构算法

3.1   网络数据

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

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

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

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

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

下载: 全尺寸图片 幻灯片

3.2   相关定义

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

定义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个节点的网络的二值数据矩阵可表示如下:

定义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的相同感染源数量

Fig. 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所示数据矩阵对应的相同感染源矩阵为

定义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对应的子图节点集合为

定义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对应的子图相同感染源矩阵为

3.3   子图重构

给定任意数据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}$表示第i条数据对应子图的度方差值; ${k}_{j}$表示子图中节点的度值; ${\bar{k}}_{i}$表示子图的平均度值, ${N}_{i}$为子图节点数量. 例如, 数据1对应的子图重构过程如图3所示.

图 3  子图重构过程

Fig. 3.  Subgraph reconstruction process.

下载: 全尺寸图片 幻灯片

3.4   子图叠加

对所有数据得到的重构子图${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  子图叠加过程

Fig. 4.  Subgraph superposition process.

下载: 全尺寸图片 幻灯片

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

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

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

4.   实验结果分析

4.1   网络重构指标

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

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

4.2   三种网络重构效果分析

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

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

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

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

下载: 导出CSV 

| 显示表格

4.2.1   WS小世界网络实验

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

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

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

下载: 全尺寸图片 幻灯片

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

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

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

Fig. 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小世界网络不同平均度值对网络重构实验效果的影响

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

下载: 全尺寸图片 幻灯片

4.2.2   BA无标度网络实验

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

图 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.

下载: 全尺寸图片 幻灯片

4.2.3   ER随机网络实验

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

图 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.

下载: 全尺寸图片 幻灯片

4.2.4   三种网络对比实验

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

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

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

下载: 全尺寸图片 幻灯片

4.3   三种实际网络重构效果分析

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

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

Table 2.  Basic topological characteristics of three practical networks.

实际网络	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

下载: 导出CSV 

| 显示表格

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

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

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

下载: 全尺寸图片 幻灯片

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

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

下载: 全尺寸图片 幻灯片

5.   总结与展望

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