传播动力学本科生毕业论文(设计)报告-复杂网络上的传播动力学研究.doc

中国科学技术大学本科毕业论文 中国科学技术大学本科毕业论文（设计）报告题目： 复杂网络上的传播动力学研究 系别： 少年班系 专业： 理论物理 学制： 四 年 制 姓名： 周 涛 学号： PB00011127 导师： 汪秉宏教授 周佩玲教授 2004 年 6 月 11 日摘 要近几年来，大量关于复杂网络的文章发表在Science，Nature，PRL，PNAS等国际一流的刊物上，从一个侧面反映了复杂网络已经成为物理界的一个新兴的研究热点。研究复杂网络的终极目的，是去理解和解释网络拓扑结构对于在网络上发生的各种物理过程的影响，本文主要讨论复杂网络上的传播动力学行为。文章首先介绍了复杂网络的基本概念与研究背景，以及相关的图论基础知识。在第二章，作者给出了Ore定理的简单证明，此方法可以无困难地将Ore定理推广到有向图形式。利用类似的分析方法，可以得到直径图平均距离的下界定理，Entringer，Ng等人的结果可以作为该定理的一个自然的推论给出。结合此定理与Ore定理，可以得到只依赖于阶数和直径的平均距离下界，该下界是目前已知的最好的下界。在第三章，作者给出了复杂网络上传播动力学研究的一个综述，包括简单介绍了经典传播模型，较为详细地讨论了小世界网络和无标度网络的传播特性以及网络免疫技术，简要总结了物理学家进入网络研究领域的意义，并提出了目前尚无答案且笔者认为值得进一步研究的四个问题。然后，作者在此基础上建立了SARS传播的随机演化模型，讨论了SARS传播的动力学性质，发现在自由传播的情况下SARS感染人数有一个上界。通过对基本模型的外推，建立了仿真模型，该模型能够较好地解释北京市的实际数据。实验表明，政府采取严格的控制政策的时间对于SARS传播行为有决定性的影响，在自由传播时期，民间适度的恐慌心理有利于对SARS传播的抑制。最后，作者开创性地研究了复杂网络上微扰地传播动力学行为，着重讨论了网络拓扑结构如何影响归因于微扰的网络灾变行为，实验表明灾变在复杂网络中发生的频度远远大于欧几里德格子，而且复杂网络中最严重的灾变的严重程度也远远大于欧几里德格子。本文的工作有助于更深刻地理解发生在真实网络中的传播行为。AbstractIn the recent years, the discovery of small-world and scale-free properties of many real-life networks was stimulated a great deal of interest in studying how the topological structures affect the processes taking place on networks. One of the original, and still primary, reasons for studying networks is to understand the mechanisms by which diseases and other things spread over them. In this article, we provide a review of the main results obtained in the modeling of epidemic spreading in complex networks, including the classical epidemic models, epidemic spreading in small-world networks, epidemic spreading in scale-free networks and the technique of immunization.Where after, we established a stochastic evolvement model of SARS spreading based on complex network, and studied the dynamic character of SARS spreading. We found that the total number of infected individuals has an upper bound in free-sqreading period. By extending the basic model, we established a simulant model, which can explain the real data. The experiments show that the time when the government starts to take strict control policy has the crucial influence on SARS spresding, and in free-spreading period, the panic within measure will suppress the epidemical spreading.And then, a model similar to OFCs is established to mimic the catastrophes occurring in networks. We have found that the catastrophes occur much more frequently in scale-free networks than in Euclidean lattices and the greatest catastrophe in scale-free networks in much more serious than that in Euclidean lattices.目 录摘要2Abstract3第一章 引言 5第二章 图论基本知识简介 1021 复杂性科学的起源1022直径、平均距离、簇系数与度分布 1323随机图的基本模型与主要结论 15第三章 复杂网络上的传播动力学1631经典传播模型简介 2132小世界网络的传播特性 2133无标度网络的传播特性 2234网络免疫技术 2335基于复杂网络的SARS传播模型研究 2436结束语 33第四章 基于复杂网络的SARS传播模型研究3541微扰与网络灾变 3542模型简介 3643数值模拟结果 3644结语与展望 38第五章 结束语40附录1致谢 41附录2攻读学位期间参加各种竞赛获奖情况 42附录3攻读学位期间完成学术论文汇总 43 第一章： 引 言自然界中存在的大量复杂系统都可以通过形形色色的网络加以描述。一个典型的网络是由许多节点与连接两个节点之间的一些边组成的，其中节点用来代表真实系统中不同的个体，而边则用来表示个体间的关系，往往是两个节点之间具有某种特定的关系则连一条边，反之则不连边，有边相连的两个节点被看作是相邻的。例如，神经系统可以看作大量神经细胞通过神经纤维相互连接形成的网络；计算机网络可以看作是自主工作的计算机通过通信介质如光缆、双绞线、同轴电缆等相互连接形成的网络。类似的还有电力网络、社会关系网络、食物链网络等等。数学家和物理学家在考虑网络的时候，往往只关心节点之间有没有边相连，至于节点到底在什么位置，边是长还是短，是弯曲还是平直，有没有相交等等都是他们不在意的。在这里，我们把网络不依赖于节点的具体位置和边的具体形态就能表现出来的性质叫做网络的拓扑性质，相应的结构叫做网络的拓扑结构。那么，什么样的拓扑结构比较适合用来描述真实的系统呢？两百多年来，对这个问题的研究经历了三个阶段。在最初的一百多年里，科学家们认为真实系统各因素之间的关系可以用一些规则的结构表示，例如二维平面上的欧几里得格子，它看起来像是格子体恤衫上的花纹；又或者最近邻环网，它总是会让你想到一群手牵着手围着篝火跳圆圈舞的姑娘。到了十九世纪五十年代末，数学家们想出了一种新的构造网络的方法，在这种方法下，两个节点之间连边与否不再是确定的事情，而是根据一个概率决定。数学家把这样生成的网络叫做随机网络，它在接下来的四十年里一直被认为是描述真实系统最好的网络。直到最近几年，由于计算机数据处理和计算能力的飞速发展，科学家们发现大量的真实网络既不是规则网络，也不是随机网络，而是具有与前两者皆不同的统计特征的网络。这样的一些网络被科学家们叫做复杂网络，对于他们的研究标志着第三阶段的到来。复杂网络不同于规则网络和随机网络的统计特性到底有哪些呢？下面我们将使用一种直观但不严格的语言描述它，读者可以在阅读完第二章后自行给出严格的定义。在复杂网络的诸多统计特征中最重要的是小世界效应和无标度特性。如果网络中的两个节点可以通过一些首尾相连的边连接起来，我们就说这两个点是可达的，并把连接他们所需要的最少的边的数目叫做他们之间的距离，显然，这两个点之间的距离总是比网络拥有的节点总数要小。如果两个节点是不可达的，我们就令它们之间的距离等于网络的节点总数。把所有节点对的距离求平均，就得到了网络的平均距离。另外一个叫做簇系数的参数，专门用来衡量节点集聚成团的情况。对于某个节点，它的簇系数被定义为它所有相邻节点之间连边的数目占可能的最大连边数目的比例。类似的，网络的簇系数则是所有节点簇系数的平均值。研究表明，规则网络具有大的簇系数和大的平均距离，随机网络则具有小的簇系数和小的平均距离。1998年，物理学家通过以某个很小的概率改变规则网络中边的连接方式构造出了一种介于规则网络和随机网络之间的网络，它同时具有大的簇系数和小的平均距离，因此既不能当作规则网络处理，也不能被看作是随机网络。后来物理学家把大的簇系数和小的平均距离两个统计特征合在一起称为小世界效应，具有这种效应的网络就是小世界网络。 图1.1：小世界网络拓扑结构示意图 左边的网络是规则的，右边的网络是随机的，中间的网络是在规则网络上加上一点随机的因素而形成的小世界网络，它同时具有大的簇系数和小的平均距离。科学家们对大量的真实网络，比如电力网络、计算机互联网、食物链网络、演员关系网、科学家合作网络等等做了大量实证性的研究，发现它们几乎都是小世界网络，同时，他们还发现了真实网络的另一重要统计特征，即节点度服从幂律分布。节点度是指一个节点拥有相邻节点的数目，节点度服从幂律分布就是说具有某个特定度的节点数目与这个特定的度之间的关系可以用一个幂函数近似地表示。幂函数曲线是一条下降相对缓慢的曲线，这使得我们不仅能在网络中发现大量度很小的节点，还能找到一些度很大的节点。上面那幅图中的规则网络，随机网络和小世界网络的节点度分布都不是幂律的，它们的分布区间非常狭窄，几乎找不到偏离节点度均值较大的点。对于这样的网络，上述均值就可以被看作衡量其节点度的一个特征标度，在这个意义上，我们把节点度服从幂律分布的网络叫做无标度网络，并称这种节点度的幂律分布为无标度特性。图1.2：无标度网络的拓扑结构 1999年，物理学家给出了生成无标度网络的一种简单方法，本图例有130个节点，节点度服从幂指数为-3的幂律分布。遗憾的是，就目前而言，科学家们还没有给出复杂网络精确严格的定义，从这几年的研究来看，之所以称其为复杂网络，大致上包含以下几层意思：首先，它是大量真实复杂系统的抽象；其次，它至少在感觉上比规则网络和随机网络复杂，因为我们可以很容易地生成规则和随机网络，但就目前而言，还没有一种能够生成完全符合真实网络统计特征的简单方法；最后，它还被认为是有希望解决“复杂系统之所以复杂”这一至关重要问题的有力武器。如前所述，关于网络的研究，数学家早在两百多年前就开始了，他们已经发展出了成体系的理论与技术，而物理学家的进入只有不到五年的历史！到底是什么鼓动物理学家来趟这塘浑水，他们的到来有意义吗？在我看来，研究对象特殊的尺度效应是召唤物理学家到来的根本原因。数学家经典的网络理论，要么是包含几十数百个顶点，可以清晰地画出来形成直观印象的网络；要么是讨论不含尺度效应，可以精确求解的网络性质。“随机移走一个顶点会对网络的性能产生什么样的影响？”这个问题对于数学家是有意义的，但对于拥有几千万个节点，连接方式复杂多样的真实网络而言，或许“随机移走3的顶点会对网络性能产生什么样的影响？”这个问题更有意义。这个尺度的网络，是被物理学家称作“足够大”的网络，对它们的研究，需要使用统计物理的方法。有的人可能会问，数学家除了经典的网络理论外，还发明了一套随机图的理论，这套理论就是专门对付“足够大”的网络的，统计力学的方法到底能不能得到随机图论不能得到的新的有意义的结果呢？正如在以后的章节中所要提到的，随机图论的方法的确在复杂网络的研究中扮演了不可或缺的角色，我也会专门辟出章节介绍它的理论和应用，但是，数学家的“足够大”和物理学家的“足够大”完全不是一个概念，虽然他们都使用顶点数趋于无穷的假设。对于物理学家而言，平均场的近似，主方程的求解，在网络顶点数达到百十万甚至几万时，误差就已经可以接受了；而随机图的大量有意义的结果，要求节点数在连续求取三次常用对数后还要比10大，而在我们的宇宙中，目前还没有任何一个有物理意义的数值达到如此的量级。物理学家不仅在方法论上为网络研究注入了新的活力，而且大大地拓展了网络研究的视野。他们不仅和数学家一样关心网络自身的拓扑性质，而且关注网络上进行的各种物理过程和动力学行为，诸如传播、同步、自组织临界、玻色爱因斯坦凝聚等等，他们发现了网络拓扑结构对各种动力学行为的影响，并给出了很多虽不严谨但很美妙的解释。这些工作很有可能会推动相关数学物理理论的发展。近几年来，大量关于复杂网络的文章发表在Science，Nature，PRL，PNAS等国际一流的刊物上，从一个侧面反映了复杂网络已经成为物理界的一个新兴的研究热点。香港城市大学的陈关荣教授统计了几年来被SCI收录的关于复杂网络的文章数量，从中可以看出明显的增长趋势。Evans统计6年来在cond-mat上提交的标题含有“network”的文章数，也同样发现了逐年递增的趋势。我国科学界也很敏感地注意到了复杂网络这一新兴前沿，并于2004年在无锡召开了首届复杂动态网络学术交流会，国家自然基金委也将在2005年推出有关复杂动态网络的重大项目。后面的章节将充斥着晦涩的术语、复杂的公式、诡异的技巧和不得不引用的文献，因此我在第一章的叙述中尽可能地避免使用这些东西。作为第一章的结尾，为读者介绍几篇重要的综述是很有意义的。图1.3： SCI收录的关于复杂网络的研究论文数量 统计了从1998年到2004年第一季度的情况，从图中可以看出，复杂网络的研究方兴未艾。图1.4： Arxiv:cond-mat上关于网络的研究论文数量 统计了从1997年到2003年cond-mat上标题含有“network”的文章情况，从图中可以看出，网络的研究在近6年来越来越受到物理学家的关注。关于小世界网络的研究，Newman1和Hayes2-3给出了不算太长的三篇综述，更短的一篇由Strogatz完成4，发表在Nature上；Albert和Barabsi给出了一篇更像是教科书的综述5，他们讨论的重点是演化的无标度网络,这篇文献在两年之内已经被引用了近千次；最为详尽的综述是Dorogovtsev和Mendes给出的6，在这篇文章中，他们用超过100页的篇幅穷举了在此之前几乎所有关于演化网络的结论，和相当详细的实验与分析的过程；2003年Newman的综述堪称精品7，漂亮的组织结构，地道风趣的语言和独到的视角，是你在阅读时会忘掉是在读一篇学术文献，后面所附的四百多篇参考文献，足以填饱任何人的肚子；Wang和Chen在电子信息类的期刊上的一篇短综述8，非常适合作为入门读物，一个完全不谙此道的人都可以通过一个下午的阅读对复杂网络研究的概貌有所了解；Wang的另一篇综述像是上一篇文章的扩展版9，在这篇文献中，Wang强调了复杂网络上的混沌同步和混沌控制，对这方面工作感兴趣的读者切不可放过该文献。最新的综述是Evans在2004年5月完成的10，这篇文献中包含了很多最新研究的结果。参考文献1 M. E. J. Newman, J. Stat. Phys., 101, 819(2000).2 B. Hayes, American Scientist, 88, 9(2000).3 B. Hayes, American Scientist, 88, 104(2000).4 S. H. Strogatz, Nature, 410, 268(2001).5 R. Albert and A-L Barabsi, Rev. Mod. Phys., 74, 47(2002).6 S. N. Dorogovtsev and J. F. F. Mendes, Advances in Physics, 51, 1079(2002).7 M. E. J. Newman, arXiv: cond-mat/0303516.8 X. -F. Wang and G. -R. Chen, IEEE Circuits & Systems Magazine, 3, 6(2003).9 X. -F. Wang, Int. J. Bifurcation & Chaos, 12, 885(2002).10 T. S. Evans，arXiv: cond-mat/0405123.第二章 图论基本知识简介对于网络的研究，最早是从数学家开始的，其基本的理论就是图论，图论本身也是目前组合数学领域最活跃的分支之一。我们在复杂网络的研究中将要遇到的各种类型的网络，无向的、有向的、加权的都可以用图论的语言和符号精确简洁地加以描述。图论不仅为物理学家提供了描述网络的语言和研究的平台，而且其结论和技巧已经被广泛地移植到复杂网络的研究中。图论，尤其是随机图论已经与统计物理并驾齐驱地成为研究复杂网络的两大解析方法。考虑到物理学家对于图论这一领域比较陌生，我在此专辟一章介绍图论的基本知识，同时将在后面的章节中不加说明地使用本章定义过的符号。进一步研究所需要的更深入的图论知识，请参考相关文献1-5。本章只给出非平凡的定理的证明，过于简单直观的定理的证明将留给读者。个别定理涉及到非常深入的数学知识和繁复的证明，我们将列出相关参考文献并略去证明过程。对于图论知识比较熟悉的读者可以直接跳过此章，不影响整体阅读。第一节 图的基本概念图G是指两个集合(V，E)，其中集合E是集合VV的一个子集。集合V称为图的顶点集，往往用来代表实际系统中的个体，集合E被称为图的边集，多用于表示系统中个体之间的关系或相互作用。若，就称图G中有一条从x到y的弧（有向边），记为x y，其中顶点x叫做弧的起点，顶点y叫做弧的终点。根据定义，从任意顶点x到y至多只有一条弧，这是因为如果两个顶点有多种需要区分的关系或相互作用，我们总是乐意在多个图中分别表示，从而不至于因为这种复杂的关系而给解析研究带来困难。如果再假设图G中不含自己到自己的弧，我们就称图G为简单图，或者更精确地叫做有向简单图。记G中顶点数为，边数为，分别叫做图G的阶和规模，显然有。图2.1a给出了一个计算机分级网络的示意图，及其表示为顶点集和边集的形式。如果弧x y与弧y x要么同时存在，要么同时不存在，我们就把这两条弧合为一条边，记为xy或yx，这样的图叫做无向图（对称图），可以被看作上述一般图（有向图）的一种特例。显然，对无向图而言，有，其中表示无向图中边的数目。图2b给出了一个无向图的示意。以后提到的图，若没有特别的说明，均指无向图。下面介绍的大部分结论都可以自然地从无向图推广到有向图，勿需重复叙述，对于那些本质上有差异的特性，我们会在文中明确指出。 图2.1：网络拓扑结构示意图 图a是10阶有向图，顶点集为1,2,3,4,5, 6,7,8,9,10，边集为12,13,14,25,26,27,36,47, 48,69,79, 810；图b是6阶无向图，顶点集为1,2,3,4,5,6，边集为13,14,15,23, 24,26,36,56。 对于两个图，如果，就称是的子图。若，则称是的生成子图；若在中所有连接集合中两顶点的边都出现在集合中，则称是的导出子图，记为。如果图与图有相同的顶点集，并且图中两点之间有边相连（相邻）当且仅当在中这两点是不相邻的，就称图是图的余图，记做。拥有条边的阶无向图或拥有条边的阶有向图叫做完全图，用符号表示，其余图叫做空图。在无向图中，与某顶点关联的所有边的数目叫做的度，用符号表示，在不致混淆的时候，可以简单地记为。对于有向图，由于需要区分从顶点出去的弧和进入顶点的弧，所以不能简单地用度表示。我们把以顶点为起点的弧的数目叫做的出度，把以顶点为终点的弧的数目叫做的入度，分别记为和。顶点度与图的规模之间有一个显然的关系：定理2.1：对于无向图有： (2.1)对于有向图有： (2.2)在图中，以为起点，为终点的路是指一系列首尾相连的边组成的集合：。其中，。边的数目被称作路的长度。如果，则称边集为圈，其长度为。中最短的路的长度称为点的距离，记为，如果中不存在路，则记(物理学家有时为了计算的方便令)。称无向图（有向图）为连通图（强连通图），如果对中任意两个不同顶点，都能够找到至少一条路。有向图被称为连通图，如果对中任意两个不同顶点，至少能找到一条路或路。若图的顶点集可以拆成两个不相交的子集，且中不含两端点同时位于中或同时位于中的边，就称图为二部分图。容易证明：定理2.2：是二部分图当且仅当中不含奇圈。如果图不含圈，我们就称其为森林，若它同时还是连通图，则被叫做树。定理2.3至定理2.5给出了树的基本性质。定理2.3：下面几个命题是等价的：(1) 是树；(2) 是最小连通图，也就是说，任意去掉一条边，都会变成非连通图；(3) 是最大无圈图，也就是说，任意加上一条边，都会变成含圈图；(4) 是连通图，且中任意两顶点之间有且只有一条路。定理2.4：阶树有条边。定理2.5：阶数大于1的树至少有两个度为1的顶点。第二节 直径、平均距离、簇系数与度分布对复杂网络的研究最早始于对真实网络诸如直径、平均距离、簇系数等参数的取值以及顶点度分布的性质的实证研究，后续的大量研究也是围绕这些概念进行的，因此有必要详细地介绍这些概念的定义以及相关的基本结论，这些介绍将有助于我们更好地理解当前复杂网络研究的物理意义。在分析传输网络的性能与效率时，有两个因素总是受到特别的关注，即最大传输时延与平均传输时延。在图理论中，它们被近似地抽象为两个参数：直径与平均距离。图的直径与平均距离可分别表为： 为了叙述方便，后文中使用来代替有关的讨论，其中。关于图直径和平均距离的研究可以追溯到半个世纪前，Ore给出了无向图直径一个漂亮的紧界6，Entringer,Jackson,Slater和Ng,Teh分别就无向图和有向图的情形给出了图平均距离粗糙但具有开创意义的下界7,8，之后Plesnik给出了平均距离只依赖于阶数和直径的下界9。Zhou等人通过一种新的构造分析方法，给出了Ore定理的简单证明，此方法可以无困难地将Ore定理推广到有向图形式。利用类似的分析方法，可以得到直径图平均距离的下界定理，Entringer，Ng等人的结果可以作为该定理的一个自然的推论给出。结合此定理与Ore定理，可以得到只依赖于阶数和直径的平均距离下界，该下界是目前已知的最好的下界10-11。Ore通过类似于构造广度优先树的方法将无向图分割成一圈圈的等距子图，其证明手法是优美而繁复的。由于其构造中隐含了的条件，因此无法直接推广到有向图的形式。显然，任何阶图都可以看作从完全无向图或完全有向图中移走若干条边后得到的，下面将从这一简单而直观的角度出发，给出 Ore定理的简单证明。定理2.66,10-11：对任意无向图，有： (2.3)其中图是指阶数为，直径为的简单有限图。证明：用表示要得到无向图至少需要从完全图中移走的边的数目，则对任意无向图，有： (2.4)令为中长为的最短路，由的最短性易知中两点不相邻，若。这就意味着至少有条边必须从中移走以得到图。同样由的最短性知，对于不在中的顶点，若中两点满足，则不能同时与相邻，即最多与中形如的三个顶点相邻。换句话说，中至少有个点不与相邻。由于中不在上的顶点数为，即有至少条边必须从中移去以得到。综上可知： (2.5)结合(2.4)(2.5)即得(2.3)式。 利用同样的分析方法，可以得到Ore定理的有向图形式，证明略。定理2.710-11：对任意强连通有向图，有： (2.6) 下面两个定理将给出平均距离的下界，由于证明比较复杂，此处省略。定理2.810-11：设为无向图，若的规模为，则有： (2.7)定理2.910-11: 对任意无向图，有： (2.8)有向图的下界可以类似的得到，此处不再赘述。图的簇系数是衡量图的成团特性的参数。对于无向图，记某顶点的邻点集合为，显然，顶点的簇系数被定义为它所有相邻节点之间连边的数目占可能的最大连边数目的比例，即：图的簇系数则被定义为所有顶点簇系数的平均值： 对于无向图，记度为的顶点数目为，则给出了图的顶点度分布。关于顶点度分布的基本性质，需要到第三节才能给出。第三节 随机图的基本模型与主要结论随机图论起源于20世纪40年代一些零星的文章，其中Sezle的文章给出了目前已知的最早利用概率方法证明的非平凡的图论定理12-14。1959年到1961年，Erds和Rnyi三篇著名的文献，使得随机图论开始成为图论一个正式的分支，他们所构建的随机图的模型在后来被称作ER模型15-17。下面的三份重要文献向我们展现了随机图论的全貌，也包含了我们将要讨论到的大部分问题1,18-19。考虑一个阶无向图，Erds和Rnyi给出了两种相似但又不完全相同的随机图的模型。如果任意两点之间独立地以概率连边，以概率不连边，就得到第一种ER随机图，习惯上记做；如果完全随机地选择条边作为边集，则得到第二种ER随机图，习惯上记做。本节主要讨论的性质，其中大多数的结论对于图也是适用的（这里显然要求）。设且（实际物理应用时只需要足够大，足够小既可以近似地求解），使得节点平均度为有限常数。只需注意到任意节点度为的概率为 (2.9)即可得到下面显然但却常用的定理：定理2.10：若满足，且为有限常数，则其度分布为均值为的泊松分布，因此常被叫做泊松网络。我们将图的顶点标号，以便彼此区别，对于某个阶图，被定义为中与同构的图的数目。定理2.11给出了在中特定结构出现的频次。定理2.11：记为图中与同构的子图的数目，则的期望值为： (2.10)其中是自同构群的阶数。证明：显然有，且根据同构计数原理有，故可得（2.10）式。 定理2.11虽然简单，但是是随机图论最基本的定理之一，有着广泛的应用。作为例子，下面我们给出定理2.11两个直接的推论。推论2.12：记为中子图的数目，则有： (2.11)推论2.13：记为中导出子图为圈图的点集数目，则有： (2.12)需要提醒注意的是，由于推论2.13中要求的是导出子图，所以多了一个因子。仍然假设，用表示第一种ER随机图构成的概率空间，定理2.14给出了一个似乎不那么直观但易于证明的结果。定理2.14：设为给定的自然数，则在中几乎所有（概率趋于1）图都满足：对于任意一个长度为的点序列，图中至少存在一个点，它与前个点相邻，而与后个点不相邻。证明：我们考察“存在一个长度为的点序列，使图中不存在任何点，它与前个点相邻，而与后个点不相邻”的概率。长度为的点序列的不同选取方法共有种，对于某个选定的点序列，没有任何顶点与前个点相邻，而与后个点不相邻的概率为。故有： (2.13)此结论与定理2.14等价。 由定理2.14可以得到一些有趣的推论：推论2.15：对给定的正整数，几乎所有图都满足，其中表示的最小度。推论2.16：几乎所有图的直径都为2。对某种性质，如果在任意具有该性质的图上添加一条边后得到的图依然具有性质，则称性质是单调递增的。Erds和Rnyi的研究表明，随着的增加，很多单调递增的性质会以某种很突然的方式涌现。对于给定的单调递增的性质，称为的下极限函数，如果当时，几乎所有图都不含性质；类似地，称为的下极限函数，如果当时，几乎所有图都含有性质。事实上，在很多情况下，下极限函数和上极限函数靠得非常近，因此我们才说相应的性质出现得非常突然。物理学家往往把这种现象看作一种相变，定理2.17给出的例子就可以被看作从不连通相向连通相的一个突变。定理2.17：记且，令，则几乎所有的图都不连通，而几乎所有的图都连通。这里我们不打算给出定理的证明，但需要特别强调的一点是，很多物理学家在研究网络时依然保留着在推导定理后再设计实验进行验证的习惯，这种习惯在网络研究中是危险的，因此必须特别地谨慎。比如对于定理2.17，Bollobs认为必须足够大以保证，这种量级的显然不是当前计算机能力所能处理的。因此，如果只是随便选取或进行实验，那么不管结果怎样，都只是一种假象。下面的定理给出了一个经典的相变图景，物理学家关于逾渗模型20-21很多重要的结论可以作为该定理的一个自然推论或利用类似的分析方法容易地得到。定理2.18：考虑一个每次在图上随机添加一条边的随机过程，其生成的图序列记为，显然为空图，为完全图。令为确定的常数，与定理2.17一致。取，有：（1） 如果，则对任意的和几乎所有的图，有： (2.14)其中是图各连通片按阶的大小排成的非增序列。（2） 存在常数，对任意的和几乎所有的图，有： (2.15)（3） 如果，则对几乎所有的图，有： (2.16)其中，唯一地由式(2.17)决定： (2.17)进一步的，对所有，式(2.14)成立。 定理2.18的证明请参考文献16，更细致的研究结果请参考文献22-25。参考文献1 B. Bollobs, Random Graphs(London: Academic Press Inc, 1985). 2 B. Bollobs, Modern Graph Theory(New York: Springer-Verlag, 1998). 3 J. Bond and U. S. R. Murty, Graph Theory with Applications(London and Basingstoke, MacMillan Press LTD, 1976). 4 J. -M. Xu, Topological Structure and Analysis of Interconnection Network(Kluwer Academic Publishers, 2001). 5 J. -M. Xu, Theory and Application of Graphs(Kluwer Academic Pub