[互联网]复杂网络基础4.ppt

《[互联网]复杂网络基础4.ppt》由会员分享，可在线阅读，更多相关《[互联网]复杂网络基础4.ppt（90页珍藏版）》请在三一文库上搜索。

1、复杂网络 复杂网络上的传播动力学 4.1 引言 复杂网络上的传播动力学问题是复杂网络研究的一个 重要方向。 主要研究社会和自然界中各种复杂网络的传播机理与 动力学行为以及对这些行为高效可行的控制方法。 复杂网络上的传播过程可以分为两类：不符合物质或 能量守恒的过程以及符合物质或能量守恒的过程。 本章首先介绍复杂网络上的流行病传播机理，接着介 绍复杂网络的免疫策略，然后介绍复杂网络上的舆论 传播和知识传播，最后介绍复杂网络上的数据包传递 机理和拥塞控制。 4.2复杂网络上的流行病传播 4.2.1流行病传播的基本模型 4.2.2均匀网中的流行病传播 4.2.3非均匀网中的流行病传播 4.2.4社团

2、网上的流行病传播 4.2.5有限规模无标度网络和广义无标度网络的传播阈值 4.2.6关联网络的传播阈值 4.2复杂网络上的流行病传播 流行病传播的速度很快，对社会的影响非常大，引起 全社会的极大关注，如网络病毒、人类社会中的 SARS、性病、艾滋病和谣言等等。 在复杂网络上，最近的理论和实验都表明流行病的传 播阈值与网络系统的尺寸(节点数)有着紧密联系。 在复杂网络传播动力学的研究中，传播阈值c是理论 和实验研究工作者特别关注的一个重要参量。对于尺 寸非常大的网络系统而言，如果流行病的传播概率大 于该传播阈值，那么受感染人数将占一个有限大小的 比例，即传染病会爆发且持续地存在；否则，受感染 人

3、数会呈指数衰减，其占总人数的比例将接近于0， 即传染病将会自然消失。 4.2复杂网络上的流行病传播 真实网络通常由有限的个体所组成，不符合系统尺寸 无限大的这个极限。因此，理论和数值研究结论与实 验结果将存在很大差异。 网络的结构对传染病的传播也会产生很大的影响。 在不同的网络模型上系统研究体系尺寸对传播阈值的 影响，对于探讨真实复杂系统中传播特性具有指导意 义。 本节首先介绍流行病传播的几个基本模型，然后介绍 不同结构性质的复杂网络上的传染病传播规律，接着 介绍具有社团结构的网络对传染病传播的影响，最后 简要介绍特殊无标度网络和关联网络的传播阈值。 4.2.1流行病传播的基本模型 需要采用不

4、同的数学模型来表征不同的传播规律，它 们是复杂网络传播动力学研究的基础。 传播模型中的每一类个体都处于同一种状态。基本状 态包括：易感状态(S)，即健康的状态，但有可能被 感染；感染状态(I)，即染病的状态，具有传染性；移 除状态(R)，即感染后被治愈并获得了免疫力或感染 后死亡的状态。处于移除状态的个体不具有传染性， 也不会再次被感染，即不再对相应动力学行为产生任 何影响，可以看作已经从系统中移除。 在真实系统中不同种类的传染病具有不同的传播方式 ， 研究它们的传播行为通常采用不同的传播模型。 4.2.1流行病传播的基本模型 1. SI模型 SI模型用来描述那些染病后不可能治愈的疾病，或对

5、于突然爆发尚缺乏有效控制的流行病，如黑死病及非 典型肺炎。 设s(t)和i(t)分别标记群体中个体在t时刻处于S态和I态 的密度，为传染概率，则SI模型的动力学模型可以 用如下的微分方程组描述： 4.2.1流行病传播的基本模型 2. SIS模型 SIS传播模型适合描述像感冒、淋病这类治愈后患者 不能获得免疫力的疾病；计算机病毒也属于这一类 型。 在SIS传播模型中，个体只存在两种状态：易感状态 (S)和感染状态(I)。感染个体为传染的源头，它通过 一定的概率将传染病传给易感个体。同时，感染个 体本身以一定的概率得以治愈。另一方面，易感人 群一旦被感染，就又成为新的感染源。SIS模型的感 染机制

6、可以描述如下： 4.2.1流行病传播的基本模型 假设t时刻系统中处于易感状态、感染状态的个体的 密度分别为s(t)和i(t)。当易感个体和感染个体充分混 合时，SIS模型的动力学行为可以描述为如下的微分 方程组 令有效传染率，该方程存在阈值c，当c 时，稳态解i(T)0；而当c时，稳态解i(T)0。 其中，T代表达到稳态所经历的时间。 4.2.1流行病传播的基本模型 3.SIR模型 SIR模型适合于两种情形：第一种情形是患者在治愈 后可以获得终生免疫力，如腮腺炎、麻疹及天花等； 第二种情形是患者几乎不可避免走向死亡，如艾滋 病。 在SIR模型中，感染个体不再变为易感个体而是以概 率变为免疫个体

