Ch7 网络上的动力学

第7章

网络上的动力学7.1网络上的传播动力学7.2网络上的随机游走7.3网络上的同步17.1网络上的传播动力学27.1.1经典的疾病传播模型3SI模型两类人群：易感人群(S)和感染人群(I)感染状态的个体比例随时间逐渐增大，其变化速率如下：7.1.1经典的疾病传播模型4SI模型的传播曲线7.1.1经典的疾病传播模型5SIS模型SIS模型中感染个体可以以一定概率被治愈，变为易感个体。SIS模型可以用如下微分方程组描述：7.1.1经典的疾病传播模型6令

，则上述方程存在一个阈值，即SIS模型的传播临界值，

当

时，方程的稳态解

，T为达到稳态所需要的时间。

当

时，方程的稳态解为

，感染将无法扩散。SIS模型的传播曲线7.1.1经典的疾病传播模型7SIR模型SIR模型包含了3类人群：易感人群(S)、感染人群(I)以及免疫人群(R)。个体处于免疫状态是指个体被治愈后获得了免疫能力或者死亡，该个体不能被感染疾病或是传播疾病。SIR模型的示意图：7.1.1经典的疾病传播模型8令s(t)、i(t)、r(t)分别为时刻处于易感状态、感染状态、免疫状态的人数比例，s(t)+i(t)+r(t)=1SIR模型可以用如下微分方程组：7.1.1经典的疾病传播模型9SIR模型的传播曲线7.1.2网络上的疾病传播10网络上的SIS模型小世界网络上的SIS模型被感染节点的密度可以用如下方程描述：右端等于零，可以得到:解得感染节点的稳态密度:7.1.2网络上的疾病传播11BA无标度网络上的SIS模型被感染节点的密度可以用如下方程描述:稳态解：被感染节点的稳态密度：7.1.2网络上的疾病传播12网络上的SIR模型小世界网络上的SIR模型可以用如下微分方程组描述:

解得：

传播效率：7.1.2网络上的疾病传播13BA无标度网络上的SIR模型动力学方程为：

初始条件:

传播阈值:7.1.2网络上的疾病传播14网络免疫技术免疫策略：随机免疫、目标免疫、熟人免疫随机免疫：完全随机地选取网络中的一部分节点进行免疫，即各个节点被免疫的概率是相等的。以网络上的SIS模型为例：

小世界网络

无标度网络7.1.2网络上的疾病传播15目标免疫针对无标度网络的有效免疫策略。通过有选择地对少量关键节点进行免疫的一种策略。帕斯特-萨托拉斯和韦斯皮尼亚尼提出了优先免疫度大节点的目标免疫策略。这种免疫策略的效果要优于随机免疫，可以使免疫临界值由随机免疫策略的

降低到

。由此可见，有选择地对无标度网络进行目标免疫，其临界值要比随机免疫小得多。7.1.2网络上的疾病传播16熟人免疫基本思想：从含有个节点的网络中随机选择比例为的节点，再从每一个被选出的节点中随机选择它的一个邻居节点进行免疫。这种策略只需要知道被随机选择出来的节点以及与它们直接相连的邻居节点，并且由于在无标度网络中度大的节点含有更多的邻居，这些度大的节点要比度小的节点被选中的概率更大，因此该策略效果比随机免疫好很多。7.1.3网络上的经典舆论动力学17舆论形成，包括投票选举、各种党派团体的形成等，是社会系统中常见的一种集群现象。社会学家对于舆论形成一般从社会心理学等角度来考虑微观层面上个体选择的形成以及个体选择对于宏观行为的影响，但从个体心理如何发展到群体心理层面的集群涌现机制，主要是从定性上进行解释，定量上的研究很少。事实上，舆论形成的机制与铁磁相变中通过微观上个体之间的相互作用涌现出宏观行为的机制类似。于是近年来，物理学家在Ising模型的基础上，研究了舆论形成问题。本小节将重介绍Ising模型以及基于Ising模型的投票模型。7.1.3网络上的经典舆论动力学18

7.1.3网络上的经典舆论动力学19系统的哈密顿量为:系统的配分函数为：作用于格点的等效平均磁场:平均场近似下原系统配分函数可简化为:7.1.3网络上的经典舆论动力学20

则系统的磁矩为：当没有外磁场B=0时，得出临界温度：7.1.3网络上的经典舆论动力学21复杂网络下的Ising模型哈密顿量为：经典平均场理论下，磁矩自旋集团的能量为：7.1.3网络上的经典舆论动力学22Bethe近似方法可以很好的求解标准Bethe晶格、树状网络和全连接网络中的Ising模型。退火网络近似方法能够很好的讨论在复杂网络中临界现象的发生。形式简单，却能给出很好的近似解。适用于解决在耦合和度相关的网络中以及存在随机外场时的Ising模型问题。哈密顿量定义为：7.1.3网络上的经典舆论动力学23投票模型主要思想是：团结就胜利，分裂就失败。每个人可以被视为一个节点，相当于Ising模型中的铁分子，有向上和向下两种自旋

。对应在投票系统中，就是两个候选人A和B可供选择。具体的演化机制是：包含N个节点的一维链上，每一次随机选择相邻的两个节点

i和

i+1。7.1.3网络上的经典舆论动力学24稳态解：所有节点都选A所有节点都选B每一对相邻节点选择不同候选人。磁化强度

反映了舆论导向。如果m=0，说明有一半人选A，一半人选B。如果m>0，说明选A的比选B的人要多，A胜出，反之，B胜出。m在演化中的变化，是判定系统是否到达终态的度量之一。7.2网络上的随机游走2526

