3.1 复杂网络上SIR疾病爆发阈值的预测研究

众多真实社会现象可描述为复杂网络上的传播动力学，近十年来引起了学者们的广泛关注 ^[1，2] 。这些实例包括接触网络上的流行病传播 ^[184] ，无线网络上的恶意病毒传播 ^[185] ，以及邮件网络中的电脑病毒传播 ^[186] 等。网络结构对传播动力学的影响很大，使得难以准确理解传播动力学。现有传播动力学研究可分为两个方面：理论研究（如非平衡临界现象 ^[187，188] ）和实际应用研究（如提出有效的免疫策略 ^[32，76] ）。其中，爆发阈值的研究是网络传播动力学的一个重要课题，具有重要的理论意义和现实意义。在理论方面，准确地判断爆发阈值，不仅给出了全局大规模疾病出现的临界条件 ^[188] ，还对研究临界现象有重要的影响 ^[187] ，包括确定临界指数 ^[189] 和Griffiths现象 ^[190] 。在实际应用方面，疾病爆发阈值可以刻画一个免疫策略的有效性 ^[76] ，有助于识别最优初始传播源 ^[163] 。

已有大量的理论研究来预测SIR疾病爆发阈值 ^[1] 。根据对网络结构信息的使用，这些熟知的理论方法可以分为以下三类。第一类是平均场类型（MFL）方法，这类方法只利用度分布来描述网络结构，包括异质平均场理论 ^[26，188] 、渗流理论 ^[31] 、边划分方法 ^{[32，191，192]} 和点对近似方法 ^[119，193] 。第二类是淬火平均场（QMF）方法，这类方法利用邻接矩阵来描述网络结构，包括离散马尔科夫链 ^[157] 和 N 缠绕方法 ^[194] 。第三类是动态信息传递（DMP）方法，这类方法利用非回溯矩阵来描述网络结构 ^[165] 。这三类方法已用于揭示网络的宏观特性（如度分布 ^[188] 和权重分布 ^[32] ）、中尺度特性（如度关联 ^[153] 和社区结构 ^[180] ）和微观特性（如节点度 ^[27] 和边权 ^[32] ）对传播所带来的影响。例如，当度分布异质性很强且网络规模趋于无穷时，不存在疾病爆发阈值 ^[153，188] 。

通常情况下，在理论方法中假设：①网络规模很大且稀疏 ^{[31，188，191]} ，②相邻节点之间不存在动力学关联性 ^[188] ，③相同类型的节点或连边没有差异性 ^[32，188] 。这三类理论方法往往只适用于某一类特殊网络结构，如无关联网络、高集群系数网络或社区网络。对于任意一个网络，这三类方法通常会给出不同的理论预测值。为了能揭示这三类方法预测得到的理论阈值之间的关系，以及哪个方法更接近真实阈值，第 3.1 节将系统地研究SIR疾病在无关联配置网络和 56 个真实网络上的情况。在无关联配置网络上，MFL方法和DMP方法所预测的理论阈值相同，都大于QMF方法所预测的理论阈值。然而，在真实网络上，这三类方法所预测的理论阈值之间的关系还未知。在 56 个真实网络中，DMP方法在大多数情况下更接近真实阈值，因为它考虑了所有网络结构信息和部分动力学关联性。由于邻接矩阵最大特征值的局域性，所以QMF方法很容易偏离真实阈值。对于特征向量局域于 K 核的网络、正关联网络和集群系数高的网络，MFL方法更接近真实阈值，尽管它只使用了度分布来描述网络结构。对于特征向量局域于中心节点的网络、负关联网络和集群系数低的网络，DMP方法在大多数情况下更接近真实阈值。这三类方法的准确性随模块度的变化并没有明显的规律，但在大多数情况下DMP方法最接近真实阈值。

3.1.1 理论爆发阈值

平均场类型（MFL）方法、淬火平均场（QMF）方法和动态信息传递（DMP）方法是预测疾病爆发阈值的三类常用理论方法。第3.1.1节将厘清这三类方法所预测的理论爆发阈值之间的关系。

平均场类型（MFL）方法包括异质平均场理论、渗流理论、边划分方法和点对近似方法。 MFL方法仅运用度分布来预测疾病爆发阈值，它还假设：①同类节点之间不存在差异性，②相邻节点状态相互独立，③网络无穷大。 MFL方法预测的疾病爆发阈值为其中，‹ k ›和‹ k ² ›分别表示度分布的一阶矩和二阶矩。尽管 能很好地预测无关联网络上的疾病爆发阈值，但真实网络往往具有错综复杂的结构，导致它无法准确预测其上的疾病爆发阈值 ^[27，34] 。