7、(处于移除状态)。由此，SIR模型的 感染机制可以描述如下： 假设t时刻系统中处于易感状态、感染状态和移除状 态的个体的密度分别为s(t)、i(t)和r(t)。当易感个体和 感染个体充分混合时，SIR模型的动力学行为可以描 述为如下的微分方程组： 4.2.1流行病传播的基本模型 随着时间的推移，上述模型中的感染个体将逐渐增加。 但是，经过充分长的时间后，因为易感个体的不足使得 感染个体也开始减少，直至感染人数变为0，传染过程结 束。 因此，SIR模型在稳态时刻tT的传染密度r(T)和有效传 染率存在着一一对应的关系，且r(T)可以用来测量传染 的有效率。 4.2.1流行病传播的基本模型 同样，

8、SIR模型也存在一个阈值c，当c时，感染 无法扩散出去；而当c时，传染爆发且是全局的 ，系统中所有个体都处于移除状态，而感染个体的数 目为零。 由此可见，SIR模型和SIS模型的主要区别在于：SIS 的终态为稳定态(包括震荡态和不动点)，低于临界阈 值时终态为0；SIR的终态为无感染态，低于临界阈 值时总感染个体的密度为0。 4.2.1流行病传播的基本模型 4. SIRS模型 SIRS模型适合描述免疫期有限或者说免疫能力有限 的疾病。 与SIR模型不同的是，在SIRS模型中，处于移除状态 的个体(治愈后具有免疫力)还会以概率失去免疫 力。 当易感个体和感染个体充分混合时，SIRS模型的动 力学

9、行为可以描述为如下的微分方程组： 4.2.1流行病传播的基本模型 4. SEIR模型 SEIR模型适合于描述具有潜伏态的疾病，如季节性 的感冒。 易感个体与感染个体接触后先以一定概率变为潜伏 态(E)，然后再以一定概率变为感染态。SEIR模型 的感染机制可以描述如下： 假设t时刻系统中处于易感状态、潜伏状态、感染状 态和移除状态的个体的密度分别为s(t)、e(t)、i(t)和 r(t)。 4.2.1流行病传播的基本模型 SIRS模型的动力学行为可描述为如下的微分方程组： 4.2.2均匀网络中的流行病传播 按照度分布，复杂网络可以分为均匀网络和非均匀网 网络。 均匀网的度分布范围不大，在某一平均

10、值附近且度分 布指数衰减，如随机网络与小世界网络。 对于均匀网络，其传播动力学通常可以由平均场或均 匀混合方法给出。 本小节介绍均匀网络中的流行病传播规律，分别基于 SIS和SIR两种模型加以讨论。 4.2.2均匀网络中的流行病传播 1 基于SIS模型的情形 均匀网络中每个节点的度近似等于网络的平均度，即 kk。 对于SIS模型来说，在每一个时间步，如果网络中易感 个体至少和一个感染个体相连，则它被感染的概率为 ；同时，感染个体被治愈变为易感个体的概率为。 为了便于研究，这里对SIS模型作了两个假设：(1)均 匀混合假设：有效传染率与系统中处于感染状态的个 体的密度(t)成正比，即和都是常数。

11、(2)假设病毒 的时间尺度远远小于个体的生命周期，从而不考虑个 体的出生和自然死亡。令有效传染率(或叫有效传播率 )，它是一个非常重要的参量。 4.2.2均匀网络中的流行病传播 均匀网络中存在一个传播阈值c。 当有效传播率大于c时，感染个体能够将病毒传播 扩散，并使得整个网络中感染个体的总数最终稳定于 某一平衡状态，网络此时处于激活相态(active phase) ； 当有效传播率小于c时，感染个体的数量呈指数衰 减，无法大范围传播，网络此时处于吸收相态 (absorbing phase)。 所以在均匀网络中，存在一个正的传播阈值以将激活 相态和吸收相态明确地分隔开。 4.2.2均匀网络中的流

12、行病传播 不失一般性，令1(这种做法只是改变演化时间的 尺度)，利用平均场理论，均匀网络中被感染个体的 密度随时间的演化满足如下方程： 式中第一项表示感染个体以单位速率减少(因为假设 概率1)，第二项表示单个感染个体产生的新感染 个体的平均密度，它与有效传播率、节点(个体)的平 均度k及感染节点与易感节点连接的概率(t)1- (t)成正比。 式中，为感染个体的稳态密度。可以解得，均匀网 络流行病传播的阈值为： 4.2.2均匀网络中的流行病传播 而且满足 由此可见，传播阈值与平均度成反比。这很好理解， 因为接触的人越多，被感染的几率就越大，故降低平 均度是控制传染病传播的一个有效手段。 【例4.

