（计算机应用技术专业论文）广义复杂网络上传染病阈值及其免疫策略研究.pdf

浙江大学硕士学位论文 摘要 摘要 复杂网络是以图论为基础而衍生的研究对象。作为一种有效的建模工具，它 被广泛应用于生物学、社会学、物理学等领域。传染病模型可描述疾病在人群中 传播的动力学过程。其中的s i s 模型是在复杂网络上广泛应用的传染病模型之一。 对于传染病模型在复杂网络上的应用研究有以下方面的意义：( 1 ) 提供了针对传 染病扩散的数学化的研究手段；( 2 ) 与药物免疫、个体隔离等微观手段不同，该 方法提供了一种新的宏观的免疫思路；( 3 ) 其规划方案的全局性能为政府机构提 供科学决策的依据；( 4 ) 其与计算机病毒扩散的相似性能为计算机病毒的免疫提 供帮助。 在s i s 模型应用于接触网络的研究方面，这些网络的节点往往是被无向无权 的边连接，并满足一定的统计规律。而本文研究了在广义复杂网络上s i s 传染病 模型的阈值问题和免疫问题。由于广义复杂网络可以包含不同类型的节点和边， 因此可以更精确的描述现实环境。本文的工作包含如下几方面： ( 1 ) 提出并证明了复杂网络上传染病灭绝的充分必要条件是其相应的参数化 邻接矩阵的谱半径小于l ，模拟结果符合这个论断； ( 2 ) 将该结果还应用于评估免疫策略的效率。本文以传统的平均免疫、随机 免疫、目标免疫和熟人免疫为例给出了分析示例，表明目标免疫效果最佳，与其 他文献的认识基本一致； ( 3 ) 设计了若干个算法，可以在参数化邻接矩阵已给定的情况下用于精确地 找到最优免疫策略，以及快速地找到近似免疫策略。这些算法的有效性在模拟实 验中得到了验证。 本文的工作可以应用到相关领域的数值计算、符号推导等方面，也可推动计 算机网络方面的免疫设计。而在未来，广义社会网络有望进一步发展成为动态社 会网络，作为这一领域研究的新趋势。 浙江大学硕士学位论文 摘要 关键词： s l s 模型，复杂网络，传染病阈值，特征值，免疫 a b s t r a c t c o m p l e xn e t w o r ki sa r e s e a r c ho b j e c tb a s e do ng r a p ht h e o r i e s a sa ne f f e c t i v e m o d e l i n gt o o l ，i ti sa p p l i e di nb i o l o g y , s o c i o l o g y , p h y s i c s ，e t c e p i d e m i cm o d e l s c a r l d e s c r i b e t h ed y n a m i c s o f e p i d e m i c s p r e a d i n ga m o n g i n d i v i d u a l s t h e s u s c e p t i b l e i n f e c t e d - s u s c e p t i b l e ( s i s ) m o d e li so n e o ft h em o s tw i d e l yu s e de p i d e m i c m o d e l si nc o m p l e xn e t w o r k s t h es i g n i f i c a n c e so ft h er e s e a r c ho ne p i d e m i cs p r e a d i n g i nc o m p l e xn e t w o r k sa l ea sf o l l o w s ：( 1 ) i tp r o v i d e sam a t h e m a t i c a la p p r o a c hf o r e p i d e m i cs p r e a d i n g ；( 2 ) d i f f e r e n t f r o mm i c r o s c o p es t r a t e g i e ss u c h 邪d n 玛 i m m u n i z a t i o na n di n d i v i d u a li s o l a t i o n ，i tp r o v i d e sam a c r o - v i s i o no ni m m u n i z a t i o n ；( 3 ) n eg i o b a ls t r a t e g yi tp r o v i d e dc a nh e l pt h eg o v e r n m e n tm a k es c i e n t i f i cd e c i s i o n s ；( 4 ) t h es i m i l a r i t yb e t w e e ne p i d e m i c sa n dc o m p u t e rv i r u sc a nm a k et h i sr e s e a r c hh e l p c o n t r o lt h ec o m p u t e rv i r u s w h e ns i sm o d e li sa p p l i e do nc o n t a c tn e t w o r k s ，t h e s en e t w o r k sm o s t l yc o n s i s to f n o d e sc o n n e c t e db yu n d i r e c t e da n du n w e i g h t e de d g e sf o l l o w i n gc e r t a i ns t a t i g i c a l p r o p e n i e s ，w h e r e a st h i sd i s s e r t a t i o nc o n s i d e r st h e t h r e s h o l da n di m m u n i z a t i o np r o b l e m f o rt h es i sm o d e lo ng e n e r a l i z e dn e t w o r k st h a tm a yc o n t a i nd i f f e r e n tk i n d so f n o d e s a n de d g e sw h i c ha r ev e r yp o s s i b l ei nt h e r e a ls i t u a t i o n t h e s ew o r k si n c l u d e ： ( 1 ) i ti sp r o p o s e da n dp r o v e dt h a ta ne p i d e m i c w i l lb e c o m ee x t i n c ti fa n do n l yi f t h es p e c t r a lr a d i u so ft h ec o r r e s p o n d i n gp a r a m e t e r i z e da d j a c e n tm a t r i x ( p a m ) i s s m a l l e rt h a n1 ，w h i c hi sv e r i f i e db ys i m u l a t i o nr e s u l t ( 2 ) b yt a k i n g u n i f o r mi m m u n i z a t i o n ，r a n d o mi m m u n i z a t i o n ，t a r g e t e d i m m u n i z a t i o na n da c q u a i n t a n c ei m m u n i z a t i o na se x a m p l e s ，t h i sp r o p o s i t i o ns h o w s i t s a b i l i t yo fe v a l u a t i n gt h ee f f i c i e n c yo f i m m u n es t r a t e g i e s ( 3 ) s e v e r a lm e t h o d sa r ed e v e l o p e dt h a tc a np r e c i s e l y f i n dt h eo p t i m a li m m u n e s l ：r a t e g i e s ，a n dq u i c k l y f i n dt h ea p p r o x i m a t e do p t i m a li m m u n i z a t i o n ，f o r n e t w o r k sw i t h t h eg i v e np a m t h ec o n t r i b u t i o no ft h i sd i s s e r t a t i o nc a nb eu s e di nn u m e r i c a lc o m p u t a t i o na n d s v m b o l i cd e d v a t i o ni nr e l a t i v ea r e a s ，a n dc a np r o m o t e t h ed e s i g no fi m m u n es t r a t e g i e s 浙江大学硕士学位论文a b s t r a c t i nc o m p u t e rn e t w o r k s f i n a l l yi nt h i sd i s s e r t a t i o n ，t h es u m m a r yi sp r o v i d e da n dt h e f u t u r ed i r e c t i o no ft h ec o m p l e xn e t w o r kr e s e a r c ho ne p i d e m i c si sd i s c u s s e d i nt h e f u t u r e ，t h eg e n e r a l i z e dn e t w o r k sm a yd e v e l o p e dt ob e c o m ed y n a m i c a ls o c i a ln e t w o r k s ， s ot h a tt ob ean e wt r e n di nt h er e s e a r c ho ft h i sa r e a s i sm o d e l ，c o m p l e xn e t w o r k s ，e p i d e m i ct h r e s h o l d ，e i g e n v a l u e ，i m m u n i z a t i o n 浙江大学硕十学位论文图日录 图目录 图1 1s i s 模型中一个节点所能经历的状态变化的过程2 图2 1 感染比例( i n f e c t i o nr a t e ) 与a 耵的关系图。三条重合的线分别表示在 第5 0 0 步( 蓝色实线) 、第1 0 0 0 步( 红色虚线) 以及第1 5 0 0 步( 绿色 点线) 时，a , u 与感染比例的数值关系。每条线都是取5 轮模拟后的平均 1 ) i 【。11 图2 2 感染比例( i n f e c t i o nr a t e ) 与时间的关系图。蓝色实线表示平均自1 0 0 轮、每轮2 0 0 步的模拟后结果，而红色虚线则是来自公式( 2 5 ) 的结果。 本图对应的网络节点数为1 0 。1 3 图2 3 感染比例( i n f e c t i o nr a t e ) 与时间的关系图。蓝色实线表示平均自1 0 0 轮、每轮2 0 0 步的模拟后结果，而红色虚线则是来自公式( 5 ) 的结果。 本图对应的网络节点数为1 0 0 。1 3 图2 4 感染比例( i n f e c t i o nr a t e ) 与时间的关系图。蓝色实线表示平均自1 0 0 轮、每轮2 0 0 步的模拟后结果，而红色虚线则是来自公式( 5 ) 的结果。 本图对应的网络节点数为1 0 0 0 。1 4 图4 1 寻找最优免疫策略的算法流程图2 5 图4 2 感染比例( i n f e c t i o nr a t e ) 与时间的关系图。在这张图中，被免疫的 节点占总节点的比例为上图o 1 ，下图0 2 。图中的每条线表示在节点数 为5 0 的e r 随机网络上，分别采用以下免疫策略所得到的模拟结果：随 机免疫( 黑色) ，目标免疫( 蓝色) ，熟人免疫( 青色) ，最优免疫( 红 色) ，近似最优免疫( 紫色) 。每种免疫都是在同样的初始条件下执行。 每条线都是平均自5 0 次在5 个不同网络上的模拟结果。2 7 图4 3 感染比例( i n f e c t i o nr a t e ) 与时间的关系图。在这张图中，被免疫的 节点占总节点的比例为上图o 3 ，下图o 4 。图中的每条线表示在节点数 为5 0 的e r 随机网络上，分别采用以下免疫策略所得到的模拟结果：随 机免疫( 黑色) ，目标免疫( 蓝色) ，熟人免疫( 青色) ，最优免疫( 红 色) ，近似最优免疫( 紫色) 。每种免疫都是在同样的初始条件下执行。 每条线都是平均自5 0 次在5 个不同网络上的模拟结果。2 8 图4 4 感染比例( i n f e c t i o nr a t e ) 与时间的关系图。在这张图中，被免疫的 节点占总节点的比例为上图0 1 ，下图0 2 。图中的每条线表示在节点数 为1 0 0 0 的e r 随机网络上，分别采用以下免疫策略所得到的模拟结果： 随机免疫( 黑色) ，目标免疫( 蓝色) ，熟人免疫( 青色) ，近似最优免 疫( 紫色) 。每种免疫都是在同样的初始条件下执行。每条线都是平均 自1 0 次在5 个不同网络上的模拟结果。2 9 图4 5 感染比例( i n f e c t i o nr a t e ) 与时问的关系图。在这张图中，被免疫的 节点占总节点的比例为上图0 3 ，下图o 4 。图中的每条线表示在节点数 为1 0 0 0 的e r 随机网络上，分别采用以下免疫策略所得到的模拟结果： u 浙江大学硕士学位论文 图h 录 随机免疫( 黑色) ，1 7 1 标免疫( 蓝色) ，熟人免疫( 青色) ，近似最优免 疫( 紫色) 。每种免疫都是在同样的初始条件下执行。每条线都是平均 自1 0 次在5 个不同网络 二的模拟结果。3 0 图5 1 一个现有交通灯控制算法的控制流程图阁3 6 b i 浙江大学硕士学位论文第1 章绪论 第1 章绪论 1 1 研究背景 传染病问题长期以来一直对人类的生活有着重要的影响。仅列入中国甲、乙 类法定报告的传染病就有鼠疫、霍乱、病毒性肝炎、伤寒副伤寒、艾滋病在内的 多种性传染病等数十种，其中2 0 0 8 年病毒性肝炎和肺结核的发病率分别高达l o 万人1 0 6 5 4 和8 8 5 2 ，鼠疫和人禽流感的病死率均高达1 0 0 ，狂犬病和艾滋病的 病死率则分别高达9 6 。2 3 和5 3 。5 7 【1 1 。另有研究指出，截止2 0 0 5 年已知的人类 病原体有1 , 4 0 7 种，其中5 8 是人畜共患疾病，即可感染其他宿主物种【2 】。在这 1 , 4 0 7 种病原体中，有1 7 7 种是新出现或消失后再现的病原体【2 】。人畜共患疾病 与仅在人群中传播的疾病相比，将具有更强的生存能力和传播能力。 尽管疫苗的广泛应用、治疗手段的提升以及病例发现和处置方案的改进，使 得传染病的扩散能力与过去相比有一定下降，传染病大规模扩散的威胁依旧存 在。新兴的传染病病原体例如s a r s ，h 1 n 1 往往使我们对传染病的控制措手不及； 传统的病原体如a i d s 则往往由于病毒携带者的隐蔽性而给健康人群的预防带来 了困难。这些不利因素使得决策者在面对大规模人群的疫病控制时难以抓住重 点。 为解决这个问题，本文分析了传染病模型及其接触网络的研究现状，并经过 推导、证明以及实验模拟，得出了传染病的阈值规律和找到最佳免疫策略的方法。 1 2 传染病模型 传染病的传播模型与人群中特定疾病的传播有关，致力于描述疾病的动力学 特征并设计控制策略以消除该传染病【3 】。数理流行病学在2 0 世纪中期以后进入快 速发展期【3 】。理论过程往往基于这样的假设：在每一时刻将整个群体根据群体内 个体的不同状态划分成若干个组。在比较常见的s i s ( 易受感染态一被感染态 一易受感染态) 模型和s i r ( 易受感染态一被感染态一被移除态) 模型中， 浙江大学硕i ：学位论文第l 章绪论 个体存在于网络的每个节点，并且疾病通过邻居关系以一定概率传播。在s i s 模 型中，个体被感染后一段时间能再次恢复健康成为易受感染态，而在s i r 模型中， 个体被感染后经过一段时间即被移除。 在研究这两个模型时，比较常见的假设是均匀混合假设，即每个个体以相同 的概率随机选择其他个体接触作为接触对象【4 】。由此可以写出相应的微分表达式 【3 1 。更完善的表达形式是针对具体网络的统计量或网络特征对传播动力学进行描 述。 s i s 模型的称谓来源于它的英文表达：s u s c e p t i b l e ( 易受感染态，简称易染) 一i n f e c t e d ( 被感染态，简称感染) - - s u s c e p t i b l e ( 易受感染态，简称易染) 。s i s 模型是数理流行病学领域的基本主题之一【5 】。在基本的s i s 模型中，在任意一个 时间片内：每个个体或者是易染，或者是感染；并且，每个易染者能被邻居感染 者以君的概率转化成感染者；而每个感染者能以再的概率自动愈合而恢复为易感 者。如 图1 1 所示。这个模型及其许多衍生模型【6 ，7 ，8 】可被用于模拟许多病毒在群体 中的扩散。 易受感染 图1 1s i s 模型中一个节点所能经历的状态变化的过程 2 染态，i 浙江大学硕士学位论文第l 章绪论 1 3 传染病模型在复杂网络上的应用 传染病在人群中既可以以爆炸性的速度传播，也可以在一个低水平的状态下 长期存在。这和传染病所处的接触网络的结构有重要关系。 现实中的复杂网络往往具有小世界特性和无标度分布特性。小世界特性是指 节点间的平均最短路径随网络大小的增长关系最多呈指数级【1 0 1 。无标度特性是指 现实中大量网络表现出的幂律( p o w e rl a w ) 形状的度( d e g r e e ，与节点连接的边 的条数) 分布，即p ( 玉) 一a 七一，其中k 是度数变量，4 和1 是常量【1 1 】。 最近，自p a s t o r - s a t o r r a s 和v e s p i g n a n i 1 2 , 1 3 j f l ：始，网络结构对疾病传播速度的 影响问题开始有了大量的讨论 3 , 1 4 , 1 5 】。这些研究对多种尺度下的传染病问题构造了 不同的传播网络模型 1 6 , 1 7 , 1 8 】。 s i s 模型在网络上的传播也同样受到网络结构的重要影响。当s i s 模型用于 接触网络时，传染病阈值足数理流行病学的一个重要标准量1 1 2 】。受病毒类型和网 络结构的影响，当传染病的某些属性高于阈值时，该传染病将持续存在，而当低 于阈值时，该传染病将灭绝。对于s i s 模型在接触网络上阈值的研究在早期常常 基于异质或均质假设的网络【1 9 1 ，或网格网络【2 0 】；近年来常常基于带权网络【2 1 1 ，或 无权无向网络例如节点关联网络( c o r r e l a t e dn e t w o r k s ) 1 2 2 】和无标度网络( s c a l e f r e e n e t w o r k s ) 1 1 3 。所有这些网络均服从特定的统计指标【3 】o 在无权无向网络上，yw a n g 等 2 3 , 2 4 ，h e t h c o t e l 2 5 和m o e zd r a i e f l 2 6 还提供了从邻接矩阵特征值角度求解传染病 詹 1 阈值的方法。其中yw a n g 等【2 3 刀】证明了在无权无向网络上传染病阈值为；= _ j l ， na 这里入是无权无向网络对应邻接矩阵的最大特征值。 然而，大多数真实网络的最佳描述方式应当是一种广义网络：它的边可以是 无权无向边，也可以是有权边【2 刀、有向边 2 8 】或重边；它的节点也可以是带权节点。 这是因为，现实生活中每个个体得到的保健服务( 带权边和有向边) 、个体问的 接触频率( 重边) 、个体的免疫力( 带权节点) 等等会有所差别。但是广义网络 的传染病阈值问题目前很少有工作涉及。 本文首先对文献 2 3 2 4 的工作进行了推广，将基本的s i s 模型放在广义网络 3 浙江大学硕士学位论文第1 章绪论 上加以研究，提出并在理论上证明了：当且仅当其参数化邻接矩阵( p a r a m e t e r i z e d a d j a c e n tm a t r i x ，简称p a m ) 的谱半径小于l 时，一种传染病才会趋于灭绝。这 一命题框架可以帮助研究人员评价免疫策略的效率，并且本文以几个常见的免疫 策略【2 9 。3 6 】为例进行的评估其结论与之前的研究结果相近。区别予这些常见的免疫 策略，基于此命题本文还提供了一个适用于广义网络并且可以精确找到最优免疫 策略的方法。 1 4 复杂网络上的传染病模型研究意义 s i s 模型在网络上的扩散研究可以用于模拟和解释感染在群体中的扩散，包 括人类传染性疾病1 3 8 】和计算机病毒的扩散 1 2 , 3 7 等。 广义上说，研究传染病模型在复杂网络上的扩散特性有如下几个方面的意 义： ( 1 ) 提供了针对传染病扩散的数学化的研究手段。通常的社会学实证方法， 例如问卷调查等，获得的数据量少，而且难以进行有效建模。而复杂网络本身就 是一个很好的建模工具，并且在建模后能提供数学化的解决方案。 ( 2 ) 在传统的传染病免疫领域，提供了一种新的免疫思路。与药物免疫、 个体隔离等微观手段不同，通过复杂网络角度获得的免疫策略可以为决策者提供 全局的规划方案，并促进传统免疫策略发挥更好的效用。 ( 3 ) 能为政府机构提供科学决策的依据。由于基于复杂网络的方法其规划 方案具有全局性，因此这些方案可以帮助政府制定相应的宏观政策。 ( 4 ) 能对计算机病毒的免疫提供帮助。计算机病毒扩散的许多特征与传染 性疾病的传播特征有许多相似之处，而很多的计算机病毒本质就是基于网络扩散 的，因此一般的传染病模型只要稍加调整并根据相应的传播网络运用复杂网络的 手段进行建模，就能用于设计计算机病毒的控制策略。 因此，复杂网络上传染病模型的研究对于控制传染性疾病的扩散有着重要的 意义。 4 浙江大学硕十学位论文第l 章绪论 本文的结构如下：第1 章介绍了传染病与复杂网络的相关背景及研究意义。 第2 章提出并证明了广义网络上的传染病阈值问题。第3 章从阈值理论的角度对 传统的免疫方法作了分析。第4 章根据该理论构造了一个设计最优免疫策略的算 法。第5 章是对本文内容作了总结，并展望了传播网络的研究趋势。 1 5 本章小结 本章主要介绍了复杂网络及传染病模型的基本特点和发展历史，并总结了传 染病模型发展建立的历史以及常见的s i s 和s i r 模型，最后介绍了传染病模型在 复杂网络上的应用情况，包括应用范围、应用形式、传播阈值问题等，而且阐述 了本文的创新性及研究意义。 5 浙江大学硕士学位论文第2 章广义网络上的传染病阈值理论 第2 章广义网络上的传染病阈值理论 2 1 理论的提出及证明 首先，本文定义用于描述广义网络和传播状态的符号。 y w a n g 等【2 3 矧引入了系统矩阵( s y s t e mm a t r i x ) ， s = 侈a + ( 1 6 ) ， 公式( 2 1 ) 其中a 无权无向网络的邻接矩阵，是单位矩阵。与之类似，本文定义一个参数化 邻接矩阵( p a m ) 来帮助推导。 定义1 令m 是一个住卑讹的p a m ，并且每个元素满足 = 翌帕f o 眙ri # 歹j 公式( 2 2 ) 其中铊是网络的大小，屈；是节点澈节点趟过两者之间的连接边感染的概率，6 ，是 节点i 被治愈的概率。有趣的是，眠。也可以被认为是当前时刻的节点澈前一时刻 的节点主感染的概率，即一条从节点蕾出发又回到节点i 的边的权重。这种边在无向 图中也称为自环。 显然的，当没有边从节点连向节点z ( i f ) 时， z i ，= 0 。由于8 f 0 ，l 而 且6 o 。1 1 ，m 的每个元素一定是非负的，因此m 是非负矩阵。 对于系统矩阵的这一修改使得用其描述广义网络成为可能。在重边的情况 下，所有连接自节点7 、连向节点i 的边可以被一条具有如下权重的边取代： m i d 烹l 一( 1 一鼻) ，f o ri 歹 公式( 2 3 ) 五- 盘1 其中，照t 七是从节点彳连向节点i 的第五：条边的感染概率。 定义2 令只是一个n 囊1 的向量，其中的每个元素a 。表示节点疵t 时刻处于被感染 状态的概率。 6 浙江大学硕士学位论文第2 章广义网络上的传染病阈值理论 由于在时刻，节点i 不被节点蠡( i 岛) 感染的概率是1 一m 法掌融而节点i 不感染自己、即治愈的概率是1 一m 越幸p i 因此若假设只。的每个元素在计算b 时 是独立的洲，则有 1 一鼽t + 1 = ( 1 一佻，知宰m t ) 公式( 2 4 ) 鼻= 1 由此可得 藏件l = 1 一i i 1 一m 1 七丰p k t ) 玉掌1 公式( 2 5 ) 注意当且仅当网络的最大组成块( 1 a r g e s tg i a n tc o m p o n e n t ) 【3 】足够大时，文献【2 4 】 和公式( 2 5 ) 中采用的独立假设成立。否则，在实际情况中公式( 2 5 ) 的右侧 表达式将成为左侧表达式的上限，详细内容将在2 3 中讨论。 这两个定义将引出本文的第一个要点：对于任意一个网络，只要它每条边的 传播概率和每个节点的愈合概率给定，研究者通过本文给出的结论立刻就能知道 在该网络上的传染病是否会灭绝。 命题1 在s i s 模型框架内，当且仅当a 材 o ，只会很 小以至于纵。的高次幂可以忽略不计，因此有 1 一n ：1 ( 1 一m 1 七木触i ) ：1 ，嗽，玉术张，l 这表明当t k ，帮会和印一样向0 收敛。口 不同于其他文献中的类似定理，本文的推导过程不需要这样的假设：很小的 p i ( 该假设在病毒刚开始传播时成立，但并非总是成立) t 2 3 3 揪d 、的绫，；( 当每 个时间片代表一段很短的实际时间时成立，但也并非总是成立) 【3 9 1 。 定理1 表明一种在给定网络上传播的传染病会灭绝的充分必要条件是系统 毋+ l = m p t ( 公式( 2 6 ) 的向量形式) 会收敛到0 。 定理2 一个动力系统户= ( m 一歹) p 是渐近稳定的当且仅当m ( 爻射一，) 0 ，其中 r e ( a m 一，) 是矩阵m 一，的所有特征值实部的最大值。 证明。该动力系统渐进稳定的充要条件是矩阵m 一，每个特征值都有负的实部 4 0 l ，即鼢( a 村一j ) 0 。口 定理3 一个动力系统只毒，= m 只是渐近稳定的当且仅当a w 1 ，其中a 置，是一个 实数，并且是矩阵m 的一个取模后绝对值最大的特征值，也是矩阵m 的谱半径。 证明 尼年l 嚣财p t 铮 公式( 2 8 ) p = a p = 只+ l 一只= m p t 一只= ( m 一，) p 只要公式( 2 8 ) 中的两个动力系统等价、并且矩阵m 一厂的各个特征值实部比矩 阵m 对应的各个特征值实部大l ( 通过比较它们的特征方程易得) ，定理2 中关于 声篇( m 一，) p 渐近稳定的充要条件的描述就可以等价地表示为：只+ l = m p ，渐 近稳定的充要条件是r e ( a 射) 1 ，其中r e f a 材) 是矩阵m 所有特征值的最大实部。 浙江大学硕士学位论文第2 章广义网络上的传染病阈值理论 由定义可知m 是非负矩阵，而关于非负矩阵有如下描述：取模后值最大的特 征值必定是一个实数，并且这也是唯一的一个特征值它的实部大于其他特征值的 实部【4 1 1 。因此( a a ，) = a 材。 所以，在本定理中a w l 是充要条件。口 定理4 在s i s 模型框架内，在网络上传播的疾病会灭绝的充要条件是入m 1 。 证明根据定理3 ，如果a m 1 ，系统只：艏只一，是渐近稳定的，即 l i r a 只= 0公式( 2 9 ) 0 + 。c _ 【柏】，并且根据定理l 可以得到如下结论：每个节点处于感染状态的概率会下降至 0 。因此，通过这个网络传播的疾病会最终灭绝。 反之亦然。口 对于命题l 的证明结束。 定理5 ( 指数级衰减) 在s i s 模型的框架内，当一个传染病正在衰减，每个节点 被感染的概率呈现关于时间的指数级衰减。 证明正如定理1 所述当拥有相同初始值时掣s 舻，并且根据特征分解( e i g e n d e c o m p o s i t i o n ) m 2 = q a 。q 一1 公式( 2 1 0 ) 其中 是对角矩阵且f a l 村= a i 材( a 以，矩阵m 的第i 个特征值) ，q 是一个矩阵它的 第i 列是对应于九的特征向量。由此可知，在疾病传播的动力系统中， 只+ t m p f = 掰h 1 e o = q a 件1 q 一1p o ， q ( a 1 ，材幸，) 。+ 1 q - 1 p o a t l + a l ，母c 9 公式( 2 1 1 ) 浙江大学硕士学位论文第2 章广义网络上的传染病阈值理论 其中c 是一个对于任意矩阵m 都存在的常向量。 从公式( 2 1 1 ) 可知，如果入1 肘 1 ，根据定理4 即如果传染病会灭绝，只将 至少以指数级衰减。这一结论在无权无向网络上与文献 2 4 的结论一致。口 2 2 模拟方法验证理论结果 这个例子将说明一个模拟的结果如何满足本命题l 。为简化起见，本文引入 _ 系列由e r 随机图f 4 2 】修改而来的有权有向随机网络。节点数量为1 0 0 0 ，节点的 平均度数约为1 0 。每个节点的治愈率和每条边的传染概率是服从在( 0 ，1 ) 区间均匀 分布的随机数。扁也是一个随机向量。这一系列传播网络的唯一区别是它们的谱 半径a m ，在0 到2 的范围内以0 0 1 的步长变化。谱半径a a ，的变化可以通过以下 方式实现： 令m - - m a m 奉a ，其中入是希望获得的谱半径。据此产生的m 有时可能会违 背7 托f f l 的要求；如果这种情况发生，这个m 应当被丢弃，并重新产生一次， 直到获得需求的斛为止。 图2 1 显示了在0 a m 2 的情况下第5 0 0 步，1 0 0 0 步和1 5 0 0 步时被感染 节点的比例。三个时刻的感染比例( i n f e c t i o nr a t e ) 曲线基本重合表明感染比例 在5 0 0 步以后变化很小，因此在本文的模拟中，5 0 0 步可以认为是一个足够长的 时间来判断一种传染病是否会进一步持续。 注意到在图2 1 中a a ，的实际阈值距离l 大约有+ 0 0 3 的微小偏移，这正是由 于在下一节将要讨论的独立假设造成的。在后面的讨论中可知，当网络越大，这 样的偏移越小，反之亦然。另一方面，在几次试验中这个偏移量基本保持不变表 明可能存在一个甚至不需要独立假设的模型。 1 0 浙江大学硕士学位论文 第2 章广义网络上的传染病阈值理论 j 叱 c o j o e t - 图2 1 感染比例( i n f e c t i o nr a t e ) 与a ，的关系图。三条重合的线分别表示在第5 0 0 步( 蓝色 实线) 、第1 0 0 0 步( 红色虚线) 以及第1 5 0 0 步( 绿色点线) 时，a ，与感染比例的数值关系。 每条线都是取5 轮模拟后的平均值。 2 3 对独立假设的讨论 在本文以及文献 2 4 】中采用的独立假设有其应用范围的限制。首先回顾一下 公式( 2 5 ) ，来看看这个公式如何利用只计算忍斗2 ： p i h 2 = l 一( 1 一纵h 1 ) 玉= l ，t“ 公式( 2 12 ) = 1 一i i ( 1 一挑，奄枣【l 一( 1 一m 磨，尥拳p k 2 , t ) 】) e - - - - - 1 b g , 一- - i 公式( 2 1 2 ) 的最后一步不仅需要只的各个元素间的相互独立，也需要m i 詹和7 您知胞 之间的相互独立，因为在m 弧署1 1 p k 抖，乘积的过程中他们之间的独立性也是必要 浙江大学硕士学位论文第2 章广义网络上的传染病阈值理论 的。但是由于在公式( 2 1 2 ) 中，对于给定的i ， 变量m 玉娩 ( 南= 1 ，2 ，n ；k 2 = l 。2 ，札) 覆盖了矩阵m 的所有元素，而变量t t 弧( i = 某一 常量，o 后= 1 ，2 ，n ) 覆盖了矩阵m 中第i 列的所有元素：这两个变量将不得不分享 矩阵m 的同一列，因此佻和p 詹h l 乘积过程中的独立性将无法满足。即在此过程 中恰好有d , 2 中的扎个变量违反了独立假设。 由于在计算公式( 2 1 2 ) 的过程中有占总数n n z = 王他的变量会相互关联， 一个显然的消除关联性的方法是增大网络的节点数，特别是增大最大组成块的节 点数，因为孤独节点的增加将无助于减少这种的依赖性。 从r 推导到忍+ 2 是一个与上文类似的迭代过程。因此，最大组成块的节点数 的增加能减少公式( 2 5 ) 和实际情形之间的偏移。并且，注意到在公式( 2 1 2 ) 中，p i t + 2 是随着m l , k 的增大而增大的，这个正关联性表明在现实情况中p i f + 2 是小 于公式( 2 1 2 ) 中的理论值的，因而也印证了图2 1 中模拟阈值相对于理论阈值 的正偏移。 图2 2 ，图2 3 ，和图2 4 显示了传染病在三类网络中的扩散比较。这三类网 络均是无权无向平均度数为l o 的随机图f 4 2 】，它们的p a m 拥有共同的谱半径1 0 ， 并且初始向量r 是随机的且服从相同的分布。这三类网络的唯一差异是它们的大 小。图2 2 ，图2 3 ，和图2 4 表明，只要其他网络参数不变，公式( 2 5 ) 在描述 真实网络动力系统时，其精度会随着网络的增大而提高。从这些图中同样可以看 出，) 的实际值是小于理论结果的，因此如上一节所述会导致一个更大的阈值。 尽管网络节点数的增加能使得本文的独立假设更加合理、从而使得本文的命 题更加精确，在网络大小不变的情况下，网络结构、平均度数等因素也能影响独 立假设的合理性。例如，在b a r a b i s i - a l b e r t 提出的无标度网络模型【4 3 】中，许多低 度数节点只和极小部分网络演化初期的节点有连接，因此会增加低度数节点之间 的依赖性。受本文讨论主题的限制，本文将不再扩展讨论此话题。 浙江大学硕士学位论文第2 章广义网络上的传染病阈值理论 图2 2 感染比例( i n f e c t i o nr a t e ) 与时间的关系图。蓝色实线表示平均自1 0 0 轮、每轮2 0 0 步的模拟后结果，而红色虚线则是来自公式( 2 5 ) 的结果。本图对应的网络节点数为1 0 。 图2 3 感染比例( i n f e c t i o nr a t e ) 与时间的关系图。蓝色实线表示平均自1 0 0 轮、每轮2 0 0 步的模拟后结果，而红色虚线则是来自公式( 5 ) 的结果。本图对应的网络节点数为1 0 0 。 1 3 虫i叱coil。ajui o苟芷con3ajui 浙江大学硕士学位论文第2 章广义网络上的传染病阈值理论 图2 4 感染比例( i n f e c t i o nr a t e ) 与时问的关系图。蓝色实线表示平均自1 0 0 轮、每轮2 0 0 步的模拟后结果，而红色虚线则是来自公式( 5 ) 的结果。本图对应的网络节点数为1 0 0 0 。 2 4 本章小结 本章对广义网络上的传染病阈值问题进行了讨论。首先提出并证明了在s i s 模型框架内，当且仅当a m l 时，在广义网络中传播的传染病才会灭绝；并且当 一个传染病正在衰减时，每个节点被感染的概率呈现关于时间的指数级衰减。 之后提供了一个基于经典随机网络结构的模拟实例，既说明了应用的意义， 也表明了之前理论命题的具体表现形式。 最后对理论命题中的不足之处独立假设的必要性及其缺陷做了讨论和 分析，并认为可能存在一个甚至不需要独立假设的模型。 1 4 粤叱co写9jul 浙江大学硕士学位论文 第3 章从阈值理论角度理解传统免疫策略 第3 章从阈值理论角度理解传统免疫策略 根据命题1 和定理5 ，免疫策略应该以免疫后p a m 矩阵m 的谱半径久被尽可 能多得降低为目标。因为，当a l 时，应使其逐渐变小直至小于l ，从而使传染 病能够灭绝；当a l 时，应当使其取到一个更小的值，从而使传染病能够加速灭 绝。因此，只要计算能力允许，任何免疫策略都可以通过这个的标准来设计和评 估，即看该策略否能最大限度地减少p a m 的谱半径。在进入下一章免疫策略设 计前，本章中本文将以几个流行的免疫策略为例，从p a m 所对应的谱半径角度 来解读为什么有些策略是有效的而其他一些策略不那么有效。 3 1 平均免疫 平均免疫可以被看作是一个很直观的方法。平均免疫的存在将产生以口的比 例降低传播率的效果【2 9 】，而这一效果事实上与m 被m 术( 1 一g ) 取代的效果等价， 并且相应的谱半径入就变为a 宰( 1 一夕) 。因此，减少单位入的代价就是 e ：i ( 1 , 木g e 卑，善 一= 一 a 宰g a 公式( 3 1 ) 其中p 是完全免疫一个个体的成本。显然的，如果网络很大，这个策略只在每个个 体都能被很廉价地免疫的情况下才有效，例如存在很廉价的疫苗之情形。 3 2 目标免疫 为实现更高的免疫效率，研究人员设计出了一种被称为目标免疫的方法。对 于无权无向传播网络，目标免疫就是一种逐步免疫最高度数节点的方法【2 9 】。这个 方法已经被证实是优于其他很多方法的 1 4 , 2 9 ，3 1 - 3 3 ，3 5 , 4 4 1 ，特别是当它应用于无标度网 络的时候【1 4 ，3 2 3 5 , 4 4 。 在广义网络的范围内，边的权重 3 0 】和方向都应在目标节点选择时作为考虑因 素。为简化起见，在这里仅考虑这样的目标免疫策略：不断选择具有最高含权出 1 5 浙江大学硕上学位论文第3 章从阈值理论角度理解传统免疫策略 度的节点作为目标免疫的对象。当应用于无向尤权网络时，这一策略与传统的定 义具有相同的效果。因此，如果这个免疫策略在某一步骤免疫了第岛个节点，则 在该步骤必定存在 竹 七= a r g i n i a “x m 巧 j = l 公式( 3 2 ) 要分析这一免疫策略的效率，就不得不分析m 的减少量与入的减少量之间的 关系。而这个关系涉及特征值扰动理论，因而难以得到精确的等式表达式。幸运 的是，一些线索可以在针对非负矩阵的盖氏定理( g e r s c h g o r i n st h e o r e m ) 【4 5 】中被 找到。盖氏定理表明了非负矩阵最大特征值的上限是m 黼e 麓l 嘞，并且m 的越 大的扰动将造成入的更大范围的变化【4 6 】也是容易理解的。因此，在每个免疫步骤 内通过首先免疫具有最高出度的节点的方法将能导致入最大可能性的下降，从而 保证了目标免疫成为最有效率的免疫策略之一。 3 3 随机免疫 随机免疫常常被作为比较对象出现在不同作者的文章中【3 1 - 3 5 1 。为评价随机免 疫的效率，在这里只需简单地将上文所述的目标选择方法改成随机选择方法即 可。因此，在每一步骤中对随机节点作免疫只能导致一个中等的结果，而不是像 目标免疫那样能在每一步骤中都导致a 最大可能性的下降。 3 4 熟人免疫 尽管目标免疫具有很高的效率，它却需要全局的信息来支持它的功能【4 7 】。如 果只有局部信息可以获得，熟人免疫将是一个推荐的方法 3 3 3 6 , 4 引。对于广义网络， 这里考虑最基本的熟人免疫方法，即从有边指向某一随机节点的节点集中选择一 个节点做免疫，节点集中一个节点被选中的概率与与其指向该随机节点的边的权 重成比例。在无权无向网络的情况下，这个方法与c o h e n 等人【3 6 】提出的方法具有 相同的效果。 1 6 浙江大学硕士学位论文 第3 章从闷值理论角度理解传统免疫策略 在这个策略中，通过一个随机节点 使得节点知被免疫的概率是 三宰蜀 公式( 3 3 ) 一事i = 再r 一 厶j j j n 2 一汹1l l l i , j 因而通过任一随机节点使得节点确吏免疫的概率是 r 三囊竺! ：生 公式( 3 4 ) ， 一木一 “，、，_ r 7 台扎釜1m i d 这将能导致对一种高度数节点的免疫偏好，但未必针对最高度数节点。基于这个 原因，本文可以下这样的结论：熟人免疫的效率比目标免疫要低，但是却能好于 随机免疫，特别是当它应用于无标度网络时( 极少数高度数节点就能加剧