与MFL方法不同，淬火平均场（QMF）方法利用邻接矩阵 A 更加准确地描述了网络结构。离散马尔科夫链方法 ^[157] 、 N 缠绕方法 ^[194] ，以及其他利用邻接矩阵来描述网络结构的方法都可归类为QMF方法。然而，QMF仍然无法刻画相邻节点间的动力学关联性。利用QMF方法预测的疾病爆发阈值为 ＝ 1 /∧ _A [见等式（2-15）]。其中，∧ _A 是邻接矩阵的最大特征值 ^[194]

其中， 是一个列向量。值得注意的是利用等式（2-15）预测得到的疾病爆发阈值是SIS模型的真实阈值的一个下界 ^[194] 。由于SIR模型的爆发阈值大于SIS模型的爆发阈值，因此 也是SIR疾病传播的一个下界 ^[36] 。

动态信息传递（DMP）方法最先用于求解有限网络上的SIR疾病传播，最近被拓展于求解SIS疾病传播 ^{[165，195，196]} 。 DMP方法利用非回溯矩阵描述网络结构信息，以及相邻节点之间的部分动力学关联性。利用DMP方法所预测的疾病爆发阈值为 ＝ 1 /∧ _B [见等式（2-20）]。其中，非回溯矩阵的最大特征值 ^{[167，168，197，198]} 为

非回溯矩阵为

其中，1 表示一个 N × N 的单位矩阵， D 是一个对角元为节点度的对角矩阵，0 是一个 N × N 的空矩阵。从等式（3-1），（2-15）和（2-20）不难发现SIR疾病爆发阈值与边渗流模型的阈值相同 ^[198] 。由于SIR疾病传播模型是一个动态演化过程，复杂的网络结构与动力学关联性相互作用，使得疾病真实爆发阈值与边渗流模型的阈值有所不同 ^[176，177] 。因此，哪类方法能准确地预测疾病爆发阈值尤为重要。

当给定网络结构时，三类方法所得的预测值往往不同，但是仍然存在一定的关联性。比如， 小于 。为了厘清三个理论阈值之间的关系，假设 κ 是非回溯矩阵 M 的一个特征值， ω ＝ 是与之相对应的特征向量。其中， 和 分别表示 ω 的前 N 个元素和后 N 个元素。利用等式（3-4），可写成

在等式（3-5）的第一行左边乘以向量 ＝ （1，...，1），并联立等式（3-5）的第二行，可得

其中， ， d _i 表示节点 i 的度。对于无关联网络，节点→非回溯矩阵的中心性与它的度呈正相关 ^[167] ，即 。此时， 与 的值相同。

下面分析邻接矩阵和非回溯矩阵的最大特征值之间的关系。将等式（3-5）中的第二个等式代入第一个等式中，可得

在等式（3-7）的左右两端同时乘以 ，再除以 ，可得

利用矩阵理论 ^[199] ，可知矩阵 χ 的特征值 ε 和与其相对应的特征向量 满足 ，假设 ξ ₁ 和 ξ ₂ 分别是矩阵 A 和矩阵 1－ D 的特征值，即有 和 。因此，等式（3-8）可写成

由于 1－ D 的最小特征值为 1－ k _max ，因此

从而

值得注意的是， κ 和 ξ ₁ 分别是矩阵 B 和 A 的特征值，有

与文献 ^[35] 类似，并联立等式（3-12），可得 是树形网络上的疾病爆发真实阈值 λ _c 的一个下界。然而，真实网络具有高集群系数，导致它们并非树形结构。因此， 可能大于 λ _c 。

大多数真实网络度分布具有很强的异质性，比如度分布服从幂率形式 ， γ _D 表示度分布指数。在无关联无标度网络中，当 γ _D <3 时，‹ k ² ›发散，故 趋近于零；当 γ _D >3 时， 大于零，即存在疾病爆发阈值。利用QMF方法，疾病爆发阈值 由最大度 k _max 决定。当 γ _D >2.5， ；当 γ _D <2.5 时， ∝ ，不难得出 。对于无关联网络， ＝‹ k ›/（‹ k ² ›－‹ k ›），这与 相同。从等式（3-12）中发现 总是大于 。遗憾的是，在真实网络上，三种理论方法所得的疾病爆发阈值之间的关系还未知。

3.1.2 实验模拟验证