13、1】用Matlab程序产生连接概率为p=0.1的含 100个节点ER随机网络，绘制网络及其度分布，分 析其均匀性，并计算其传播阈值。 由图4.1(b)可见，ER随机网络的度分布在10附近， 是一种均匀网络，计算得到其平均度为kpN 10，所以根据式 可知其传播阈值为： 图4.1 100个节点的ER随机网络及其度分布 (a)ER随机网络；(b)度分布 4.2.2均匀网络中的流行病传播 2.基于SIR模型的情形 对于SIR模型来说，处于易感状态、感染状态和移除 状态的个体的密度s(t)、i(t)和r(t)满足如下约束条件： 同样令，1(这种做法只是改变演化时间 的尺度)，在与SIS模型相同的假设条

14、件下，易感个 体、感染个体和免疫个体(处于移除状态的个体)的密 度满足： 不同于SIS模型，这里传染效率是以最终感染人口 r(t趋于无穷大时r(t)的值)来衡量的。 4.2.2均匀网络中的流行病传播 当c时，r在非常大的人口极限下为无穷小；而当 c时，疾病传播并感染有限比例的人群。在初始条 件r(0)0与s(0)1下，由上式容易得到： 将此结果与约束条件式相结合，可得到总感染人数满 足下列自治方程： 为了得到非零解，必须满足下列条件： 这个条件等价于限制c，其阈值在这个特殊情形下 取ck-1。在c处进行泰勒展开，可得传染效 率为： 上面两种模型讨论可见：对于均匀网络，有效传染率 存在一个大于零

15、的临界值，当有效传染率大于传播阈 值时，疾病可以在网络中传播，并可以持久的存在， 当有效传染率小于传播阈值，疾病则在网络中消亡。 4.2.3 非均匀网中的流行病传播 在无标度网络中，无论流行病的传染性是多么弱，流 行病仍然能够爆发并且持续的存在。 在无标度网络中，由于度分布满足幂律分布，一个随 机选取的节点倾向于连接关键节点或连接度大的节点 ，因此度大的节点就容易感染，然后作为种子去感染 其他人，从而导致比均匀网络上更快的流行病传播。 为了刻画网络拓扑对流行病传播的影响，通常将节点 按照度来分组，相同度的节点成为一组。 本小节分别基于SIS模型和SIR模型两种情形介绍非 均匀网络中的流行病传播

16、规律。 4.2.3 非均匀网中的流行病传播 1 基于SIS模型的情形 设k(t)表示t时刻度为k的节点组中感染节点的密度， 则它满足如下微分方程： 式中第一项为湮灭项，感染群体以单位速率减少(假 设概率1)；第二项为产生项，它正比于有效传播 率、易感人群的密度1-k(t)、节点的度k以及任意邻 居被感染的概率。其中，任意邻居被感染的概率记作 (t)，它表示从一个度为k的节点连到度为任意k 的节点的联合概率P(k|k)k(t)的平均。从而上式可重 新描述为： 4.2.3 非均匀网中的流行病传播 设k为度为k的节点组中感染个体的稳态密度。显然， k只是的函数，因而稳态时相应地概率也变为的隐 函数。

17、利用稳态条件 可得： (*) 对于非关联网络，概率P(kk)满足： 则()可以写成如下自治方程： 利用上式，容易求得()，再代入(*)式可以解得k。 最终的感染个体稳态密度则可由下式估算： 另外，由自治方程可得： (*) 4.2.3 非均匀网中的流行病传播 显然，该式存在一个平凡解()0。如果要使该方 程存在一个非平凡解，必须满足： 即 于是，可求得非均匀网上SIS传播模型的阈值为： 对该阈值可理解如下：当c，若(*)式中()0 ，则由()0可知： 故式(*)的第二项肯定大于0，故当c时只有() 0才能使( * )式成立。所以，只有当c时，才 能由第二项得到不为0的()。 4.2.3 非均匀网

18、中的流行病传播 对于规模无限大的具有度分布P(k)k-(3)的网络 ，k2=，对应的c=0。 由此可见，在无标度网络中，无论传染概率多么小， 流行病都能持久存在，这个结果很好地解释了为什么 病毒与舆论可以在Internet与社会网络中传播的如此 快。 4.2.3 非均匀网中的流行病传播 2. 基于SIR模型的情形 假设一个度为k的节点组中处于易感状态、感染状态 和移除状态的个体的密度分别表示为sk(t)、ik(t)和rk(t) ，则它们满足约束关系： 与SIS模型分析类似，令 ，可以得到下列动力学演化方程： 4.2.3 非均匀网中的流行病传播 上述方程组初始条件为rk(0)=0、ik(0)=i

