（计算机软件与理论专业论文）复杂网络中具有抑制作用的双信息传播建模与仿真.pdf

1，1 a b s t r a c t i ti sf o u n dt h a taw i d er a n g eo fn e t w o r k se x h i b i ts m a l l w o r l da n dp o w e r - l a w c h a r a c t e r i s t i c ，w h i c ha r o u s e st h er e s e a r c ho ft h ec o m p l e xn e t w o r k t h es t u d yo f s p r e a d i n gd y n a m i c so nc o m p l e xn e w o r k sh a sb e e na ni m p o r t a n td i r e c t i o ni nt h ec o m p l e x n e t w o r kr e s e a r c h t h es p r e a d i n go 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 f r u m o ri nt h ec r o w d ，t h et r a n s m i s s i o no ft h et r o u b l ea n dd a n g e r , a l lo fw h i c hc a nb e v i e w e da sas p r e a d i n gb e h a v i o ro nt h ec o m p l e xn e t w o r k sw h i c he x h i b i t sac e r t a i nl a w t h es t u d yo fs p r e a d i n gd y n a m i c so nc o m p l e xn e w o r k sm a i n l yc o n c e n t r a t e so nt h es i n g l e i n f o r m a t i o ns p r e a d ，b u tt h ep h e n o m e n ao fm u l t i - i n f o r m a t i o ns p r e a d i n gi nt h er e a lw o r l d i sh i g h l yp r e v a l e n t ，a n dt h et r a n s m i m i s s i o np r o c e s si sm u c hm o r ec o m p l i c a t e d s ot h e t r a n s m i s s i o na b o u tt w ok i n d so fi n f o r m a t i o ni ss t u d i e dh e r e an e ws p r e a d i n gm o d e li s p r o p o s e db a s e do nt h es t u d yo ft h ec l a s s i c a le p i d e m i c s p r e a d i n gm o d e l s i ti sa b o u tt w ok i n d so fi n f o r m a t i o ns p r e a d i n ga n di n t e r a c t i n go nt h e n e t w o r k i nt h i sc o n d i t i o n ，t h ei n f l u e n c ec a u s e db ys o m ef a c t o r ss u c ha st h ec o n t r o le f f e c t b e t w e e nt h ei n f o r m a t i o na n dt h e i ri n t e r v a li s a n a l y z e d ，a n dt h em o d e li sp v o v e db y s i m u l a t i o n a c c o r d i n gt ot h es t u d yo ft h es p r e a d i n gm o d e la b o u tt w ok i n d so fi n t e r a c t i n g i n f o r m a t i o n ，a i m i n ga tt h es p r e a d i n gc h a r a c t e r i s t i co ft h eh 1n1v i r u s ，am o d e ls - s e i ri s e s t a b l i s h e d i nt h em o d e l ，s o m ef a c t o r ss u c ha si s o l a t i o ns t r e n g t h ，a n t i - d i s e a s ea b i l i t ya n d p e r s o n a lh y g i e n ea r ep u ti nt h em o d e lt oa n a l y z et h e i re f f e c to nt h ev i r u st r a n s mi s s i o n b e s i d e st h e s ef a c t o r s ，v a c c i n a t i o n sa r ea l s od i s s c u s e di nt h em o d e l c o m p a r e dw i t ht h e r e a ld a t a ，t h i sm o d e li sp r o v e de f f i c i e n tt os i m u l a t et h eh i n iv i r u st r a n s m i s s i o na n dc a n b eu s e dt o0 艉rs o m et h e o r yb a s i sf o rc o n t r o l l i n gt h ev i r u st r a n s m i s s i o n k e y w o r d s ：c o m p l e xn e t w o r k s ，s p r e a d i n gd y n a m i c s ，h i n lv i r u s ，s s e i rm o d e l kir 目录 第一章绪论l 1 1 选题的背景和意义1 1 2 病毒传播模型研究分析2 1 2 1 传染病背景知识2 1 2 2 经典的传播模型3 1 2 3 扩展的病毒传播模型6 1 3 研究内容和创新点9 1 4 本文的章节安排一9 第二章复杂网络的结构特性10 2 1 复杂网络的定义1 0 2 2 复杂网络的研究现状1 0 2 3 复杂刚络的基本概念1 2 2 4 几种经典的网络模型1 4 2 4 1 规则网络1 4 2 4 2 随机网络15 2 4 3 小世界网络1 6 2 4 4 无标度网络1 6 2 5 j 、结18 第三章单方抑制作用下的双信息传播模型19 3 1 多信息传播现象l9 3 2 模型的提出2 0 3 3 单方抑制作用下的双信息传播模型2l 3 3 1 模型假设2l 3 3 2 模型描述2 2 3 4 单方抑制作用下的双信息传播模型的分析2 3 3 4 1t t 时两种信息同时存在的情况2 4 3 5 仿真分析2 4 3 6 本章小结2 8 第四章甲型h i n i 流感病毒的建模仿真2 9 4 1 引言2 9 4 2 甲型h ln1 流感蔓延情况3 0 4 3 问题描述3l 4 3 1 符号定义3 2 4 3 2 模型的假设3 3 4 4s - s e i r 模型的建立3 3 4 5 模犁的参数分析3 5 4 6 仿真分析4 0 第五章总结与展望4 4 5 1 论文总结4 4 5 2 展望4 4 参考文献4 5 攻读学位期间的研究成果4 8 致谢4 9 学位论文独创性声明5 0 学位论文知识产权权属声明5 0 第一章绪论 1 1 选题的背景和意义 第一章绪论 近年来，国内外掀起了研究复杂网络的热潮。随着复杂网络研究的蓬勃发展， 人们逐渐认识到不同事物在现实网络中的传播现象，传播在自然世界和人类社会中 广泛存在，它与我们的r 常生活息息相关。流感、天花、病毒、瘟疫等广为人知的 传染病曾夺走了数百万人的生命，给人类造成了巨大的损失；2 0 0 3 年发生在我图的 “非典”，虽然经过全国各族人民的努力，疫情得到了控制，但是它带来的影响值 得我们深思；2 0 0 9 年3 月份，从墨西哥和美国开始，存极短时问内迅速扩散到全世 界的甲型h i n l 流感病毒，引起了人们的高度关注。 除此之外，计算机病毒在网络上的传播，谣言在人群。i j 的扩散，故障与危机的 传播等现象，都日j 以看作是复杂网络上服从某种规律的信息传播行为。认识这些传 播现象，研究这些传播的特点，揭力之出它们的传播特性，进而找出可以有效抑制这 些传播的方法，减小有害传播带来的危害，一直是科学家们共同关注的焦点，也是 人们研究网络拓扑结构的最终目标之一，对人类的发展和社会的进步具有非常重要 的现实意义。 信息足一个含义广泛的概念。先进文化、知识、计算机蠕虫和传染病等可以统 称为信息。有些信息是应该鼓励加以广泛传播的，如先进的文化、有用的知识；有 的信息是应该受到限制的，如计算机病毒、流行传染病等，现实系统中的若干行为 均日j 看成信息的传播。由于现实世界的许多网络具有复杂性，各种各样的信息在网 络中传播，会存在多种信息传播并存的现象，诸多信息在传播过程中会发牛相互作 用，产生传播增强或削弱的现象，它们之问的这种相互作用会反过来影响信息的传 播。例如甲犁h i n i 流感病毒在传播过程巾，病情严重的患者往往会引发肺炎的传 播，进一步促进肺炎病毒的传播，这就是两种信息在传播过程中发生作用使得其中 一种信息的传播增强的表现。 本课题针对两种信息同时在网络中传播的行为进行研究，采用复杂网络f 譬播动 力学相关理论，提出了两种信息在网络中l 刊时传播并且之问会发生抑制作用的传播 模型，分析了它们之间的抑制作用及间隔时间对传播的影响；并日以甲犁h 1 n l 病毒 和疫苗的传播为例，建立了甲型h 1 n l 流感病毒的传播模型，对其传播特性进行研究 分析，根据结果提出了一些可行性的控制策略。结果证明研究双信息传播模型不仅 可以很好的描述它们的传播行为，揭示它们的传播特性，而且对这些信息传播的行 为提供行之有效的控制方法，具有非常重要的意义。 青岛人学硕十学位论文 1 2 病毒传播模型研究分析 1 2 1 传染病背景知识 根据历史记载，人类历史上曾多次受到传染病的大规模侵袭，给人们的生活和 生命安全造成了严重威胁。前儿年爆发的s a r s 使世界各国人民和政府遭受了重大 损失。现代医学发展迅速，可以有效的预防并且治疗天花、肺结核等传染病，但是 却对突然暴发的流行性传染病措手不及，这不单单是医学领域的任务，还涉及到经 济、社会、卫生、风俗习惯等领域。为了在这些流行性传染病伯i 前可以镇定自若， 人们开始关注于对传染病的描述与预测，试图找出有效的控制方法，进而给疫苗的 研发和生产争取时问。 传染病一般是r f l 各种病原体引起的可以在人与人之间、动物与动物之间或者人 与动物之间互相传播的一类疾病。一般来讲，传染病的顺利传播，需要具备i 个条 件：即传染源、传播途径和易感人群。传染源是指体内寄存台病原体并且可以将病 原体排除去感染其他个体的人或者动物：易感人群是那些可以被感染的群体：传播 途径是指病原体在传播过程中必须依赖的各种生物或非生物媒介，一般分为空气传 染、接触感染、血液传染和飞沫传染等方式。若可以完全控制其中的任何一个条件， 则传染病就无法传播开来。 世界卫生组织搜集的伞球因传染病死产数据显示，近儿年，伞球每年因传染病 而死亡的人数高达1 4 0 0 多万，在发展中国家，因传染病导致的死亡人数占总体死 亡人数的一半。中国卫生部统计表明，中国因传染病而死亡的人数逐年上升。因此， 传染病研究迫在眉睫，找出有效的控制方法更是不容懈怠。 在对这些传染病的传播过程进行研究时，只能从现有的报告或者记录中获取数 据，进而建立模型进行研究分析，从而预测未来发展趋势并， j 提ij ：控制建议。然而， 病毒在传播过程中，充满了各种偶然因素的影响，其传播过程是一种复杂现象【i 。j 。 因为这些具有传染性的、可以被感染的个体都足具有能动作用的个体，他们的行为 方式及运动情况对病情的发展具有很人的影响，同时一些外界因素的影响，如气候 变化、国家政策、卫生防疫等冈素都能影响疫情的发展，这也造成了研究问题的复 杂性。 学者们在建立模型时，往往忽略+ 些因素，对一些重要的影响因素进行合理的 简化，从而建立起可以反映传染病传播特性的数学模型。与传统的生物统计学相比， 动力学方法能从病毒传播机制方面体现其传播规律，使人们可以从中了解传播过程 中的一些动态特性，所建立的模型也更加可靠并且符合实际【4 制。 下而介绍几种经典的流行病传播模型。 2 第一章绪论 1 2 2 经典的传播模型 1 ) s i 模型 在经典的流行病传播模型s i 中，个体状态被抽象为两类：易感态s ( s u s c e p t i b l e ) 和感染态i ( i n f e c t e d ) ，其中易感状态可以看作是个体的初始态，是未被传染病感染 的状态；感染念指个体被传染病感染后的状念。假设易感个体在单位时问内被某个 染病个体传染的概率为口，s ( t ) 、i ( t ) 分别表示t 时刻两种状态下的个体占总数的比 例。则在s l 模型中，疾病的传播可以用下列微分方程描述： 罢= o t i s ，砸) + j ( ，) = 1 公式l - ( 1 ) a t 两边积分并整理可得： 砸) = 百b 令f ( 0 ) = o ，代入公式l - ( 2 ) ，求得 c ：盥 乇 公式1 ( 2 ) 公式l 一( 3 ) 故公式l 一( 1 ) 满足初始条件f ( o ) = o 的解为： “f ) 2 再高1 0 公式卜( 4 ) ，o + 【l 一，p 很显然，f ( f ) 随时( i j 的变化规律符合著名的l o g i s t i c 曲线，如果不采取措施控 制，信息a 最后将感染网络上的所有节点。图1 1 表示的是当o = 0 0 0 0 1 ，感染率 口= o 0 6 时，两种状态的节点的变化情况。可见，若没有采取控制措施，病毒最后 将感染所有节点。显然这是不符合实际情况的，冈为它没有考虑到个体在被感染后 可以被治愈的情况。 3 青岛人学硕十学位论文 图1 1s i 模型 2 ) s i s 模型 19 9 3 年，j d m u r r a y 提出了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 ) 5 - 7 1 模型，在 该模犁中，网络巾的个体被分成两种状态：易感念s ( 也称为健康念) ，它们不会 感染其他个体，但可以被其他个体感染；感染态i ，这类节点已经被感染，具有传 染性，可以去感染其他个体。 假设易感个体在单位时间内被某个染病个体传染的概率为p ，感染态个体经过 治愈恢复变为s 态的概率为万，并用s ，i 表示群体r f l 健康类和感染类个体分别所占 的比例，则在s i s 模型中，疾病传播可用下列微分方程组描述： 面d s = 一l i b s + 6 i 万d i = 缸一万f 公式1 ( 5 ) s ( t ) + i ( f ) = 1 假设初始时刻( 即t = 0 ) 感染态个体所占比例为乇，即i ( o ) = o ，结合公式1 - ( 5 ) ，有 鲁= 肌l _ f ) _ 西 公式卜( 6 ) 【i ( 0 ) = i o 解方程组l 一( 6 ) 得， 4 第一章绪论 南+ c 一每邯切卜知7 ， 丽l o ，为= 6 这里，将笔记作名，则五表示个传染期内平均每个病人可以感染的人数。根 d 据公式l - ( 7 ) ，可求出： i ( ) ：l _ l 五，。1公式1 - ( 8 ) 【0 ，名1 可见，五= 1 是一个阈值。当名1 时，感染态个体的比例椰) 会越来越小，最后 趋于零；反之，病毒会传播开来，最后比例- 7 达到l 一。当 = 0 0 8 ，万= 0 0 2 ，i ( o ) = 0 0 0 1 时，病毒的传播情况如图1 2 所示，从图中可以看出， 最后感染态个体数量趋于7 5 ，与计算结果吻合。 图1 2s i s 模型 s i s 模型描述了易感个体在被感染成为感染个体后，义可以恢复成为易感个体 的传播过程。s i s 模型刻画了个体被治愈后能够继续被感染的情况，如流行性感冒。 3 ) s i r 模型 另类被广泛应用的病毒传播模型是s i r ( s u s c e p t i b l e i n f e c t e d r e m o v e d ) 2 - 4 模 型，在该模型中，除了易感态s 和感染态i 之外，多了一种状态r ，即免疫态( 或 5 青岛人学硕十学位论文 者称为移除态) 。它表明个体被治愈后获得埘该病毒的免疫能力或者因为死亡从网 络巾移除。同s i s 模型相似，s i r 模型可用下列微分方程表示： 瓦d s = 一胁，等= 括一历， 瓦d r = 疣 公式l - ( 9 ) 其中，表示病毒的感染率，万为病毒的移出率。 1 2 3 扩展的病毒传播模型 除了上述s i s 、s i r 模型之外，针对不同传染病的特点，科学家们在这些模型 的基础上做了许多扩展，提出了一些新的模型，如免疫期有限的s i r s 模型。对j j ： r 些免疫期有限的传染病，就可以用s i r s 模型描述，而有的疾病有定的潜伏期 爿呈现出病症，故引入了具有潜伏状态的病毒传播模型。 1 ) s i r s 模犁 s i r s l 6 1 模型的提出，主要是考虑到有些病毒的免疫期是有限的，它在s i r 模型 的基础上，多了- 个概率y ，即免疫态个体以概率7 失去免疫能力成为易感个体， 即该病毒的免疫期为z ，。该模型的状态转化图如图1 3 所示。 图1 3s i r s 模型状态转化图 结合图1 3 ，可以得到下面的微分方程： 鲁一蹦州+ 川f ) 鲁= f ) 一州，) 公式l - ( 1 。) 筹= 州沪川f ) 上述方程组的解析解不易求出，但可以给出稳定状态下的解的情况，令 掣-0，掣扎掣_o得出方程的平衡点郴加百1dt a r td t ，揣1 ，赫) ， 以以i 以+ ) 以( 以+ 1 ) 6 第一章绪论 其巾记五：笔，五：，分别表示一个感染期内平均每个病人有效感染的人数和失去 o口 免疫的人数。 2 ) s e i r 模型 s u s c e p t i b l e e x p o s e d i n f e c t e d r e m o v e d 模型，简称s e l r 模型【7 】，该模型在经典 模型s i r 的基础卜，多了一个潜伏状念e ( e x p o s e d ) ，其他状态与s i r 中定义的相同。 它认为，病毒在f 量播过程中没有立刻发病，而是存在。个感染延迟，这些被病毒感 染却没有被激活的个体所处的状态定义为潜伏态e 。处于这种状态的个体，不会立 刻去感染其他个体。该模型认为感染节点被治愈后可能成为免疫节点，以后不会再 被感染，也可能成为易感节点，有再次被感染的危险。图1 4 表示了s e l r 模型中 个体的状态变化情7 兑。 图1 4s e i r 模型状态转化图 s e i r 模型与s i r 模型相比，多出了状态e ，考虑到了有些病毒具有潜伏期这一 特性，同时冈为感染个体被治愈后有的会恢复成为易感态， 人i 此该模型也具备s i s 的特点，它对于病毒的传播过程考虑的更加周密。结合图1 4 ，町以得到下面的微 分方程： 鲁= 川咿州，) 一d e = 口s ( t ) i ( ，) 一，5 一 = 口si ) ( ，) 一 d ， 、7、7 鲁= m ，) _ ( + 鲁= 麒，) i ( t ) e ( f ) 公式l 一( 1 1 ) y ) i ( ，) 其中，j ( ，) 、占( f ) 、以) 、，( f ) 分别表示t 时刻四种状态的个体占总节点数的比 7 青岛人学硕+ 学位论文 例，且s ( f ) + p ( ，) + 砸) + ，( f ) = l ，历为感染率，坛为病毒的潜伏期，y 为治愈率，1 ，p 为恢复率。 3 ) s i d r 模型 s u s c e p t i b l e i n f e c t e d d e t e c t e d r e m o v e d 模型，简称s i d r 模型0 1 ，是一个刻画 病毒传播过程和清除过程的模型。在s i d r 模型中，较s i r 模型相比，多了监测念 d ( d e t e c t e d ) ，它表明节点已经被感染，但是被检测出来以后被隔离防止其继续向外 传播病毒，其他状态定义与s i r 中的状态定义相同。 s i d r 模型将病毒传播分为两个阶段：在反病毒措施出现之前，病毒自由传播； 传播一段时问t 后，反病毒措施出现，病毒和疫苗同时在网络上传播，易感节点和 感染节点都可以经过免疫成为免疫节点。这种传播模型，考虑到了现实生活中一些 疫苗的产生总是滞后于病毒的出现这一事实，具有很好的现实意义。图1 5 给出了 s i d r 模型的状态变化过程。 ( a ) t t ( b ) t t 图1 5 s i d r 模型 其中，参数口为病毒感染率，为检测率，即病毒被检测出来的概率。7 为节 点被检测出来隔离之后进入免疫状态的概率，参数表示易感节点直接得到免疫的 概率。 然而，以上研究的都是单信息在网络巾传播的情况，并且病毒的感染率、治愈 率等参数均为常数，实际中病毒传播影响因素众多，渚参数也会随着时间的推移而 变化，并且网络中会有多种信息同时存在，这些信息在传播过程中会发生相互作用。 基于此，本课题研究了两种信息同时在网络中传播的情况，具有非常重要的现实意 义。 8 第一章绪论 1 3 研究内容和创新点 本文的主要研究内容和创新点包括： 1 ) 现实网络中往往有多种信息同时传播，并且信息之间会相互作用，从而使得 传播加强或者减弱。针对这一。现象，本义就两种信息在网络中f 晕播，其中种信息 单方面抑制另一种信息这种情况，提出了两种信息在网络中传播的模型，即单方抑 制作用下的双信息传播模型，并h 根据两种信息实际传播现象给出了一个动态传播 率函数，分析了信息之间的相互作用及信息出现的间隔时间对传播的影响。 2 ) 基- j 二单方抑制作片j 下的双信息传播模型研究，针对甲型h l n l 流感病毒的独 特的传播特性，提出了种s - s e i r 模型，在该模型中，加入了隔离措施、人类的 身体素质状况及j f l 生防御意识等 人l 素对病毒传播的影响，分析了疫苗的使用对病毒 的作用，并与病毒实际走势比较，发现该模犁能够较好的模拟甲犁h i n l 病毒的传 播情况。 1 4 本文的章节安排 本义的章节组织结构如下： 第一章：介绍了本文的选题背景和意义，分析了目前常用的病毒传播模型，比 较了它们的优缺点，指出了本文的主要任务和创新点。 第二章：介绍本文的基础理论复杂网络的结构特性。包括复杂网络的定义、 研究现状及统计特性，并介绍了几种常见的网络模型。 第三章：分析了网络中多信息传播并且相互作用的现象，针对两种信息传播的 情况，给出了数学模型，并且进行了仿真分析。 第p n q 章：以最近流行的甲型h l n l 流感病毒与疫苗的使用为例，研究了疫苗对 传播的影响，并且针对甲型h i n l 流感病毒的传播特性，提出了s - s e i r 模型，并 且进行了仿真分析。 第五章：论文工作总结与展望。 9 第- 二章复杂网络的结构特性 第二章复杂网络的结构特性 2 1 复杂网络的定义 对我们来讲，网络并不陌生。现存，网络的概念已经深入人心，i n t e r n e t 已经成 为人们获取信息、学习知识的重要手段，成为人们牛活中的一部分。然而，随着时 代的发展，网络的概念已不再局限于常见的i n t e r n e t ，人们的生活中随处充满着各种 各样的网络，像和我们的生活密切相关的- 些具体网络，如交通网络、电力网络、 通信网络等。除此之外，还包括一些抽象的网络，如大量的神经细胞通过神经纤维 构成的神经网络、人与人之间形成的社会关系网络以及演员导演之间的合作网络 等。近几年来，随着计算机数据处理和运算能力的快速发展，学者们开始对这些真 实的网络数据进行运算分析，发现大量真实网络的特征既不同j ：规则网络也不同j j ： 随机网络，而是具有与前两种截然不同的网络特性，科学家们把这种网络称为复杂 网络( c o m p l e xn e t w o r k ) 。 复杂网络就是指那些具有复杂的拓扑结构和动力行为的大规模网络，它为研究 现实中的复杂系统提供了强有力的方法论i l l - 1 3 】，其复杂性体现在以下几个方断： 1 ) 节点的复杂性 在现实的网络中，构成网络的节点数目可以有成自上千万，甚至更多，同时， 每个个体具有很强的独立性，即每个个体在系统中可以独立的演化。在某些特定的 复杂网络中，每个节点本身可以看成足一个非线性系统。 2 ) 结构的复杂性 网络中的个体是通过边联系在一起的，连接结构既非规则也非随机，看上去错 综复杂，极为混乱。而且网络的连接结构不一定是静态的，节点的数量及边的连接 关系可能会随时变化，例如，公交网络中每天都可能有新的线路和站点产生，由于 道路维修等原因会改变路线，因此公交线路网足动态变化的。同时，某些网络中， 节点的连边可能具有方向和权重，使得网络更加复杂。 3 ) 演化的复杂性 复杂网络表现m 具有时间和空间的演化复杂性，具有丰富的复杂行为。 2 2 复杂网络的研究现状 在现实世界中，我们的生活里处处充斥着网络。网络可以看成包含大量个体并 且个体之间相互作用的复杂系统。它可以用来描述人与人之间的社会关系1 和16 1 、网 页之间的链接关系1 7 。9 1 、物种之间的捕食关系 2 0 - 2 1 l 、科学家之间的合作关系 2 2 。2 3 l 、 l o 青岛人学硕十学位论文 公交线路的换乘关系【2 4 】、以及计算机通过各种通信介质如光缆、双绞线、同轴电缆 等相互之间的连接关系1 2 5 】等。 一个典型的网络是由节点和连接两个节点之间的边组成，其中节点用米代表存 在于真实系统中的个体，而边则用来表示个体间的相互关系，若两个节点之间有某 种特定的关系则它们之问连，条边，否则彳i 连边，这样就构成。个复杂嘲络。 起初数学家们利用图论的基本理论埘网络进行研究，他们倾向于用一种规则的 拓扑结构来描述真实的网络【2 6 。2 7 】。到了1 9 5 9 年，匈牙利数学家e r d s s 和r 6 n y i 将概 率论应用于图论中，提出了随机网络的基本模型【2 蚰0 1 ，然后随机图便成为了研究复 杂网络的有力武器。直至1 9 9 8 年，d u n c a nj w a t t s 和s t e v e nh s t r o g a t z 提出了一种 介于规则模型与随机模型之间的小世界模型f 3 l 】，该模型可以较好的模拟现实网络， 从此之后，对复杂网络的研究进入了高潮阶段。在短短十几年的时问里，不同领域 的研究者们从不同的方向上对复杂网络展开了研究，并取得了丰硕的研究成果。概 括讲，目前复杂恻络的研究至少包含了以下几个方l 曲： 1 ) 对实际的网络进行统计分析 这个研究方向是对复杂网络研究的基本手段，同时也是最重要的研究方法之 一。正是基于对诸多现实网络数据的统计分析，才会在规则网络的基础上提出了小 世界网络、无标度网络及含有社团结构的复杂网络等。只有对实际的网络进行分析， 才能发现它们的共同特征，基于这种共性才能更好的构建符合实际网络特性的模 型。 2 ) 复杂网络的拓扑性质研究 研究者们根据对现实网络的数据分析结果，提炼出它们的共同特点，再结合他 们对实际网络的理解，从而构建出接近二f 实际网络的网络模型，这些模型可以很好 的模拟现实世界。1 9 9 8 年，w a t t s 和s t r o g a t z 提出了小世界模型，1 9 9 9 年，a l b e r t l a s z l o b a r a b a s i 和r e k aa l b e r t 在分析大量真实网络数据的基础上，提出了无标度网络模型 ( b am o d e l ) 3 2 1 ，后来人们又在这两个模型上的基础卜- 提 i 了一些改进，成为适合模 拟一些具体网络的模型，如w w w 网络中具有相同丰题的站点具有社团结构的复杂 网络【3 3 - 3 4 】等，这些模型将在后而的章节中具体介绍。 3 ) 复杂网络上的传播动力学研究 复杂网络的传播动力学是复杂网络研究的一个重要方向。传播动力学，就是研 究社会和自然界中各种复杂网络上的信息传播行为，通过对这些行为的研究，提出 高效可行的控制方法。 复杂网络动力学的一个主要研究目的就是了解网络的传播行为，即弄清信息在 网络上的传播规律。一般用网络上的节点表示个体，如果两个个体之间可以通过某 种方式直接联系，就认为这两个个体之间存在连接，这样就可以得到信息传播网络 第_ 二章复杂网络的结构特性 的拓扑结构。不同的网络拓扑结构对传播情7 兕有重要的影响，因此研究不同网络拓 扑下的传播行为具有重要的指导意义。木义将重点研究两种信息在网络上的传播情 况，这对于进一步理解复杂网络上的传播行为与其结构之问的联系是有意义的。 2 3 复杂网络的基本概念 在欧拉开创了图论后，人们一直使用图来描述网络。在图论中，复杂网络被表 示为边的集合e ( g ) 和点的集合v ( g ) 构成的陶g = ( v ，e ) 。其中，e ( g ) 中的每条边 都与v ( g ) 中的一对点( u ，v ) 对应。网络的节点数即个体数目记为n 爿vi ，边的数目 记为m 爿e i ，一条边连接的两个节点称为邻接节点。如果任意的节点对( u ，v ) 和( v ，u ) 对应同，条边，那么该网络称为无向网络，否则称为有向网络。如果给每条边都赋 予相应的权值，则该网络为加权网络，否则为无权网络。 在数学中，复杂网络可用邻接矩阵w 表示，矩阵的行、列号对应于网络中的 节点，对于矩阵w 中的任一元素w l i 有 屯= 僻鬣薏暑萎；擎 妣羽， u “一1o ，节点f ，之间没有边 雀风厶u ， 揭示嘲络结构的统计性质，并用合适的方法来度量这些性质，是复杂网络的一 个重要研究内容之一。为了刻画复杂网络结构的统计特性，人们提出了很多概念和 方法，这里介绍儿种重要的概念。 1 ) 度与度分布 在衡量一个网络中节点重要性的指标中，节点的度( d e g r e e ) 足很重要的一个概 念。节点i 的度k 定义为与该节点相邻的节点的个数。在用邻接矩阵表示的网络中， 其数学定义如f ： k = 公式2 - ( 2 ) 一个网络巾所有节点度的平均值定义为该网络上节点的平均度，记为k ，数学 定义如下： 乏= 万1 萎墨 公式2 。( 3 ) 在不司的网络中，节点的度具有不l 刊的意义。一般米讲，一个节点的度越大， 意味着这个节点越“重要”。 网络中节点的度分布情况用度分布函数p ( k ) 来表示，度分布p ( k ) 表示网络中 1 2 青岛人学硕十学位论文 度为k 的节点占所有节点数的比例，或者说从网络中随机选取一个节点，该节点度 为k 的概率。 2 ) 聚集系数( c l u s t e r i n gc o e f f i c i e n t ) 一个网络中，为了衡最节点的连接有多紧密，w a t t s 和t r o g a t z 3 5 - 3 6 提了聚集 系数这概念来衡量网络中个节点的两个邻接节点也连边的概率。刚络中若。个 节点i 的度为k 。，则它有k ，个节点与之相连，这k ，个节点称为该节点的邻居节点。 显然，这k 个节点之间，最多可能有k ( k 一1 条边。这k 个节点之间实际连接 的边数为e ，e 与k 条边之问能够存在的最多边数即k ( k 一的比值记做e ， e 就是节点i 的聚集系数，表示为： c ，= 2 e , k ( k 1 ) 公式2 一( 4 ) 整个网络的聚集系数c 就是指所有节点的聚集系数的平均值，它描述了网络中 节点与节点之间聚集成团的一陡质，其数学定义如i - ： c = 丙1 鲁c ， 公式2 - ( 5 ) 由定义可以看出，0 c l ，0 c l ，当且仅当网络是全连通网( 即网络中 任意一个节点都与其他节点相连) 时，c = 1 ，一般情况下，c 1 。 3 ) 最短路径长度( s h o r t e s tp a t hl e n g t h ) 网络中的任意两个节点i 和j 的最短路径长度，定义为连接节点i 和节点j 之间 的最短路径卜的边数，也称作两点间的距离。这一概念在研究网络中的运输、通信 等方面起着重要作用。例如在互联网上两台计算机传输数据，如何选择路南使得经 过路径最短，是人们一直关注的问题。 一个网络的宵径定义为该网络中任意两点间距离的最大值，记为d ，用数学公 式表示为： d = m a x 乞 公式2 。( 6 ) 该网络中任意两点间距离的平均值即为网络的平均路径长度l ，即： 2 乞 三= 羔公式2 一( 7 ) n ( n 1 ) 一 1 3 第一二章复杂网络的结构特性 其中n 爿vi ，为网络节点数。平均路径长度和网络直径可以用来衡量一个网络 的传输性能与效率。 2 4 几种经典的网络模型 目前为，i 卜，研究最多的网络模型主要有：规则网络、随机网络( r a n d o mn e t w o r k ) 、 小世界网络( s m a l l w o r l dn e t w o r k ) 和无标度网络( s c a l e - f r e en e t w o r k ) 。除此之外，人们 对存在于现实世界的大量真实网络进行研究，从不同的角度出发提出了各种各样的 更切合实际的网络拓扑结构模型1 3 7 。3 引。在这里，简要介绍一下几种最常见的模型。 2 4 1 规则网络 一般来讲，规则网络具有比较简单的拓扑结构，网络上每个节点具有相同的度 和聚集系数，如常见的全局祸合网络( g l o b a l l yc o u p l e dn e t w o r k ) 、星型网络、环状 网络等。这类网络构造简单，易+ r 分析。 1 1 全局耦合网络 全局祸合网络即全连接网络如图2 1 所示。在该模型中，每个节点与其他节点 均相连，网络的平均路径长度l = i ，聚集系数c = i 。在一个具有n 个节点的全局耦 合网络中，边的数日m ：n ( n 一1 。然而，现实世界巾大多数网络的边是稀疏的， 边的数目一般最多是o ( n ) 而不是o ( n 2 ) 。 2 ) 最近邻祸合网络( n e a r e s t n e i g h b o rc o u p l e dn e t w o r k ) 最近邻耦合网络是一种比较稀疏的规则网络，如图2 2 所示。其中每一个节点 只和它最近邻的几个节点相连。可见，当网络中的节点数目很大时，网络的最短路 径长度会很大。 囝 ， ， ， 一+ ? ti 囝+ ， 囝囝。，囝 囝 囝 ，1 一国i ，4 ：+ ，：，j 一，囝。j j 、，。) 、 囝 囝 图2 , 1 全局耦合网络 1 4 ：、：囝；7 ：，。 图2 2 最近邻耦合网络 青岛人学硕十学位论文 2 4 2 随机网络 如前面所述，随机模犁是由旬牙利数学家e r d $ s 和r 6 n y i 提 ，他们在图论中 引入了概率论，提出了随机网络这，基本模型。有n 个节点k 条边的随机网络构 造过程【3 9 】如下： 1 ) 给定n 个互不相连的节点。 2 ) 选取任意两个不相同的节点，按一定的概率p 在这两点问连边。 3 ) 重复第2 步，直到边的数目为k 为i 卜。 e r 随机网络是最简单的复杂网络【纵2 1 ，对于k 个节点，任意之间以概率p 连 接起来( 如图2 3 ) ，构成的网络中共有边数e ：_ p n ( n - i ) ，网络的平均度乏为： z 乏：等：t p n ( n - 1 ) - p ( n 一1 ) 公式2 - ( 7 ) nn 。 当节点数目n 很大时，甲均度七= p ( n 1 ) z n 。 囝囝囝囝 ，7 j ， 囝囝 囝 j ，： 囝囝 ( a ) p = 0 i 囝囝 囝 ， 囝 。，! 、 囝= 、t ； 囝囝 ( c ) p = 0 5 图2 3 e r 模型( n - - 1 0 ) 1 5 囝囝 ( b ) p = 0 3 囝 囝 囝 囝 囝 。 |一、， 、，、 ， 囝一 囝 ， ， 囝 第一二章复杂网络的结构特性 由上图可以看出，连接概率p 越大，e r 网络越接近二j ：全局耦合网络。经研究 发现，e r 随机网络的度分布符合泊松分布，即度分布在平均度k 的位置处出现峰值， 偏离峰值的两边迅速哀减。 2 4 3 小世界网络 前面提到过，在1 9 9 8 年，w a t t s 和s t r o g a t z l 8 , 4 5 1 提出了一种介于规则模型与随机 模型之间的小世界模型，我们称之为w s 小世界模型，它的典型结构特征是具有较 大的聚集系数和较小的平均距离。这旱的小世界，之所以说是小世界，是说网络具 有小的最短路径长度，网络中的节点经过很小的步长便可到达其他节点，与网络的 物理距离无关。 1 9 6 7 年，美国哈佛大学位著名的社会心理学家s t a n l e ym i l g r a m 做了一个有 趣的实验，他要求每一位参与者将一封信交给他们各自熟悉的人，然后传下去，最 终使得这封信能够到达指定的人手里。结果证明那封信平均只需经过6 个人便可以 到达指定人的手中。这一实验也就成为著名理论“六度分离”的起源。从此，小世 界这一概念便传播开来。 大的聚集系数和小的平均距离这两个统计特性便称为小世界效应，具有这种统 计特性的网络即为小世界网络。经过丈量的研究计算发现，大量的真实网络具有小 世界特征。 w s 小世界模型可以通过以下算法牛成： 1 ) 给定一规则网络。从一个具有n 个节点的最近邻耦合网络开始，每个节点 只与它最邻近的k 个节点相连( k 为偶数) ，为保证网络的稀疏性，使k 口，a a 一口，a b - - - ) b ，6 + 妒一b ，bo ) b b 公式3 - ( 1 ) 这里“o ”表示两种信息相互作用，a o b 和b o a 含义相同，“一”表示信息 作用后的结果输出。 两种信息存网络中传播，其中一种信息可以抑制另一种信息的传播，并且信息 的出现时间存在定的间隔。针对这种现象，本文提出了单方抑制作用下的双信息 第三章单方抑制作川下的舣信息传播模型 传播模型，来描述这种现象，分析信息问的抑制作用、信息出现的时问问隔以等因 素对传播的影响，以期找出更好的控制策