一个非常直观的理解是，若理论方法能准确地刻画网络结构信息，它便能准确地预测疾病爆发阈值。基于这一理解可推测DMP方法比QMF方法好，QMF方法比MFL方法好。下面通过预测SIR疾病在无关联配置网络和 56 个真实网络上的理论爆发阈值，来验证三类理论方法的准确性。用第 2.2.2 节中的相对波动方差来确定疾病爆发的真实阈值。

为了能细致地理解三类方法的准确性，根据邻接矩阵最大特征值所对应的特征向量局域性把网络分为两类 ^[1] ：①特征向量局域于中心节点的网络（LHNs），即邻接矩阵的最大特征值Λ _A 更接近于 ，其对应的特征向量分量局域于少许中心节点；②特征向量局域于 K 核的网络（LKNs），即邻接矩阵的最大特征值更接近于‹ k ² ›/‹ k ›，其对应的特征向量分量局域于少数具有高 K 核值的节点。

图3-1 系统地展示了在无关联配置网络上的SIR疾病传播的爆发阈值。假设网络大小为 N ，度分布服从幂率形式 p （ k ） ~ ， γ _D 表示度分布指数。为了使网络不存在度关联，令最小度 k _min ＝ 3，最大度 。不失一般性，在模拟过程中令 γ ＝ 1.0。图 3-1（a）和（b）分别给出了在度分布指数为 ν _D ＝ 2.1 和 ν _D ＝ 2.5 时，理论阈值 ， ， 和模拟阈值随网络大小 N 的变化。图 3-1（ c）和（d）分别给出了在 ν _D ＝ 2.1 和 ν _D ＝ 3.5 时， λ _c 与 、 和 的绝对误差随 N 的变化。对于方法 u ∈{MFL，QMF，DMP}，其预测的理论阈值与真实阈值的绝对误差为 。

根据文献 ^[161] 的定义，度指数为 γ _D ＝ 2.1 的网络属于LKNs类型，度指数为 γ _D ＝ 3.5 的网络属于LHNs类型。从图 3-1 中发现，相比于QMF方法所得的理论阈值，MFL方法和DMP方法所得的理论阈值更接近真实阈值。当 γ _D ＝ 2.1 时，MFL方法和DMP方法所预测的理论阈值与真实阈值之间的绝对误差都很小，并且绝对误差随 N 减小。当 γ _D ＝ 3.5 时，QMF方法的绝对误差随 N 的变化稳定到一个有限大小的值。需要注意的是，QMF方法预测疾病爆发阈值的准确性违背了直观认识，即它的准确性甚至比MFL方法还差。

下面讨论 ， 和 在 56 个真实网络上准确性。真实网络包括社会网络、应用网络、基础设施网络、计算机网络和蛋白质网络。为了简便，本节将有向网络抽象为无向网络，把权重网络抽象为无权网络。真实网络的信息见表 3-1 和表 3-2。

图3-2（a）展示了 、 和 预测疾病在 56 个真实网络上的爆发阈值。图中的每个形状表示理论阈值和对应的真实阈值。图 3-2（b）展示了在预测 56 个真实网络的爆发阈值时，三种理论阈值最接近 λ _c 的比例 f 。由于DMP方法考虑了网络结构的所有信息和部分动力学关联性，因此 有 40％的概率接近 λ _c 。仅使用度分布刻画网络结构的MFL方法有 36％的概率接近 λ _c ，而QMF却只有 25％的概率接于 λ _c 。总的来说， 在多数情况下接近 λ _c 。

MFL方法所得的预测值 容易偏离真实阈值，是因为它忽略了许多网络结构信息。 QMF方法的准确性违背直观认识，是因为最大特征值所对应的特征向量为局域特征向量，如图 3-3（ a）所示。图 3-3 展示了邻接矩阵和非回溯矩阵的参与反比率（IPR） ^[162，168] 对理论预测准确性的影响。图 3-3（a）和（b）分别展示了相对误差和绝对误差随参与反比率（IPR）的变化。图 3-3（b）的插入图展示了平均相对误差随IPR的变化。方法 u ∈{MFL，QMF，DMP}的相对误差计算公式为 。从图 3-3 中发现，理论阈值和真实阈值之间的绝对误差和相对误差都随IPR增加。因为IPR越大，最大特征值所对应的特征向量的分量越容易局域于中心节点或 K 核值大的节点 ^[161] ，导致QMF方法和DMP方法越容易偏离真实阈值。

注：56 个真实网络常用统计特性，包括网络大小N，边数E，最小度 ，最大度 ，平均度‹k›，度分布二阶矩‹k ² ›，度关联r，集群系数c和模块度Q。