19、0和sk(0)=1-i0 。在极限i00时，我们可取ik(0)0，sk(0)1。在 该近似条件下，由演化方程的第一个方程可得： 其中， 为如下的辅助函数(考虑演化方程的第三个方 程)： 其导数可简化为： 由此我们得到了关于 的一个自治方程，它在给定 的P(k)条件下可以求解。一旦得到 ，就可以得到 ，从而由 可得： 4.2.3 非均匀网中的流行病传播 由于 得到 ，从而可以得到关于 的 自治方程： 为了得到非平凡解(非零解)，必须满足如下条件： 于是 从而得到阈值为 这个结果与SIS模型完全相同。 4.2.3 非均匀网中的流行病传播 【例4.2】已知BA无标度网络在迭代次数趋向无穷大 时的度分

20、布特性P(k)=2m2k-3，其中m为BA网络每次 迭代增加的边数。基于SIS传播模型，求BA网络的感 染个体稳态密度与有效传染率的关系，并说明其 传播阈值为0。 解：根据BA无标度网络的度分布，可以求得： 可得： 由此求得()的非平凡解 4.2.3 非均匀网中的流行病传播 可求得感染个体的稳态密度为： 可求得感染个体的稳态密度与有效传染率的关系 ： 由上式可见，当且仅当=0时=0，意味着BA网络的 传播阈值c=0。 在SIS传播模型下，比较在相同平均度条件下WS小 世界网络与BA无标度网络的传播规律(传染率和感 染个体的稳态密度的关系)，如下图4.2所示。 4.2.3 非均匀网中的流行病传播

21、 在图4.2中，BA无标度网络的参数m=3，其平均度为 2m等于6，取WS小世界网络的参数k=6。可见， BA网络的传染率连续而平滑地过渡到0，说明无标度 网络不存在正传播阈值。对于BA网络，只要传染率大 于0，病毒都能传播并最终维持在一个稳定态，这也反 映了BA网络对病毒传播的脆弱性。 图4.2 WS小世界网络和BA无标度网络的传播规律比较 4.2.4 社团网上的流行病传播 社团结构一般出现在社会网络中，社团可以由同事、 朋友、同学或俱乐部成员等组成。在同一个社团内， 各成员联系紧密；相反，在不同社团之间则联系较 少。社团网络的结构示意图如图4.3所示。社团结构 的存在必然影响流行病的传播。

22、本小节重点探讨静态 社团结构对流行病传播的影响。 图4.3 含三个社团的社团网络结构示意图(社团内实线连接，社团间虚线连接) 4.2.4 社团网上的流行病传播 1.社团网络模型 社会网络通常具备高的集聚系数，社团内的连线密度 高，而社团间的连线密度低。假设我们将产生一个含 有N个节点、m个社团的社团网，提出如下简单方法 来构造社团网络： 步骤1：初始化。将N个节点随机分成m个组，每组 内的节点数为ni(i=1，2，m)，即 。 步骤2：社团内连线。每个组内的节点间以概率p连 线，从而组i内的连线数为 。 步骤3：社团间连线。任意两个组间的节点间以概率 q连线，从而组i和组j间的连线数为 。 通

23、过上述构造方法，最终得到的网络总边数为： 4.2.4 社团网上的流行病传播 令序参量=pq表示社团化的程度，则对于社团网 络应该有。如果=1，则上述方法得到的网络 将退化为一般的随机网络。如果给定总边数M、总节 点数N及社团划分方案和序参量，则概率p和q可由 下式给定： 4.2.4 社团网上的流行病传播 2社团网络上的流行病传播 用SIS模型来讨论流行病在社团网中的传播规律。 假定易感个体以概率与每个周围的感染个体接触。 若节点vj处于易感状态且有kj个邻居，它们中有kinf个 处于感染状态，则在每个时间步，节点vj将以概率 变 为感染状态。 同时每个感染节点以概率变为易感状态。 同前面的讨论

24、一样，为简单起见，这里令=， =1。 假定初始时有一粒种子，则它的每个邻居将以的概 率被感染，然后再感染它们的邻居。一定时间后，感 染达到稳态。 4.2.4 社团网上的流行病传播 对于c，稳态为0；而对于c，稳态为非零。 由于社团网络的非均匀结构，最终的状态依赖于选取 的种子及网络构型，因此有意义的结果必须为对各种 网络构型及各种初始条件的平均。 对具有的社团网，当较小时，传播会限制在 种子所在的社团内。 从统计意义上看，可以认为种子被均匀选取在每个社 团。对于每个特定的社团i，其阈值c(i)由其平均连线 数决定。当社团间的连线远小于社团内的连线时，有 且此关系对所有的种子成立。整个系统的c为

