（电力系统及其自动化专业论文）复杂网络理论在电力网中的若干应用研究.pdf

浙江人学博ij 学位论文 低故障传播的风险，也可增强网络的连通性，从而为无标度网的设计、规划和改 造提供优化目标和理论参考。 以浙江省电力通信网为例，对电力通信网物理路由网的复杂网络特性进行了 分析研究。浙江省电力通信网的度分布满足指数规律，为局域世界网络，其地区 子网均为无标度网络，且省网和各地区子网均为小世界网络。基于静态分析法的 鲁棒性和脆弱性分析表明，电力通信物理路由网对于节点和边的随机故障和意外 攻击具有极强的鲁棒性，而对于针对高度数节点的蓄意攻击和破坏却具有很高的 脆弱性；在基于最短路径路由的通讯原则下，应该加大对电力通信网中高度数节 点和高介数节点( 线路) 的保护。 关键词：复杂网络，复杂性，拓扑，脆弱性，电力网，电力通信网 浙江大学博ij 学位论文 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fg l o b a le c o n o m i c s ，l a r g e - s c a l e di n t e r c o n n e c t i o no f p o w e rg r i d sh a sb e c o m ea ni n e v i t a b l et r e n df o rp o w e rs y s t e m sa l lo v e rt h ew o r l d w h i l e ，t h ec a p a b i l i t yo fp o w e rg r i dt ot r a n s f e rp o w e ro v e rh u n d r e d so rt h o u s a n d so f m i l e sa l s oe n a b l e st h ep r o p a g a t i o no fl o c a lf a i l u r e si n t og l o b a ln e t w o r k t r a d i t i o n a l m e t h o d sh a v ea l r e a d yc o n f r o n t e dt h el i m i t a t i o ni nc o m p r e h e n d i n gt h em e c h a n i s mo f c a s c a d i n gf a i l u r e n e ws o l u t i o n sa r ei n s t a n t l yn e e d e dt os i m u l a t ea n ds t u d yt h e d y n a m i c so fc o m p l e xp o w e rs y s t e m t h et h e o r yo fc o m p l e x i t ya n dc o m p l e xn e t w o r k p r o v i d ea no r i g i n a lp e r s p e c t i v eo fg l o b a ln e t w o r kf r o mt h ep o i n to fv i e wo fs y s t e m l e v e l b a s e do nt h es u m m a r yo fc o m p l e xn e t w o r kt h e o r y , i n c l u d i n gr 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 ka n ds c a l e - f r e en e t w o r k ，t h er e c e n tb l a c k o u t st h r o u g h o u tt h e w o r l da n dt h em e c h a n i s mo fc a s c a d i n gf a i l u r e sd r a wo u ra t t e n t i o n t h r o u g ht h e s t a t i s t i c sa n da n a l y s i so fc h a r a c t e rv a r i a b l e so fd o m e s t i cp o w e rg r i da c c i d e n t sw i t h l o a dl o s s ，t h ep o w e rl a wr e l a t i o n s h i pb e t w e e nt h eb l a c k o u td i m e n s i o na n df r e q u e n c y i sd i s c o v e r e d ，a n dt h et h e o r yo fs e l f - o r g a n i z e dc r i t i c a l i t yi su s e dt o e x p l a i ns u c h p h e n o m e n a u s i n gt h em e t h o do fr sa n a l y s i s ，t h eh u r s te x p o n e n t so fb l a c k o u ts e r i e s a r er e s p e c t i v e l yc a l c u l a t e d ，a n dt h ef r a c t a lc h a r a c t e r i s t i ci sa l s oe x p l a i n e d w i t ht h e t o p o l o g ym o d e l l i n go fr e a l w o r l dp o w e rg r i d s ，t h ee x p o n e n t a i ll a wo fd e g r e e d i s t r i b u t i o n ，t h en e g a t i v ep o w e rl a wa n ds e l f - s i m i l a r i t yo fb e t w e e n n e s s ，t h ez i p f f r a c t a lf e a t u r ea n ds m a l l - w o r l de f f e c ta r er e s p e c t i v e l yt e s t i f i e d b a s e do nt h es t r a t e g i e so fr a n d o mf a i l u r ea n di n t e n t i o n a la t t a c k ，b o t ht h es t a t i c a n a l y s i sa n dd y n a m i ca n a l y s i sa r ea d o p t e dt os t u d yt h e r o b u s t n e s sa n dv u l n e r a b i l i t yo f n e t w o r k s t h er e a l - w o r l dp o w e rg r i d sa r er o b u s tt or a n d o mf a i l u r e sa n da r eh i g h l y v u l n e r a b l et oi n t e n t i o n a la t t a c k so nc o m p o n e n t sw i t hh i g hb e t w e e n n e s sd u et ot h e h e t e r o g e n e o u st o p o l o g ya n dd e g r e ed i s t r i b u t i o nd i s e q u i l i b r i u mo fp o w e rg r i d s t h e r e l a t i o n s h i pb e t w e e nn o d ed e g r e ea n da v e r a g eb e t w e e n n e s s h a st h ef e a t u r eo fp o w e r l a v e , a n dt h ep h a s e - t r a n s i t i o np o i n to ft o l e r a n c ep a r a m e t e ri nt h ec r i t i c a lb e h a v i o ro f c a s c a d i n gf a i l u r ei sd e r i v e dt h e o r e t i c a l l y t h ec o m p u t e dc r i t i c a lv a l u es h o w si t s c o n s i s t e n c yw i t ht h ep r a c t i c a ld y n a m i cs i m u l a t i o nr e s u l t si ne a s tc h i n ap o w e rg r i d w i t ht h eu t i l i z a t i o no fg l o b a le f f i c i e n c ym o d e l ，an e w e f f i c i e n c ye v a l u a t i o nm o d e l w i t he l e c t r i cd i s t a n c em a t r i xi sp r o p o s e d a n dt h ee f f i c i e n c yo fe a s ta n dc e n t r a lc h i n a p o w e rg r i d i se v a l u a t e d t h e n ，an e wv u l n e r a b i l i t yi n d e xc a l l e d w e i g h t e dl i n e b e t w e e n n e s si s p r o p o s e d t o i d e n t i f yt h e c r i t i c a ll i n e si nt h ep o w e rg r i d t h e s i m u l a t i o n so ni e e e3 9b u ss y s t e ma n dc e n t r a lc h i n ap o w e rg r i dp r o v et h ee f f i c i e n c y o ft h i sn e wv u l n e r a b i l i t yi n d e x i n p o w e rg r i d w i t h e x p o n e n t a i ld e g r e ed i s t r i b u t i o n ，t h em e t h o do ff a i l u r e 3 浙江大学博士学位论文 p r o p a g a t i o np r o b a b i l i t yo v e re n t i r en e t w o r ki sp r o p o s d t h em a c r o c o n t r o ls c h e m ei s p r o p o s e dt oa d j u s tt h et o p o l o g i c a lp a r a m e t e r si n o r d e rt oo p t i m i z et h en e t w o r k s t r u c t u r e ，w h i c hc o u l dr e d u c et h er i s ko fc o m p o n e n tf a i l u r ep r o p a g a t i o n ，e s p e c i a l l y t h er i s ko fc a s c a d i n gf a i l u r e a n ds c a l e - f r e en e t w o r kw i t hc o n s i s t e n ta v e r a g ed e g r e e ， n a m e l y u n d e rt h ee c o n o m i cc o n s t r a i n t o ff i x e dc o s t ，i ss t u d i e d t h ef a i l u r e p r o p a g a t i o np r o b a l i l i t ya n dc o n n e c t i v i t ya n a l y s i su n d e rs t a t i cr e m o v a lo fc o m p o n e n t s a r er e s p e c t i v e l yi n t r o d u c e d t h r o u g hf u n c t i o ng r a p h sa n dt h ec o m p u t a t i o no fg a a l g o r i t h m ，w ec a nd r a wac o n c l u s i o nt h a t ，d e c r e a s i n gt h ep o w e re x p o n e n to fs c a l e - f r e e n e t w o r ki nt h ei n t e r v a lo f ( 2 ，3 ，c a nn o to n l yd e c r e a s et h er i s ko ff a i l u r ep r o p a g a t i o n ， b u ta l s oi m p r o v et h et o l e r a n c ea n dc o n n e c t i v i t yo fs c a l e - f r e en e t w o r k s t h i ss t r u c t u r e o p t i m i z a t i o ns o l u t i o nc a np r o v i d ea no p t i m a la n dt h e o r e t i c a lr e f e r e n c ef o re n g i n e e r s a n dd e s i g n e r s t h er e s e a r c ho ne l e c t r i cp o w e rc o m m u n i c a t i o np h y s i c a lr o u t en e t w o r ks h o w st h a t ， z h e j i a n gp o w e r c o m m u n i c a t i o nn e t w o r ki s al o c a l - w o r l dn e t w o r ka n di t s s u b n e t w o r k sa r ea l ls c a l e f r e en e t w o r k s ，a n dt h e s en e t se n t i r e l yh a v et h ec h a r a c t e ro f s m a l l w o r l de f f e c t t h es t a t i ca n a l y s i si n d i c a t e st h a t ，p o w e rc o m m u n i c a t i o nn e t w o r k d i s p l a y st o p o l o g yr o b u s t n e s sa g a i n s tr a n d o mn o d ea n de d g ef a i l u r e s ，b u ti sf r a g i l et o i n t e n t i o n a la t t a c k so fh i g hd e g r e en o d e s u n d e rt h ec o m m u n i c a t i o np r i n c i p l eo f s h o r t e s tp a t hr o u t e ，t h e p r o t e c t i o n o fc o m p o n e n t sw i t hh i g h d e g r e e a n d h i g h b e t w e e n n e s si so fg r e a ti m p o r t a n c e k e y w o r d s ：c o m p l e xn e t w o r k s ，c o m p l e x i t y , t o p o l o g y , v u l n e r a b i l i t y , p o w e rg r i d ， e l e c t r i cp o w e rc o m m u n i c a t i o nn e t w o r k 4 浙江大学博二l ：学位论文 第1 章绪论 本章首先简要介绍了复杂系统与复杂性理论，对复杂网络理论的产生、发展和研究现 状进行了概述。对推动复杂网络理论发展的标志性成果，如随机网络理论、小世界网络和 无标度网络等，进行了较为详细的阐述。并对复杂性和复杂网络理论在电力网中的应用进 行了简单综述，最后介绍了本文所做的主要工作。 1 1 复杂系统与复杂性理论 随着科学技术的飞速发展和社会的进步，越来越多的复杂系统和复杂性现象 进入人们的视野，诸多物理系统、生物生态系统、经济系统、人工技术系统等看 似简单的非线性系统，却蕴涵着极为复杂的动力学行为。学者和决策者们采用传 统的理论、技术和方法处理这些问题时，遇到了许多困难。其中最重要的一点在 于，近代科学学科划分过细、条块分割，反而模糊了人们对事物总体性、全局性 的认识。面对这一现状，许多研究者开始探索从整体出发的研究方法，试图寻找 那条被打断的“沟通链条 【l j 。大量客观事实和科学论证表明：不能用还原论来 处理复杂系统，也不能用单元的个体性质来描述复杂系统整体的丰富行为【2 1 。正 是在这样的背景下，复杂性科学开始孕育、萌芽，并受到越来越多学者的关注。 如今，复杂性科学研究方兴未艾，被誉为“2 1 世纪的科学”。 一般说来，复杂性具有如下十个主要的特征或特性：非线性、多样性、多重 性、多变性、整体性、统计性、自相似性、非对称性( 对称破缺) 、不可逆性和 自组织临界性等1 3 j 。一般认为复杂性科学大致包括如下理论：现代系统科学中的 耗散结构理论、协同学；拓扑学中的突变论、复杂巨系统理论；非线性科学中的 混沌理论、分形理论、复杂适应系统理论等；以及通过计算机仿真研究而提出的 进化编程、遗传算法、人工生命、元胞自动机等。这些可以被视为复杂性科学的 内核。此外，复杂性的概念与思想在物理科学、生命科学、经济科学甚至人文社 会科学等其它领域的应用可视为复杂性科学的外沿。根据j o h nw a r f i e l d 的划分标 准，当前全球的复杂性研究可以大体分五大派：以s a n t af ei n s t i t u t e 为主要代表 的混沌动力学派，试图通过学科交叉、数学描述和计算机模拟来寻找复杂的演化 动力机制；以m i t 斯隆管理学院p e t e rs e n g e 等为代表的系统动力学派，其在管 理学界有较大影响力；以及结构学派、后现代主义学派和交叉学派1 4 1 。 对于复杂系统的定义，不同的学者有着不同的表述方式，还没有一个十分 精确的描述，目前最为普遍接受的定义是：所谓复杂系统是指由大量、不同而且 强非线性相互作用的组成单元构成的系统。复杂系统必须兼备多组成单元、单元 不同而且单元之间发生强相互作用这三个基本条件【5 培l 。“系统复杂性 是指“远 离平衡态的巨大耗散系统中由于组成单元之间局部的非线性相互作用而自发地 浙江人学博士学位论文 涌现出的系统总体性质、结构与动力学行为”。其中，“涌现”指的是由系统局部 的相互作用所产生的系统总体特征，不同于子系统( 或局部组成单元) 的原有性 质，是复杂动力系统内部的基本特征与属性。 复杂网络是对复杂系统的抽象和描述方式，它突出强调了系统结构的拓扑 特征，是复杂性科学研究中的一个重要组成部分。在过去的十年中，有关于网络 刻画和理解的研究工作非常活跃，网络不但是许多复杂系统所表现出的结构形 态，还可作为系统结构拓扑特性的模型。所以当我们想要对一个复杂系统建模的 时候，我们首先要处理的问题就是，怎样理解其网络的连接属性。一切事物都是 相互作用的表现，系统可以认为是处于相互作用的稳态。因此，事物作为系统， 其结构可以抽象为网络，各类构成单元和作用体可抽象为网络节点，各种相互作 用可抽象为节点之间的连接线或边。这样，随着数据库容量的持续增加以及计算 机存储和计算能力的增强，人们就可以运用图论和网络分析的理论、方法和工具 进行系统结构的拓扑特性研究，用系统的眼光来看待这些巨大的数据集合，寻找 这些复杂系统的演化和动力学背后的规律和模式。尽管系统具有明显的复杂性和 随机性，但是也会出现可以用数学和统计语言来描述的清晰的模式和规律。这个 思路已引起一些学科领域的重视，这一理论和方法在基础科学研究和实际工程应 用上也已经取得了巨大的进展【9 , 1 0 】。 1 2 复杂网络理论概述 1 2 1 图论及初期网络理论 现实世界中的大多数复杂系统可以用网络的形式来描述1 1 1 , 1 2 】，网络是一个大 量个体和个体间相互作用的系统。研究复杂网络首先要有一个描述网络的统一工 具，这个工具最初在数学上被称之为图( g r a p h ) 。任何一个典型的网络都是由数 目众多的节点与连接两个节点之间的边组成的，其中节点用来代表真实系统中不 同的个体，而边则用来表示个体之间的关系。 将网络作为一门科学，将实际网络进行图表示的方法则可以追溯到1 7 3 6 年， 瑞士数学家列昂哈德欧拉( l e o n h a r de u l e r ) 提出了著名的哥尼斯堡( k o n i g b e r g ) 七桥问题，他用抽象分析法和论证思想将这个问题转化为历史上第一个图论问 题，欧拉证明了此问题无解，进而将该问题进行了推广，并发表了图论( g r a p h t h e o r y ) 的首篇论文。 在最初的一百多年时间里，当时的科学家们认为真实系统各因素之间的关系 可以用一些规则的结构表示，因此图论的早期工作也主要集中在规则图上，涉及 一些可以利用简单规则网络来研究的问题，如数学上传统的“一笔画问题”、“邮 递员问题”等二维平面上的欧几旱德格网。但是由于规则网络在结构上的明显特 殊性，使得被研究图的规模不能很大，导致规则网所能描述系统的范围非常有限。 浙江大学博士学位论文 无论是初期的网络研究还是后来的复杂网络理论，在传统上都属于图论的 范畴。下面，首先介绍几个最为基本，但也最为重要的网络参数概念： 节点：是网络的最基本单元，有时亦称为顶点( v e r t e x ) 。物理学上习惯于 称之为s i t e ，信息和计算机科学一般称之为n o d e ，社会学上则形象地将其称为 社会舞台上的“演员”( a c t o r ) 1 2 j 。本文中用变量表示网络中的节点总数。 边：表示两个节点之间的直接作用或连接。物理学称其为b o n d ，信息科学 和计算机科学中一般称之为l i n k 、社会学上则将其称为t i e 1 2 】。本文中用变量m 表示网络中边的总数。 度：也称度数，表示与网络中某节点相连接的其他节点的数量，一般用变 量天表示，网络中节点的度分布情况一般用分布函数描述。度是单独节点属性 中简单而又重要的概念，是贯穿整个复杂网络理论研究的关键性基础概念之一， 复杂网络的拓扑结构性质以及复杂网络上的动力学行为等均紧密依赖于复杂网 络的度分布。 1 2 2 随机图理论与随机网络模型 对于小规模规则图的研究取得很大进展以后，图论和初期网络理论的研究开 始转向了统计和解析的分析。对于一些具有复杂结构和未知组织结构规则的网络 而言，其外在通常表现为随机性，由此逐渐开始有学者将随机性的因素引入到网 络研究中来。在研究者开始采取概率统计的探索方法以后，网络理论产生了第一 个突破性的研究飞跃，匈牙利数学家p a u le r d 6 s 和a l f r e dr 6 n y i 于1 9 5 9 年发表了 随机网络的演化一文，提出了随机图理论，构造了一种完全随机的网络模型 【1 3 】，并描述了通信网络和生命科学中的网络，后人将该模型用他们名字的首字 母命名为e r 随机网络模型，将该理论称为e r 随机图理论。 随机图和经典图之间最大的区别在于引入了随机的方法，使得图的空间变得 更大，其数学性质也发生了巨大的变化。e r d 6 s 和r 6 n y i 将随机图定义为：个带 有初始编号的节点共有m 条边相连接，这些连接边是从完全图的( 一1 ) 2 条 边中随机选取的。e r d 6 s 矛t r 6 n y i 认为边的出现为概率事件，网络中任意两个节点 之间的连接概率是独立的。因此有着个节点和m 条边的图共有c 麓忱种， 这就构成了一个概率空间，这其中每一种图出现的概率是相同的。 e r d 6 s 和r 6 n y i 在构造随机图时，首先是从多个孤立节点开始的，通过在这些 节点间随机布置连接进行系统模拟，这一构造过程被称为演化。在随机图的数学 演化模型中，连接概率p 定义为系统中已有边的数量占完全图中边数量的比例， 个独立节点之间的边数随着随机连接概率p 的增大而不断增加，直至p = 1 的 时候，网络演化为一个完全图。e r 随机图理论关注的问题之一就是在随机连接 概率为哪些值或增大到哪些值时，网络会出现哪种特定的拓扑结构，会产生哪些 浙江大学博j ：学位论文 特定的性质。例如，e r d 6 s 币1 3 r 6 n y i 经研究发现，当连接概率达到临界值p 一1 n 时， 随机图的拓扑结构产生了突变，网络从低密度的松散分散小集团的组合演化为高 密度的由单一巨集团占主导地位的系统，这就是随机图最为重要的相变性质。 e r d 6 s 年d r 6 n y i 在他们1 9 6 0 左右发表的一系列论文中给出了随机网中最大和 最小的度分布，b o l l o b ：i s 在1 9 8 1 年计算得出了所有度分布的形式。在网络规模足 够大的情况下，随机网络的度分布服从二项分布或大极限下的泊松( p o i s s o n ) 分布，其特征是网络中绝大多数节点的度数分布在均值附近。后来，学者的进一 步研究表明，最大度和最小度是确定和有限的；此外对于足够大的连接概率，几 乎所有随机图的最大度与平均度都在同一个数量级上。在此意义下，尽管网络中 的边是随机的，但大多数的节点却有着数量差不多的度数，由此可见典型的随机 网络是均质网络。 众多研究者发现随机网络的随机性十分符合真实网络中的某些连接特性，并 利用e r 随机网络模型对随机网络中的子图、连通性、临界相变、网络直径、图 谱等问题进行了广泛而深入的探讨。e r 随机网络模型和随机图理论大大拓展了 网络研究的范围，奠定了网络理论，尤其是大规模网络研究的基础。此后将近4 0 年里，e r 随机图理论一直是研究复杂网络的基本模型。 1 2 3 从随机网络理论到复杂网络 e r 随机图理论也引发了人们对现实世界中复杂网络的形成是否完全受随机 因素影响的讨论。规则网络是秩序的象征，随机网络是混乱的代表，但是实际网 络似乎不太可能都可以用这两种极端的网络类型进行描述。随着越来越多的人对 网络研究产生兴趣，许多科学家逐渐产生了疑问：绝大多数的真实的网络显然不 是规则耦合网，但他们是否都是随机的呢? 如此庞大复杂的网络系统是否存在某 种共性的组织原则呢? 如果存在这样的组织原则，那么这究竟是怎样的一套原则 呢l ? 这些原则是否可能从网络的拓扑结构上得到解答呢? 带着上述的种种疑问，各个不同学科领域中都有越来越多的学者加入到了复 杂网络研究的队伍中来。起初，他们只对本领域中可以进行复杂网络抽象的系统 进行了研究，也取得了很多第一手的数据资料，但并没有解答以上的种种疑问。 近些年来，两个关键因素掀起了人们对复杂网络研究的又一次新高潮，很多突破 性成果也应运而生。 一是，信息和计算机技术的迅猛发展。随着全球范围内信息化进程的不断加 快，计算机的存储能力和处理速度持续增强，数据库容量的不断增大，这就为人 们研究大型复杂网络提供了坚实有力的技术保证。过去，即便是面对仅仅几十个 或者上百个节点的网络，研究者也对大量繁杂的统计和矩阵计算而伤透脑筋；如 今计算机的广泛普及和高性能使得研究者们已经完全可以对很多以前无法统计 4 浙江大学博小学位论文 的超大型网络系统进行细致而深入的计算和分析。例如，上世纪九十年代末引起 人们广泛研究热情的万维网，在1 9 9 9 年底就已经有了近1 0 亿个节点。1 9 9 9 年 b a r a b 矗s i 和b e r t 研究的是包含了3 2 6 万个网页的万维网子网；k u m a r 等人用a l e x a 公司的机器人爬行了有4 0 0 0 万个网页的网络；到了2 0 0 0 年，b r o d e 等人用了两台 1 9 9 9 a l t a v i s t a 机器人在有着2 亿个网页的网络上进行了虚拟行走。 二是，关于复杂网络的基础理论不断得到发展和完善，学科之间的互通与交 融不断深化。首先，人们为了更进一步弄清楚系统的整体行为，对已有的图论和 随机网络理论等进行了深入的探索，通过对已有理论的补充、完善、推广和应用， 不断有新的成果涌现，为复杂网络的研究奠定了坚实的理论基础。其次，许多相 关学科飞速发展，在各自领域内获了大量有价值的统计数据，也得到了许多现实 世界网络的拓扑性质和相关成果，为复杂网络的研究提供了丰富翔实的样本资 料。再次，随着学术界对学科壁垒的打破和学科融合的不断推进，越来越多有着 本学科扎实功底的研究者开始都进入到了复杂网络研究的领域中来，他们掌握着 多种技术手段和形式多样的研究手法，不断用各种各样的新方法进行探索和尝 试，使得复杂网络的研究视野变得越来越宽广，为复杂网络的研究提供了多样化 的研究方法和技术平台。 在过去的十年时间里，网络科研工作者对包括自然界和人工技术网络在内的 许多实际大型网络进行了一系列的统计研究。分析结果表明，现实世界中的复杂 网络绝大多数并不是简单的完全随机网络，即这些网络不是均质的，而是符合异 质网络特性的。他们认为，复杂网络的形成必定受到一定规则的支配，我们必须 探索研究它们的组织原则，因此研究者开始进一步从网络所呈现出来的拓扑结构 中挖掘网络形成的内在机理。 上世纪末，正是在这样的大技术背景下，随着人们对大规模网络的关注和不 断探索，两个标志性成果的问世带来了复杂网络理论的又一次历史性飞跃。1 9 9 8 年6 月，美国c o m e l l 大学的w a t t s 矛1 ：1 s t r o g a t z 提出了小世界模型1 4 j ，构造出一种介 于规则网络和随机网络之间的网络一一小世界网络。1 9 9 9 年1 0 月，美国n o t r e d a m e 大学的b a r a b ：i s i 和a l b e r t 提出了无标度网络模型1 5 j ，首次构造了具有幂律度 分布的网络。小世界网络和无标度网络两个网络模型和理论的提出是一次划时代 的进步，标志着复杂网络的研究进入了一个全新的发展阶段。关于小世界网络和 无标度网络，本章将在其后两节中还会对其进行更为详细和深入的介绍。 自1 9 9 8 年以来，自然、科学、物理评论快讯等权威杂志发表了多篇 复杂网络领域的相关文章，研究者们提出了一大批网络演化模型以便探讨小世界 网和无标度网拓扑结构的演化形成机制，其中很多模型都同时包括了“完全规则 演化”的部分和“完全随机演化”的部分，也都非常重视运用平均场近似、重整 化群、蒙特卡罗法模拟、主方程法等统计物理中的方法进行解析推导。复杂网络 浙江大学博tj 学位论文 和复杂性的研究进入了高速发展的新时期【1 1 , 1 2 l 。 1 2 4 复杂网络分类 复杂网络无处不在，复杂网络研究的内容也非常丰富，可以说自然界和整个 人类社会都被包围在各种类型的复杂网络之中。对复杂网络的分类也因为考虑问 题角度的不同而有多种分类方式： ( 1 ) 从网络边是否有权值的角度，可以将复杂网络分为无权网络和有权网 络。例如：对于学者合作网，节点为学术论文的作者，边的权重则可以表示两个 合作者合作完成论文的数量；对于交通网络，节点间连线的权重可以表示两个机 场、车站等节点之间的客流量。 ( 2 ) 从节点间连接边是否具有方向性的角度，可以将复杂网络分为有向网 络和无向网络。例如：人与人之间的电话网和电子邮件网就是典型的有向网，对 于每一次通话和每一个邮件的发送而言，信息都是单方向传递的；此外，公路网 中的单行道也是非常直观的有向边。 ( 3 ) 美国密歇根大学安娜堡分校的m e j n e w m a n 是研究复杂网络的美国 著名科学家，他根据网络功能，将现实网络归纳为四个类型：社会网络、信息网 络、技术网络和生物网络1 1 2 j 。 ( 4 ) 国内有学者从生成方式角度，将网络分为随机性网络、确定性网络和 混合网络1 1 6 】，其中确定性网络是指生成方式确定、拓扑特性易于精确求解的网 络，真实世界的网络基本都是介于随机性网络和确定性网络之间的混合网络。 ( 5 ) 从网络节点度分布的角度，a m a r a ll a n 等人提出现实世界的网络可 分为无标度( s c a l ef r e e ) 网、广标度( b r o a d s c a l e ) 网和单标度( s i n g l e s c a l e ) 网三种【1 7 1 ，也有学者提出可将网络分为指数网络和无标度网络两种，但是这两 种分类方式在本质上是统一的。 目前，复杂网络已经成为科学界研究的前沿和热点，其研究者来自数学、物 理学、化学、生命科学、工程科学、材料科学、计算机科学、社会学、管理学以 及经济学等多个不同领域。近年来复杂网络研究工作的迅猛发展表明：非线性、 连接性以及复杂性问题的研究已经使人类对自然界的认识产生了新的飞跃，并已 取得了重要的进展。有学者预言2 1 世纪是复杂性的世纪，复杂性研究将会展示 更为美好的应用前景，它将是新世纪科学研究的最前沿的课题之一【9 - 1 2 1 。 1 3 小世界特性与小世界网络 1 3 1 从六度分离到小世界效应 关于小世界特性研究最早的试验是由美国社会心理学家、哈佛大学的s t a n l e y m i l g r a m 完成的，他断定在美国大多数人之间相互认识可以通过“朋友的朋友” 进行联系。试验要求内靠拉斯加州的3 0 0 多名参与者把一封信寄给某市一个他们 6 浙江火学博士学位论文 熟悉的人，条件是使得这封信最终能够传递到某个指定的“目标个体”波士 顿的一位股票经纪人，以此来分析熟人网络中路径长度的分布问题。于是一个发 信人链条就此形成，链上的每个成员都力图把这封信寄给他们的朋友、家庭成员、 商业同事或偶尔认识的人，以便尽快到达目标人。m i l g r a m 请求参与者在转寄信 件的同时也寄给他一张明信片，以跟踪每一条不同的路径。试验中大约有四分之 一的信寄达了目标个体，共6 0 个邮件链条最终到达了目标人。试验的结果令很 多人十分惊讶，因为每封信平均只传递过约六人之手，也就是说只经过六次连接 就可以完成任意两个个体之间的信息传递。这一试验就是m i l g r a m 在今日心理 学杂志上提出的著名的“六度分离( s i xd e g r e e so f s e p a r a t i o n ) 概念的起源。 当时虽然没有提出“小世界”这一术语，而且时至今日也没有关于六度分离 的严格理论证明，但这项试验却已经直接揭示出了“小世界”效应的存在。其实， 在m i l g r a m 实验之前，匈牙利科学家f r i g y e sk a r i n t h y 就曾发表短篇文章对“小 世界”效应提出猜测，p o o l 和k o c h e n 的数学论文也对此做出过更为严密的猜测， 但m i l g r a m “六度分离”试验却是历史上首次从试验角度揭示了“小世界”现象。 六度分离试验和由此带来的小世界特性听上去十分神奇，因为按照每一个人 认识5 0 0 个人计算，这5 0 0 人中每一个又认识5 0 0 个人，这样通过一层的中间人 关联，我们可以认识2 5 万人；通过两层中间人，可以认识1 2 5 亿人；到了第三 层就已经可以认识几乎全世界的全部的6 0 多亿人了。 在m i l g r a m 试验之后，有人使用了其他的替代方法去检验“六度分离”的假 说。其中最著名的一个是所谓“凯文培根( k e w i nb a c o n ) 游戏”。这个游戏的 主角是美国好莱坞的电影演员k e v i nb a c o n ，游戏的目的是把b a c o n 和另外任意 一个演员联系起来。b a c o n 还在游戏中为每个演员定义了一个b a c o n 数：将曾与 他同剧组表演的演员的b a c o n 数标为1 ，和他的同剧组演员曾经同剧组表演的演 员的b a c o n 数标为2 ，如此类推，也就是说b a c o n 数描述了这个演员合作网中任 意一个演员到b a c o n 的最短距离。b a c o n 经过统计发现：当b a c o n 数为4 时，几 乎所有美国演艺圈的演员全部都被包含了进来。这个研究结论让人们感叹“世界 真小畦! ”，小世界效应也由此得名。 其后，弗吉尼亚大学计算机系的科学家建立起了一个完整的电影演职员表数 据库( h t t p ：w w w c s v i r g i n i a e d u o r a c l e ) ，放在网上供人们随意查询，该网站的数 据库里目前共有近6 0 万个演员的信息和近3 0 万部电影的信息。该数据库表明： 电影界的演员合作网中，b a c o n 数最大仅为8 ，绝大多数的b a c o n 数不超过4 ， 平均b a c o n 数仅为2 9 9 4 。可见，电影界的演员合作网的确是一个小世界网络， 通常只须通过几个中间环节，就可以把任意两个演员连接在一起。 1 9 9 8 年6 月，c o m e l l 大学理论与应用力学系的博士生w a t t s 和其导师s t r o g a t z 在自然杂志上发表了题为“小世界网络的群体动力学行为的文章，揭 7 浙江大学博j j 学位论文 示了演员合作网、电力网和线虫神经网中的小世界特性，首次建立了小世界网络 模型1 4 】，这项开创性的工作首先掀起了近期研究复杂网络的新热潮。 2 0 0 3 年，已经来到哥伦比亚大学社会学系的的w a t t s 及其领导的研究小组又 在科学杂志上发表了题为六封电邮环游地球的研究报告，报告中描述了 他们利用网络通信这一现代化的技术手段对六度分离和小世界现象的又一次尝 试：全球约有六万多名志愿者通过实验网站( s m a l l w o r l d c o l u m b i a e d u ) 参与了 这次利用电子邮件进行通信的网络试验，世界各地的参与者利用电子邮件这一更 为快捷可靠的媒介互相联系。试验的结果表明，任意两人之间的通信联络也只要 通过平均六封电子邮件。可以说，这个试验用先进的技术手段在全世界范围内又 一次检验了上述韵六度分离假说和小世界效应。 1 3 2 小世界网络模型 小世界网络所描述的小世界现象广泛存在于自然界和人类社会，万维网、 i n t e r n e t 网、演员合作网、科学家合作网、电力网、地铁网、世界航空网、新陈 代谢网等都具有小世界特性，可以说小世界特性是整个世界系统组织的基本原则 之_ _ 1 1 , 1 2 , 2 2 】，具有十分重要且深远的研究意义。 w a t t s 和s t r o g a t z 在“小世界 网络的群体动力学行为一文中首次给出了 一个小世界模型的构造方法【1 4 j 。他们所研究的示例网络的总节点数= 2 0 ，每 个节点的平均度数都为4 。假设每一条边重新连接的概率均为p ，即以概率p 断 开随机选定的某条边的一个端点，并重新连接，重新连接的另一个端点从网络中 的其他节点中随机选择，如果所选的新节点已经有边与此节点相连，则再随机选 择其他节点来连接。显然，p = 0 的初始状态下每个节点与其最临近的4 个节点 各有一条边相连，代表一个环形的规则网络。随着连接概率p 的增加，节点之间 的远距离连接逐渐增多，直到p = 1 的时候，网络已经演化为一个完全随机的网 络。w a t t s 和s t r o g a t z 提出，小世界网络是一种介于规则网络与随机网络之间的 网络模型，通过上述随机重新连线的过程，可以清楚表明小世界网络与其他两者 的关系，这个随机重新连线的过程如图1 - 1 所示。我们也可以这样认为：规则网 络和随机网络分别是该小世界网络在p 分别为0 和1 时的特例。 规则网络 小世界网络随机网络 oo 恭 p = o 1 瓯砸鼐广斗萨1 图1 1w s 小世界网络模型示意图 f i g 1 - 1i l l u s t r a t i o no fw s s m a l l - w o r l dn e t w o r km o d e l 浙江大学博1 0 学位论义 w a t t s 邱s t r o g a t z 提出的小世界模型构造方法十分形象，后被称为w s 小世 界模型。如果将该模型的构造方式进行数学推广，我们就可以将w s 小世界模型 的构造算法描述为：( 1 ) 基本网络结构。从规则图开始，考虑一个节点总数为 的近邻均匀环网，即节点间形成一个耦合环，每个节点都与它左右最近相邻的各 k 2 个节点相连( k