（应用数学专业论文）复杂网络上的传染病模型研究.pdf

中文摘要 摘要 近年来，关于复袈网络的研究正处于蓬勃发展的阶段。其研究者来鑫圈论、 统计臻壤学、幸 算瓤阏络、生态学、柱会学以及经济学等各个不霞领域。巍然雾 中存在的大量复杂系统都可以通过网络加以描述由于计算机数据处理和运算能力 的飞速发展，科学家们发现大量的真实网络既不是规则网络，也不是随机隧络， 两是其裔与兹两者鹫不弼的统计特征豹弼络。这样的一些嘲绦绶辩学家稻列徽复 杂网络( c o m p l e xn e t w o r k s ) 。 病鬻在计算机网终上的蔓延、传染病在人群审的流行、谣言在社会中的扩数等， 都可班麓作是服麸莱种兢律豹网络传器行为。本文主要研究了基于复杂掰络上豹 传染病模型。首先，对于目前比较熏要的复杂网络模型的研究成果进行了总结， 并且介缨了各耪经典的传染病模型茅眭它钌的性袋。其中，重点对于近年由m o r e n o 提出静横型l 鞠逶行了深入探讨。从实验模拟和瓒论分析角度静研究，提出了一个 改进策略，通过实验对比，证明该策略对于传播的效率和可靠度有较大提简。 另外本文通过理谂分析，借助数学! 琏纳法褥爨7 节点豹发窥它该被幸孪葛孵窃 的大小，给出了一个爨化的公式关系。从而最大限度的挖掘h u b s 节点鼢潜力。 最厝，就本文所做的主要工作进行了总结并提出以后需要注意的问题。 美毽谶：复杂弱终；枣整赛羯终；舞撂褒霜络；蒋染痰模鍪 英文摘要 t h ee p i d e m i cm o d e l so nt h e c o m p l e x n e t w o r k s a b s t f a c t h lr e c e n t y e a r s t h e d i s c o v e r i e so fc o m p l e xn e t w o r k sh a v ea t t r a c t e dal o to f i n t e r e s t t h er e s e a r c h e r sc o m ef r o mt h ef i e l d so fg r a p ht h e o r y ，s t a t i s t i c a lp h y s i c s ， c o m p u t e rn e t w o r k s ，e c o l o g y ，s o c i o l o g ya n de c o n o m i c s 1 1 1 en e t w o r k sc a nd e s c r i b e m a n yc o m p l e xs y s t e m si nt h en a t u r ew o r l d w i t ht h ed e v e l o p i n g o fc o m p u t e r t e c h n o l o g y ，s c i e n t i s t sr e c o g n i z et h a tm a n yn e t w o r k si n t h er e a lw o r l da r en e i t h e r r e g u l a rn e t w o r k sn o rr a n d o mn e t w o r k s ，b u tt h en e t w o r k sw h i c hh a v et h es t a t i s t i c a l c h a r a c t e r i z a t i o n st h a tn o tb e l o n gt ot h ef i r s tt w o 耽i sk i n do fn e t w o r ki sc a l l e dc o m p l e x n e t w o r kb ys c i e n t i s t s 1 1 l es p r e a do ft h ev i r u si nc o m p u t e rn e t w o r k s t h ep r e v a l e n c eo fi n f e c t i o u sd i s e a s e s i nt h ec r o w d ，c a nb ev i e w e da sab e h a v i o ro fc o m m u n i c a t i o no nt h en e t w o r k sw h i c hi s s u b j e c t e dt oac e r t a i nl a w t h i sp a p e rs t u d i e di nt h ee p i d e m i cm o d e l so nt h ec o m p l e x n e t w o r k s f i r s t ，w er e v i e wt h em o s ti m p o r t a n tc o m p l e xn e t w o r k sm o d e l sa n ds o m e c l a s s i ce p i d e m i cm o d e l s a n dw ep a ym o r ea t t e n t i o n so nm o r e n o sm o d e l s w e i n t r o d u c eam e t h o dt oi m p r o v et h e r e l i a b i l i t ya n de f f i c i e n c y i t i s p r o v e db y e x p e r i m e n t a ls i m u l a t i o n i nt h i sp a p e r , w eh a v ef o u n da ne q u a t i o nt od e s c r i b et h er e l a t i o n s h i pb e t w e e nt h e p a r a m e t e r 口a n d 置i tc a nr e l e a s em o r ep o t e n t i a lo fh u b si nt h en e t w o r k s f i n a l l y , i ts u m m a r i z e st h em a i nw o r kd o n ei nt h ep a p e ra n dg i v e ss o m eq u e s t i o n s t os o l v ei nt h ef u t u r e k e yw o r d s ：c o m p l e xn e t w o r k s ；s m a l lw o r l dn e t w o r k s ；e p i d e m i cm o d e l s ； s c a l e f r e en e t w o r k s 大连海事大学学位论文原创性声明和使用授权说明 原刨性声明 本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取得的成果， 撰写成硕士学位论文 ：! 复苤圜终生丝佳鎏痘撞型硒究：。除论文中已经注明引 用的内容外，对论文的研究做出重要贡献的个人和集体，均已在文中以明确方式 标明。本论文中不包含任何未加明确注明的其他个人或集体已经公开发表或未公 开发表的成果。 本声明的法律责任由本人承担。 论文作者签名：葺滓拐远1 ，；7 年弓月帽 学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连海事大学研究生学位论文提交、 版权使用管理办法”，同意大连海事大学保留并向国家有关部门或机构送交学位论 文的复印件和电子版，允许论文被查阅和借阅。本人授权大连海事大学可以将本 学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或扫 描等复制手段保存和汇编学位论文。 不保密瞰请在以上方框内打“”) 论文作者签名5 年鹕逸，导师签名：彩。：芯年 日期：劢9 7 年弓月z 牛日 复杂网络上的传染病模型研究 第1 章引言 网络可以看作是一个包含了大量个体及个体之间相互作用的系统。网络可以 用来描述人与人之间的社会关系1 1 ，2 t3 1 ，物种之间的捕食关系，词与词之间的语义 联系，计算机之间的网络联接 4 1 ，网页之间的超链接 5 1 ，科研文章之间的引用关系， 以及科学家之间的合作关系瓯7 1 ，甚至产品的生产与被生产关系。网络还可以作为 现象的背景舞台，例如在社会关系网络上讨论舆论的传播，接触关系网络上讨论 传染病的传播【8 1 ，计算机病毒在i n t e r n e t 网络或邮件网络上的传播，在引文网络上研 究新思想的提出与传播，在科学家网络上研究科学家之间的相互影响等。网络与 现象结合还可以用来讨论网络的稳定性等结构与功能关系，例如在食物链网络上 讨论个别或部分物种灭绝对整体生态系统的影响，在不同的网络上讨论传染病传 播的控制，在科学家网络中讨论某个领域中不同的科学家的影响力对网络演化的 影响。此外，网络本身的演化过程也是一个有趣的问题，例如i n t e r n e t 网络的形成 被认为是无限定原则的，但是它却展现了一些重要而普适的结构特征与稳定性， 再比如，对于某一个学科内的引文网络与科学家网络的演化机制的研究，有可能 给出促进科学发展的新的方案与模式。 每一个系统中的网络都有其自身的特殊性质，有其紧密联系在一起的独特现 象，有其自身的演化机制，但是由于都可以使用网络分析的方法，所以有其共性。 例如关于顶点度值、介数的分析方法以及大量不同网络中存在的相同的统计特征， 再如随机去点与选择性攻击对网络结构的影响及其分析方法。研究网络的几何性 质，网络的形成机制，网络演化的统计规律，网络上的模型性质，以及网络的结 构稳定性，并把它与具体系统结合起来是复杂网络研究的中心内容。 传染病和新出现的疫病严重危害人类健康与社会经济发展。对传染病发病机 理、传播规律和防治策略研究的重要性日益突出。目前，对传染病的研究方法主 要有描述性研究、分析性研究、实验性研究和理论性研究。传染病动力掣9 l 是对进 行理论性定量研究的一种重要方法，是根据种群生长的特性，疾病的发生及在种 群内的传播、发展规律，以及与之有关的社会等因素，建立能反映传染病动力学 特性的数学模型，通过对模型动力学性态的定性、定量分析和数值模拟，来分析 第1 章g l窘 痰病的发展过稷，揭示流行残律，颟测交毒艺趋势，分轿疾病流行静淼因和荧键因 豢，寻裳颈黪鄹控制的最优策略，为防剑决策提供理论依据。传染瘸模型搬是一 种有效的信息传递机制，它大量的应用于信息传递，分布式计算领域。随着 巍今全球一体纯，电子商务时代静到来，对子僚怠传递的要求越来越高。闲诧， 笈杂疆络背景太戆传矮动力学豹磷究也越来越受到重视。 本文的研究主要分成两个部分：一部分是研究复杂嗣络的背景网络模型的拓扑 能质。翳一部分是研究传染瘸模型成蠲予不同的背景网络上的效栗。 蓄毙奔缨爨嚣堂爨上对复杂网终硬究熬进展与基本理论，分缨复杂嬲终戆一些 慕本概念，引出目前学术界最关注的几种复杂网络形式，如随机网络【1 0 】，小世界 嘲络f l l ，s c a l e f r e e 网络等几种网络模型f l l l 的构遥，然后g l 入复杂网络研究的最主 装夔见墨孛度量，麴弱终孛震熬援念，最短鼹径豹概念，集聚系数等等。 然磁重点介绍目前学术界最关注的b a 模型和w s 模型的演化方式和它们具有 的各种拓扑性质。 最鼹夯缨凡耪经典豹黉染薅挨篷s i s 模墼，s i r 摸型1 1 司窝熟识熬特点。零文应 用的传染病模烈的形成机制和具体特点与经典模型有些区别，在文章中会具体 介绍。 复杂网络上的传染病模型研究 第2 章复杂网络基本概念及基本模型 复杂性，这一名词截至目前为止仍然没有一个被大家公认的定义，但大家都 能认同的是，它具有与随机性完全不同的更复杂更丰富的表现形式和特征。对于 复杂性的定义目前业界较为认同的说法是，首先复杂系统必须由大规模的元素所 组成，或者说由大量的“节点”所组成，每个元素或节点都具有各自的动力学特 性，但整个系统并不是简单的由各个独立的系统进行简单的叠加，而是各个节点 相互影响，相互制约，相互作用，从而使整个系统具有极其纷繁复杂的动力学特 性。这一特性，有两个关键点，一个是大量的节点而不是几个或者小规模的数量； 另一关键点是，节点间的相互作用。 自然界中存在的大量复杂系统都可以通过形形色色的网络加以描述。一个典 型的网络是由许多节点与连接两个节点之间的一些边组成的，其中节点用来代表 真实系统中不同的个体，而边则用来表示个体间的关系，往往是两个节点之间具 有某种特定的关系则连一条边，反之则不连边，有边相连的两个节点在网络中被 看作是相邻的。例如，神经系统可以看作大量神经细胞通过神经纤维相互连接形 成的网络【1 l ；计算机网络可以看作是自主工作的计算机通过通信介质如光缆、双绞 线、同轴电缆等相互连接形成的网络1 4 】。类似的还有电力网络1 1 1 、社会关系网络【1 ，2 3 1 、交通网络【1 3 1 等等。 数学家和物理学家在考虑网络的时候，往往只关心节点之间有没有边相连， 至于节点到底在什么位置，边是长还是短，是弯曲还是平直，有没有相交等等都 是他们不在意的。在这里，我们把网络不依赖于节点的具体位置和边的具体形态 就能表现出来的性质叫做网络的拓扑性质，相应的结构叫做网络的拓扑结构。那 么，什么样的拓扑结构比较适合用来描述真实的系统呢? 两百多年来，对这个问 题的研究经历了三个阶段。在最初的一百多年里，科学家们认为真实系统各因素 之间的关系可以用一些规则的结构表示，例如二维平面上的欧几里德格网，它看 起来像是格子体恤衫上的花纹；又或者最近邻环网，它总是会让你想到一群手牵 着手围着篝火跳圆圈舞的姑娘。到t - 十世纪五十年代末，数学家们想出了一种 新的构造网络的方法，在这种方法下，两个节点之间连边与否不再是确定的事情， 第2 章复杂网络基本概念及基本模型 而是根据一个概率决定。数学家把这样生成的网络叫做随机网络，它在接下来的 四十年里一直被很多科学家认为是描述真实系统最适宜的网络【6 ，7 1 0 l 。直到最近几 年，由于计算机数据处理和运算能力的飞速发展，科学家们发现大量的真实网络 既不是规则网络，也不是随机网络，而是具有与前两者皆不同的统计特征的网络。 这样的一些网络被科学家们叫做复杂网络，对于它们的研究标志着第三阶段的到 来。 遗憾的是，就目前而言，科学家们还没有给出复杂网络精确严格的定义，从 这几年的研究来看，之所以称其为复杂网络，大致上包含以下几层意思：首先， 它是大量真实复杂系统的拓扑抽象；其次，它至少在感觉上比规则网络和随机网 络复杂，因为我们可以很容易地生成规则和随机网络，但就目前而言，还没有一 种简单方法能够生成完全符合真实统计特征的网络；最后，由于复杂网络是大量 复杂系统得以存在的拓扑基础，因此对它的研究被认为有助于理解“复杂系统之 所以复杂”这一至关重要的问题。 2 1 网络的图表示 一个具体网络【4 3 】可能抽象为一个由点集矿和边集e 组成的图g 一，e ) 。节点 数记为n - 1 v i ，边数记为肘- 吲。e 中每条边都有y 中一对点与之对应。从统计 物理学的角度来看，网络是一个包含了大量个体以及个体之间相互作用的系统， 是把某种现象或某种关系抽象为个体( 顶点) 以及个体之间的相互作用( 边) 而形成的 用来描述这一现象或关系的图。如果任意点对( f ，) 与( ，i ) 对应同一条边，则该网 络称为无向网络( u n d i r e c t e d n e t w o r k ) ，否则称为有向网络( d i r e c t e dn e t w o r k ) 。如果给 每条边都赋予相应的权值，那么该网络就称为加权网络( w e i g h t e dn e t w o r k ) ，否则称 为无权网络( u n w e i g h t e dn e t w o r k ) 表示网络的图的结构信息用邻接矩阵表示，如果节点，与节点，存在着连接的 边，那么矩阵上相应位置我们就用1 来表示，如果不存在连接我们就用0 来表示， 显然一个无向图的邻接矩阵具有对称结构。 复杂网络上的传染病模型研究 图2 1 网络 f i g2 1n e t w o r k s 图2 1 是一个示意性的网络，它有n = 4 个节点和，v ，五y ) 和m = 4 条边 ，e 。， e w ，e u v ) 2 2 网络的静态几何量 如果要想深入理解网络的内在特征f 4 3 1 ，我们就不得不谈到三个概念：网络的 度数，网络的成簇系数和网络的最短路径。实际上，有向网络，无向网络，加权 网络中各种静态的几何量是各有特点的。以下，我们主要以无向网络为例子讨论 网络中各种不同的几何量： 2 2 1 节点的度分布 度( d e g r e e ) 是单独节点的属性中简单而又重要的概念。节点f 的度七。定义为与 该节点连接的其他节点的数目。有向网络中一个节点的度分为出度( o u t d e g r e e ) 和 入度( i n d e g r e e ) 。节点的出度是指从该节点指向该节点的边的数目。直观上看，一 个节点的度越大就意味着这个节点在某种意义上约“重要”。网络中所有节点的度 的平均值称为网络的( 节点) 平均度，记为c 七，。网络中节点的度的分布情况可用 分布函数p ) 来描述。p 体) 表示的是网络中度数为七的顶点的个数占顶点总个数 的比例。完全随机网络的度分布近似为p o i s s o n 分布，其形状在远离峰值忙) 处呈 指数下降( 图2 2 ( a ) ) 。这意味着当七，tk ，时，度为七的节点实际上是不存在的。 这类网络称为均匀网络( h o m o g e n e o u sn e t w o r k ) 。 近几年的大量研究表明，许多实际网络的度分布明显地不同于p o i s s o n 分布。 第2 章复杂网络基本概念及基本模犁 特别地，许多网络的度分布可以用幂率形式p ( t ) “k ”来更好地描述( 图2 2 ( b ) ) 。 幂率分布曲线比p o i s s o n 分布曲线下降要缓慢得多。 差 善兰1 0 4 一 t 一 j 、 ； l ，略丁冉 ( a )( b ) 图2 2 两种分布的对比：( a ) p o i s s o n 分布；( b ) 幂率分布( 对数坐标系) f i g2 2t h et w ok i n do fd e g r e ed i s t r i b u t i o n s ( a ) p o i s s o nd s t n b u t o n sc o ) p o w e rd i s t r i b u t i o n 幂率分布也称为无标度( s c a l e f r e e ) 分布，具有幂率度分布的网络也称为无标度 网络，这是由于幂率分布函数具有如下无标度性质。 幂率分布函数的无标度性质：考虑一个概率分布函数f ( x ) ，如果对任意给定 常数a ，存在常数b 使得函数厂0 ) 满足如下“无标度条件” f ( a x ) 一6 ，0 )( 2 1 ) 取工- 1 ，我们有f ( a ) 可( 1 ) ，从而6 - f ( a ) f ( 1 ) ，则 f ( a x ) ；紫 ( 2 1 2 ) 由于上述方程对任意的a 都成立，方程两边对a 求导可得 巧一锷帅) ( 2 3 ) 若取a 一1 ，则有 酽 矿 铲 复杂网络上的传染病模型研究 x f , 蜘篙m ( 2 4 ) 微分方程的解为 l n m ；器l n x + l n ，( 1 ) ( 2 5 ) 则 ( x ) 一o ) x - - f ，其中r - 一t o ) ( 1 )( 2 6 ) 所以说，幂率分布函数是唯一满足“无标度条件”的概率分布函数。 在一个度分布为具有适当幂指数( 通常为2 ，3 ) 的幂率形式的大规模无标 度网络中，绝大部分的节点的度相对很低，但存在少量的度相对很高的节点。因 此，这类网络也称为非均匀网络( i n h o m o g e n e o u sn e t w o r k ) ，而那些相对很高的节点 称为网络的“集散点”。例如，美国高速公路网就可以近似看作是一个均匀网络， 因为不可能有上百条高速公路都经过同一个城市；而美国航空网则可看作是一个 无标度网络，大部分机场都是小机场，但却存在少量连接众多小机场的非常大的 机场，如芝加哥，达拉斯，亚特兰大和纽约机场。 对于其他类型的网络而言，其顶点度分布更为复杂。例如，对于二部图，每一 种顶点分别有一个顶点度分布。对于有向图，每个顶点都有一个出度和入度，因 此其顶点度分布也成为两个变量的函数p 。，代表入度为，且出度为i 的顶点的个 数占顶点总个数的比例。 2 2 2 最短路径长度 网络中两个节点i 和j 之间的距离比定义为连接这两个节点的最短路径上的 边数。网络中任意两个节点之间的距离的最大值称为网络的直径【4 3 ( d i a m e t e r ) ，记 为d ，即 d - m a 。 (27)xd 网络的平均路径长度l 定义为任意两个节点之间的距离的平均值，即 工- _ 。l 一如 ( 2 8 ) 去( + 1 ) 4 。 第2 章复杂网络基本概念及基本模型 其中j v 为网络的节点数。网络的平均路径长度也称为网络的特征路径长度。 如果网络中有顶点对之间没有路径连接，则令此顶点对之间的最短距离为无穷 大，但这样，l 的值也变为无穷了。为了避免这一问题，采用计算“调和平均”最 短距离，即倒数平均值的倒数： 上4 一丁- ! 一d f 。1 ( 2 9 ) 妄( + 1 ) “ 二 这样d 。的无穷值就对总数没有影响。 一 图2 3 网络的最短路 f i g2 3t h es h o r t e s tp a t ho ft h en e t w o r k s 上面给出了一个加权网络图，由最短路算法容易得出从s o u r c e 到d e s t i n a t i o n 的 最短路为1 2 5 8 。 2 2 3 聚类系数 在你的朋友关系网络中，你的两个朋友很可能彼此也是朋友，这种属性称为 网络的群聚属性。一般地，假设网络中的一个节点有k 个条边将它与其他节点相 连，这t 个节点就称为该节点的邻居。显然，在这七。个节点之间最多可能有 t 一1 ) 2 条边。而这置个节点之间实际存在的边数巨和总的可能的边数 七。 。一1 ) 2 之比就定义为节点f 的聚类系数c 。，即 c 。上( 2 1 0 ) 去t 一1 ) 从几何特点上来看，上式的一个等价定义为 8 - 复杂网络上的传染病模型研究 c ，- 等糕粼 与点f 相连的三元组的数量 7 其中，与节点i 相连的三元组是指包括节点i 的三个节点，并且至少存在从节点i 到 其他两个节点的两条边。 整个网络的聚类系数c 就是所有节点的聚类系数的平均值，即 c 。三三c ( 2 1 2 ) 很明显，0 c 1 。c 一0 当且仅当所有的节点均为孤立节点，即没有任何连接边； c 一1 当且仅当网络是全局耦合的，即网络中任意两个节点都直接连接。 图2 4 聚类系数 f i g2 4c l u s t e r i n gc o e f f i c i e n t 计算一个具有m = 4 个节点，n = 4 个边的图的聚类系数的方法如下：图中有 一个三角形和五个相连的三角，其中的三个三角在图中用箭头表示。另外两个三 角，如移动内部箭头的起始位置也可以得到，也就是把一v 起始的前头分别换成 以石和以y 起始。那么成簇系数我们利用方程可以计算得到为3 5 。 聚类系数即为网络中三角形的密度。例如社会网络中总是存在熟人圈或朋友 圈，其中每个成员都认识其他成员。集聚程度的意义是网络集团化的程度；这是 一种网络的内聚倾向。这就意味着实际的复杂网络并不是完全随机的，而是在某 种程度上具有“物以类聚，人以群分”的特性。 2 2 4 介数 在一些大型的实际网络中，每个节点的地位是不同的。例如，在攻击网络的 节点的过程中，某些节点如果受到攻击，会导致网络的瘫痪。衡量一个点的重要 第2 章复杂网络基本概念及基本模型 性，顶点的度可以作为一个衡量指标，但又不尽然，例如图2 4 的这种情形，虽然 顶点v 的度数很小，但如果去除掉点v ，那么就会导致两个集团的分离，因此v 在 网络中起到极其重要的作用。对于这样的点，我们定义另一个衡量点的重要指标 为介数( b e m e e n n e s sc e n t r a l i t y ) 。节点v 的介数为通过节点v 的最短路径的数目 集团1 图2 5 介数 f i 9 2 5b e t w e e n n e s sc e n t r a l i t y 集团2 图2 5 节点v 的度数很小( 只有两度) ，但从集团1 到集团2 的最短路径都必经 顶点v 。节点v 的介数为 酬= ，互，警 ( 2 1 3 ) 其中口。表示从顶点s 到顶点f 的所有的最短路径的条数，而d 。( v ) 表示从顶点s 到 顶点t ，经过顶点v 的所有的最短路径的条数。 我们利用上式来计算图2 5 中顶点p 的介数 咖警观1 - 2 n s e c i , 。c z s e c i , t e c 2 1 2 = 9 6( 2 1 4 ) 口盯 其中n 。( ：) 表示集团c 1 ( c ：) 中的节点的个数。 2 ，2 5 社团结构 随着对网络性质的物理意义和数学特性的深入研究，人们发现许多的实际网 络都具有一个共同性质，即“社团结构”，也就是说，整个网络是由若干个“群 ( g r o u p ) ”或“ ( c l u s t e r ) ”构成的。每个群内部的节点之间的连接相对非常紧密， 复杂网络上的传染病模犁研究 但是各个群之间的连接相对来说却比较稀疏。 图2 6 社团结构 f i g2 6g r o u p ss t r u c t u r e 图2 6 一个小型的具有社团结构性质的网络示意图。如图2 6 所示，图中的网 络包含三个社团，分别对应图中三个虚线圆圈包含的部分，而社团之间的联系就 稀疏得多。实际中也经常碰到这种情况，人们一般会按照兴趣、职业、年龄和其 他等方面的不同分为不同的群体；w w w 可以看成是由大量网站社团组成，其中 同一个社团内部的各个网站所讨论的都是一些有共同兴趣的话题；在生物网络或 者电路网络中，同样可以将各个节点根据其不同的性质划分为不同的社团。揭示 网络中的社团结构，对于了解网络结构与分析网络特性都是很重要的。 2 2 6 顶点度相关性与异配性 网络中高度数的顶点是偏向于与其它高度数顶点相关联，还是偏向于与低度 数顶点相关联? 实际证明，在一些网络中，两种情形都存在。度相关性描述的是 网络中不同节点之间的连接关系。 对于给定度的节点i 的邻居节点的平均度 1 2 m ( ) 。毒磊j ) 暑，( 2 1 5 ) 其中v ( f ) 表示i 的邻居节点的集合。 第2 章复杂网络基本概念及基本模型 对于度为k 的所有节点的平均邻居节点的平均度为 1 七m ( 。) 。赢。殿m ( ) ( 2 1 6 ) 此式表明，若k 。 ) 随着度数k 增长，说明高度数的点偏向于与高度数顶点相关联， 具有此类特性的网络我们称之为同配网络( a s s o r t a t i v c ) 。反之，若七。 ) 随着度数k 减少，说明高度数的顶点偏向于与低度数顶点相关联，则称该网络为异配网络。 2 3 网络机制模型 以上我们主要总结了对于实际网络的静态性质的统计【4 2 】研究，这节我们去 看一看什么样的网络模型会展现这些特定的统计性质。这是研究网络上的动力学 模型的基础。如考虑不同网络上的传染病模型，用来描述接触性传染病的传播， 谣言在人群中的传播等现象，或者不同网络上的渗流模型。对于这些问题，我们 可以选择用微分方程来描述。例如以下l o g i s t i c 模型， 等- ( 1 一x 讧 ( 2 1 7 ) f 我们把口看成是健康人与受感染人之间发生接触并获得传染的几率。所以在此模 型中，所有个体是均匀混合的，没有局域近邻的概念，就好像是溶液中发生的化 学反应一样。或者我们这样来理解，把疾病看作只要接触就传染，那么p 的意 义是平均来看每一个体的近邻数目占所有人口的比例。因此，可见l o g i s t i c 模型的 背景是完全随机网络。作为补充，我们可以在规则网络上用模拟或者重整化群的 方法来研究同一问题。而作为模型真实背景的是人的社会交往的网络，这样一些 网络可以通过实证研究获得对其静态性质一定的认识。但是对于研究这些网络上 的动力学模型来说，更加广泛的研究还需要网络模型，而不仅仅是实际网络数据。 例如，人类相互认识的网络是s m a l lw o d d 网络，那么当我们研究这样的网络上的动 力学模型的时候，我们就需要一个相应特征的网络来作为我们的背景。当然，我 们可以收集这个网络的实际信息，然后在这个实际网络上进行分析。但是这有很 大的局限性，尤其对于理论研究。如果我们能够设计一个具有这些性质的网络演 化机制模型。那么我们进一步对网络上动力学模型的研究就可以以这些机制模型 复杂网络上的传染病模型研究 为基础。巍然，如果缎现现有的机制模型不能震现已有的几何饿质，我 订就需要 修改模型。本节中，我们将分别介绍规则网络和随机网络，s m a l lw o r l d 网络，s c a l e f r e e 网络熬鞔隶模型。 2 3 1 规划网络 早期，人们认为真实系统各因索之间的关系可以用一些规则网络表示，如一 缝链、：缳平嚣主煞妖尼矍褥疆秘等。雳熬最多豹篾裂网络蔑滋令苓煮缎减靛 全局耦含婀络，在一个全局耦合网络中，任意两个节点之间都有边直接相连( 图 2 7 ( a ) ) 。因此，在具有棚同节点数的所有网络中，全局耦合网络具有最小的平均路 径长瘦1 鞠最大懿凝聚系鼗1 。虽然全嚣藕合霹络蔽浚了诲多实鼯褥终吴奏豹囊震， 但该模型作为实际网络模型的局限饿也是很明显的；一个有个点的全局耦合网 络有( 一1 ) 2 条边。然而大多数大型的实际网络都是很稀疏的。 一今缮爨大量骚究煞稳巯戆麓瓣瓣络是蕞近邻糕会藕络，箕孛每一令帮杰廷窝 它周围的邻居节点相选。具有周期边界条件的最近邻耦合网络包含个围成一个 环的点，其中每个节点都与它左右备k 2 个邻居麓点相连，这熙是是一个偶数( 图 2 7 c o ) ) 。辩较大静芷蘸，最近邻藕会翔络熬聚类系数泌瓷 c 。一坐4 ( k 望- 1 ) 一三4 ( 2 1 8 )。”。一【z + 1 5 j 因蔻这群戆露络是褰凌浆类熬，然瓣，最近邻耧会瓣缮不莛一个套整赛瓣络，稳 反，对固定的足值，当点数很大时，该网络的平均路径长度为 k 。去”。 ( 2 1 9 ) 第2 章复杂网络基本概念及基本模型 桊 ( a )( b )( c ) 图2 7 几种规则网络：( a ) 全局耦合网络；( b ) 最近邻耦合网络；( c ) 星形网络 f i g2 7r e g u l a rn e t w o r k s ( a ) g l o b a lc o u p l i n gn e t w o r k ( b ) t h en e a r e s tn e i g h b o u rc o u p l i n gn e t w o r k ( c ) s t a rn e t w o r k 另外一个常见的规则网络是星形耦合网络( s t a rc o u p l e dn e t w o r k ) ，它有一个中心 点，其余的一1 个点都与这个中心点相连接，而它们彼此之间不连接( 图2 7 ( c ) ) 。 星形网络的平均路径长度f 4 l 】为 l 。- 2 一而2 ( t 。两- 1 ) 一2 ( 2 2 。) 星形网络的聚类系数为 c 。- 等一， 星形网络是比较特殊的一类网络。这是假设如果一个节点只有一个邻居节点，因 此星形网络的聚类系数为0 2 3 2 随机图 随机网络模型时由e r d o s - r e n y i 在1 9 5 9 年提出的【1 4 1 ，目前已经发展为数学中 非常重要的一个分支，在交通，通信，计算机科学技术等许多工程实际领域都有 很重要的应用。随机网络理论在复杂网络研究中也扮演着举足轻重的作用。见图9 复杂网络上的传染病模型研究 图2 8 随机网络 f i g2 8r a n d o mn e t w o r k 图2 8 图中的网络为n = 2 4 个节点，m = 6 0 条边的网络，相应的系数p = 0 2 2 。该 网络是用e r 模型的生成方法产生，该图的平均度数吐 = 5 。 随机图理论最早提出的成形的网络模型，随机图网络定义如下： 个固定节点， 个边是从掣个可能边中随机选取。连通概率尸是指任 意两个节点相连接或者说这两个节点间存在边的概率 p 玎( 趔尘尘) ( 2 2 2 ) 由个节点和 个随机边可构成c ；( ，一d 个等价的构型。 e r 随机图的平均度是t k 一p ( 一1 ) 一p 。设三b 是e r 随机图的平均路径 长度。直观上，对于e r 随机图中随机选取的一个点，网络中大约有tk ，k 个其 他的点与该点之间的距离等于或非常接近于工积因此，n * t k ) “，即 l e a i n n i i n k e r 随机图中两个节点之间不论是否具有共同的邻居节点，其连接概率均为p 。 因此，e r 随机图的聚类系数是c - p - n ( 1 ，这意味着大规模的e r 随机 图凝聚系数小。 固定e r 随机图的平均度c k ，不变，则对于充分大的，由于每条边的出现 与否都是独立的，e r 随机图的度分布可用p o i s s i o n 分布来表示 p c 七，一( 譬) p o p ，”4 一半 c z 乃， 第2 章复杂网络基本概念及基本模型 其中，对固定的女，当趋于无穷大时，最蔚的近似等式怒精确成立的。因此，e r 随机图也称为“p o i s s i o n ”随机圈。 圉2 9p o i s s o n 分布的度分布 f i g 2 9d e g r e ed i s t r i b u t i o no ft h ep o i s s o nd i s t r i b u t i o n 黧2 9 。当n 缀大鞋，夔帮蝴络发兹分礞遮织手p o i s s o n 分毒，该嚣巾骥鳖撂是 代表度数，纵坐标是经过归一亿后的度的概率分布僵。 尽管e r 随机图作为实际复杂网络的模嬲存在明显的缺陷，在2 0 墩纪的后4 0 年孛，e r 蕤秘霆瑗论一壹是磁究复杂嚣终掇羚豹萋本理论，冀孛豹一黧摹本愚鏊 在霸前的复杂网络理论研究中仍然很重要。人们可以从多个角度对e r 随机图进行 扩展以使其更加接近真实的刚络。真实的图的最简单的一个性质是非p o i s s o n 分布， 这戴楚象谓豹“懿黉貘型”。 2 3 3 小世界网络 小世界网络的 氍念是来源予个由s t a n l e ym i l g m m ( k l e i n b e r g ，2 0 0 2 ) 1 5 】设计 豹穆鬻著名静安黢。1 9 6 7 年，章圭会心瑾学家s t a n l e ym i l g r a m 蠢屠往在美灏n e b r a s k a 和k a n s a s 两地的随机选择的几百个人寄出了封具有相同内容的信件。信件内容 是告诉这些人，将这封信转交绘屠住在b o s t o n 的两个“鞠橡”人物中的一个。信 串网噩雩指出，翔莱纯稍叁己不认识这两个嚣标人物的话，藏请将新转交给叁己酝 复杂网络上的传染病模型研究 熟悉的人中自己认为他( 她) 最有可能认识目标人物的人。后续的收信人都按照相同 的方式向下转发。信中给出的关于目标人的信息有目标人物的名字，家庭住址和 职业。同时要求每个经手人寄一张明信片给m i l g r a m ，这样m i l g r a m 可以记录下每 封信的转发路径。最后的结果显示，一般只需要大约6 次转发，信就可以到达目 标人物的手中。这就是著名的“六度论”的由来，也是世界上第一证明世界是小 世界的实验。 规则的最近邻耦合网络具有高聚类特性，e r 随机图具有小的平均路径长度， 因此这两类网络模型都不能再现真实网络的一些重要特性，毕竟大部分的实际网 络既不是完全规则的，也不是完全随机的。在现实生活中，人们通常认识他们的 邻居和同事，但也可能有少量的远在异国他乡的朋友。小世界网络被定义为既具 有较短的平均路径长度又具有较高的凝聚系数的网络。下面来介绍它的构造方法。 作为从完全规则网络向完全随机图的过渡，w a t t s 和s t r o g t z 于1 9 9 8 年引入了 一个有趣的小世界网络模型，称为w s 小世界模型【1 】ow s 小世界模型的构造算法 如下： 从规则图开始：考虑一个含有个点的最近邻耦合网络，它们圈成一个环， 其中每个节点都与它左右的相邻的各j “2 节点相连，k 是偶数。 随机化重连：以概率p 随机地重新连接网络中的每条边，即将边的一个端点 保持不变，而另一个端点取为网络中随机选择的一个节点。其中规定，任意两个 不同的节点之间至多只能有一条边，并且每一个节点都不能有边与自身相连。 在上述模型中，p 一0 对应于完全规则网络，p - 1 则对应于完全随机网络，通 过调节p 的值就可以控制从完全规则网络到完全随机图的过渡，如图1 0 所示。 o 蛰 ( a ) 1 7 a 】 第2 章复杂网络基本概念及基本模型 o ” ( b ) 图2 1 0 ( a ) w s 小世界模型( 随机化重连) ；f o ) r c w 小世界模型( 随机化加边) f 塘2 1 0 ( a ) w s 删w o r l dm o d e l n ws m a l lw o r l dm o d e l w s 小世界模型构造算法中的随机化过程有可能破坏网络的连通性。因此， n e w m a n 和w a t t s 稍后提出的n w 小世界模型6 】的具体构造算法如下： 从规则图开始：考虑一个含有个点的最近邻耦合网络，它们圈成个环， 其中每个节点都与它左右的相邻的各r 2 节点相连，k 是偶数。 随机化加边：以概率p 随机选取的一对节点之间加上一条边。其中规定， 任意两个不同的节点之间至多只能有一条边，并且每个节点都不能有边与自身 相连。 n w 模型只是将w s 小世界模型构造中的“随机化重连”改变为“随机化加边”。 并且当p 足够小时和足够大时，n w 小世界模型本质上就等同于w s 小世界模型。 小世界网络模型反映了实际网络所具有的一些特性，例如朋友关系网，大部分 人的朋友都是和他们住在同一个地方，其地理位置不是很远，或只在同单位工 作或学习的同事和同学。另一方面，也有些人住得较远的，甚至是远在异国他乡 的朋友，这种情形好比w s 小世界模型中通过重新连线或在n w 小世界模型中通 过加入连线产生的远程连接。 下面介绍小世界网络模型的一些统计性质。 ( 1 ) 凝聚系数 w s 小世界网络的凝聚系数为 c ( 小糕帅) 3 ( 2 2 4 ) n w 小世界网络的凝聚系数为 复杂网络上的传染病模犁研究 c q ) 一硒j a 再( k 画- 2 ) 石酉 ( 2 ) 度分布 对于基于“随机化重连”机制的w s 小世界模型，当k k 2 时有 p ) ( 2 ) ( 1 一py 1 1 9 ( x 2 ) - n 石( p = k i 2 丽) k - ( x 2 ) - e 。雎心 ( 2 2 6 ) 当k k 2 时，p ) 一0 。 对于基于“随机化加边”机制的n w 小世界模型，每个节点的度至少为k 。 因此当七k 时，一个随机选取的节点的度为k 的概率为 p ，t ( 。羔) ( 等) “5 ( ，一鲁厂“ c z 勿 而当k k 时p 他1 0 列表2 1 实际网络的度分布 t a b2 1d e g r e ed i s t r i b u t i o n si nt h er e a lw o r l d 第2 章复杂网络基本概念及基本模型 列表2 1 列表中包括所研究网络的实际对象( n e t w o r k ) ，大d , ( s i z e ) ，平均度值( ) ， 平均最短距离( 1 ) ，按随机网络算的最短距离( k 。0 ，平均集聚程度( c ) ，按随机网络 计算的集聚程度( c 枷通过对比实际网络与相应( 相同顶点数和边数) 随机网络的性 质，可以发现网络的s m a l lw o r l d 特征。 2 3 4 无标度网络 e r 随机图和w s d , 世界模型的一个共同特征在于网络的连接度分布都可近似 用p o i s s o n 分布来表示，该分布在度平均值ck ，处有一峰值，然后呈现指数快速衰 减。近年来，随着网络规模的不断增大，网络呈现了一些e r 随机图和w s 小世界模 型不能解释的现象，随着顶点和边以一定的方式加入网络，网络便以某种方式开 始生长。 2 3 4 18 a 无标度演化模型 不久前，b a r a b a s i & a l b e r t ( 1 9 9 9 ) i u i 在对许多真实世界的网络进行研究时发现 些特别的现象，首先每个节点的度数并不均匀，网络中总是存在几个具有较大 度数的点，另外，他们发现许多网络的度的分布函数呈现出幂律分布的特点。渐 渐地人们不断发现，诸如w w w ，i n t e r n e t 网络，分子网络等许多真实世界的网络 都呈现出幕律分布的度的特征。在1 9 9 9 年b a r a b a s i a l b e r t ( 1 9 9 9 ) 1 1 1 】提出了一种 新的网络模型，该模型主要具有以下性质： 增长( g r o w t h ) 特性：即网络的规模是不断扩大的。例如每个月都有大量的 新的科研文章发表，而w w w 上则每天有大量的新的网页产生。优先连接 ( p r e f e