25、不同构 型及不同实现的平均，即对不同的种子平均，因此c 与p间的定量关系为c1p。 4.2.4 社团网上的流行病传播 其中a为一常数。因此c与M成反比。对于给定的M ，上式可被写为： 这就是c对社团程度的依赖关系。 随着社团度的降低，流行病的传播阈值将增加并在随 机网时达到极大值。 换句话说，流行病在随机网上比在社团网上更不容易 爆发。 通过前面的讨论，还可以得到一个结论：传染病本身 的动力学性质和个体所在的网络结构共同决定了流行 病的传染行为和传染过程。 4.2.5 有限规模无标度网络和广义无标度网 络的传播阈值 1 有限规模无标度网络的传播阈值 无限规模无标度网络的传播阈值为0完全是由于其

26、 k2=之故。而对于有限规模的无标度网络来说， 其度的取值范围是有限的，假设其最大度为kmax，该 值取决于节点总数N，于是根据其度分布规律可以求 出一个有限的k2值。 通过一个具有指数截止度分布的无标度网络进行分析 。假设度分布为： 其中，指数满足23，kc为截止度(类似于截止 频率)，A为归一化因子，满足： 4.2.5 有限规模无标度网络和广义无标度网 络的传播阈值 该度分布能保证k2为有限值。Pastor-Satorras和 Vespignani推导了其在SIS传播模型下对应的非零传 播阈值。可得： 这里m为网络中的最小度。若令 为非完整积分的Gamma函数，则上式的结果可写为 () 而

27、指数截止度分布的平均度为： 4.2.5 有限规模无标度网络和广义无标度网 络的传播阈值 为了在相同的平均度条件下比较有限规模无标度网络 和均匀网络传播阈值，我们可得到具有上式的平均度 的均匀网络的传播阈值为： 得到两种网络的传播阈值比值为： 下面来看当kc比较大时的近似比值。当kc比较大时， 对于23，对()式进行泰勒展开保留主要项，可 得： 4.2.5 有限规模无标度网络和广义无标度网 络的传播阈值 由上式可见，随着截止度kc的逐渐增加，传播阈值将 趋于0。在kc比较大时，指数截止度分布的平均度( 2)基本上固定为： 于是 可以得到当kc较大时两种网络的传播阈值近似为： 为了更形象地对比均匀

28、网络和有限规模无标度网络的 传播阈值，图4.4给出在各种指数条件下传播阈值比 值随着截止度kc的变化曲线 4.2.5 有限规模无标度网络和广义无标度网 络的传播阈值 从图中可以看出，对于2.5的情况，即使取相对较小的kc，有限规模无标 度网络的传播阈值约为均匀网络中的110。这说明有限规模无标度网络的 传播阈值比均匀网络的传播阈值要小得多，并且当kc增大或者网络规模趋于 无穷大，传播阈值仍会趋于0。所以，有限规模无标度网络对流行病传播还 是有脆弱性的。最后，值得指出的是，那些在SIS模型下得到的传播阈值结 论在SIR模型下都是成立的。这两种不同的传染过程并没有影响均匀网络和 非均匀网络中的病毒

29、传播传播阈值特性。 2.5 2.2 2.8 100 10-1 10-2 102103104 kc/m c (kc)/ cH 图4.4 具有相同平均度的均匀网络和有限规模无标度网络的传播阈值比值随kc/m的变化曲线 4.2.5 有限规模无标度网络和广义无标度网 络的传播阈值 2 广义无标度网络的传播阈值 考虑一类具有可变幂律指数的无标度网络，通常称 之为广义无标度网络(generalized scale-free network)，其度分布可以用如下的标准函数来表征： 其中，m为网络的最小度。当23时，上式就是 一个普通意义上的无标度网络，是非均匀网络，其传 播阈值c0。而当3时，可直接证明传播

30、阈值为 ： 特别地，当4时，广义无标度网络的传播阈值与 指数网络(即均匀网络，如小世网络、随机图等)几乎 没有差别。 4.2.6 关联网络的传播阈值 用条件概率P(k|k)来表示度为k的节点与度为k的节 点相连接的概率。如果这一条件概率独立于k，则退 化到节点连接为非关联的情形。假设网络度分布P(k) 和条件概率P(k|k)满足规范化和平衡条件，即 其中， 表示两个度分别为k和k的节点相连的联合 概率， =1(k=k)； =0(kk)。定义矩阵： 4.2.6 关联网络的传播阈值 可以求得，关联网络的传播阈值为： 其中max为矩阵C的最大特征值。对于无关联网络， C只有唯一的特征值 在考虑网络的

