（理论物理专业论文）复杂网络模型及其拓扑结构的变化对系统非线性动力学行为影响的研究.pdf

中文摘要 中文捅妻 复杂网络的分析已经方法广泛应用于各个学科领域。许多自然或人造系统 都可以通过形形色色的网络加以描述。一个典型的网络由若干节点及节点间相 互连接的边构成。其中节点代表真实系统中不同的个体，而边则用来表示个体 间的相互作用与联系。考虑网络时，通常只关心节点之间有没有边相连，至于 节点到底在什么位置，边是长是短，是弯曲还是平直，有无相交等都是次要 的。在此，将网络不依赖于节点的具体位置和边的具体形态就能表现出来的性 质叫做网络的拓扑性质，相应的结构叫做网络的拓扑结构。本文主要就复杂网 络的模型，及模型拓扑结构的变化对其自组织临界行为的影响进行研究。 目前许多文献所述工作主要针对无权网络，无权网络仅能给出节点间相互 作用存在与否的定性描述。但很多时候，节点间的关系或相互作用的强度起至 关重要的作用。因此，研究加权网络十分必要。加权网络通过给边赋予权重， 为刻画系统性质提供了一个新维度，调整权重也为优化网络的性质及功能提供 了新手段。另一方面，加速增长型网络在社会、生物等真实网络中广泛存在。 在这些随时间演化的真实网络中，网络规模随时间的增长可以由连接节点的边 数量上的变化来标志。此时，边数的增长同网络巾节点数的增长不再线性相 关。综合以上两点，本文首先研究了两类考虑非线性增长因素的加权演化网络 模型。通过引入权重驱动、内部选择性连接这两种演化机制、点强度优先和 扶贫这两种选点规则以及边的加速增长模式，我们提出了相应的平凡加速增 长( c a g ) 模型与扶贫( p a ) 模型。c a g 模型的点强度分布p ( s ) 为幂律形式，并且 幂律指数，y 的值依赖于参量0 ，卢的选取。特别是，在0 p 这三个不 同的取值范同内，7 有不同的变化趋势。p a 模型的点强度分布尸( s ) 可以呈现出 从幂律分布到泊松分布的转变。通过数值模拟，分析了参量取值的变化对p a 模 型的影响。同时，对两个模型的聚类系数、平均路径长度与直径、匹配系数这 三个最重要的结构性质进行了必要的对比。 原初的o f c 地震模型是建立在二维规则格子上的，其拓扑结构各向同性， 站在格子内部任意一个格点观察四周不会发现有任何差异。但是，由于地震结 构的非均匀性，地壳中真实发牛的地震显然不会以如此理想的方式发生，真实 的地震系统实际上是各向异性的。因此，为研究地震现象而抽象出的地震模型 自然也需要考结构上的异质性因素。由于c a g 模型：币i j p a 模型的拓扑结构具有很 强的非对称性，因此，我们研究了这两个加权演化网络模型拓扑结构的变化对 中文摘要 其地震行为的影响。由于所选择的这两类模型的规模不可能无限大，为分析规 模有限的系统，采用了有限尺度分析的方法来考察其有限尺度效应。 关键词：复杂网络、加权网络、加速增长网络、自组织临界性、地震行为、幂 律分布 一i i a b s t r a c t a b s t r a c t t h ev i e wo fc o m p l e xn e t w o r k sh a sb e e nw i d e l ya p p l i e dt oe a c hd i s c i p l i n e m a n y n a t u r a lo rm a n m a d es y s t e m sh a v e b e e nr e p r e s e n t e da sn e t w o r k so rg r a p h s ，w h e r et h e n o d e sa r et h ec e l l so fs y s t e m sa n d e d g e sd e n o t et h ei n t e r a c t i o n sa m o n gt h e m s c i - e n t i s t sj u s tc o n c e r na b o u tw h e t h e rt h e r ea r ee d g e sa m o n gn o d e s t h e yd on o tc a r e f o rw h e r et h el o c a t i o no fn o d e sa r e ，w h e t h e rt h ee d g e sa r el o n go rs h o r t ，c u r v e do r s t r a i g h t ，w h e t h e rt h e r ei si n t e r s e c t i o no rn o t ，a n ds of o r t h a sar e s u l t ，t h en a t u r eo f t h e t o p o l o g yo fn e t w o r ki sd e f i n e da st h eq u a l i t i e sw h i c ha r ei n d e p e n d e n to ft h es p e c i f i c l o c a t i o no fn o d e sa n dt h ec o n c r e t ef o r mo fe d g e s ，a n dt h ec o r r e s p o n d i n gs t r u c t u r ei s c a l l e dt h en e t w o r kt o p o l o g yc o n f i g u r a t i o n t h i sd i s s e r t a t i o ni n v e s t i g a t e st h ec o m p l e x n e t w o r km o d e l ，a n dt h ei n f l u e n c eo ft h ec h a n g eo ft h en e t w o r kt o p o l o g ys t r u c t u r eo n s e l f - o r g a n i z e dc r i t i c a l i t y ( s o c ) b e h a v i o r n o w a d a y s ，m u c he f f o r tg e n e r a l l yf o c u s e so nt h et o p o l o g i c a ls t r u c t u r eo fg r a p h s ， t h a ti s ，u n w e i g h t e dn e t w o r k s h o w e v e r , i ti ss t i l ld e f i c i e n tt od e s c r i b er e a ln e t w o r k s b yt h e s eu n w e i g h t e dm o d e l s ，s i n c en e t w o r kc o n f i g u r a t i o n sa n dq u a l i t i e sc a nb em o d u l a t e db yt h ei n t e r a c t i o ns t r e n g t hi nt e r m so ft h ew e i g h tt a k i n gp l a c ea l o n gt h ee d g e e i t h e r t h e r e f o r e i ti sc r i t i c a lt oi n v e s t i g a t et h ew e i g h t e dn e t w o r k s o nt h eo t h e rh a n d ， a c c e l e r a t i n gg r o w t hn e t w o r k sa r em o r eu n i v e r s a la n di m p o r t a n ti ns o c i e t ya n db i o l o g yn e t w o r k s i nt h e s er e a l - w o r l dn e t w o r k sw h i c he v o l v ew i t ht i m e ，n o n l i n e a rg r o w t h a l o n gw i t ht i m ec a nb ei d e n t i f i e df r o mt h en u m b e ro fe d g e s i nt h i ss i t u a t i o n ，e d g e n u m b e rg r o w sf a s t e rt h a nl i n e a r l yw i t hn e t w o r ks i z e a si ss h o w na b o v e ，i n t r o d u c i n g t h ew e i g h t - d r i v e na n di n n e rs e l e c t i o nd y n a m i c s ，s t r e n g t hp r e f e r e n t i a lp r o b a b i l i t ya n d t h ep r o b a b i l i t yo fp o v e r t ya l l e v i a t i o no fs t r e n g t ha n dt h ea c c e l e r a t i n gg r o w t hm a n n e ro f o u t g ：o i n ge d g e s ，w ei n v e s t i g a t eb o t ht h ec o m m o na c c e l e r a t i n gg r o w t h ( c a g ) m o d e la n d t h ep o v e r t ya l l e v i a t i o n ( p a ) m o d e l i nt h ec a gm o d e l ，t h en e t w o r ke x h i b i t saw i d e - r a n g ep o w e rl a wd i s t r i b u t i o no fn o d es t r e n g t h s ，a n dt h ee x p o n e n tc a nb ea d j u s t e db y t h ep a r a m e t e r s0a n d8 i np a r t i c u l a r , t h ee x p o n e n t1h a sd i f f e r e n tv a r i a t i o n a lt r e n d si n t h ef o l l o w i n gf i e l d s ：0 8 ，e = 8a n d0 8 i nt h ep am o d e l ，i ti ss h o w nt h a tt h e n o d e s s t r e n g t hd i s t r i b u t i o np ( s ) c a nd i s p l a yt r a n s i t i o nf r o map o w e rl a wd i s t r i b u t i o n t oap o i s s i o n l i k ed i s t r i b u t i o n w ep e r f o r mn u m e r i c a ls i m u l a t i o n st of i n do u tt h ep r o p e r t i e so ft h ep am o d e lb yc h o o s i n gd i f f e r e n tp a r a m e t e r s t h ec l u s t e r i n gc o e f f i c i e n t ，t h e a v e r a g ew e i g h t e ds h o r t e s tp a t hl e n g t h ，t h ed i s t a n c ea n dt h ec o r r e l a t i o np r o p e r t yo f o u r m o d e l sh a v e b e e ni n v e s t i g a t e ds i m u l t a n e o u s l y 一i 一 a b s t r a c t t h e o r i g i n a lo f ce a r t h q u a k em o d e l i sc o n s t r u c t e do nt h et w od i m e n s i o n a ll a t t i c e a n dt h es t r u c t u r eo ft o p o l o g yi sh o m o g e n e o u s h o w e v e r , t h er e a le a r t h q u a k ew h i c h b r e a k i n go u ti nt h ee a r t h sc r u s tw o u l dn o tg oa l o n gw i t ht h i sp e r f e c tw a y t h er e a l e a r t h q u a k es y s t e mi sh e t e r o g e n e o u s t h e r e f o r e i ti sc r u c i a lt oi n t r o d u c et h eh e t e r o g e n e i t yo fs t r u c t u r ei nt h es t u d yo fo f ce a r t h q u a k em o d e l s i n c et h e r ea r es t r o n g u n s y m m e t r yi nt h ec a gm o d e la n dp am o d e l w es t u d yt h ei n f l u e n c eo ft h ec h a n g eo f t h en e t w o r kt o p o l o g ys t r u c t u r ei nc a gm o d e la n dp am o d e lo ns e l f - o r g a n i z e dc f i t i c a l i t y ( s o c ) b e h a v i o r b e c a u s et h es i z eo ft h e s et w om o d e l sc a nn o tb e c o m ei n f i n i t e l a r g e 。w eu s et h ef i n i t e s i z ea n a l y s i st oi n v e s t i g a t ei t sf i n i t e s i z ee f f e c t k e yw o r d s ：c o m p l e xn e t w o r k ，w e i g h t e dn e t w o r k ，a c c e l e r a t i n gg r o w t hn e t w o r k ， s e l f - o r g a n i z a t i o nc r i t i c a l i t y , p o w e r - l a wd i s t r i b u t i o n ，e a r t h q u a k eb e h a v i o r 一一 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名： 年丁月如日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 解密时间：年月日 各密级的最长保密年限及书写格式规定如下： j 内部5 年( 最长5 年，可少于5 年) 秘密1 0 年( 最长1 0 年，可少于l o 年) 机密2 0 年( 最长2 0 年，可少于2 0 年) 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行研究工作 所取得的成果。除文中已经注明引用的内容外，本学位论文的研究成果不包含 任何他人创作的、已公开发表或者没有公开发表的作品的内容。对本论文所涉 及的研究工作做出贡献的其他个人和集体，均己在文中以明确方式标明。本学 位论文原创性声明的法律责任由本人承担。 学位论文作者签名： 年r 月幽日 第一章引言 第一章引言帚一早，li 自然科学在宇观、宏观和微观三个前沿发展着。探索宇宙演化的奥秘和微 观世界的结构这两个尖端，涉及愈益庞大的投资和设备，往往成为单个国家难 以独立支持的项目。美国前些年下马的超级超导对撞机以及现今仍在巡天的哈 勃太空望远镜就是两个实例。当今世界，能有幸直接从事这类研究的学者数目 逐年减少，多数人只能从旁欣赏他们的成果与发现。这两方面的研究成果，有 重大的认识论意义，在历史尺度上而非计日程功地改变着我们人类的生产方 式。与此形成尖锐对比的是，宏观层次的自然科学，包括广义的物理学、生命 科学、地球与环境科学等等，集中了众多的人力与物力，也同人类的生产和生 活更加息息相关。这里的研究对象斑驳陆离、五花八门、复杂多变，有没有共 同的理论线索呢? 一门旨在研究这些复杂现象的前沿科学“复杂性科学”应运 而牛。它为科学的发展提供了一个用“整体 或者“系统”来处理复杂性问题 的新方向。 自近代科学诞牛以来，人们对客观对象的分析主要运用的是还原论的方 法，即线性方法和机械思维。譬如牛顿第二定律f = m o ，虽然它仅仅告诉我 们若一物体受到外力作用则必定会发生相应的加速或减速运动，但这个简单的 定律足以用来描述苹果是如何落到地面，行星是如何围绕恒星转动。麦克斯韦 方程6 d e = j 描述了电流与磁场间的相互作用，使我们明白发电机是如何工作 的。爱因斯坦的相对论表明，物体高速运动时牛顿定律需要做相应的修正。量 子力学告诉我们，原子中的电子只能处于特定的能级上，电子从一个能级激发 到另一个能级根本不花时间。这些物理定律是简单的。许多科学家曾经相信， 一旦我们找到能表征世界的最基本的定律，并且基本粒子得以证实，一旦我们 完成了这项功绩，那么物理学的角色一“科学的国王 的戏份也就没有了。剩 下的工作就要留给其他科学，如化学、生物学、地球与环境科学等来整理结 果【l 】。虽然复杂现象比比皆是，人们还是努力要把它们还原成更简单的组分或 过程。但是，我们所处的世界真的是如此简单地演化么? 答案当然是否定的。 随着科学的发展，人们发现越来越多的自然现象绝不能简单的机械求和。我们 所面临的实际系统是复杂多变的，是一个涉及到多种因素和多方面相互作用的 复杂系统，是没有可能还原而必须从整体论的角度去把握的。复杂系统随处可 见，物理学中的湍流，化学中的反应波、演化的天体、发展的地貌、生物学中 的生命现象和生态问题、经济学中的股市和国民经济规划、社会学中的政治和 第一章引言 人口问题等都是我们常见的典型复杂系统。当前国际学术界正致力于复杂性理 论与现有传统学科交叉的研究，这一前瞻性和探索性的研究将突破文艺复兴以 来还原论的框架，试图为当代学术研究和科学技术带来一场深刻变革。 事实上，复杂性并非新问题。在美国国会图书馆1 9 7 5 年至1 9 9 9 年2 月1 5 日 的入藏书目中，标题里含有复杂性( c o m p l e x i t y ) - - 词的就有4 8 9 种【3 1 。其中涉及 算法复杂性、计算复杂性、生物复杂性、生态复杂性、演化复杂性、发育复 杂性、语法复杂性、乃至经济复杂性、社会复杂性，凡此种种，不一而足。 其实，现代电子计算机之父冯诺依曼( j v o nn e u m a n n ) 早就说过，“阐明复杂 性和复杂化概念应当是2 0 世纪科学的任务，就像1 9 世纪的熵和能量一样。”看 来，2 0 世纪的科学并没有完成这个任务，要把它传递到新的千年。 复杂性的定义是相对于简单性而言的，其概念目前并没有一个统一的说 法，而是根据研究对象的不同有不同的提法。譬如，从熵的角度看，复杂性等 于热力学测定的一个系统的熵和无序；从信息的角度，复杂性等于一个系统使 一个观测者“惊奇的能力”；从分形的尺度，复杂性等于一个系统的“模糊状 况”，即在越来越小的尺寸上显示的详细程度；从有效复杂性角度看，可将复 杂性看做一个系统显示“规律性”而非随机性的程度；从体系复杂性角度看， 可将复杂性看做由一个体系结构系统的不同层次所显示的多样性；从语法复杂 性角度看，可将复杂性看做描述一个系统所需要的语言的普遍性程度；从热力 学深度看，可将复杂性看作将一个系统从头组织在一起所要的热力学资源的数 量；从时间计算上的复杂性角度看，可将复杂性看作一部计算机描述一个系统 或解决一个问题所需要的时间；从空间计算上的复杂性角度看，可将复杂性看 作一部计算机描述一个系统或解决一个问题所需要的存储量 2 1 等等。 复杂性科学往往研究的是复杂系统，复杂系统主要有以下表现 3 - 8 ： ( 1 ) 复杂系统具有多层次、多功能的结构，每一层次均成为构筑其上一层 次的单元，同时也有助于系统某一功能的实现。 ( 2 ) 复杂系统具有整体性、系统性。系统整体不等于各组成部分之和，每 个组成部分不能代替整体，每个层次的局部不能说明整体，低层次的规律不能 说明高层次的规律。 ( 3 ) 复杂系统不同单元、不同层次间的联系广泛而紧密，构成一个网络。 因此每一单元、每一层次的变化都会受到其他单元、其他层次变化的影响，并 会引起其他单元、其他层次的变化。而且这种相互联系也是多种多样的。 一2 一 第一章引言 ( 4 ) 复杂系统是动态的，它处于不断的发展变化之中，而且系统大多对未 来的发展变化有一定预测能力。 ( 5 ) 复杂系统在发展过程中能够不断地学习并对其层次结构与功能结构进 行重组与完善。 ( 6 ) 复杂系统是开放的，它与环境有密切联系，能与环境相互作用，并能 不断向更好地适应环境的方向发展变化。 ( 7 ) 复杂系统的演化过程是阶段性的、存在渐变和突变，整个过程是非线 性的。渐变是突变的基础，突变则是从低级到高级的变化原因。可将突变视为 某个复杂系统由一种阶段、一种状态向另一种阶段、另一种状态演化的转折。 ( 8 ) 复杂系统在远离平衡的状态下也可以通过自组织达到稳定，确定性的 系统有其内在的随机性( 譬如混沌) ，而随机性的系统也有其内在的确定性( 譬如 突变) 。 复杂性科学的发展主要经历了三个阶段：自2 0 世纪2 0 年代到6 0 年代为第一 阶段：贝塔郎菲( k l v o nb e r t a l a n f f y ) 提出一般系统论、维纳( n w i e n e r ) 提出的 控制论、香农( c e s h a n n o n ) 提出的信息论、诺依曼( j v o nn e u m a n n ) 提出的元 胞自动机等是这个时期复杂性研究的代表性成果，标志着复杂性研究的起源 和萌芽。2 0 世纪6 0 年代到8 0 年代为第二阶段：普里高津( i p r i g o g i n e ) 的耗散结 构、哈肯( h h a k e n ) 的协同论、艾根( m e i g e n ) 的超循环论等自组织理论、托 姆( r t h o m ) 的突变论、混沌学理论以及后来的分形论是这个阶段的代表性成 果，标志着复杂性研究在自组织理论、非线性科学方面已经取得了比较明确的 成果。2 0 世纪8 0 年代至今为第三阶段：它是复杂性科学真正诞生的时代，它是 在自组织理论和非线性科学理论的基础上发展起来的。1 9 8 4 年诺贝尔物理学奖 获得者盖尔曼( m g e l l m a n ) 、安德逊( pa n d e r s o n ) 矛l ：l 诺贝尔经济学奖获得者阿 若( k m r o w ) 等人，聚集了一批从事物理、经济、理论物理、计算机等科学的 研究人员，组成了圣塔菲研究所( s f i ) ，专门从事复杂性科学的跨学科交叉研 究，试图在生命系统、免疫系统、人脑系统、经济系统等不同的复杂系统间找 出共性复杂性。他们认为，所有复杂系统都有一种能力，能使秩序与混乱 达到某种特别的平衡，在这个我们称之为“混沌边缘”的平衡点上，系统的组 分从来不会真正锁定在一个位置上，但也不会分解开来，融入混乱之巾。与此 同时，2 0 世纪9 0 年代初以来，中国的钱学森教授所领导的系统科学学派也在复 杂性科学研究中进行了许多创造性的探索，提炼出复杂巨系统的概念，并创造 性地提出了“从定性到定量的综合集成法”以及“从定性到定量的综合集成研 一3 一 第一章引言 究厅体系”。美国圣塔菲复杂性科学研究所、中国钱学森教授领导的系统科学 学派以及后来的一系列复杂性科学研究所的创立和兴起大大促进了复杂性科学 研究的发展，复杂性科学研究从此引起了国际社会众多有识之士的高度关注， 目前国际上已经掀起了一股研究复杂性和非线性问题的热潮，并正在与各门学 科进行交叉，数学家、物理学家、经济学家、生物学家和计算学家等都在共同 开展这一问题的研究，复杂性科学将成为一个驾驭在2 1 世纪生命科学、信息科 学、材料科学等高新领域之间的一个横断学科，被誉为“2 1 世纪的科学”。目 前人们己提出并发展了复杂适应系统的概念，在经济系统的演化、免疫系统的 形成、人工生命、基因和神经网络的计算等方面已取得了巨大的进展。实际问 题是典型的复杂性问题，对其运用复杂性科学理论进行研究不仅有利于认清实 际复杂系统的规律，而且反过来又会大大促进复杂性科学基础理论的研究进 程，引起国内外广泛兴趣和众多学科的关注。复杂系统的非线性、非平衡性、 不可逆性、开放性、多层次性、动态性、自组织性、临界性、自相似性、统计 性等鲜明特征向现有的科学理论和新世纪科学技术提出了巨大的挑战，人们预 计复杂性科学在新世纪将不仅会在基础理论方面有重大突破，同时也将为人类 提供发展高新技术的极好机遇，必将展示美好的应用前景。 自然界与人类社会中广泛存在着复杂系统，而复杂系统正好可以通过各种 各样的复杂网络来描述。事实上，复杂网络的研究极大地促进了对复杂系统的 研究和发展，已经成为当今复杂系统或复杂性科学研究中最受关注以及最具挑 战性的科学前沿课题之一。“网络科学”是与众多学科和领域广泛交叉的一门 新兴科学，它的诞生既适应现代网络信息时代的需要，又符合2 1 世纪复杂性科 学研究的趋势。正如当代物理学家史蒂芬霍金在世纪之交所预言的，“2 1 世 纪将是复杂性的世纪”。2 1 世纪9 年多来世界科学的发展越来越印证了这一科 学预言。历史证明，任何科学的突破都离不开时代背景与环境。2 0 世纪9 0 年代 以来，由于计算机、互联网等科技的迅猛发展，人们能够更方便快捷地获取所 需的信息和资源，促使人类加速跨入了网络信息时代，人类生活与科学研究因 此发牛了巨大的历史性变化。复杂网络已经成为信息时代生活中不可或缺的一 部分，发挥着主导性作用。与此同时，各领域的科学家们积极合作，充分利用 人类已有的科学知识和科技成果，从理论和实践上深入探索“网络科学的内 蕴，推进各种复杂网络的广泛应用，这已经成为这一领域研究和发展的强大动 力。 一4 一 第一章引言 11 复杂网络 复杂网络已经被广泛应用于各个学科领域。许多自然或人造的系统都可以 通过形形色色的网络加以描述，比如因特阏( i n t e r n e t ) 、互联网( w w w ) 、生物 网，社会经济网、科学家合作网( s c n ) 、世界航空网( w a n ) 等等 81 4 l 。一个典 型的网络由若干节点及节点间相互连接的边构成，其中节点代表真实系统巾不 同的个体，而边则用来表示个体间的相互联系与作用。通常当两个节点间具有 某种特定的关系时在其间添加_ 条边，否则不添加边。有边相连的两个节点在 网络中被看作是相邻的。譬如，可将神经系统视为大量神经细胞通过神经纤维 相互连接形成的网络，而计算机网络可被视为自丰工作的计算机通过通信介 质如光缆、双绞线、同轴电缆等相互连接形成的网络 t s l 。数学家和物理学家在 考虑网络的时候，往往只关心节点之间有没有边相连，至于节点到底在什么位 置，边是长还是短，是弯曲还是平直，有没有相交等都是次要的。在此，我们 将网络不依赖于节点的具体位置和边的具体形态就能表现出来的性质称为网络 的拓扑性质，相应的结构称为网络的拓扑结构。 复杂网络是综合以往的自组织理论、非线性科学与复杂性理论的研究成果 而形成的崭新课题。复杂网络的兴起，为系统科学的研究开拓了视野，提供了 全新的_ 【l l 角。复杂网络作为复杂系统的一种一般性的抽象和描述方式，作为复 杂系统的结构形态，突出强调了复杂系统的拓扑性质。为了更好地理解复杂系 统的动力学行为，研究复杂网络的拓扑结构是必要的。因此，我在硕士期间的 工作主要研究嘲络的拓扑结构与性质及其拓扑结构的变化对系统自组织临界行 为的影响。 1 1 1 网络科学的发展历程 图1 ll 八世纪的梧尼斯堡，图中标出了七座桥 第一章引言 b 图1 2 左图为格尼斯堡河流与桥梁的简化示意图。右图为对应的节点和边构成的网络 从数学的角度看，网络的研究与发展有悠久的历史。追溯网络发展的足 迹，我们发现网络首先是得益于图论与拓扑学等应用数学的发展。历史上，多 位杰出的数学家各自独立地建立和研究过图论，他们的贡献功不可没。关于图 论的文字记载最早出现在欧拉( l e u l e r ) 的著作中。1 7 3 6 年，欧拉对格尼斯堡七 桥问题( k 6 n i g s b e r gb r i d g ep r o b l e m ) 产生浓厚兴趣。格尼斯堡位于东普鲁士的首 都，今俄罗斯加里宁格勒市，普莱格尔河横贯其中。1 8 世纪在这条河上建有7 座 桥，将河中间的两个岛同河岸连接起来。人们闲暇时经常在桥上散步，有人提 出：能否每座桥都只走一遍，最后又回到出发点的位置。这个看起来简单却很 有趣的问题吸引了大家，很多人在尝试各种各样的走法，然后无数次的尝试都 没有成功。看来要得到一个明确、理想的答案并不容易。1 7 3 6 年，有人带着这 个问题找到了当时的大数学家欧拉。欧拉经过一番思考，很快就用一种独特的 方法给出了答案。欧拉首先将这个问题简化，他把两座小岛以及河的两岸分别 看成四个点，而将七座桥看做这四个点之间的连线，如图1 2 所示，a 、b 、c 、d 代表陆地。问题是要从这四块陆地中任何一块开始，通过每一座桥正好一 次，再回到起点。即这个问题简化成，能否用一笔就把这个图形画出来。经 过进一步分析，欧拉得出结论不可能每座桥都走一遍，最后回到原来的位 置。并且给出了所有能够一笔画出来的图形所需具备的条件。这是拓扑学的 “先声 。欧拉在1 7 3 6 年解决了这个问题，用抽象分析法将这个问题化为第一 个图论问题：即把每块陆地用一个点代替，将每座桥用联结相应两个点的一条 线代替，从而相当于得到一个图。欧拉证明这个问题没有解，并且推广了这个 问题，给出了对于一个给定的图可以以某种方式走遍的判定法则：图中是否存 在欧拉回路。这个工作使得欧拉成为图论( 与拓扑学) 的创始人【1 6 】。这是科学家 对网络科学的开创性贡献，于是欧拉被誉为图论之父。在过去的三个世纪里， 图论成为描述网络性质的主要数学工具。在其最简化的形式中，一个网络可以 一6 一 第一章引言 被抽象成为一组由众多节点以及节点与节点之间相互连接的边所构成的图形。 这些节点和边的组合几乎可以代表任何事物。通过忽略问题的细节，图论可以 清晰地描绘出其拓扑性质。因此，图论的应用范围超越了单纯的数学问题，特 别是近十几年，图论已经应用于工程、军事研究以及计算机科学等等。如今图 论甚至受到社会学家的广泛青睐。 另一个对网络科学理论作出具有里程碑意义贡献的是两位匈牙利著名数 学家爱多士e d 6 s 矛lr e n y i 。他们在2 0 世纪5 0 年代末和6 0 年代建立的随机图理 论，被公认为是在数学上开创了复杂网络理论的系统性研究 1 7 1 。在e d 6 s 和 r e n y i 研究的随机图模型( 称为e r 随机图) 中，任意两个节点之间有一条边相连 接的概率都为p 。因此，一个含个节点的e r 随机图中边的总数是一个期望 值为pf ( 一1 ) 2 1 的随机变量。由此可以推得，产生一个有个节点和m 条 边的e r 随机图的概率为pm ( 1 一p ) n ( n _ 1 ) 2 一m 。e d 6 s 和r e n y i 系统性地研究了 当_ 时e r 随机图的性质( 如连通性) 与概率p 之间的关系。他们采用了以下 定义：几乎每一个e r 随机图都具有某种性质q ，当_ 。时产生具有这种性 质q 的e r 随机图的概率为1 。e d 6 s 和r e n y i 最重要的发现是：e r 随机图的许多重 要性质都是随网络规模的增大突然涌现的。也就是说，对于任意给定的概率p ， 要么几乎每一个图都具有某个性质q ，要么几乎每一个图都不具有该性质。他们 创立的e r 随机图理论为图论的阈函数和巨大分支涌现的相变等奠定了基础，成 为研究网络的一种重要的数学理论。他们还与那些伟大的理论物理学家和数学 家，如爱因斯坦、哥德尔、奥本海默等有密切的学术交往。确实，用图论的语 言和符号可以精确简洁地描述各种网络，图论不仅为数学家和物理学家提供了 描述网络的共同语言和研究平台，而且至今许多图论的研究成果、结论、和方 法技巧仍然能够自然地应用到现在复杂网络的研究中去，成为网络科学研究的 有力方法和工具之一。可见在长达四十年的时间巾e r 随机图对于图论以及网络 科学理论的影响之大与之广。 直到1 9 9 8 年，学界迎来了复杂网络的又一次突破性进展，首先冲破了e r 理 论局限的是，康奈尔( c o r n e l l ) 大学理论和应用力学系的博士研究生w a t t s 及其导 i ) i t i s t r o g a t z 在( ( n a t u r e ) ) 杂志上发表了题为“小世界”网络的群体动力行为 的论文 引，提出了小世界网络的模型。这实际上是2 0 世纪6 0 年代哈佛大学心理 学家m i l g r a m 曾经做过的著名的小世界实验的一种拓展 1 8 1 。m i l g r a m 提出的“六 度分离”( s i xd e g r e e so fs e p e r a t i o n ) 是社会调查后的推断，它原意是指在美国大 多数人中，任意两个人平均通过6 个人就能够彼此认识。不管是谁，如果想认 一7 一 第一章引言 识一个素不相识的人，只要通过六个他的朋友的朋友转达之后，一般就能够联 系得上。人们常有这样的体验，当参加国内外会议或访问或旅游时，经常与 遇到的一些新朋友交谈时，就会很快发现，他认识你的朋友，你认识他的朋 友。于是大家不约而同地感慨，这个世界真小啊! 这便是所谓“小世界效应( 现 象) ”。这里包含了“六度分离概念”的基本思想。 接着，1 9 9 9 年，圣母( n o t r ed a m e ) 大学物理系的b a r a b z i s i 教授及其博士 牛a l b e r t 在( ( s c i e n c e ) ) 上发表了题为随机网络中标度的涌现一文【9 1 ，提 出了一个无标度网络模型，发现了复杂网络的无标度性质，并和m n e w m a n n ，d j w a t t s 共同编辑了网络的结构与动力学专著。该书在国际上产 生了广泛影响，引起了全世界高度重视。正是由于他在网络科学方面的杰出贡 献，因此于2 0 0 6 年获得了冯诺依曼计算金奖。标志着复杂网络研究进入了网络 科学的新时代【1 9 ，2 0 1 ，由此诞生了一门崭新的科学：网络科学。 网络科学的两大发现，以及随后许多真实网络的实证研究表明，真实世界 网络既不是规则网络，也不是随机网络，而是兼具小世界和无标度特性，具 有与规则网络和随机图完全不同的统计特性。这在全世界学术界激起了千重 浪，研究复杂网络的文章铺天盖地席卷而来，网络科学的综述和专著不断涌现 【1 0 ，2 1 - 3 1 1 ，从物理学到牛物学，从社会科学到技术网络，从工程技术到经济管理 等众多领域，受到了人们的空前关注和重视，正在突飞猛进的发展。 1 1 2 复杂网络的应用以及研究意义 无论是在自然界还是在社会生活中，网络都是普遍存在的。当前国内外网 络科学的研究方兴未艾，复杂网络的应用领域已经涉及到军事、经济、通信、 工程技术、社会、政治和管理等众多领域。小世界网络和无标度网络等的发现 极大地改变和丰富了人们对复杂世界的认识，揭示了前所未有的理论和技术问 题，不仅适用于自然网络，也适用于人造网络，无论对自然界还是人类社会， 都具有极大的应用价值。但是网络科学的规律尚未完全揭开，进一步探索网络 科学的奥秘，不仅具有理论意义，也具有巨大的应用潜力 2 8 1 。 首先，研究复杂网络具有现实的及长远的军事国防意义。事实上因特网的 发展首先是大国军事和信息竞争的需求。1 9 6 9 年美国国防部最早建立了计算机 网络，并向国际j 巨联网、因特网发展。其后，欧洲、日本相继建立了资源共享 的计算机网络。2 0 世纪9 0 年代，因特网扩大到世界范闱，创造了人类崭新的互 联网军事、经济、文化和科技新领域。2 1 世纪是互联网和信息时代，互联网的 一8 一 第一章引言 发展正带动计算机、微电子、通信和软件等信息产业的发展，成为2 1 世纪全球 军事和经济的主要推动力，正是这些需求又推动着因特网向宽带、高速发展。 积极探索下一代：巨联网，包括光：巨联网以及未来的量子互联网，这些都极富挑 战性。为了适应现代国防和经济持续发展的双重需求，网络科学的深入研究具 有长远的战略意义和巨大的应用潜力。 其次，复杂网络理论可以为蓬勃发展的技术网络和网络工程等的设计、 防护和开发应用提供坚实的理论与技术基础。目前，人们牛产生活对这些实 际复杂网络的依赖程度日益增强，与社会牛活息息相关的因特网、互联网、 电力网、航空网、电子邮件网、食物链网等网络愈加备受关注。令人震惊的 是，2 0 0 3 年8 月1 8 日北美突然大停电，就是复杂电力网络的一系列级联反应导 致整个电力系统土崩瓦解。美国与加拿大北部部分地区一夜间陷入一片黑暗之 中，经济损失和社会影响十分严重。国内外电力网络的数据初步分析表明，这 种灾变与网络的性质有关，涉及到网络本身的结构和功能的缺陷等内在的联 系。近年又一令人震惊的事件是，2 0 0 6 年1 2 月2 7 日台湾地区的地震演变成史无 前例的亚太地区通讯网络大灾难。由于地震损毁了铺设于台湾周边的全部六条 深海电缆，整个亚太地区大量海外客户的金融、商贸无法交易。台湾地区的六 条发生中断的国际海底通信光缆包括中美海缆、亚太1 号、亚太2 号、f l a g 海 缆、亚欧海缆、f n a l 海缆等，断点在台湾以南1 5 公里的海域。受余震影响， 抢修工作一直困难重重，加之海底施工难度很大，修复工作持续了两个多月， 造成的经济损失和社会影响不可估量。这类网络灾变迫使人们提出令人高度关 注的问题：人类如何应对网络灾变? 怎样确保网络可靠运转? 如何面对如此严 峻的挑战? 另一起人们不会忘记的事件是，2 0 0 0 年5 月4 日，“爱虫”病毒在互 联网上大肆扩散，一天之内造成全球经济损失十多亿美元，而且现在仍在肆 虐。2 0 0 6 年下半年“熊猫烧香”的肆虐并不亚于“爱虫”病毒。因此，同样令 人关注的一个问题是：计算机病毒如何在互联网上传播而导致流行? 病毒如何 通过电子邮件传播? 人们如何才能控制病毒传播? 怎样保持当前不断恶化的全 球生态系统的平衡? 当前，这些问题都与复杂网络的特性密切相关，为了有效 地防止黑客侵入互联网、阻止病毒在互联网上传播蔓延，需要继续深入研究这 类与应用密切相关的课题。总之，网络的一系列谜团仍然闲难重重，亟待解 开。为此，必须揭开网络的深层次奥秘才能找到真正的解决方法。复杂网络大 多数是高科技的产物，在享受高科技带来的便捷同时，科学家们正在努力寻找 解决和应对新挑战的办法，积极探索如何大力发展和充分利用高科技的成果进 一9 一 第一章引言 一步推动复杂网络科学的基础和应用研究工作，以尽快揭示复杂网络系统的 “庐山真面目”。 第三，我们一直面对着社会领域复杂网络的严峻考验，特别是艾滋病、非 典、禽流感、甲型h 1 n 1 等高致病性传染病的威胁。2 0 0 3 年的“非典”对宏观经 济和人类生命安全造成巨大威胁与损害，而近年禽流感已经成为另一世界范围 内关注的焦点。我们面临的问题是，在特定的社会网络中传染病如何通过接触 关系传播进而导致流行的? 决策者如何控制这些疾病将损失降到最低限? 只有 深入揭开复杂网络的奥秘才有希望找到这些问题的合理答案和解决途径。 1 1 3 网络科学研究的特点 目前的网络科学，不仅用数学上图论的语言、符号和理论来精确而简洁的 描述，而且以统计物理等诸多现代科学为理论基础。一般复杂网络具有以下几 个特征和研究内容【2 0 】： ( 1 ) 网络规模极其巨大，节点数一般成千上万，甚至达到数十亿以上。因 此网络的行为特性必然需要用统计的方法来处理。 ( 2 ) 网络的结构具有复杂性和多样性：大多数实际的网络结构，既非完全 规则，也非完全随机，而是随机性与确定性相混合的一种结构。由于网络系统 由大量子系统或单元所组成，结构庞大而复杂。因此，复杂网络是一类最典型 的复杂系统。不仅需要应用图论、非线性、复杂性科学等现代数学理论方法进 行研究，而且需要应用和开拓现代统计物理方法( 平衡态与非平衡态理论) ，利 用许多已有的科学知识成果来深入地研究复杂网络的特殊性和普适性。 ( 3 ) 网络