WUHAN TEXTILE UNIVERSITY
2013届本科毕业论文(设计)
题 目：复杂网络上流行病传播的研究
院 系：数学与计算机学院 专 业：信息与计算科学 姓 名：陆乔时 学 号：0909281023 指导老师：赵军产
2013年5月
摘 要
复杂网络作为一门新兴的学科在最近几十年得到了迅速发展，在现实世界中许多实际问题都可以抽象为复杂网络模型进行研究，如很多疾病的传播过程等都可通过复杂网络动态方法来进行相关研究。研究复杂网络上疾病传播有非常重要的实际意义，可以帮助我们揭示疾病流行的规律，预测其发展趋势，分析疾病流行的原因和关键因素，进而探索对其预防和控制的最优策略。
首先介绍了复杂网络发展过程中几个重要的网络模型，比如：规则网络模型、随机网络模型、WS 小世界网络模型、BA 无标度网络模型，并用MATLAB 生成了对应网络的拓扑结构分布图以及度的概率分布图。然后在已建立好的两种网络模型(WS小世界网络模型、QQ 网络模型) 上分别研究流行病的传播与预防机制，最后得出相关结论。
关键词：复杂网络； WS小世界网络； QQ网络； 度； 流行病
Abstract
Complex network is a new subject that has been developing rapidly in recent decades. In the real world, many practical problems can be abstracted as a complex network model for research such as disease transmission. The study of complex network is quite important, for example, it can help us control the disease to spread, forecast trends, analyze the causes and key factors of epidemics, look for the best strategy for prevention and treatment.
Firstly, introducing the most important of network models, such as the regular network, the random network, the WS network and the BA network. Next using the tool of MATLAB simulations to achieve the topology and degree of distribution. Secondly, working out the efficiency of them and strategy for prevention based on the founded network models (the WS network and QQ network).Finally, we can directly find the result from the data.
Key words ：complex network; WS network; QQ network; degree; disease
目 录
1. 绪论 . ............................................. 1
1.1 研究背景和研究意义 ................................... 1
1.2 复杂网络理论的研究现状 ............................... 1
1.3 复杂网络在传播动力学方面的应用 ....................... 3
1.4 复杂网络对于传染病的研究方法 ......................... 3
2. 预备知识 . ......................................... 5
2.1 复杂网络图的概念及表示 ............................... 5
2.2 复杂网络上网络系统的复杂性 ........................... 6
2.3 复杂网络的常用统计量 ................................. 7
2.3.1 度与度分布 (Degree and degree distribution) . ................... 7
2.3.2 平均路径长度（Characteristic path length） . ...................... 7
2.3.3 聚类系数（Clustering coefficient） ..................................... 8
2.3.4 介数（Betweenness ） . ....................................................... 9
2.4 复杂网络模型 ......................................... 9
2.4.1 规则网络(regular network) .................................................. 9
2.4.2 随机网络(random network) ............................................... 10
2.4.3 WS 小世界网络(WS network) .......................................... 11
2.4.4 BA 无标度网络(BA network) ............................................. 13
2.5 本章小结 ............................................ 14
3. 模型建立 . ........................................ 15
3.1 随机网络 ............................................ 15
3.2 WS小世界网络 ....................................... 17
3.3 QQ网络 ............................................. 20
3.4 本章小结 ............................................ 20
4. 针对网络模型节点感染分析 ......................... 21
4.1 选取较大节点进行控制 ................................ 21
4.2 选取随机节点进行控制 ................................ 22
4.3 选取“熟人免疫”节点进行控制分析 .................... 23
4.4 本章小结 ............................................ 24
5. 总结 . ............................................ 27
参考文献： .............................................. 28
致 谢 .................................................. 29
1 绪论
1.1 研究背景和研究意义
人类历史上曾多次受到危害极其严重的传染病的威胁，对传染病的描述和预测是人们由来已久的研究课题。从20世纪四、五十年代开始，以微分方程为主的决定论模型逐渐受到重视，一直到现在仍然具有非常重要的学术地位。近年来，复杂网络引起了许多相关领域(其中包括自然、生物、信息管理等) 研究人员的高度关注。所谓复杂网络就是具有复杂拓扑结构和动力学行为的大规模网络，它是由大量的节点通过边的相互连接而构成的图。例如：无线通讯网络、食物链网络、社会关系网络、科学家合作网络、新陈代谢网、蛋白质网、流行病传播网等等都是复杂网络。实际生活中存在大量的复杂网络，这促使我们去研究这些复杂网络的拓扑几何性质、网络的静态行为以及发生在网络上的传播动力学行为[6]。
传染疾病的传播过程中充满了偶然因素的影响，它的传播显然是一种复杂现象。这是因为传染病传播的载体——人和人之间的交流、接触、联系所形成的系统是复杂的。易感染、有传染性的个体，全都是有主动性的个体，他们的行为方式对于病情的发展具有影响，同时也会随外界情况的变化产生适应性的变化，这也造成了要研究的问题的复杂性。
深入研究复杂网络，可以揭示隐藏在复杂系统(其中一些复杂系统关乎国计民生) 中的共同规律，这种一般性规律的揭示对于把握复杂系统的宏观特征，对于调节复杂系统上的动力行为都将具有重要意义[13]。
1.2 复杂网络理论的研究现状
自1998年Watts 和 Strogatz [1] 提出WS 小世界网络模型之后，在短短不到十年的时间里，科学家们在全世界范围内掀起了研究复杂网络的热潮。不同领域的研究者们从不同的方向上展开了复杂网络的具体研究工作，并取得了大量的研究成果。
对实际网络进行统计分析是复杂网络最基本、也是最重要的研究手段之一。特别是航空网络、股票网络、科学家合作网络等等，通过对数据的分析与统计，发现这些实际的网络都具有复杂网络的特性。
根据各种不同的复杂网络数据的分析结果，概括出它们的共同特性，就可以
构建出与实际网络相同或类似的网络模型。如最初Watts 和 Strogtz 提出的小世界模型[4]和BA 无标度网络模型[2]。
复杂网络起源于传统的网络图的研究。人们对于网络的图的研究可以追溯到18世纪的著名的柯尼斯堡“七桥问题”。Konigsberg 是东普鲁士(现俄罗斯) 的一个城镇，城中有一条横贯城区的河流，河中有两个岛，两岸和两岛之间共架有七座桥，传说当地居民常常议论这样一个有趣的问题：一个人能否在一次散步中走过所有的七座桥，而且每座桥只经过一次，最后返回原地？走过问题看起来似乎相当简单，但长期以来小镇上没有一个人能走出这样一条路径。1735年，瑞士数学家欧拉研究并解决了此问题，他对于七桥问题的研究所采用的抽象和论证的思想，开创了数学的一个分支—图论(graph theory)的研究。事实上，今天人们关于复杂网络的研究与欧拉当年关于七桥问题的研究在某种程度上是一脉相承的，即网络结构与网络性质密切相关。在欧拉解决了七桥问题之后的相当长一段时间里，图论并未获得足够的发展。直到1936年才出版了关于图论的第一部专著，此后图论开始进入发展与突破的快车道。20世纪60年代，匈牙利数学家Erdos 和Renyi 建立了著名的随机图理论(random graph theory)，开创了复杂网络理论的系统研究之路[5]。在此之后的四十年中，随机图理论一直是研究复杂网络的理论基础。在此期间，人们也做了试图揭示社会网络特征的一些实验，比较著名的小世界实验(small word experiment)如Milgram 的“六度分离”小世界实验[4]，Kevin Bacon游戏及Internet 上的小世界实验等。而事实上，绝大多数实际的复杂网络结构并非是完全随机的。例如，两个人是否是朋友，Internet 中两个路由器之间是否有光纤连接，WWW 上两个页面之间是否有超文本链接等都不会完全是靠抛硬币来决定的。在20世纪即将结束之际，对复杂网络的科学探索发生了重要的转变，复杂网络理论研究也不再局限于数学领域。人们开始考虑节点数量众多、连接结构复杂的实际网络的整体特性，在从物理学到生物学的众多学科中掀起了研究复杂网络的热潮，甚至被称为“网络的新科学” [4-5]。有两篇开创性的文章可以看作是复杂网络研究新纪元的标志：一篇是美国康纳尔(Cornell)大学理论和应用力学的博士生Watts 及其导师、非线性动力学专家Strogatz 教授于1998年6月在Nature 杂志上发表的题为《“小世界”网络的集体动力学》(Collective Dynamics of ‘Small-World ’ Networks) 的文章[4]；另外一篇是美国Notre Dame
大学物理系的Barabasi 教授及其博士生Albert 于1999年10月在Science 杂志上发表的题为《随机网络中标度的涌现》 （Emergence of Scaling in Random Networks ）[5]的文章。这两篇文章分别揭示了复杂网络的小世界效应和无标度特性，并建立了相应的模型阐述它们的形成机理。
1.3 复杂网络在传播动力学方面的应用
基于复杂网络上的传播动力学问题一直都是复杂网络研究领域的重要课题。近年来，随着复杂网络拓扑结构研究的迅猛发展，人们逐步认识到不同事物在真实系统中的传播现象，例如传染病在人群中的传播，计算机病毒的传播，谣言在社会中的传播等，都可以看做是在复杂网络上服从某种规律的传播行为。如何去描述这些事物的传播过程，揭示他们的传播特性，进而寻找出能够有效控制这些行为的方法一直都是科学家们关注的焦点。由于近年来人类正面临种种疾病(如甲型H1N1、最近的H7N9等) 的长期而严峻的威胁，这给我国人民的生命和国家经济带来了严重的影响。由此复杂网络上疾病传播行为的研究也日益走向人们高度重视与研究的趋势，成为网络研究的最主要的目的之一。在复杂网络疾病传播的研究中将人群中的个体看作网络中的节点，个体间联系看作网络中的边，这样就建立了网络的拓扑结构。由于真实网络通常具有小世界性和无标度性，因此在研究中一般假设研究的网络是WS 均匀网络或BA 无标度网络。建立网络拓扑结构后，可根据疾病在个体间的传播特性、发展规律以及人与人之间的传染机制，建立能够反映传染病动力学特性的数学模型。近年来科学家对于复杂网络上的传染病动力学行为进行了深入的研究，并提出了很多相关的符合实际的传播模型。通过对模型动力学性态的定性、定量的分析和数值模拟，来显示疾病的传播过程，揭示疾病的流行规律，预测其发展变化趋势，进而找出疾病流行的原因和关键因素，从而寻找对其预防和控制的最佳策略，为人们防治决策提供理论基础和数量依据。
1.4 复杂网络对于传染病的研究方法
首先介绍了复杂网络上几个重要的拓扑几何性质，比如：度、度分布、平均度、最短路径的算法[7]等，这些概念与性质对于刻画复杂网络有着非常重要的意义。其次详细介绍了复杂网络发展过程中最重要的几个网络模型，如：规则网络模型、随机网络模型、WS 小世界网络模型、BA 无标度网络模型，并依靠MATLAB
开发工具对其进行了不同层次的分析。
接着在已建立好的WS 小世界网络模型和QQ 网络模型上针对节点的控制情况进行分析，采用控制度较大节点、随机节点和“熟人免疫”节点三种不同方式进行比较分析，得出流行病的预防与控制的最佳策略。
最后对与在复杂网络上流行病的研究理论作了较细致的总结，对传播数据做了系统合理化的分析。
2 预备知识
2.1 复杂网络图的概念及表示
复杂网络研究的兴起使得人们开始广泛关注网络结构复杂性及其与网络行为之间的相互关系。要研究各种不同的复杂网络在结构上的共性，首先需要有一种描述网络的统一的工具，这种工具在数学上称为图(Graph)[7]。
图论是一门应用数学，它的概念和结果来源非常广泛，既有来自生产实践的问题，也有来自理论研究的问题，就拿著名的Konigsberg 七桥问题为例：在贯穿古普鲁士Konigsberg 城(第二次世界大战时划归原苏联，改名Kalin-ingrad ，今属白俄罗斯) 的 Pregel 河上有七座连接两岸及河中的两个小岛(如图2-1所示，第二次世界大战时已几乎夷为平地) 。当时困扰当地居民的一个问题是：是否存在一种走法，走过每座桥恰好一次。虽然当时多数人相信不存在这种走法，但没有人能解释其原因。问题被提到当时在St.Peitersburg 的数学教授Euler (1707~1782)面前，他把每块地用一个顶点代替，把每座桥用连接对应顶点的一条边代替，把问题抽象为图2-2中的图。为解决这个问题，他提出了判定一般图存在这种走法的充要条件，并给出了必要性的证明。
图 2-1 图2-2
网络最初属于图论的研究范畴，从数学意义上来说一个具体网路是由节点集V 和边集E 组成的图，且此图可以用G = (V , E) 来表示。其中网络中的节点总数用N = 表示，网络中的边数用M =E 表示，且边集E 中中每条边都有一个节点与之对应。我们把节点对(i , j )与(j , i )对应同一条边的网络成为无向网络(undirected network)，否则称为有向网络(directed network)。如果网络中每条边都赋予了与之相应的权值，则该网络称为加权网络(weighted network)，否则该网络成为无权网络(unweighted network)，基于这一定义那么无权网络可以看作是每条
边的权值都为1的等权网络。此外一个网络中节点可能是不同类型的，例如在科
学家合作网络中，节点代表不同的科学家，而权代表科学家之间的合作次数。图
2-3给出了几个不同类型的网络的例子。在图论中，称不包含环和重边的图为简
单图(simple graph)。
图2-3 a)单一类型节点和边的无向网络 b) 不同类型节点和边的无向网络
c) 节点和边权重变化的无向网络 d) 有向网络
2.2 复杂网络上网络系统的复杂性
一切系统都具有网络结构，复杂系统具有复杂的网络结构。复杂网络也是研
究复杂系统的一种技术和方法，它关注系统中个体相互作用的拓扑结构，是理解
复杂系统性质和功能的基本方法。网络系统的复杂性主要体现在以下四个方面：
(1) 结构复杂性
网络连接结构错综复杂、极其混乱，同时又蕴含着丰富的结构：社区、基序、
聚集性、生成规律等等，而且网络连接结构可能是随时间变化的，例如：WWW
上每天都不停地有页面和链接的产生和删除。
静态结构的复杂性和结构动态演化的复杂性。例如：神经系统有神经元互联
形成，连接以“突触连接结构”实现，突触有强弱、兴奋与抑制、不同的神经递
质；连接不断改变，形成连接结构变化。(重边，加权等)
(2) 节点复杂性
网络中的节点可能是具有分岔和混沌等复杂非线性行为的动力系统。如基因
网络中每个节点都具有复杂的时间演化行为，而且，一个网络中可能存在多种不
同类型的节点。例如：控制哺乳动物中细胞分裂的生化网络就包含各种各样的基
质和酶。
当关联失去时，这类特性会在节点处消失或改变。例如，
耦合神经元重复地
被同时激活，那么它们之间的连接就会加强，这被认为是记忆和学习的基础。
(3) 复杂网络之间相互影响的复杂性
实际的复杂网络会受到各种各样因素的影响和作用。如电力网络故障会导致
Internet 网速变慢，运输系统失控等一系列不同网络间的连锁反应。
(4) 网络分层结构的复杂性
行政管理网络是具有层结构的，多数网络都有节点的分层结构，只是在许多
网络中没有意识到时一种造成复杂性的重要结构。
2.3 复杂网络的常用统计量
2.3.1 度与度分布 (Degree and degree distribution)
度(degree)是单个节点的属性中最基本的概念，图论中节点i 的度k i 定义为与
该节点连接的其他节点的数目，从直观上，一个节点的度越大就意味着这个节点
在某种意义上越重要。一般来说，并不是所有的节点都具有相同的度，通常用分
布函数P(k)来描述网络中节点的度分布情况，P(k)表示一个随机选定节点的度
恰好为k 的概率。节点度的分布特征是网络的重要几何性质，规则网络中各节点
的度值相同，符合Delta 分布，随机网络的度分布可近似为Poisson 分布，大量
的实际网络存在幂律形式的度分布，称为无标度网络，同时在现实中还有很多网
络的度分布服从指数分布。
2.3.2 平均路径长度（Characteristic path length）
网络中两个节点i 和j 之间的距离d ij 定义为连接这两个节点的最短路径上
的边数。网络中任意两个节点之间的距离的最大值称为网路的直径(diameter)，
记为D ，即：
D =max d ij i , j
网络的平均路径长度定义为任意两个节点之间的距离的平均值，即：
L =1d ij ∑N (N +1) /2i ≥j
式中:N为网络节点数。网络的平均路径长度也称为网络的特征路径长度，
用来衡量网络节点间的离散程度。研究表明，尽管许多实际网络的节点数巨大，
但网络的平均路径长度L 相对于N 来说却很小，这种现象称之为“小世界效应” 。
2.3.3 聚类系数（Clustering coefficient）
在很多真实网络中，常常有这样的情况：如果顶点A 与顶点B 相连，并且顶
点B 与顶点C 相连，那么顶点A 也极有可能与顶点C 相连。把此类情况引申到社
会网络中，即你的朋友的朋友也有可能是你的朋友，这种属性是很容易理解的，
在复杂网络中我们通常把这种属性称为网络的聚类性。
一般地，假设网络G 中一个节点i 有e i 条边和其他k i 个节点相连，这k i 个节
点就称为节点i 的邻居。显然，这k i 个节点间最多可能有k i (k i -1) /2条边，k i 个
节点之间实际存在的边数E i 与总的可能边数的比值定义为节点i 的聚类系数C i ，
网络中所有节点i 的聚类系数的平均值就是网络的聚类系数，用C 表示，即：
C i =2E i ， k i (k i -1)
1
N C =∑G
i ∈G i 。
显然从上面式子可知，整个网络的聚类系数C 满足0≤C ≤1。当C =0时对
应网络中所有的节点都是孤立节点的情况，即任何节点对之间都没有边连接；而
C =1对应的网络是全局耦合网络。
此外节点i 的聚类系数也可定义为:
与点i 相连的三角形的数量 C i =与点i 相连的三角组的数量
式中：与点i 相连的三角组的数量是指包括节点i 的3个节点，并且至少存
在从节点i 到其他2个节点的2条边，如图2-4所示。
图2-4(a)中节点i 的聚类系数C i =1；图2-4(b)中节点i 的聚类系数C i =0。
图2-4 以节点i 为中心的三点组的可能形式
2.3.4 介数（Betweenness ）
介数(Betweenness Centrality) 通常分为边介数和节点介数两种。节点介数定义为网络中所有最短路径中经过该节点的路径的数目占最短路径总数的比例。边介数定义为网络中所有最短路径中经过该边的路径的数目占最短路径总数的比例。介数反映了相应的节点或者边在整个网络中的作用和影响力，是一个重要的全局几何量，具有很强的现实意义。例如，在社会关系网或技术网络中，介数的分布特征反映了不同人员、资源和技术在相应生产关系中的地位，这对于发现和保护关键资源、技术和人才具有重要意义。
2.4 复杂网络模型
复杂网络中最重要的几个模型，其中包括规则网络(regular network) 、随机网络(random network ) 、WS 小世界网络(WS network ) 以及BA 无标度网络(BA network ) 。
2.4.1 规则网络(regular network)
在一个全局耦合网络（globally coupled network ）中，任意两个点之间都有边直接相连。因此，在具有相同节点数的所有的网络中，全局耦合网络均有最小路径长度L gc =1和最大聚类系数C gc =1。
在一个网路规模为N 的全局耦合网络中，其对应的边数有N (N -1)/2条，然而大多数大型的实际网络都是很稀疏的，它门的数目一般至多是O (N )而不是O N 2，这就表明全局耦合网络作为实际网络是有局限性的。 ()
在最近耦合网络(nearest-neighbor coupled network) 中每个节点和它周围的邻居点相连。具有周期边界条件的最近邻耦合网络包含N
个围成一个环的点，其
中每个节点都于它左右各K /2个邻居点相连，这里K 是一个偶数。对较大的K 值，最近邻耦合网络的聚类系数为：
C nc =3(K -2)3≈ 4K -14
由此最近邻耦合网络是高度聚类的网络。然而，最近耦合网络不是一个小世界网络。相反，对固定的K 值，该网络的平均路径长度为：
L nc ≈N →∞(N →∞) 2N
另外，规则网络中还有一类比较特殊的为星形耦合网络(star coupled network) 。它有一个中心点，其余的N -1个点都只是与这个中心点连接，而N -1个点之间彼此不连接，其中星形网络的平均路径长度为：
L star =2-2(N -1)→2(N →∞) N N -1常见的几个规则网络如下图：
a) b)
c) 图2-5 (a)全局耦合网络；(b)最近邻耦合网络；(c)星形网络
2.4.2 随机网络(random network)
20世纪60年代，由两位匈牙利数学家Erd ǒs 和R ényi 建立的随机图理论（random graph theory）被公认为是在数学上开创了复杂网络理论的系统性研究。与完全规则网络相反的是完全随机网络，随机网络的描述方式如下：给定网络节点总数N ，网络中任意两个节点以概率p 连接，生成的网络全体记为G (N , p )，构成一个概率空间。
由N 个节点构成的图中，可以存在N (N -1)/2条边，从中随机连接M 条边所构成的网络就叫随机网络。其中一个典型的模型是Erdos 和Renyi 于40
多年
前开始研究的ER 随机网络图模型，简称ER 模型。它的模型构造算法是对于N 个网络节点，以概率p 对每一个节点对进行连边，得到一个有N 个节点，约pN (N -1)/2条边的随机网络。
假设有大量的节点(N >1)落在纸上，并以相同的概率p 给每对节点连上一根线，这样就得到一个有N 个节点，约pN (N -1)/2条边的ER 随机图的实例，如下图2-6:
图2-6 a) 概率p =0，给定的10个孤立点生成的随机图
b) 概率p =0. 1，给定的10个孤立点生成的随机图
c) 概率p =0. 15给定的10个孤立点生成的随机图
2.4.3 WS 小世界网络(WS network)
我们或许有过这样的经历：偶尔碰到一个陌生人，同他聊了一会儿后发现你认识的某个人居然他也认识，然后发出“这个世界真小”的感慨。那么对于世界上任意两个人来说，借助第三者、第四者这样的间接关系来建立起他们两人的联系，平均需要通过多少人呢？20世纪60年代美国哈佛大学的心理学家Stanley Milgram 通过一些实验后得出结论：中间的联系人平均只需要5个。他把这个结论称为“六度分离(six degrees separation)”。也就是平均只要通过5个人，你就能与世界任何一个角落的任何一个人发生联系。这个结论定量地说明了我们世界的
“大小”，或者说人与人关系的紧密程度。
30多年来，六度分离理论一直被作为社会心理学的经典范例之一。尽管如此，实际上这个理论并没有得到严格的证实。美国心理学教授朱迪斯•克兰菲尔德(Judith Kleinfeld) 对米尔格伦最初的实验提出不同意见，因为她发现实验的完成率极低。
作为完全规则网络像完全随机网络的过渡，1998年，Watts 和Strongtz 提出了一种小世界网络模型，称为WS 小世界网络模型。WS 网络是一种不同于规则网络和随机网络的网络，它的构造算法如下：
(1)从规则网络开始：考虑一个含有N 个节点的最近邻耦合网络，它们围成一个环，每个节点都与它左右相邻的各K /2节点相连接结，其中K 是偶数。
(2)随机化重连：以概率p 随机地重新连接网络中每个边，即将边的一个端点保持不变，而另一个端点取为网络中随机选择的一个节点。假设任意两个不同的节点之间至多只能有一条边，并且每一个节点都不能有边与自身相连。 当p 取不同的值时对应不同的网络，当p =0对应于完全规则网络，p =1则对应于完全随机网络，当p 满足条件0
由上述算法得到的网络模型的平均路径长度L (p )和聚类系数C (p )特性都可以看作重连概率p 的函数，图2-7显示了网络的平均最短路径L 和平均聚类系数C 重连概率p 的变化关系(图中对两个值作了归一化处理) 。当p =0时是规则网络，当p =1时则为随机网络；对于0
图2-7 WS小世界模型的聚类系数和平均路径长度随重连概率p 的变化关系
2.4.4 BA 无标度网络(BA network)
无标度网络经过长时间演化后将导致绝大多数点只有少数连接边，而存在极少数点具有大量连接边，由大量边连接的节点成为该网络的中枢点。因此，无标度网络针对随机失效具有很强的鲁棒性(Robustness)，对于选择性攻击，无标度网络具有脆弱性(Fragility)性。近年来，学者们通过实证研究发现得到了大量的实际网络都是无标度网络，其中包括我们熟知的Internet 、WWW 、各种社会网络等等。由此无标度网络也是近年来一个重要的研究课题。
为了解释幂律分布的产生机理，Barabasi 和Albert 提出了一个无标度网络模型，现被称为BA 模型，其对应的演化算法如下：
(l)增长(Growth)性：开始有少量(m 0个)点，每新添加一个节点，新的节点与
已存在于系统中的m ≤m 0个点相连接，产生m 条新边。例如www 上每天会有
大量的新的网页产生，每个月会有许多新的科研文章发表。
(2)择优连接 (Preferential attachment)性：即新的节点更倾向于与那些具有较高的连接度的“大”的节点相连接。这种现象也称为“富者愈富(rich get richer)”或“马太效应 (Matthew effect)”。例如，一些新发表的文献倾向于引用那些被广泛引用的重要文献，新的个人主页上的超文本链接更有可能指向百度、新浪等著名网点。一个新的节点与一个已经存在的节点i 相连的概率∏i 与节点i 的度k i 、节点j 的度k j 之间满足如下关系： ()
∏i =k i k j
j
在t 时刻，BA 模型演化成一个有N =t +m 0个节点、mt 条边和总度数为∑k j j =2mt 的随机网络。图2-8显示了当m =m 0=2时的BA 网络的演化过程。初始网络有两个节点，每次新增加的一个节点按优先机制与网络中已存在的两个节点相连。
图2-8 BA 无标度网络的演化(m =m 0=2)
2.5 本章小结
本章主要介绍了有关复杂网络的一些基本知识，比如：度、度分布，最短路径，聚类系数。这些概念和性质是刻画复杂网络特征的基本手段和重要工具。其次，介绍了复杂网络发展过程中几个重要的网络模型，比如：规则网络模型、随机网络模型、小世界网络模型、无标度网络模型。接下来的章节会用到度的概念以及已经介绍了的两个网络模型：WS 小世界网络和QQ 网络。通过研究两种模型下节点的控制情况来分析流行病的蔓延，做到更好的预防与控制。
3 模型建立
3.1 随机网络
通过matlab 工具建立一个随机网络(random network) 模型，具体设定参数如下：
网络图中节点的总数目N =20；网络图中边的平均连接度alph =0. 25；表征边的平均长度的参数beta =0. 3。选取的是概率排序法，即总共生成的边数为
并以一定的较小的概率对边随机化重连；重新连接的概率p N *(N -1)/2*alph ，
分别选取0,0.1,1。
1）重新连接的概率为0时，计算所得该随机图的边数为：48，随机图的平均路径长度为：2.6632，随机图的聚类系数为：0.75155，随机图的平均度为：4.8，其中节点4只有一个邻居节点，其聚类系数赋值为0；节点17只有一个邻居节点，其聚类系数赋值为0
生成的随机网络图如下：
网络图中各节点的度的大小分布图
网络图中节点度的概率分布图
各节点的度数K 节点度为K 的概率 P (K ) 节点编号n 节点的度 K
图3-1 生成的节点为20，p =0的随机网络、
度的大小以及度的概率分布图
2）重新连接的概率为0. 1时，计算所得该随机图的边数为：48，随机图的平均路径长度为：Inf ，随机图的聚类系数为：0.46873，随机图的平均度为：4.8，其中节点4为孤立节点，其聚类系数赋值为0；节点12为孤立节点，其聚类系数赋值为0，由此可得该网络图不是连通图 生成的随机网络图如下：
节点度为K 的概率 P (K )
网络图中各节点的度的大小分布图
各节点的度数K
节点编号n
网络图中节点度的概率分布图
节点的度 K
图3-2 生成的节点为20，p =0. 1的随机网络、 度的大小以及度的概率分布图
3）重新连接的概率为1时，计算所得该随机图的边数为：48，随机图的平均路径长度为：Inf ，随机图的聚类系数为：0.23405，随机图的平均度为：4.8，其中节点3为孤立节点，其聚类系数赋值为0，由此可得该网络图不是连通图
生成的随机网络图如下：
节点度为K 的概率 P (K )
网络图中各节点的度的大小分布图
各节点的度数K
节点编号n
网络图中节点度的概率分布图
节点的度 K
图3-3 生成的节点为20，p =1的随机网络、
度的大小以及度的概率分布图
根据上图显示的网络图形可看出，随机网络有着很小的平均路径长度，但同时集聚系数也很小，每条边的出现与否都是独立的，因此随机网络不能反应真实网络的性质。
3.2 WS小世界网络
通过matlab 工具建立一个WS 小世界网络(WS network)模型，具体设定参数如下：
网络图中最近邻耦合网络中节点的总数N =20；最近邻耦合网络中每个节点的邻居节点的个数的一半k =2。随机化重连的概率p 分别选取0,0.3,1。
1）重新连接的概率为0时，得出该随即图的平均路径长度为2.8947，该随机图的聚类系数为0.5，该随即图的平均度为4。
生成的WS 小世界网络图如下：
网络图中各节点的度的大小分布图
各节点的度数K
节点度为K 的概率 P (K )
节点编号n
网络图中节点度的概率分布图
节点的度 K
图3-4 生成的节点为20，p 0的WS 小世界网络、
度的大小以及度的概率分布图
2）重新连接的概率为0. 3时，得出该随即图的平均路径长度为2.2158，该随机图的聚类系数为0.30381，该随即图的平均度为4。
生成的WS 小世界网络图如下：
网络图中各节点的度的大小分布图
各节点的度数K
节点编号n
网络图中节点度的概率分布图
节点度为K 的概率 P (K )
节点的度 K
图3-5 生成的节点为20，p 0. 3的WS 小世界网络、 度的大小以及度的概率分布图
3）重新连接的概率为1时，得出该随即图的平均路径长度为2.1211，该随机图的聚类系数为0.073095，该随即图的平均度为4。
生成的WS 小世界网络图如下：
各节点的度数K
网络图中各节点的度的大小分布图
节点编号n
网络图中节点度的概率分布图
节点度为K 的概率 P (K )
节点的度 K
图3-6 生成的节点为20，p 1的WS 小世界网络、
度的大小以及度的概率分布图
根据上图显示的网络图形可看出，大部分节点彼此并不相连，但绝大部分节点之间经过少数几步后就可到达。各节点之间的连接也很均匀，因此小世界网络的度也分布十分均匀，对应的节点度的概率分布也十分均匀。
3.3 QQ网络
根据Excel 数据表格，所描出QQ 网络模型图如下：
图3-7 生成的节点为113的QQ 网络
由图3-7可得，班级社会网络的聚类系数为0.6147，非常高，说明有明显的聚类性质（抱团现象）。根据Excel 表格数据分析，可得出节点的度呈现较大趋势变化，这也正与图3-7显示一致，这一点在班级紧密结构上表现得很明显。
3.4 本章小结
本章主要建立三个网络模型，分别是规模为20的随机网络(random network)和规模为20的WS 小世界网络(WS network) 以及规模为113的QQ 网络。其中随机网络(random network)的节点的平均度为4.8，总度数为96，而WS 小世界网络(WS network)的节点的平均度为4，总度数为80。两个网络规模到总的度数都是相近的，在数据分析上具有一定的可比性。虽然两者的规模相近，但从网络的结构特性上有着很大的差异，一个度分布十分均匀，另一个还存在孤立点。
下一章将基于两种网络：WS 小世界网络与QQ 网络模型，分析不同的节点控制情况，从而更好的做到流行病的控制。
4 针对网络模型节点感染分析
本章选用三种控制节点方式进行研究：选取度较大节点、选取随机节点、
选取“熟人免疫”节点。选取度较大的节点就是指将200个节点中的度最大的节点按顺序依次选取控制；随机选取节点就是指在200个节点中不考察节点度数任意选取若干个控制；“熟人免疫”就是先在随机选取了若干个节点的情况下，再把随机选取的节点的任意一个有关系的节点控制起来。
将选取的节点控制起来，那些和已经控制的节点有联系的也看做被控制了，但是重复被控制的只记一次。在200个节点中按选取情况选取10个节点，按照控制2个、4个、6个等的顺序将这些节点控制起来，再统计一共控制的节点，求出相应的控制率，用matlab 作出控制率的曲线，以便更直观的观察控制情况。主要是分别将两种网络模型放在一起进行比较，然后再单个去分析三种选取节点的方式对这个两个网络模型的优势和劣势。
4.1 选取较大节点进行控制
第一种选取节点的方式为选取度较大的节点，将其控制起来。所谓度较大的节点，指的是图中与其它节点连线最多的节点。将200个节点中的度最大的前十个排序列举出来，分别控制2、4、6、8、10个，计算控制率。
可以得出以下数据：
表4.1
通过matlab 描点得出控制节点图如下：
2
345678910
图4-1 “—”WS 小世界网络 “---”QQ 网络
由图4-1可知，WS 小世界网络和QQ 网络的控制率与控制节点的个数成正相关增长。但是度较大的节点对QQ 网络而言更具有控制力度，更重要。
4.2 选取随机节点进行控制
第二种选取节点的方式为随机选取。随机在200个节点中选取10个，分别2、4、6、8、10个，计算控制率
表4.2
通过matlab 描点得出控制节点图如下：
2
345678910
图4-2 “—”WS 小世界网络 “---”QQ 网络
由图4-2可知，QQ 网络的控制率还是明显高于WS 小世界网络。但QQ 网络的节点度分布差异很大，所以在控制曲线斜率的问题上，每一次的随机选取作出的曲线斜率差距会出现很大的波动。相对而言，WS 小世界网络在随机选取节点做控制时，会稳定很多，会随着节点控制数量的增加而网络控制率平稳的上升。
4.3 选取“熟人免疫”节点进行控制分析
所谓“熟人免疫”就是指对随机选出节点再随机选一个邻近节点进行免疫。在本篇中就是指在4.2中的随机选取节点后再做一步选取，控制随机选取的节点的一个与其有联系的随机的邻近节点。控制率的算法和以上两种情况也一样。
表4.3
通过matlab 描点得出控制节点图如下：
2
345678910
图4-3 “—”WS 小世界网络 “---”QQ 网络
由图4-3可知，QQ 网络控制效果好。当随机选一点再选择其邻居节点时，QQ 网络中度大节点比度小节点被选中的概率大得多。那么控制度较大的节点的概率也就大大提高，相应的对整个网络的控制率就大大提高。
4.4 本章小结
4.1-4.3分别将三种选取节点的方法对于两种网络的控制率曲线进行对比。
显然，QQ 网络的控制率远高于WS 小世界网络，且选取度较大的节点控制后，对整个网络的控制率影响很明显。由于QQ 网络节点度上升很快，控制率上升很快，而WS 小世界网络这一变化就不是很明显，即在图上表现为曲线斜率很小。QQ 网络的节点度分布很不均匀，部分节点度很大，部分可能为孤立点，所以当随机选取QQ 网络节点时，得到的控制率曲线可能变化不均匀，即在图上显示曲线的斜率变化波动较明显。而对于WS 小世界网络而言，因为其度分布较均匀，所以三种选取方式对WS 小世界网络差别不大。
2
345678910
图4-4 WS小世界网络 “—”选取度较大节点的控制曲线
“---”选取随机节点的控制曲线 “o —”选取“熟人免疫”节点的控制曲线
由图4-4可得，对于一个WS 小世界网络，在三种节点选取后，还是度较大的节点对整个网络的影响更大。但是由于WS 小世界网络的度分布比较均匀，所以控制曲线的斜率差距并不是很大。
对于复杂网络上流行病的研究，如果采取的是WS 小世界网络建模分析，很
明显采取较大节点对于节点控制率有着更好的效果，即控制较大节点后对于流行病的传播有着更好的措施，从而控制传染病的蔓延。
2345678910
图4-5 QQ 网络
“—”选取度较大节点的控制曲线
“---”选取随机节点的控制曲线 “o —”选取“熟人免疫”节点的控制曲线
由图4-5可得，对于QQ 网络选取较大节点对整个网络具有更好的控制效果。由于QQ 网络本身节点的度分布就不均匀，存在很多度较大的节点以及一些孤立点，所以选取度较大的节点控制起来对于整个网络的节点控制效果还是很理想的。但随机选取或是选取“熟人免疫”节点，那么对网络控制的情况会存在很大的不确定性。
所以对于一个QQ 网络，节点的度是考察节点重要性一个重要依据。在选取控制节点时，选取度较大的节点往往可以得到很好的效果。
对于QQ 网络而言，针对复杂网络上流行病的蔓延与阻止，选取较大节点对于传染病的控制更具有显著的效果，能更好的抑制传染病的传播，做到更好的相对控制。
5 总结
本文首先给出了复杂网络的基本概念，复杂网络中几个重要的网络模型，并用MATLAB 仿真生成了相对应的随机网络(random network) 和WS 小世界网络(WS network) 。其次针对不同的网络模型分析了节点控制问题，并分别选取度较大节点、随机节点以及“熟人免疫”节点进行相关分析，求出各自的控制率。最后通过matlab 描出相应的曲线图，通过比较得出QQ 网络对于节点的控制具有更好的效果，选取度较大进行控制相比其他控制效果好。仿真到复杂网络上流行病的研究问题，QQ 网络对于传染病具有更好的控制作用，选取度较大的节点具有最优性，能更好的控制传染病的蔓延。
目前为止，大多数复杂网络的研究都是关于无权网络的，事实上很多实际网络都表现出加权网络的特征，比如社会关系网，相互作用强度对网络上的疾病传播等过程会产生重要影响、科学家合作网，科学家合作次数、Internet ，Internet 上的宽带等等。此时无权网络的描述就有局限性了，因此研发人员下一步将尝试模型应用到加权网络中，进一步考察其在加权网络上的传播特性[15]。
参考文献：
[1] Watts D J,Strogatz SH.Collective dynamics of mall-word networks[J].Nature,1998.
[2] Barabasi A L.Linked: The New Science of Networks [D]. Massachusetts: Persusu Publ ishing,2002.
[3] Watts D j.The ‘new’ science of networks [J]. Annual Review of Sociology, 2004, 30: 243-270.
[4] Barabasi A L, Albert R. Emergence of scaling of ‘small-world’ networks [J]. Science, 1999, 286 (5439):509-512.
[5] Erdos P, Renyi A.On the evolution of random graghs [J]. Publ Math Inst Hung. Acad. Sci,1960, 5: 17-60.
[6] 汪小帆, 李翔, 陈关荣, 复杂网络理论及其应用清华大学出版社[M].北京,2006.
[7] 孙惠泉, 图论及其应用科学出版社. 北京,2004,30:1-5.
[8] 范彦静, 王化雨. 基于复杂网络的知识网建模研究[J].心智与计算,2008,(01):28-34.
[9] 苟清明, 一个具有阶段结构SIS 流行病模型[J].四川师范大学学报,2007,30(9):590-59 3.
[10] 李光正, 史定华, 复杂网络上疾病传播行为分析[J].自然科学进展,2006.16(4):508-51 2.
[11] 刘浩广, 蔡绍洪, 张玉强等, 复杂网络中几种经典的传播模型的比较[J].贵州大学学报 (自然科学版),2007,24(5):473-478.
[12] 褚建勋. 基于复杂网络的知识传播动力学研究[D].中国科学技术大学,2006.
[13] 高崇阳, 浮燕, 贾丽. 浅谈复杂网络研究及意义[J].中国科技信息,2009,(14):3-5.
[14] 张大陆, 王志晓, 刘雯, 杨哲. 基于复杂网络的本体结构分析[J].同济大学学报(自然科 学版),2009,(02):33-54.
[15] 刘建香. 复杂网络及其在国内研究进展的综述[J].系统科学学报,2009,(04):7-8.
致 谢
本研究及学位论文是在导师赵军产副教授的精心指导下完成的。赵教授严谨的治学态度、敏锐的洞察力、开阔的思维方式深深的影响着我，使我学会了解决问题和处理问题的方法。从课题的选择到项目的最终完成，赵军产老师都始终给予我细心的指导和不懈的支持。感谢导师在百忙之中花大量时间来修改我的论文，使我的工作能顺利进行。借此论文完成之际，谨向敬爱的恩师致以衷心的感谢！
感谢在一起愉快的度过大学生活的信科091班各位同学，是你们让我的大学生活充满了欢笑、快乐，也让我成长，祝愿我们都有美好的未来！特别感谢我的室友，他们在学习上给了我很大的鼓励和帮助，他们的陪伴让我度过了短暂而快乐的大学生活。
毕业论文是再一次系统学习的过程，毕业论文的完成，同样也意味着新的社会生活的开始。我将铭记我曾是一名武汉纺织大学的学子，在今后的工作中把武汉纺织大学的优良传统美德发扬光大。
最后，向所有关心和帮助过我的人致以衷心的感谢！
陆乔时
WUHAN TEXTILE UNIVERSITY
2013届本科毕业论文(设计)
题 目：复杂网络上流行病传播的研究
院 系：数学与计算机学院 专 业：信息与计算科学 姓 名：陆乔时 学 号：0909281023 指导老师：赵军产
2013年5月
摘 要
复杂网络作为一门新兴的学科在最近几十年得到了迅速发展，在现实世界中许多实际问题都可以抽象为复杂网络模型进行研究，如很多疾病的传播过程等都可通过复杂网络动态方法来进行相关研究。研究复杂网络上疾病传播有非常重要的实际意义，可以帮助我们揭示疾病流行的规律，预测其发展趋势，分析疾病流行的原因和关键因素，进而探索对其预防和控制的最优策略。
首先介绍了复杂网络发展过程中几个重要的网络模型，比如：规则网络模型、随机网络模型、WS 小世界网络模型、BA 无标度网络模型，并用MATLAB 生成了对应网络的拓扑结构分布图以及度的概率分布图。然后在已建立好的两种网络模型(WS小世界网络模型、QQ 网络模型) 上分别研究流行病的传播与预防机制，最后得出相关结论。
关键词：复杂网络； WS小世界网络； QQ网络； 度； 流行病
Abstract
Complex network is a new subject that has been developing rapidly in recent decades. In the real world, many practical problems can be abstracted as a complex network model for research such as disease transmission. The study of complex network is quite important, for example, it can help us control the disease to spread, forecast trends, analyze the causes and key factors of epidemics, look for the best strategy for prevention and treatment.
Firstly, introducing the most important of network models, such as the regular network, the random network, the WS network and the BA network. Next using the tool of MATLAB simulations to achieve the topology and degree of distribution. Secondly, working out the efficiency of them and strategy for prevention based on the founded network models (the WS network and QQ network).Finally, we can directly find the result from the data.
Key words ：complex network; WS network; QQ network; degree; disease
目 录
1. 绪论 . ............................................. 1
1.1 研究背景和研究意义 ................................... 1
1.2 复杂网络理论的研究现状 ............................... 1
1.3 复杂网络在传播动力学方面的应用 ....................... 3
1.4 复杂网络对于传染病的研究方法 ......................... 3
2. 预备知识 . ......................................... 5
2.1 复杂网络图的概念及表示 ............................... 5
2.2 复杂网络上网络系统的复杂性 ........................... 6
2.3 复杂网络的常用统计量 ................................. 7
2.3.1 度与度分布 (Degree and degree distribution) . ................... 7
2.3.2 平均路径长度（Characteristic path length） . ...................... 7
2.3.3 聚类系数（Clustering coefficient） ..................................... 8
2.3.4 介数（Betweenness ） . ....................................................... 9
2.4 复杂网络模型 ......................................... 9
2.4.1 规则网络(regular network) .................................................. 9
2.4.2 随机网络(random network) ............................................... 10
2.4.3 WS 小世界网络(WS network) .......................................... 11
2.4.4 BA 无标度网络(BA network) ............................................. 13
2.5 本章小结 ............................................ 14
3. 模型建立 . ........................................ 15
3.1 随机网络 ............................................ 15
3.2 WS小世界网络 ....................................... 17
3.3 QQ网络 ............................................. 20
3.4 本章小结 ............................................ 20
4. 针对网络模型节点感染分析 ......................... 21
4.1 选取较大节点进行控制 ................................ 21
4.2 选取随机节点进行控制 ................................ 22
4.3 选取“熟人免疫”节点进行控制分析 .................... 23
4.4 本章小结 ............................................ 24
5. 总结 . ............................................ 27
参考文献： .............................................. 28
致 谢 .................................................. 29
1 绪论
1.1 研究背景和研究意义
人类历史上曾多次受到危害极其严重的传染病的威胁，对传染病的描述和预测是人们由来已久的研究课题。从20世纪四、五十年代开始，以微分方程为主的决定论模型逐渐受到重视，一直到现在仍然具有非常重要的学术地位。近年来，复杂网络引起了许多相关领域(其中包括自然、生物、信息管理等) 研究人员的高度关注。所谓复杂网络就是具有复杂拓扑结构和动力学行为的大规模网络，它是由大量的节点通过边的相互连接而构成的图。例如：无线通讯网络、食物链网络、社会关系网络、科学家合作网络、新陈代谢网、蛋白质网、流行病传播网等等都是复杂网络。实际生活中存在大量的复杂网络，这促使我们去研究这些复杂网络的拓扑几何性质、网络的静态行为以及发生在网络上的传播动力学行为[6]。
传染疾病的传播过程中充满了偶然因素的影响，它的传播显然是一种复杂现象。这是因为传染病传播的载体——人和人之间的交流、接触、联系所形成的系统是复杂的。易感染、有传染性的个体，全都是有主动性的个体，他们的行为方式对于病情的发展具有影响，同时也会随外界情况的变化产生适应性的变化，这也造成了要研究的问题的复杂性。
深入研究复杂网络，可以揭示隐藏在复杂系统(其中一些复杂系统关乎国计民生) 中的共同规律，这种一般性规律的揭示对于把握复杂系统的宏观特征，对于调节复杂系统上的动力行为都将具有重要意义[13]。
1.2 复杂网络理论的研究现状
自1998年Watts 和 Strogatz [1] 提出WS 小世界网络模型之后，在短短不到十年的时间里，科学家们在全世界范围内掀起了研究复杂网络的热潮。不同领域的研究者们从不同的方向上展开了复杂网络的具体研究工作，并取得了大量的研究成果。
对实际网络进行统计分析是复杂网络最基本、也是最重要的研究手段之一。特别是航空网络、股票网络、科学家合作网络等等，通过对数据的分析与统计，发现这些实际的网络都具有复杂网络的特性。
根据各种不同的复杂网络数据的分析结果，概括出它们的共同特性，就可以
构建出与实际网络相同或类似的网络模型。如最初Watts 和 Strogtz 提出的小世界模型[4]和BA 无标度网络模型[2]。
复杂网络起源于传统的网络图的研究。人们对于网络的图的研究可以追溯到18世纪的著名的柯尼斯堡“七桥问题”。Konigsberg 是东普鲁士(现俄罗斯) 的一个城镇，城中有一条横贯城区的河流，河中有两个岛，两岸和两岛之间共架有七座桥，传说当地居民常常议论这样一个有趣的问题：一个人能否在一次散步中走过所有的七座桥，而且每座桥只经过一次，最后返回原地？走过问题看起来似乎相当简单，但长期以来小镇上没有一个人能走出这样一条路径。1735年，瑞士数学家欧拉研究并解决了此问题，他对于七桥问题的研究所采用的抽象和论证的思想，开创了数学的一个分支—图论(graph theory)的研究。事实上，今天人们关于复杂网络的研究与欧拉当年关于七桥问题的研究在某种程度上是一脉相承的，即网络结构与网络性质密切相关。在欧拉解决了七桥问题之后的相当长一段时间里，图论并未获得足够的发展。直到1936年才出版了关于图论的第一部专著，此后图论开始进入发展与突破的快车道。20世纪60年代，匈牙利数学家Erdos 和Renyi 建立了著名的随机图理论(random graph theory)，开创了复杂网络理论的系统研究之路[5]。在此之后的四十年中，随机图理论一直是研究复杂网络的理论基础。在此期间，人们也做了试图揭示社会网络特征的一些实验，比较著名的小世界实验(small word experiment)如Milgram 的“六度分离”小世界实验[4]，Kevin Bacon游戏及Internet 上的小世界实验等。而事实上，绝大多数实际的复杂网络结构并非是完全随机的。例如，两个人是否是朋友，Internet 中两个路由器之间是否有光纤连接，WWW 上两个页面之间是否有超文本链接等都不会完全是靠抛硬币来决定的。在20世纪即将结束之际，对复杂网络的科学探索发生了重要的转变，复杂网络理论研究也不再局限于数学领域。人们开始考虑节点数量众多、连接结构复杂的实际网络的整体特性，在从物理学到生物学的众多学科中掀起了研究复杂网络的热潮，甚至被称为“网络的新科学” [4-5]。有两篇开创性的文章可以看作是复杂网络研究新纪元的标志：一篇是美国康纳尔(Cornell)大学理论和应用力学的博士生Watts 及其导师、非线性动力学专家Strogatz 教授于1998年6月在Nature 杂志上发表的题为《“小世界”网络的集体动力学》(Collective Dynamics of ‘Small-World ’ Networks) 的文章[4]；另外一篇是美国Notre Dame
大学物理系的Barabasi 教授及其博士生Albert 于1999年10月在Science 杂志上发表的题为《随机网络中标度的涌现》 （Emergence of Scaling in Random Networks ）[5]的文章。这两篇文章分别揭示了复杂网络的小世界效应和无标度特性，并建立了相应的模型阐述它们的形成机理。
1.3 复杂网络在传播动力学方面的应用
基于复杂网络上的传播动力学问题一直都是复杂网络研究领域的重要课题。近年来，随着复杂网络拓扑结构研究的迅猛发展，人们逐步认识到不同事物在真实系统中的传播现象，例如传染病在人群中的传播，计算机病毒的传播，谣言在社会中的传播等，都可以看做是在复杂网络上服从某种规律的传播行为。如何去描述这些事物的传播过程，揭示他们的传播特性，进而寻找出能够有效控制这些行为的方法一直都是科学家们关注的焦点。由于近年来人类正面临种种疾病(如甲型H1N1、最近的H7N9等) 的长期而严峻的威胁，这给我国人民的生命和国家经济带来了严重的影响。由此复杂网络上疾病传播行为的研究也日益走向人们高度重视与研究的趋势，成为网络研究的最主要的目的之一。在复杂网络疾病传播的研究中将人群中的个体看作网络中的节点，个体间联系看作网络中的边，这样就建立了网络的拓扑结构。由于真实网络通常具有小世界性和无标度性，因此在研究中一般假设研究的网络是WS 均匀网络或BA 无标度网络。建立网络拓扑结构后，可根据疾病在个体间的传播特性、发展规律以及人与人之间的传染机制，建立能够反映传染病动力学特性的数学模型。近年来科学家对于复杂网络上的传染病动力学行为进行了深入的研究，并提出了很多相关的符合实际的传播模型。通过对模型动力学性态的定性、定量的分析和数值模拟，来显示疾病的传播过程，揭示疾病的流行规律，预测其发展变化趋势，进而找出疾病流行的原因和关键因素，从而寻找对其预防和控制的最佳策略，为人们防治决策提供理论基础和数量依据。
1.4 复杂网络对于传染病的研究方法
首先介绍了复杂网络上几个重要的拓扑几何性质，比如：度、度分布、平均度、最短路径的算法[7]等，这些概念与性质对于刻画复杂网络有着非常重要的意义。其次详细介绍了复杂网络发展过程中最重要的几个网络模型，如：规则网络模型、随机网络模型、WS 小世界网络模型、BA 无标度网络模型，并依靠MATLAB
开发工具对其进行了不同层次的分析。
接着在已建立好的WS 小世界网络模型和QQ 网络模型上针对节点的控制情况进行分析，采用控制度较大节点、随机节点和“熟人免疫”节点三种不同方式进行比较分析，得出流行病的预防与控制的最佳策略。
最后对与在复杂网络上流行病的研究理论作了较细致的总结，对传播数据做了系统合理化的分析。
2 预备知识
2.1 复杂网络图的概念及表示
复杂网络研究的兴起使得人们开始广泛关注网络结构复杂性及其与网络行为之间的相互关系。要研究各种不同的复杂网络在结构上的共性，首先需要有一种描述网络的统一的工具，这种工具在数学上称为图(Graph)[7]。
图论是一门应用数学，它的概念和结果来源非常广泛，既有来自生产实践的问题，也有来自理论研究的问题，就拿著名的Konigsberg 七桥问题为例：在贯穿古普鲁士Konigsberg 城(第二次世界大战时划归原苏联，改名Kalin-ingrad ，今属白俄罗斯) 的 Pregel 河上有七座连接两岸及河中的两个小岛(如图2-1所示，第二次世界大战时已几乎夷为平地) 。当时困扰当地居民的一个问题是：是否存在一种走法，走过每座桥恰好一次。虽然当时多数人相信不存在这种走法，但没有人能解释其原因。问题被提到当时在St.Peitersburg 的数学教授Euler (1707~1782)面前，他把每块地用一个顶点代替，把每座桥用连接对应顶点的一条边代替，把问题抽象为图2-2中的图。为解决这个问题，他提出了判定一般图存在这种走法的充要条件，并给出了必要性的证明。
图 2-1 图2-2
网络最初属于图论的研究范畴，从数学意义上来说一个具体网路是由节点集V 和边集E 组成的图，且此图可以用G = (V , E) 来表示。其中网络中的节点总数用N = 表示，网络中的边数用M =E 表示，且边集E 中中每条边都有一个节点与之对应。我们把节点对(i , j )与(j , i )对应同一条边的网络成为无向网络(undirected network)，否则称为有向网络(directed network)。如果网络中每条边都赋予了与之相应的权值，则该网络称为加权网络(weighted network)，否则该网络成为无权网络(unweighted network)，基于这一定义那么无权网络可以看作是每条
边的权值都为1的等权网络。此外一个网络中节点可能是不同类型的，例如在科
学家合作网络中，节点代表不同的科学家，而权代表科学家之间的合作次数。图
2-3给出了几个不同类型的网络的例子。在图论中，称不包含环和重边的图为简
单图(simple graph)。
图2-3 a)单一类型节点和边的无向网络 b) 不同类型节点和边的无向网络
c) 节点和边权重变化的无向网络 d) 有向网络
2.2 复杂网络上网络系统的复杂性
一切系统都具有网络结构，复杂系统具有复杂的网络结构。复杂网络也是研
究复杂系统的一种技术和方法，它关注系统中个体相互作用的拓扑结构，是理解
复杂系统性质和功能的基本方法。网络系统的复杂性主要体现在以下四个方面：
(1) 结构复杂性
网络连接结构错综复杂、极其混乱，同时又蕴含着丰富的结构：社区、基序、
聚集性、生成规律等等，而且网络连接结构可能是随时间变化的，例如：WWW
上每天都不停地有页面和链接的产生和删除。
静态结构的复杂性和结构动态演化的复杂性。例如：神经系统有神经元互联
形成，连接以“突触连接结构”实现，突触有强弱、兴奋与抑制、不同的神经递
质；连接不断改变，形成连接结构变化。(重边，加权等)
(2) 节点复杂性
网络中的节点可能是具有分岔和混沌等复杂非线性行为的动力系统。如基因
网络中每个节点都具有复杂的时间演化行为，而且，一个网络中可能存在多种不
同类型的节点。例如：控制哺乳动物中细胞分裂的生化网络就包含各种各样的基
质和酶。
当关联失去时，这类特性会在节点处消失或改变。例如，
耦合神经元重复地
被同时激活，那么它们之间的连接就会加强，这被认为是记忆和学习的基础。
(3) 复杂网络之间相互影响的复杂性
实际的复杂网络会受到各种各样因素的影响和作用。如电力网络故障会导致
Internet 网速变慢，运输系统失控等一系列不同网络间的连锁反应。
(4) 网络分层结构的复杂性
行政管理网络是具有层结构的，多数网络都有节点的分层结构，只是在许多
网络中没有意识到时一种造成复杂性的重要结构。
2.3 复杂网络的常用统计量
2.3.1 度与度分布 (Degree and degree distribution)
度(degree)是单个节点的属性中最基本的概念，图论中节点i 的度k i 定义为与
该节点连接的其他节点的数目，从直观上，一个节点的度越大就意味着这个节点
在某种意义上越重要。一般来说，并不是所有的节点都具有相同的度，通常用分
布函数P(k)来描述网络中节点的度分布情况，P(k)表示一个随机选定节点的度
恰好为k 的概率。节点度的分布特征是网络的重要几何性质，规则网络中各节点
的度值相同，符合Delta 分布，随机网络的度分布可近似为Poisson 分布，大量
的实际网络存在幂律形式的度分布，称为无标度网络，同时在现实中还有很多网
络的度分布服从指数分布。
2.3.2 平均路径长度（Characteristic path length）
网络中两个节点i 和j 之间的距离d ij 定义为连接这两个节点的最短路径上
的边数。网络中任意两个节点之间的距离的最大值称为网路的直径(diameter)，
记为D ，即：
D =max d ij i , j
网络的平均路径长度定义为任意两个节点之间的距离的平均值，即：
L =1d ij ∑N (N +1) /2i ≥j
式中:N为网络节点数。网络的平均路径长度也称为网络的特征路径长度，
用来衡量网络节点间的离散程度。研究表明，尽管许多实际网络的节点数巨大，
但网络的平均路径长度L 相对于N 来说却很小，这种现象称之为“小世界效应” 。
2.3.3 聚类系数（Clustering coefficient）
在很多真实网络中，常常有这样的情况：如果顶点A 与顶点B 相连，并且顶
点B 与顶点C 相连，那么顶点A 也极有可能与顶点C 相连。把此类情况引申到社
会网络中，即你的朋友的朋友也有可能是你的朋友，这种属性是很容易理解的，
在复杂网络中我们通常把这种属性称为网络的聚类性。
一般地，假设网络G 中一个节点i 有e i 条边和其他k i 个节点相连，这k i 个节
点就称为节点i 的邻居。显然，这k i 个节点间最多可能有k i (k i -1) /2条边，k i 个
节点之间实际存在的边数E i 与总的可能边数的比值定义为节点i 的聚类系数C i ，
网络中所有节点i 的聚类系数的平均值就是网络的聚类系数，用C 表示，即：
C i =2E i ， k i (k i -1)
1
N C =∑G
i ∈G i 。
显然从上面式子可知，整个网络的聚类系数C 满足0≤C ≤1。当C =0时对
应网络中所有的节点都是孤立节点的情况，即任何节点对之间都没有边连接；而
C =1对应的网络是全局耦合网络。
此外节点i 的聚类系数也可定义为:
与点i 相连的三角形的数量 C i =与点i 相连的三角组的数量
式中：与点i 相连的三角组的数量是指包括节点i 的3个节点，并且至少存
在从节点i 到其他2个节点的2条边，如图2-4所示。
图2-4(a)中节点i 的聚类系数C i =1；图2-4(b)中节点i 的聚类系数C i =0。
图2-4 以节点i 为中心的三点组的可能形式
2.3.4 介数（Betweenness ）
介数(Betweenness Centrality) 通常分为边介数和节点介数两种。节点介数定义为网络中所有最短路径中经过该节点的路径的数目占最短路径总数的比例。边介数定义为网络中所有最短路径中经过该边的路径的数目占最短路径总数的比例。介数反映了相应的节点或者边在整个网络中的作用和影响力，是一个重要的全局几何量，具有很强的现实意义。例如，在社会关系网或技术网络中，介数的分布特征反映了不同人员、资源和技术在相应生产关系中的地位，这对于发现和保护关键资源、技术和人才具有重要意义。
2.4 复杂网络模型
复杂网络中最重要的几个模型，其中包括规则网络(regular network) 、随机网络(random network ) 、WS 小世界网络(WS network ) 以及BA 无标度网络(BA network ) 。
2.4.1 规则网络(regular network)
在一个全局耦合网络（globally coupled network ）中，任意两个点之间都有边直接相连。因此，在具有相同节点数的所有的网络中，全局耦合网络均有最小路径长度L gc =1和最大聚类系数C gc =1。
在一个网路规模为N 的全局耦合网络中，其对应的边数有N (N -1)/2条，然而大多数大型的实际网络都是很稀疏的，它门的数目一般至多是O (N )而不是O N 2，这就表明全局耦合网络作为实际网络是有局限性的。 ()
在最近耦合网络(nearest-neighbor coupled network) 中每个节点和它周围的邻居点相连。具有周期边界条件的最近邻耦合网络包含N
个围成一个环的点，其
中每个节点都于它左右各K /2个邻居点相连，这里K 是一个偶数。对较大的K 值，最近邻耦合网络的聚类系数为：
C nc =3(K -2)3≈ 4K -14
由此最近邻耦合网络是高度聚类的网络。然而，最近耦合网络不是一个小世界网络。相反，对固定的K 值，该网络的平均路径长度为：
L nc ≈N →∞(N →∞) 2N
另外，规则网络中还有一类比较特殊的为星形耦合网络(star coupled network) 。它有一个中心点，其余的N -1个点都只是与这个中心点连接，而N -1个点之间彼此不连接，其中星形网络的平均路径长度为：
L star =2-2(N -1)→2(N →∞) N N -1常见的几个规则网络如下图：
a) b)
c) 图2-5 (a)全局耦合网络；(b)最近邻耦合网络；(c)星形网络
2.4.2 随机网络(random network)
20世纪60年代，由两位匈牙利数学家Erd ǒs 和R ényi 建立的随机图理论（random graph theory）被公认为是在数学上开创了复杂网络理论的系统性研究。与完全规则网络相反的是完全随机网络，随机网络的描述方式如下：给定网络节点总数N ，网络中任意两个节点以概率p 连接，生成的网络全体记为G (N , p )，构成一个概率空间。
由N 个节点构成的图中，可以存在N (N -1)/2条边，从中随机连接M 条边所构成的网络就叫随机网络。其中一个典型的模型是Erdos 和Renyi 于40
多年
前开始研究的ER 随机网络图模型，简称ER 模型。它的模型构造算法是对于N 个网络节点，以概率p 对每一个节点对进行连边，得到一个有N 个节点，约pN (N -1)/2条边的随机网络。
假设有大量的节点(N >1)落在纸上，并以相同的概率p 给每对节点连上一根线，这样就得到一个有N 个节点，约pN (N -1)/2条边的ER 随机图的实例，如下图2-6:
图2-6 a) 概率p =0，给定的10个孤立点生成的随机图
b) 概率p =0. 1，给定的10个孤立点生成的随机图
c) 概率p =0. 15给定的10个孤立点生成的随机图
2.4.3 WS 小世界网络(WS network)
我们或许有过这样的经历：偶尔碰到一个陌生人，同他聊了一会儿后发现你认识的某个人居然他也认识，然后发出“这个世界真小”的感慨。那么对于世界上任意两个人来说，借助第三者、第四者这样的间接关系来建立起他们两人的联系，平均需要通过多少人呢？20世纪60年代美国哈佛大学的心理学家Stanley Milgram 通过一些实验后得出结论：中间的联系人平均只需要5个。他把这个结论称为“六度分离(six degrees separation)”。也就是平均只要通过5个人，你就能与世界任何一个角落的任何一个人发生联系。这个结论定量地说明了我们世界的
“大小”，或者说人与人关系的紧密程度。
30多年来，六度分离理论一直被作为社会心理学的经典范例之一。尽管如此，实际上这个理论并没有得到严格的证实。美国心理学教授朱迪斯•克兰菲尔德(Judith Kleinfeld) 对米尔格伦最初的实验提出不同意见，因为她发现实验的完成率极低。
作为完全规则网络像完全随机网络的过渡，1998年，Watts 和Strongtz 提出了一种小世界网络模型，称为WS 小世界网络模型。WS 网络是一种不同于规则网络和随机网络的网络，它的构造算法如下：
(1)从规则网络开始：考虑一个含有N 个节点的最近邻耦合网络，它们围成一个环，每个节点都与它左右相邻的各K /2节点相连接结，其中K 是偶数。
(2)随机化重连：以概率p 随机地重新连接网络中每个边，即将边的一个端点保持不变，而另一个端点取为网络中随机选择的一个节点。假设任意两个不同的节点之间至多只能有一条边，并且每一个节点都不能有边与自身相连。 当p 取不同的值时对应不同的网络，当p =0对应于完全规则网络，p =1则对应于完全随机网络，当p 满足条件0
由上述算法得到的网络模型的平均路径长度L (p )和聚类系数C (p )特性都可以看作重连概率p 的函数，图2-7显示了网络的平均最短路径L 和平均聚类系数C 重连概率p 的变化关系(图中对两个值作了归一化处理) 。当p =0时是规则网络，当p =1时则为随机网络；对于0
图2-7 WS小世界模型的聚类系数和平均路径长度随重连概率p 的变化关系
2.4.4 BA 无标度网络(BA network)
无标度网络经过长时间演化后将导致绝大多数点只有少数连接边，而存在极少数点具有大量连接边，由大量边连接的节点成为该网络的中枢点。因此，无标度网络针对随机失效具有很强的鲁棒性(Robustness)，对于选择性攻击，无标度网络具有脆弱性(Fragility)性。近年来，学者们通过实证研究发现得到了大量的实际网络都是无标度网络，其中包括我们熟知的Internet 、WWW 、各种社会网络等等。由此无标度网络也是近年来一个重要的研究课题。
为了解释幂律分布的产生机理，Barabasi 和Albert 提出了一个无标度网络模型，现被称为BA 模型，其对应的演化算法如下：
(l)增长(Growth)性：开始有少量(m 0个)点，每新添加一个节点，新的节点与
已存在于系统中的m ≤m 0个点相连接，产生m 条新边。例如www 上每天会有
大量的新的网页产生，每个月会有许多新的科研文章发表。
(2)择优连接 (Preferential attachment)性：即新的节点更倾向于与那些具有较高的连接度的“大”的节点相连接。这种现象也称为“富者愈富(rich get richer)”或“马太效应 (Matthew effect)”。例如，一些新发表的文献倾向于引用那些被广泛引用的重要文献，新的个人主页上的超文本链接更有可能指向百度、新浪等著名网点。一个新的节点与一个已经存在的节点i 相连的概率∏i 与节点i 的度k i 、节点j 的度k j 之间满足如下关系： ()
∏i =k i k j
j
在t 时刻，BA 模型演化成一个有N =t +m 0个节点、mt 条边和总度数为∑k j j =2mt 的随机网络。图2-8显示了当m =m 0=2时的BA 网络的演化过程。初始网络有两个节点，每次新增加的一个节点按优先机制与网络中已存在的两个节点相连。
图2-8 BA 无标度网络的演化(m =m 0=2)
2.5 本章小结
本章主要介绍了有关复杂网络的一些基本知识，比如：度、度分布，最短路径，聚类系数。这些概念和性质是刻画复杂网络特征的基本手段和重要工具。其次，介绍了复杂网络发展过程中几个重要的网络模型，比如：规则网络模型、随机网络模型、小世界网络模型、无标度网络模型。接下来的章节会用到度的概念以及已经介绍了的两个网络模型：WS 小世界网络和QQ 网络。通过研究两种模型下节点的控制情况来分析流行病的蔓延，做到更好的预防与控制。
3 模型建立
3.1 随机网络
通过matlab 工具建立一个随机网络(random network) 模型，具体设定参数如下：
网络图中节点的总数目N =20；网络图中边的平均连接度alph =0. 25；表征边的平均长度的参数beta =0. 3。选取的是概率排序法，即总共生成的边数为
并以一定的较小的概率对边随机化重连；重新连接的概率p N *(N -1)/2*alph ，
分别选取0,0.1,1。
1）重新连接的概率为0时，计算所得该随机图的边数为：48，随机图的平均路径长度为：2.6632，随机图的聚类系数为：0.75155，随机图的平均度为：4.8，其中节点4只有一个邻居节点，其聚类系数赋值为0；节点17只有一个邻居节点，其聚类系数赋值为0
生成的随机网络图如下：
网络图中各节点的度的大小分布图
网络图中节点度的概率分布图
各节点的度数K 节点度为K 的概率 P (K ) 节点编号n 节点的度 K
图3-1 生成的节点为20，p =0的随机网络、
度的大小以及度的概率分布图
2）重新连接的概率为0. 1时，计算所得该随机图的边数为：48，随机图的平均路径长度为：Inf ，随机图的聚类系数为：0.46873，随机图的平均度为：4.8，其中节点4为孤立节点，其聚类系数赋值为0；节点12为孤立节点，其聚类系数赋值为0，由此可得该网络图不是连通图 生成的随机网络图如下：
节点度为K 的概率 P (K )
网络图中各节点的度的大小分布图
各节点的度数K
节点编号n
网络图中节点度的概率分布图
节点的度 K
图3-2 生成的节点为20，p =0. 1的随机网络、 度的大小以及度的概率分布图
3）重新连接的概率为1时，计算所得该随机图的边数为：48，随机图的平均路径长度为：Inf ，随机图的聚类系数为：0.23405，随机图的平均度为：4.8，其中节点3为孤立节点，其聚类系数赋值为0，由此可得该网络图不是连通图
生成的随机网络图如下：
节点度为K 的概率 P (K )
网络图中各节点的度的大小分布图
各节点的度数K
节点编号n
网络图中节点度的概率分布图
节点的度 K
图3-3 生成的节点为20，p =1的随机网络、
度的大小以及度的概率分布图
根据上图显示的网络图形可看出，随机网络有着很小的平均路径长度，但同时集聚系数也很小，每条边的出现与否都是独立的，因此随机网络不能反应真实网络的性质。
3.2 WS小世界网络
通过matlab 工具建立一个WS 小世界网络(WS network)模型，具体设定参数如下：
网络图中最近邻耦合网络中节点的总数N =20；最近邻耦合网络中每个节点的邻居节点的个数的一半k =2。随机化重连的概率p 分别选取0,0.3,1。
1）重新连接的概率为0时，得出该随即图的平均路径长度为2.8947，该随机图的聚类系数为0.5，该随即图的平均度为4。
生成的WS 小世界网络图如下：
网络图中各节点的度的大小分布图
各节点的度数K
节点度为K 的概率 P (K )
节点编号n
网络图中节点度的概率分布图
节点的度 K
图3-4 生成的节点为20，p 0的WS 小世界网络、
度的大小以及度的概率分布图
2）重新连接的概率为0. 3时，得出该随即图的平均路径长度为2.2158，该随机图的聚类系数为0.30381，该随即图的平均度为4。
生成的WS 小世界网络图如下：
网络图中各节点的度的大小分布图
各节点的度数K
节点编号n
网络图中节点度的概率分布图
节点度为K 的概率 P (K )
节点的度 K
图3-5 生成的节点为20，p 0. 3的WS 小世界网络、 度的大小以及度的概率分布图
3）重新连接的概率为1时，得出该随即图的平均路径长度为2.1211，该随机图的聚类系数为0.073095，该随即图的平均度为4。
生成的WS 小世界网络图如下：
各节点的度数K
网络图中各节点的度的大小分布图
节点编号n
网络图中节点度的概率分布图
节点度为K 的概率 P (K )
节点的度 K
图3-6 生成的节点为20，p 1的WS 小世界网络、
度的大小以及度的概率分布图
根据上图显示的网络图形可看出，大部分节点彼此并不相连，但绝大部分节点之间经过少数几步后就可到达。各节点之间的连接也很均匀，因此小世界网络的度也分布十分均匀，对应的节点度的概率分布也十分均匀。
3.3 QQ网络
根据Excel 数据表格，所描出QQ 网络模型图如下：
图3-7 生成的节点为113的QQ 网络
由图3-7可得，班级社会网络的聚类系数为0.6147，非常高，说明有明显的聚类性质（抱团现象）。根据Excel 表格数据分析，可得出节点的度呈现较大趋势变化，这也正与图3-7显示一致，这一点在班级紧密结构上表现得很明显。
3.4 本章小结
本章主要建立三个网络模型，分别是规模为20的随机网络(random network)和规模为20的WS 小世界网络(WS network) 以及规模为113的QQ 网络。其中随机网络(random network)的节点的平均度为4.8，总度数为96，而WS 小世界网络(WS network)的节点的平均度为4，总度数为80。两个网络规模到总的度数都是相近的，在数据分析上具有一定的可比性。虽然两者的规模相近，但从网络的结构特性上有着很大的差异，一个度分布十分均匀，另一个还存在孤立点。
下一章将基于两种网络：WS 小世界网络与QQ 网络模型，分析不同的节点控制情况，从而更好的做到流行病的控制。
4 针对网络模型节点感染分析
本章选用三种控制节点方式进行研究：选取度较大节点、选取随机节点、
选取“熟人免疫”节点。选取度较大的节点就是指将200个节点中的度最大的节点按顺序依次选取控制；随机选取节点就是指在200个节点中不考察节点度数任意选取若干个控制；“熟人免疫”就是先在随机选取了若干个节点的情况下，再把随机选取的节点的任意一个有关系的节点控制起来。
将选取的节点控制起来，那些和已经控制的节点有联系的也看做被控制了，但是重复被控制的只记一次。在200个节点中按选取情况选取10个节点，按照控制2个、4个、6个等的顺序将这些节点控制起来，再统计一共控制的节点，求出相应的控制率，用matlab 作出控制率的曲线，以便更直观的观察控制情况。主要是分别将两种网络模型放在一起进行比较，然后再单个去分析三种选取节点的方式对这个两个网络模型的优势和劣势。
4.1 选取较大节点进行控制
第一种选取节点的方式为选取度较大的节点，将其控制起来。所谓度较大的节点，指的是图中与其它节点连线最多的节点。将200个节点中的度最大的前十个排序列举出来，分别控制2、4、6、8、10个，计算控制率。
可以得出以下数据：
表4.1
通过matlab 描点得出控制节点图如下：
2
345678910
图4-1 “—”WS 小世界网络 “---”QQ 网络
由图4-1可知，WS 小世界网络和QQ 网络的控制率与控制节点的个数成正相关增长。但是度较大的节点对QQ 网络而言更具有控制力度，更重要。
4.2 选取随机节点进行控制
第二种选取节点的方式为随机选取。随机在200个节点中选取10个，分别2、4、6、8、10个，计算控制率
表4.2
通过matlab 描点得出控制节点图如下：
2
345678910
图4-2 “—”WS 小世界网络 “---”QQ 网络
由图4-2可知，QQ 网络的控制率还是明显高于WS 小世界网络。但QQ 网络的节点度分布差异很大，所以在控制曲线斜率的问题上，每一次的随机选取作出的曲线斜率差距会出现很大的波动。相对而言，WS 小世界网络在随机选取节点做控制时，会稳定很多，会随着节点控制数量的增加而网络控制率平稳的上升。
4.3 选取“熟人免疫”节点进行控制分析
所谓“熟人免疫”就是指对随机选出节点再随机选一个邻近节点进行免疫。在本篇中就是指在4.2中的随机选取节点后再做一步选取，控制随机选取的节点的一个与其有联系的随机的邻近节点。控制率的算法和以上两种情况也一样。
表4.3
通过matlab 描点得出控制节点图如下：
2
345678910
图4-3 “—”WS 小世界网络 “---”QQ 网络
由图4-3可知，QQ 网络控制效果好。当随机选一点再选择其邻居节点时，QQ 网络中度大节点比度小节点被选中的概率大得多。那么控制度较大的节点的概率也就大大提高，相应的对整个网络的控制率就大大提高。
4.4 本章小结
4.1-4.3分别将三种选取节点的方法对于两种网络的控制率曲线进行对比。
显然，QQ 网络的控制率远高于WS 小世界网络，且选取度较大的节点控制后，对整个网络的控制率影响很明显。由于QQ 网络节点度上升很快，控制率上升很快，而WS 小世界网络这一变化就不是很明显，即在图上表现为曲线斜率很小。QQ 网络的节点度分布很不均匀，部分节点度很大，部分可能为孤立点，所以当随机选取QQ 网络节点时，得到的控制率曲线可能变化不均匀，即在图上显示曲线的斜率变化波动较明显。而对于WS 小世界网络而言，因为其度分布较均匀，所以三种选取方式对WS 小世界网络差别不大。
2
345678910
图4-4 WS小世界网络 “—”选取度较大节点的控制曲线
“---”选取随机节点的控制曲线 “o —”选取“熟人免疫”节点的控制曲线
由图4-4可得，对于一个WS 小世界网络，在三种节点选取后，还是度较大的节点对整个网络的影响更大。但是由于WS 小世界网络的度分布比较均匀，所以控制曲线的斜率差距并不是很大。
对于复杂网络上流行病的研究，如果采取的是WS 小世界网络建模分析，很
明显采取较大节点对于节点控制率有着更好的效果，即控制较大节点后对于流行病的传播有着更好的措施，从而控制传染病的蔓延。
2345678910
图4-5 QQ 网络
“—”选取度较大节点的控制曲线
“---”选取随机节点的控制曲线 “o —”选取“熟人免疫”节点的控制曲线
由图4-5可得，对于QQ 网络选取较大节点对整个网络具有更好的控制效果。由于QQ 网络本身节点的度分布就不均匀，存在很多度较大的节点以及一些孤立点，所以选取度较大的节点控制起来对于整个网络的节点控制效果还是很理想的。但随机选取或是选取“熟人免疫”节点，那么对网络控制的情况会存在很大的不确定性。
所以对于一个QQ 网络，节点的度是考察节点重要性一个重要依据。在选取控制节点时，选取度较大的节点往往可以得到很好的效果。
对于QQ 网络而言，针对复杂网络上流行病的蔓延与阻止，选取较大节点对于传染病的控制更具有显著的效果，能更好的抑制传染病的传播，做到更好的相对控制。
5 总结
本文首先给出了复杂网络的基本概念，复杂网络中几个重要的网络模型，并用MATLAB 仿真生成了相对应的随机网络(random network) 和WS 小世界网络(WS network) 。其次针对不同的网络模型分析了节点控制问题，并分别选取度较大节点、随机节点以及“熟人免疫”节点进行相关分析，求出各自的控制率。最后通过matlab 描出相应的曲线图，通过比较得出QQ 网络对于节点的控制具有更好的效果，选取度较大进行控制相比其他控制效果好。仿真到复杂网络上流行病的研究问题，QQ 网络对于传染病具有更好的控制作用，选取度较大的节点具有最优性，能更好的控制传染病的蔓延。
目前为止，大多数复杂网络的研究都是关于无权网络的，事实上很多实际网络都表现出加权网络的特征，比如社会关系网，相互作用强度对网络上的疾病传播等过程会产生重要影响、科学家合作网，科学家合作次数、Internet ，Internet 上的宽带等等。此时无权网络的描述就有局限性了，因此研发人员下一步将尝试模型应用到加权网络中，进一步考察其在加权网络上的传播特性[15]。
参考文献：
[1] Watts D J,Strogatz SH.Collective dynamics of mall-word networks[J].Nature,1998.
[2] Barabasi A L.Linked: The New Science of Networks [D]. Massachusetts: Persusu Publ ishing,2002.
[3] Watts D j.The ‘new’ science of networks [J]. Annual Review of Sociology, 2004, 30: 243-270.
[4] Barabasi A L, Albert R. Emergence of scaling of ‘small-world’ networks [J]. Science, 1999, 286 (5439):509-512.
[5] Erdos P, Renyi A.On the evolution of random graghs [J]. Publ Math Inst Hung. Acad. Sci,1960, 5: 17-60.
[6] 汪小帆, 李翔, 陈关荣, 复杂网络理论及其应用清华大学出版社[M].北京,2006.
[7] 孙惠泉, 图论及其应用科学出版社. 北京,2004,30:1-5.
[8] 范彦静, 王化雨. 基于复杂网络的知识网建模研究[J].心智与计算,2008,(01):28-34.
[9] 苟清明, 一个具有阶段结构SIS 流行病模型[J].四川师范大学学报,2007,30(9):590-59 3.
[10] 李光正, 史定华, 复杂网络上疾病传播行为分析[J].自然科学进展,2006.16(4):508-51 2.
[11] 刘浩广, 蔡绍洪, 张玉强等, 复杂网络中几种经典的传播模型的比较[J].贵州大学学报 (自然科学版),2007,24(5):473-478.
[12] 褚建勋. 基于复杂网络的知识传播动力学研究[D].中国科学技术大学,2006.
[13] 高崇阳, 浮燕, 贾丽. 浅谈复杂网络研究及意义[J].中国科技信息,2009,(14):3-5.
[14] 张大陆, 王志晓, 刘雯, 杨哲. 基于复杂网络的本体结构分析[J].同济大学学报(自然科 学版),2009,(02):33-54.
[15] 刘建香. 复杂网络及其在国内研究进展的综述[J].系统科学学报,2009,(04):7-8.
致 谢
本研究及学位论文是在导师赵军产副教授的精心指导下完成的。赵教授严谨的治学态度、敏锐的洞察力、开阔的思维方式深深的影响着我，使我学会了解决问题和处理问题的方法。从课题的选择到项目的最终完成，赵军产老师都始终给予我细心的指导和不懈的支持。感谢导师在百忙之中花大量时间来修改我的论文，使我的工作能顺利进行。借此论文完成之际，谨向敬爱的恩师致以衷心的感谢！
感谢在一起愉快的度过大学生活的信科091班各位同学，是你们让我的大学生活充满了欢笑、快乐，也让我成长，祝愿我们都有美好的未来！特别感谢我的室友，他们在学习上给了我很大的鼓励和帮助，他们的陪伴让我度过了短暂而快乐的大学生活。
毕业论文是再一次系统学习的过程，毕业论文的完成，同样也意味着新的社会生活的开始。我将铭记我曾是一名武汉纺织大学的学子，在今后的工作中把武汉纺织大学的优良传统美德发扬光大。
最后，向所有关心和帮助过我的人致以衷心的感谢！
陆乔时