31、关联程度时，复杂网络的传播阈值由矩 阵C的特征值决定。 关联网络中的病毒传播范围比相同的度分布下非关联 网络的传播范围小。 在有限的关联网络中，传播阈值相比非关联网络要更 大一些，这说明关联网络表现出比非关联网络更强的 抵抗病毒传播的鲁棒性。 4.3 复杂网络上的免疫策略 无标度网络是很容易受到病毒感染而导致病毒流行的 ，因此选择合适的免疫策略显得非常重要。 人们针对免疫策略作了较多的研究，通常根据节点在 网络中的地位(例如以节点的度来衡量)来关注节点的 选择。 下面简要介绍复杂网络的三种免疫策略：随机免疫、 目标免疫和熟人免疫。 4.3.1 随机免疫 4.3.2 目标免疫 4.3.3 熟人免

32、疫 4.3.1 随机免疫 随机免疫完全随机地选取网络中的一部分节点进行免 疫。 免疫节点不会再被感染，所以它们不会再影响它们的 邻居。 针对均匀网络，容易得出随机免疫的免疫临界值为： 对于无标度网络来说，推导，可以得到此时随机免疫 的免疫临界值gc为 显然，随着网络规模的无限增长，无标度网络的k2 ，其传播阈值c趋于0，而免疫临界值gc趋于1 。 这表明，如果对于无标度网络采取随机免疫策略，则 需要对网络几乎所有节点都实施免疫才能保证最终消 灭病毒传染。 4.3.2 目标免疫 目标免疫根据无标度网络的不均匀特性，选取少量度 最大的节点进行免疫。 就BA无标度网络而言，目标免疫对应的免疫临界值

33、为： 上式表明，即使传染率在很大的范围内取不同的值 ，都可以得到很小的免疫临界值。因此，有选择地对 无标度网络进行目标免疫，其临界值要比随机免疫小 得多。 4.3.2 目标免疫 图4.5横坐标为免疫密度g，纵坐标为g/0，0表示网络未加免疫的稳态 感染密度，g为网络中加入比例为g的免疫节点后的稳态感染密度。 可以看出，随机免疫和目标免疫在无标度网络中存在着明显的临界值差 别。在随机免疫情况下，随着免疫密度g的增大，最终的被感染程度下降 缓慢，只有当g=1时，才能使被感染数为零。而在目标免疫的情况下， gc0.16，这意味着只要对少量度很大节点进行免疫，就能消除无标度 网络中的病毒扩散。 图4.

34、5 对BA无标度网络采取随机免疫和目标免疫的对比57 4.3.3 熟人免疫 熟人免疫:对随机选出的节点的邻居进行免疫，该策 略基本思想是：从N个节点中随机选出比例为s的节 点，再从每一个被选出的节点中随机选择它的某个邻 居节点进行免疫。 1 0.8 0.6 0.4 0.2 0 22.5 3 3.5 gc 图4.6 无标度网络中免疫临界值随幂律指数的变化情况58 4.4 复杂网络上的舆论传播和知识传播 舆论可以作为一种特殊的流行病，来研究它在网络中 的传染规律。 现实生活中的知识传播都是嵌入到网络中的，系统地 研究知识传播网络受到越来越多的关注。 本节关注舆论演化动力学以及舆论和知识的传播问题

35、。前者主要研究舆论的建立和演化过程，后者则与 4.2节的流行病传播一样研究舆论和知识在不同性质 网络和不同传染模型下的传染特性。 4.4.1 复杂网络上的舆论演化动力学 4.4.2 复杂网络上的舆论传播 4.4.3 复杂网络上的知识传播 4.4.1 复杂网络上的舆论演化动力学 1 舆论及其特性 舆论是由许许多多的社会个体的意见相互作用而形成 的，其发展变化受到自然、社会、经济、文化、政治 、法律等各种因素的影响，它的演化过程具有： 复杂性 开放性 不确定性 非平衡性 自组织性等特性。 协议是社会群体中非常重要的方面之一，每天的日常 生活都需要人们达到共识，而协议使得组织更协调有 效并可以扩展在

36、社会上的影响力。 4.4.1 复杂网络上的舆论演化动力学 2 舆论动力学研究现状 Weidlich第一个提出了舆论动力学模型，该模型是在 概率论社会动力学基础上提出来的。 Ising模型的提出使得这个模型第一次出现在舆论动 力学中：自旋之间的耦合代表了相互作用的个体对， 磁矩则代表社会的主流意见。 USDF舆论模型掀起了一股热潮，引起人们对这一领 域的广泛关注。 Deffuant等人和Hegselmann、Krause在0和1之间的 连续尺度上分别建立了Deffuant模型和Hegselmann- Krause模型。 4.4.1 复杂网络上的舆论演化动力学 Galam模型，它并不考虑人员之间的