复杂网络上的随机游走是指以网络节点为载体，按照一定概率从网络上任意一个节点转移到与之有连接的其他节点的状态转移过程。大量研究结果表明，网络上的随机游走不但与节点中心性、网络平均距离、生成树数目等网络自身结构性质有关,而且与网络上运输、导航、疾病传播等其他动力学过程也存在密切关系。因此，网络上的随机游走具有广泛的应用，如解决网络中的搜索、节点相似性测定、社团划分等。7.2.1随机游走的基础理论27考虑一个个体在网络上进行离散简单随机游走，即该个体每个时间步内只能移动一步。邻接矩阵为：

一步转移概率：

一步转移概率矩阵由一步转移概率可以知道个体在游走n+1步之后，位于节点j的概率为：平稳概率分布：平稳概率：7.2.2随机游走的简单应用28基于随机游走的搜索策略随机游走策略是最常用的一种搜索策略。在每个节点都只知道自己邻居节点信息的条件下，从源节点出发，应用随机游走策略搜索目标节点时，其搜索过程为：先判断自己的邻居节点中是否含有目标节点：如果含有，则终止搜索；如果没有，则向任一个邻居查询其邻居节点中是否含有目标节点。不断重复这个过程，直到搜索到目标节点为止。在此简要介绍3种不同的随机游走策略。7.2.2随机游走的简单应用29无限制的随机游走搜索策略（URW）每一步中，当前节点不加任何限制地在其所有邻居中随机选择一个邻居节点将查询传递过去，直到搜索到目标节点的任一个邻居节点为止。不返回上一步节点的随机游走搜索策略（NRRW）除了刚刚将查询传递过来的上一步节点之外，每一步中，当前节点在其余的所有邻居中随机选择一个邻居节点将查询传递过去，直到搜索到目标节点的任一个邻居节点为止。7.2.2随机游走的简单应用30不重复访问节点的随机游走搜索策略（SARW）已经被查询过的节点不允许再被查询，并且每一步中当前节点在其所有未被查询过的邻居节点中随机选择一个，并将查询传递过去，直到搜索到目标节点的任一个邻居节点为止。这3种随机游走搜索策略在WS小世界网络上的搜索效率，介于最近邻耦合网络和ER随机网络之间，其中NRRW的搜索效率比URW稍有改进，而SARW的搜索效率则有较大提高。7.2.2随机游走的简单应用31基于随机游走的节点相似性指标平均通勤时间(averagecommutetime，ACT)平均通勤时间定义为：基于ACT的相似性为：7.2.2随机游走的简单应用32基于随机游走的余弦相似性(Cos+)重启的随机游走(randomwalkwithrestart，RWR)t+1时刻该粒子到达网络各个节点的概率向量为：RWR相似性为：7.2.2随机游走的简单应用33SimRank（SimR）指标局部随机游走指标(localrandomwalk，LRW)系统演化方程：基于t步随机游走的相似性为：7.2.2随机游走的简单应用34叠加的局部随机游走指标(superposedrandomwalk，SRW)这个指标的目的就是给邻近目标节点的点更多的机会与目标节点相连。在LRW的基础上将t步及其以前的结果加总便得到SRW的值，即：7.2.2随机游走的简单应用35基于随机游走的社团划分一般而言，相似性越高的节点越有可能属于一个社团，因此可以基于节点间的相似性来划分社团。节点之间的相似性可以由节点间的距离来度量，而基于随机游走又恰好可以计算节点间的距离，所以应用随机游走来衡量节点间的相似性，进而挖掘网络中的社团结构。7.2.2随机游走的简单应用36庞斯与拉塔皮提出的Walktrap算法Walktrap算法初始将每个节点看作一个社团，然后基于节点间的距离进行层次聚类，直到所有节点都归为一类，最终应用函数得到最优的社团结构。由节点

i跳跃到其邻居节点

j的概率为：两个节点结构等价的程度由距离衡量：7.2.2随机游走的简单应用37Walktrap算法流程7.3网络上的同步3839

对于两个或多个动力学系统，除了自身的演化外，它们之间还存在相互作用（耦合），并且这种相互作用既可以是单向，也可以是双向。对于这样的动力学系统，当满足一定条件时，在耦合的影响下，这些系统的状态输出就会逐渐趋同进而完全相等，称为同步（精确同步）。除了精确的同步外还存在如像相同步、频率同步等这样广义的同步。7.3.1同步的定义40以一般连续时间耦合网络为研究对象，讨论它的完全同步问题。

第i个节点的状态方程为：

耗散耦合条件：

如果在动态网络中，当

时有

则称网络达到完全（渐进）同步。

如果存在

使得

则称动态网络中的所有节点的状态完全（渐近）同步于

。7.3.1同步的定义41设网络的同步化区域为

，其中

，如果此网络的耦合强度和拉普拉斯矩阵的特征值满足如下同步判据：那么，该网络的同步流形是渐进稳定的。网络关于拓扑结构的同步化能力可以用对应的拉普拉斯矩阵的最大特征值与最小非零特征值的比率来刻画。7.3.2网络的同步能力度量42最近邻耦合网络对于节点度为K（假设为偶数）的最近邻耦合动态网络，它所对应的拉普拉斯矩阵的特征值满足：当网络规模

N很大时，

比率的值很大，因而网络的同步化能力很差。7.3.2网络的同步能力度量43全局耦合网络全局耦合动态网络对应的拉普拉斯矩阵的最大特征值和最小非零