现有研究表明网络具有不同类型的特征向量局域性 ^[161] 。因此，真实网络可分为特征向量局域于中心节点的网络（LHNs）和特征向量局域于 K 核的网络（ LKNs）。根据临界矩阵的最大特征值所对应的特征向量局域类型，在这 56 个真实网络中有 19 个LHNs类型的网络和 37 个LKNs类型的网络。图 3-4（d）展示了LHNs类型网络邻接矩阵的最大特征值 Λ _A 更接近 （方块），LKNs类型网络的 Λ _A 更接近‹ k ² ›/‹ k › （圆圈）。图 3-4 验证了三种理论方法预测真实网络疾病爆发阈值的准确性。图 3-4（ a）和（ b）分别展示了在LHNs类型的网络和LKNs类型的网络上，理论阈值 ， 和 随模拟阈值 λ _c 的变化。图 3-4（ c）给出了在LHNs类型的网络和LKNs类型的网络上， 、 和 更接近于 λ _c 的比例。对于LHNs类型网络，DMP方法更容易接近真实阈值，MFL方法最容易偏离真实阈值，这与直观认识一致，如图 3-4（a）和（c）所示。恰恰相反，在LKNs类型网络中，MFL方法比DMP方法更接近于真实阈值，如图 3-4（b）和（c）所示。

下面分析网络结构对理论预测准确性的影响，包括度关联 r 、集群系数 c 和模块度 Q 的影响。为了衡量指定方法的准确性，计算在区间（ x － Δx /2， x ＋ Δx /2）内的平均相对误差。其中， x ∈{ r ， c ， Q }，令 Δx ＝ 0.1。图 3-5 展示了度关联对不同理论阈值的相对误差的影响。图 3-5（a），（c）和（e）分别给出了理论阈值和模拟阈值的相对误差 随度关联 r 的变化。图 3-5（ b），（ d）和（ f）分别给出了理论阈值和模拟阈值的平均相对误差 随度关联 r 的变化。图 3-5 的每一列分别表示 56 个真实网络、LHNs类型网络和LKNs类型网络上的结果。

从图 3-5（a）和（b）中发现，DMP方法在绝大多数情况下相对误差最低。当 r <0 时，DMP方法最容易接近真实阈值，MFL方法最容易偏离真实阈值。当 r > 0 时，MFL方法最容易接近真实阈值，QMF方法最容易偏离真实阈值。对于LHNs类型网络，现象与 3-5（a）和（b）类似。对于LKNs类型网络，现象却有所不同。当 r <0时，DMP方法最接近真实阈值；当 r >0 时，MFL方法最接近真实阈值，QMF最容易偏离真实阈值。这一现象表明用MFL方法来预测度关联为正的网络的爆发阈值更准确，其余情况用DMP方法更好。

利用与图 3-5 类似的分析方法，图 3-6 研究集群系数 c 对理论阈值准确性的影响。图 3-6（a），（c）和（e）分别给出了理论阈值和模拟阈值的相对误差 随 c 的变化。图 3-6（ b），（ d）和（ f）分别给出理论阈值和模拟阈值的平均相对误差 随 c 的变化。图 3-6 中的每一列分别表示 56 个真实网络、LHNs类型网络和LKNs类型网络上的结果。从图 3-6（a）和（b）中发现：当 c <0.1 时，DMP方法相对误差最低，而MFL方法相对误差最大；当 c >0.1 时，MFL方法的相对误差最低，QMF相对误差最大。因此，当 c < 0.1时，用DMP方法能更准确地预测疾病爆发阈值；当 c > 0.1 时，用MFL方法能很准确地预测疾病爆发阈值。对于LHNs类型网络，现象与 3-6（a）和（b）类似[图 3-6（c）和（d）]。图 3-6（e）和（f）研究了三类方法对LKNs类型网络上阈值的准确性。当 c 较小时，DMP方法最接近真实阈值；当 c 较大时，MFL方法最接近真实阈值。

在图 3-7 中研究了模块度 Q 对三类方法准确性的影响。图 3-7（a），（c）和（e）分别给出了理论阈值和模拟阈值的相对误差 随 Q 的变化。图 3-7（b），（d）和（f）分别给出了理论阈值和模拟阈值的平均相对误差 随 Q 的变化。图 3-7 中的每一列分别表示 56 个真实网络、LHNs类型网络和LKNs类型网络上的结果。总体来说，三类方法的相对误差随 Q 增大。对于LHNs类型网络和LKNs类型网络，三类方法的准确性没有明显的规律，在大多数情况下DMP方法最容易接近真实阈值。