37、相互影响而改变 人员的态度，而是在n步分组和迭代后选出议员来代 表整个社区的意见。 Panic模型采用分子动力学方法，人员的态度一部分 来自周围多数意见而一部分则根据自身意见来更新， 是一种模拟的极限情况。 Majority-Minority模型中人员的态度则以一定概率由 局域内的邻居的多数意见或少数意见来决定。 承载舆论演化的社会网络存在两种情况：静态网络和 动态网络。一种观点认为社会网络的变化在时间尺度 上比舆论演化的过程来得慢，另一种观点则把社会网 络的发展和舆论演化同步进行。 4.4.1 复杂网络上的舆论演化动力学 3 舆论动力学基本模型 由于社会网络的复杂性，出现了自组织、相变、临界

38、 现象等，因此很多舆论动力学模型都借鉴物理学中的 Ising思想。 舆论动力学中的五种主要模型包括： Voter模型 Majority Rule模型 Sznajd模型 Deffuant模型 Hegselmann-Krause模型。 4.4.2 复杂网络上的舆论传播 舆论传播的动力学行为也服从SIR模型。但是它的三 种状态和流行病中的三种状态S、I、R代表：不知道 消息的人群，知道消息的并有能力继续传播消息的人 群，及知道消息但已经失去传播能力或兴趣的人群。 假设网络上有N个节点，每个节点代表一个可传播消 息的个人，他们传播消息的行为方式如下：如果得到 了一个消息(I态)，那么他就有兴趣把这个消

39、息传播出 去，在传播过程中，他将随机地从邻居中选取一人并 将消息传给他，如果这个邻居不知道这个消息(S态) ，则该邻居就得到此消息(I态)，并进行下一轮的传播 。但如果他的邻居已经知道了这个消息，那么传播消 息的人会认为该消息失去了继续传播的价值，并失去 传播该消息的兴趣(R态)。整个过程可由以下关系简 单地表示出来： 4.4.2 复杂网络上的舆论传播 假设在一个有限网络中所有的节点都处于S态，在某 一时刻突然有一个节点得到了一个新的消息，它将成 为I态。那么按照上面所定义的规则，这个消息将在 网络中传播，直到最终网络中没有I态的节点为止。 称这个状态为终态。 4.4.2 复杂网络上的舆论传播

40、 考虑两个相邻节点A与B，它们由一条边联系。假定 节点A知道消息并于时间t将消息传给节点B。则在时 刻t+1，节点B将选取一个邻居作为目标来传递消息 。由于A为B的“父”点，A与B的其他邻居所处的地 位就将不一样。一旦A被选取为B传递消息的邻居， 按照传播规则，B将肯定变为R态；而当B的其他邻 居被选取时，B将依据当时的情形来决定是保留在I态 还是变为R态，即B变为R态的概率小于1。如果B的 度为k，则选择A的概率为1/k，而选择其他邻居的概 率为1-1/k。将这个分析与均匀混合假设结合起来， 就得到关于各态的数目nk,S、nk,I、nk,R的演化方程如 下： 4.4.2 复杂网络上的舆论传播

41、 Nk代表度为k的节点数，nk,S(t)、nk,I(t)、nk,R(t)分别表 示t时刻度为k的节点中处于S态、I态和R态的节点数 ，而nk,S(t)/Nk与(nk,I(t)+nk,R(t)/Nk则来自于均匀混合 假设。nk,I(t+1)可从守恒条件Nk=nk,S(t)+nk,I(t)+nk,R(t) 中获得。假定所研究的网络是无度关联的，即 P(k|k)=kP(k)/k。上面的式子是一个离散迭代映 射，可以改写成连续形式如下： 4.4.2 复杂网络上的舆论传播 重点关注“最终有机会听到消息”的人口密度。令T 代表舆论传播结束时的时间，即 。为得到上 述方程在时间t=T的解，引入辅助变量 。如

42、 果初始的感染种子(在t=0时)具有度k0，有初始条件： 对kk0有nk,S=Nk、nk,I=0及nk,R=0，对k=k0有nk,S=Nk -1、nk,I=1及nk,R=0，于是演化方程的解为： 由不同k的nk,I(T)=0，可得到一套关于sk的超越方程， 可用精确的数值求解。于是可得终态时度为k的节点 处于R态的人口密度为： 4.4.2 复杂网络上的舆论传播 其中 依赖于网络结构。显然，k将随k单 调增加，并对大的k趋于1。传播过程中总感染的节 点数为： 总感染的密度为： 由此可见，总感染密度依赖于度分布P(k)。 对于相同平均度的网络，无标度网比随机网络具有更 多度大的节点，因此无标度网中

43、的消息可较容易的传 递给大节点然后再到其他节点。一旦大节点处于I态 或R态，其他节点因为以较大概率连接到它们，从而 更容易变成R态；而随机网则没有这个特点。因此， 舆论在无标度网络上的传播要比在随机网络上结束得 快，从而导致无标度网的总感染密度比随机网的小。 4.4.2 复杂网络上的舆论传播 【例4.3】针对均匀网络，试求刘宗华的舆论传播模 型的总感染密度R与平均度的关系。 解：对于均匀网络来说，每个节点的度基本上相等， 故不需要针对度值分开讨论。类似于上面的分析，令 nS(t)、nI(t)、nR(t)分别表示t时刻处于S态、I态和R态 的节点数，可得如下方程： 其中，(nR(t)+nI(t)

44、/N来自于均匀混合假设。将上式转 化为连续形式如下： 引入辅助变量 结合初始条件nS(0)=N-1、 nI(0)=1及nR(0)=0可得： 若终止时刻为T，则nI(T)=0，由此得到s(T)，然后代 回上式可得到最终感染密度如下： 可见，最终感染密度与均匀网络的平均度密切相关。 4.4.2 复杂网络上的舆论传播 4.4.3 复杂网络上的知识传播 知识传播过程由知识传播者、知识学习者和知识免疫 者来完成，也具有传染性、免疫性和流行性，也可以 用类似于SIR的模型来描述。 从知识传播者传播到知识学习者，呈现出一定的传染 性。 有些知识学习者在学习知识过程中认为是无用的知识 而放弃学习，成为知识免疫

45、者。 知识同样也具有流行性，如果采用有效的激励措施， 将会加速知识的传播。 下面介绍几种典型的知识传播模型。 1 Cowan模型 Cowan和Jonard率先提出了复杂网络上的一种知识 扩散模型和一种知识增长模型。 他们利用复杂网络模型模拟了知识在社会网络中传播 扩散的过程，分别研究了网络结构与知识扩散阈的关 系、网络结构与知识增长间的关系。 发现在“小世界”网络中知识传播效率最高，但同时 知识差异也最大(也就是知识传播扩散最不公平，从传 播学角度看就是“知识沟”最大)。 Cowan模型仍存在一些不足：第一个假设是知识传播 的“实物交换”传播机制假设；第二个假设是知识传 播的无条件主动假设。

46、4.4.3 复杂网络上的知识传播 4.4.3 复杂网络上的知识传播 2 基于柯布道格拉斯生产函数的知识传播模型 知识具有非磨损性、可共享性和无限增值性。该模型 引入了柯布道格拉斯生产函数，并分别考察在个体 不进行知识自我增长和进行知识自我增长情况下的知 识传播。 假设在t时刻，个体vi是知识溢出者，vj是知识接收者 ，当vi与vj进行交互时，知识水平的增长以柯布道 格拉斯生产函数来表示： 式中：0A，1；确保外在的知识溢出 效应对知识增长的贡献高于内在知识水平的贡献，这 与知识扩散引起知识增长的前提是一致的；+1 ；A表示技术因素给生产带来的影响，0Al用于 调节知识的增加值，使其不产生过大的

47、值，否则与常 理不符合；li,t，lj,t分别表示个体vi和vj在t时刻的知识 水平。 在不考虑个体知识可以自我增长的情况时，模型主要 反映的是网络知识的扩散效应，此时群体存在知识水 平的上限，为此，当0.99lj,tli,t1.01时，近似认 为两个个体的知识水平相等，这样可保证群体最终的 知识水平收敛于某一个极限值。在考虑个体知识可以 自我增长的情况时，取消知识水平上限的设置，个体 知识的自我增长采用下式表示： 4.4.3 复杂网络上的知识传播 4.4.3 复杂网络上的知识传播 在t时刻，网络的平均知识水平t为： 反映知识分布均匀程度的知识水平标准差： 在其它条件相同的情况下，网络的随机化程度越大， 网络中知识的扩散速度越快，知识的分布越均匀。 但是，如果刻意地突出近邻环境的压力作用，对传播 机制作一些变化，小世界特性立刻就能发挥出来。 一般来说，人们期望集群在具有较快的知识传播速度 的同时又保持一定的知识分布不均匀性，这样既能保 持群体有高的综合能力，又可以保持群体内存在一定 的竞争压力，有利于群体长久发展。 4.4.3 复杂网络上的知识传播 3 基于信任