（理论物理专业论文）复杂网络的拓扑结构、雪崩特征及动力学.pdf

硕士学住论文 m a s t e r st h e s i s 摘要 本文综述和介绍了有关复杂网络基本概念和美国航空网络( a n a ) 的实证研究、 几个重要网络模型和基于生物网络特点而建立的偏好复制生长网络( g n p c l 以及复 杂网络上的自组织临界性现象和推广小世界网络上的雪崩动力学特征研究，本文工 作主要分为三个部分。 第一部分介绍了复杂网络的基本拓扑概念和性质，在此基础上，本文研究了 现实中的美国航空网络( a n a ) ，通过对这个有方向有周期带权重网络的研究， 发现a n a 具有小世界特点：较大的平均聚集系数g f o 6 1 8 1 和较小的平均最短距 离三( 2 4 ) ，但是其又具有小世界网络没有的性质一一等级性( g ( ) o ( ) ，而且同 大多数的生物技术网络一样，具有非协调性一= 0 3 7 ) 。通过和其他航空网络比 较，如世界航空网( a n w ) ，中国航空网( a n c ) 等，可以得到航空网络都具有小世 界性质。 第二部分介绍了基于现实网络性质和现象上的几个重要模型，如e r d j s r e 礼彬随机网络、w a t t s s t r o g a t z 小世界网络、b r n 6 n 崩一a f 6 e r t 无标度网络等，这 些模型的提出各有其试验背景，而目前为止，不同于社会和技术网络，生物网络有 一个很重要的特点就是不论网络的结构大小，其直径都在一个很小的范围内变化， 基于生物网络的这个特点，本文构造了一种偏好复制生长网络f g n p c ) ，该模型较 好地全面展现了生物网络的连接度无标度性( p ( ) “k 一“) ，小世界性质，等级性质 和不变的直径等特点。 最后，对于自组织临界性( 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 的 经典模型做了介绍，并简要介绍目前在复杂网络上的进行的自组织临界性研究，在 此基础之上，本文探讨了推广小世界网络上( g s ) 的沙堆模型，发现随着推，。 小世界网络上连线( 西) 的增加，也即其平均连接度的减小，其时间和空间的雪崩分 形维数都会增加，最后逐渐达到一个最大值( 口。，) ，而且时间的分形维数总是要大 于空间的分形维数，在推广小世界网络上进行的雪崩动力学研究的结论性质和在其 上进行扩散聚集模型( d l a ) 的性质类似，这个都是源于网络的拓扑结构导致。 关键词：网络，拓扑结构，小世界，无标度，偏好复制，自组织临界性 硕士学位论定 m a s t e r st h 嚣s l s a b s 七r a c t i h i sd i s s e r t a t i o ni 8c o n c e r n e d d t h 七h eb 黼i cc o n c e p to fc o m p l e xn e t w o r ka r l d 墟e8 艇yo f 壕e 蹿o l o g i e 越p r o p e 砖妇馥e 妇p o 砖n e 蠡w 。矗a 越e r i e 勰( a 辩a ) ； w i t h 矗v ei m p o r t a 血tc o m p l e xn e t w o r km o d e l 8a n dw ep r o p o s eah l o d e lg r o w i n gb y p r e 熙r e n t i a lc o p y i n gm e c h a 1 1 i s mb 躺e do n 址l eo b s e r v a t i o no fb i o l o g i e a ln e t w o r k w 扎h 强es e l 奴 r g 粕i z ee r 溉c ( s 0 e ) i nn 积u r ea n d 疆es 0 c 遮疆eg 懿嚣艇i z e ds m 赫b w 疆l d n e t w o r k s ( s w n ) s o ，t h i 8t h e s i sc a nb ed i v i d e di n t ot h r e ep a r t 8 戢l e 最r s tp 黼ti n 七r o d u c es o m eb a 8 i e n c e p t s 强dp 帅p e r t i e 8o fc 。m p l 懿n 威w o r k ， a f t e rt h a t ，w e8 t u d yt h et o p o l o g i e 艇p r o p e r t i e so fa n aa sa ne x a m p l e ，w 圭娃c hi s 鑫 w e i g h t e dd i r e c t e dn e t w o r k t h ea i r p o r tn e t w o r ko fa m e r i c a ni sas i n 缸1w o r l dn e t w o r k ： i th 黯s1 8 r g ea v e 酶g ee l u s t e r i n gc o e 擐c i e n tf o 墨1 8 ) a 丑ds m 蠢l 姗a g ep a t hl e n 缈h ( 2 ，4 ) ， d i 舶r e n tf r o mm o s to ft h es w n ，i ti sah i e r a r c h i c a ln e t w o r k 咿( 惫) 。c 奄啪) ) ，i t s d i s 躺s o r t a t i v ec o e 伍c i e n tri s 一03 7 ，j u s t1 i k em 0 8 to ft h eb i 0 1 0 9 i c a la n dt e c h n i c a l n 醴姻r b ，e o m p 8 i 珏gw l t ho t h e ra i p o 砖珏e t 蚴f ；【s ，s u c ha s 蠢r p o 赡致e t w o r ko fw w w ( a n w ) ，c h i n a ( a n c ) ，i n d i a ( a n i ) ，、楷c o n c l u d et h a tt h ea i r p o nn e 钾r k 8 壮ea i i s m a l l 、阳r l dn e t w o r l ( s 眦dm o r ec o n 8 t r 8 i n e db yt h eg e q 匿r a p h i c a lc o n d i t i o n 举h es e e 。珏dp a r ti 盛r o d 毽e es o m ei m p o r t 8 n 毫n e t w o 矗m o d e i s ，a 8 嚣斑。s - 矬y 量 g r a p h ，、 ，a t t 8 “s t r a g a t z 玎嚏o d e l ，b a r a b a s i - a l b e r tm o d e l t h e s em o d e l sa r ea uw e l l 丘t s o m e 甜e a s o b 8 e r v a t i o n s of a r ，出疑r e n tf r o ms o c i a la n dt e 出n i c a ln e t w o r k ，b i 0 1 0 9 i c a l n e t w o l ki sp 8 y i n gm l l c hm o r ea t t e n t i o nt h a 拈o t h e r s ，f o rt h e r ea r es om u c ha b u n 矗a n c e p h e n o m e n ai nt h eb i o l o g i c a ln e t w o r k s ，ep r o p o s eag r o w i n gn e t w o r kb y 王) r e f e r e n t i a lc o p y i n g g n p e ) 掰o d e l ，遣e 融揩p d u c em o s t 搬eb 主0 1 0 9 y 必e n o l 丑躐a ，s u c h a s8 c a l e f r e ed e g r e ed i s t r i b u t i o n ( ( p ( 角) 。( 奄) ) ，t h ep r o p e r t yo fs m 越1w o r l d8 以d h i e r a r c h i c a l p i 羟穰y ，妇建r o 鑫u c e 氇e n e e 辩蠢f - o r g a 芏l i z ee f 激e 越，t w os o g 瑶o d 8 1 88 珏d 8 0 i n es o cw o r kd o n ei n 恤ec o m p l e xn e 七w o 嫩8 w bs t u d yt h es a 飘d p l l ei nt h eg e n e r a l - i z e d8 m a uw o r l dn e t w o r k ( g s w n ) a n dg e ti n t e r e 8 t i n gr e s u l ta sd e c r e a s i n gt h es h o r t e 珏ti nt h eg s w nw 量l i e hm e a n ss 搬采l e ra e r 8 9 ed e g r e e ，t 量l ed i m e l l s i o 珏o fa v 氇1 8 珏c h e i n8 p a t i a la n dt i m ew i l li n c r e a s e ，m o r ei m p o r t a n t l y t h ed i m e 8 i o ni nt i m ea l w a y s l a r g e r 妇a n 妇越t h et i m e t h e 8 er e s u l t sa r em 。r e8 n 拽l o g yt ot l l ed i m l 8 i o n 一1 i m i t e d 8 9 9 r e g a t i 。n ( d l a ) i nt h eg e n e r a l i z e ds m a 硅w o r i dn e t w o r k 慧翥。 k e y w o r d s ：n 蕊w o 矗，t o p o 圭o g i e 骥s t r u e t 砒e ，s m a 王王_ w 。r l d ，s c 争静e e ，p r e f e e n t i 畦 p y i n 岛s e i f - o r 9 8 n i z a t i o nc r i t i c a l 儿l 黧。 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取 得的成果。除文中已经注明引用的内容外，本论文不含任何其他个人或集体已经发表或撰 写过的作品或成果。对本文的研究做出重要贡献的个人和集体，均己在文中以明确方式标 明。本声明的法律结果由本人承担。 论文作者签名：三一落 日期：a m g 年，月必日 学位论文版权使用授权说明 本人完全了解华中师范大学关于收集、保存、使用学位论文的规定，即：学校有权保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授 权华中师范大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用 影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密论文在解密后遵守此规定。 论文作者签名：三一甚 日期：砷6 年f 月磨日 本人已经认真阅读。c a l i s 高校学位论文全文数据库发布章程”，同意将本人的学位 论文提交“c a l i s 高校学位论文全文数据库”中全文发布，并可按“章程”中规定享受相 论文作者签名：五荔 日期：) 7 幽：r 月，窖日 导师签名： 日期：捌 淼怒。 第一章引言 复杂性科学怒用以研究复杂系统和复杂性的一f 1 方兴米艾的交叉学科，复杂性 辩学赣究熬复杂系统涉及静范蓉缀广，包括自然、工程、生物、经济、管理、教治 与社会等各个方面；它探索的复杂现躲从一个细胞呈现出来的生命现象，到股票市 场的涨落、城市交通的管蠼、皂然灾鹰浆预测，乃至社会的兴衰等薅，曩蘸，荧于 复杂健的研究受潮了世界备国科学家们的广泛关注。1 9 9 9 年，美国科学杂志出 版了一期以“复杂系统”为主题的专辑，这个专辑分别就化学、生物举、神经学、动 兹学、蠡然逮瑷、气候学、经济学等学攀 镁域中豹复杂魏骚突进行了擐遂。出予冬 学科对复杂性的认识和理解都不一样，所以该专辑避开术语上的争论，采用了“复 杂系统”这个名词。概括起来，复杂系统都有些共同的特点，就是在变化无常的 活动鬻爱，呈瑰爨菜秘挺摸不定静彀海，其孛浚铯、溪瑗、鑫缓织、鑫适应、鑫穗 似被认为是复杂系统的共劂特征。 涌观机制是复杂系统出现各种激动人心现象、图案和模式的共间表征，这里既 包括灾难式嚣突蕊，也包掇氆额式静灞现。涌糯静数学、物理学、生物学帮瓠会学 表征及其临界点将成为认识复杂系统的重要标虑。复杂系统中宏观结构的涌现往往 孕育予其叁组织的枧制，这在生物学稠社会学中均不乏铡诞。自组织还是复杂系统 对环境产生自适应性的一个重要的调熬机制。裔适应性裳征了复杂系统在系统联次 上的自身调控能力。复杂系统与各层次子系统之间往往具肖一定的囱相似性，可以 糕用分形寒搬戬攒述。复杂系绕磁究狰破了牛灏默来一壹绞治秘学瓣线牲论、楚经 论和还原论的憨维方式。 在复杂系统研究中，j 鹾年来尤其是关于复杂网络的研究正处于蓬勃发展的阶 段。这拿歪是本文豹磺究藏强。 自然界中存猩的大量复杂系统都可以通过形形色色的网络加以描述。一个麒型 的网络是由许多节点与连接两个节点之间的一黧边组成的，其中节点用来代袭真实 系统中不弼兹令钵，雨边囊g 霜亲表示个俸闽豹关系，往往是两个节点之翔翼鸯楚释 特定的关系则连一条边，殷之则不连边，有边相连的两个节点在网络中被看作是相 邻的。例如，神缀系统可以看作大量章孛经细胞通过神经纤维相互连接形成的喇络； 计算梳网络可懿褥作是自主工作酌计簿机通过通信介质如光缆、双绞线、同辅电缆 等相曩连接形成的网络；类似的还有电力网络、社会关系网络、交通网络等等。 数学家和物理学家在考虑踺终的孵候，往缓哭关心节点之阗有没考边超逡，至 硕士学住论文 m a s t e r st h e s i s 于节点到底在什么位置，边是长还是短，是弯曲还是平直，有没有相交等等都是他 们不在意的。在这里，我们把网络不依赖于节点的具体位置和边的具体形态就能表 现出来的性质叫做网络的拓扑性质，相应的结构叫做网络的拓扑结构。那么，什么 样的拓扑结构比较适合用来描述真实的系统呢? 两百多年来，对这个问题的研究经 历了三个阶段。在最初的一百多年里，科学家们认为真实系统各因素之间的关系可 以用一些规则的结构表示，例如二维平面上的欧几里德格网，又或者最近邻环网。 到了二十世纪五十年代末，数学家们想出了一种新的构造网络的方法，在这种方法 下，两个节点之间连边与否不再是确定的事情，而是根据一个概率决定。数学家把 这样生成的网络叫做随机网络，它在接下来的四十年里一直被很多科学家认为是描 述真实系统最适宜的网络。直到最近几年，由于计算机数据处理和运算能力的飞速 发展，科学家们发现大量的真实网络既不是规则网络，也不是随机网络，而是具 有与前两者皆不同的统计特征的网络。这样的一些网络被科学家们叫做复杂网络 ( c o m p l “n e t w o r k s ) ，对于它们的研究标志着第三阶段的到来。 遗憾的是，就目前而言，科学家们还没有给出复杂网络精确严格的定义，从这 几年的研究来看，之所以称其为复杂网络，大致上包含以下几层意思：首先，它是 大量真实复杂系统的拓扑抽象：其次，它至少在感觉上比规则网络和随机网络复 杂，因为我们可以很容易地生成规则和随机网络，但就目前而言，还没有一种简单 方法能够生成完全符合真实统计特征的网络；最后，由于复杂网络是大量复杂系统 得以存在的拓扑基础，因此对它的研究被认为有助于理解“复杂系统之所以复杂”这 一至关重要的问题。 关于网络最经典的一篇是a l b e r t 和b o r n k j i 在2 0 0 2 年给出的类似于教科书的综 述 1 】，在这几年被应用了近千次，而后n e w m a n 2 0 0 3 年用独特的视角和所附的四百 多篇的参考文献 2 】的综述吸引了大量的读者；w a n g 和c h e n 在i e e e 期刊2 0 0 3 上的一 篇短综述3 适合作为网络知识的入门读物，而a m a r 8 1lan 和o t t i n ojm 的2 0 0 4 一 篇 4 1 和、a n g 和c h e n 在i e e e 期刊上的短综述 3 】类似，但是其涉及范围更为广阔一 些，还囊括非线性动力学和统计物理，同年，b o r 0 6 口或al 的l i n k e d ：h o we v - e r y t h i n gi sc o n n e c t e dt oe v e r y i n ge l s ea n dw h a ti tm e a n 8f o rb u s i n e 8 8 ， s c i e n c e ，a n d e v e r y d a yl i f e 一书f 5 1 把网络的发展历史用翔实的实例贯穿，介绍非常生动形象， 而s md o r o g o v t s e v 和j f f m e n d e s 于2 0 0 3 年的e v 0 1 u t i o no fn e t w o r k s ：f r o mb i - 0 1 0 9 i c 甜n e t st ot h ei n t e r n e ta n dw w w 一书【6 】则是其继2 0 0 2 给出的十分详尽的综 述 7 的扩展版本，他们又于2 0 0 4 年写了一篇类似于科普的文章 8 】，用通俗易懂的语 言描述了网络的基本性质和概念，不过若是因为此而对网络产生了浓厚的兴趣， 2 硕士学位论文 m a s t e r st h e s l s 可以按照这篇文章后面的详尽的最新综述和最新书的指引而对当前研究进展有一 个了然的掌握，e v a n sts 的2 0 0 4 年的综述f 9 1 也包含了最新的研究进展；吴金闪和 狄增如2 0 0 4 年用中文写了第一篇关于网络的国内综述1 0 1 ，而周涛、傅忠谦等人对 复杂网络上的动力学传播的2 0 0 5 年的综述 1 1 】以及n a o k im a 8 u d a 和n o r i ok o l l i l o 的 疾病传播论述 1 2 】使得可以更快进入这方面的前沿；若是想快速全瞰网络研究的 思考前沿，可阻参考2 0 0 4 的一期欧洲物理杂志1 3 1 ，这里汇聚了关注各个网络方向 的前沿者的思考问题，同年的由e b e n - n a i m ，h n a u e n f e l d e r 和z t o r o c z l 【a i 主编 的c o m p l e xn e t w o r k s 一书【1 4 l 则是汇集了各个前沿者的最新工作；ld af c o s t a 及 其和作者在2 0 0 5 年【1 5 ，1 6 l 从数学的语言出发，用离散数学特别是数学形态学描述 网络的概念及其发展历史，更是开辟了新的视野，最近阻b n r 0 6 n 或al 为带头人 在n a t u r e 和s c i e n c e 【1 7 ，1 8 】上面发表的关于社会科学网络理论也许又是会掀起网络 研究的热潮，而基于生物为基础的网络研究更是广泛和热门1 9 】，最新最近的篇 综述是由s b o c c a l e t t i 等完成f 2 0 1 。 基于复杂网络研究的多样性，本文从三个不同的角度对复杂网络进行了分析。 第一章为前言，简要介绍关于复杂性科学的主要概念和内容。第二章，作者将介绍 网络性质和些主要研究方法。在第三章中，我们以美国航空网络为例，研究现实 中网络的各种拓扑性质，包括带权重和不带权重的连接度分布、聚集系数、平均最 短路径、协调系数、等级性质等，发现美国航空网络是一个有等级的非协调的小世 界网络。同时，作者还和其他国家或者地区的航空网络的性质作了比较，发现美国 航空网络和世界航空网络、中国航空网络、印度航空网络的性质类似，都是非协调 的小世界网络。大量的研究表明，技术生物网络都是非协调性的，而社会网络都是 协调性的，这个还是目前有待探讨的话题，但是生物网络却具有非协调性。根据现 实网络的各种特点，些前言工作者提出了几个有影响力的模型，这些模型及其相 关性质将在的四章中介绍。在第五章中，作者以生物网络中的各种现象为依据，构 造了一个偏好复制模型。此模型可咀较好的得到生物网络中的无标度的连接度、较 大的聚集系数较小的平均最短距离，等级结构以及不变的直径的特点，而目前多数 生物网络模型都还不能完全同时得到这些性质。以上的网络研究最特别的是会出现 幂率性质，即，无标度的特征。目前对幂率性质的解释有许多，自组织临界性就是 其中之一。关于白组织临界性的诞生、定义及发展将在第六章中简要介绍。那么这 些网络的拓扑结构和自组织临界性有什么关系和内在联系呢? 作者将在第七章中研 究基于b t w 模型基础上的一种推广小世界网络上的雪崩动力学。第八章为工作展 望。 3 参考文献 1 r a l b e r ta da l b 口r 0 6 0 豇s t a t i 8 t i c 越m e c h a i c so fc o m p l e xn e t w o r k s 盼 v i e w so fm o d e r p h y s i c s ，7 4 ( 4 7 ) ，2 0 0 2 2 】m e j n e w m a s t r u c t u r ea n df u n c t i o n o fc o m p l e xn e t w o r k s s i a mr e _ v i e w ，4 5 ( 2 ) ：1 6 7 _ 2 5 6 ，2 0 0 3 【3 h n gx f ，c h e ngr i e e ec i r c u i t sa n ds y s t e m sm a g a z i n e ，2 0 0 3 ，3 ：6 4 a m a r a ll an 和0 t t i n ojme u r p h y s j b3 8 ，1 4 7 _ 1 6 2 ( 2 0 0 4 ) 【5 b o r o 乩氯all i n k e d ：h o we v e r y t h i n gi sc o n n e c t e dt oe v e r y i n ge l s ea n d w h a ti t m e a n sf o r b u 8 i n e s s ，s c i e c e ，a n de v e r y d a yl i f e2 0 0 3n e wy o r k ( p e n g u i ng r o u p p r e 8 s 1 【6 ls n d o r o g o v t s e v ， j f f m e n d e s e v o l u t i o no fn e 七v r k s ：f r o mb i o l o g i c a ln e t s t ot h ei n t e r n e ta n dw w w ( o x f o r du n i v e r s i t yp r e s s ，0 x f o r d ，2 0 0 3 ) 【7 】d o r o g d v t 8 e vsn ，m e n d e sjf f a d v a n c e 8i np 1 1 y s i c s ，2 0 0 2 ，5 l ：1 0 7 9 【8 】d o r o g a v t s e vsn ，m e n d e s jff a r x i v ：c o n d m a t 0 4 0 4 5 9 3 f 9 】e v a m sts a r x i v ：c o n d - m a t 0 4 0 5 1 2 3 1 0 】吴金闪，狄增如从统计物理学看复杂网络研究物理学进展2 0 0 4 2 411 8 2 6 【1 1 1 周涛，傅忠谦，牛永伟，王达，曾燕，汪秉宏，周佩玲。复杂网络上传播动 力学研究综述自然科学进展2 0 0 51 555 1 3 _ 5 1 8 【1 2 】n a o k im a 8 u d a la n dn o r 主0k o n n 0 2a r x i v ：c o n d m a t 0 5 0 4 3 2 9 1 3 】e u r p h y s j b3 8 ，1 4 3 一1 4 5 ( 2 0 0 4 ) 1 4 je b e n n a i m ，h e y a u e n f e l d e r ，z 7 r o r o c z k a ic o m p l e xn e t w o r k sl e c t u r en o t e s i np h y s i c s ，s p r i n g e r - v e r l a g ，2 0 0 4 1 5 】l d af c o s t afa r o d r i g u e sg i y a v i e s op r v i l l a sb o a sa r x i v ：c o n d m a t 0 5 0 5 1 8 5 ： 4 硕士学位论文 m a s t e r st h e s i s 1 6 】d af c o s t aa n dl u i se n r i q u ec d ar o c h aa r x i v ：c o n d m a t 0 4 0 8 0 7 6 17 b r 0 6 n 自aln a t u r e2 0 0 54 3 51 22 0 7 - 2 1 1 1 8 】b n r 0 6 0 筑als c i e c e2 0 0 53 0 82 96 3 9 6 4 0 1 9 】r a 1 b e r t ，j c e l ls c i 1 1 8 ( 2 0 0 5 ) 4 9 4 7 ；m cp 出u 瑚b o ，a c 0 1 0 s i m o ，a g i u l i a n i ， l f a r i n a ，f e b sl e t t e r s 5 7 9 ( 2 0 0 5 ) 4 6 4 2 ；m c h a e s ，r a l b e r t ，e d s o n t a g ，p r e p r i n t q _ b i o m n 0 5 0 1 0 3 7 2 0 】s b o c c a l e t t i ，v l 8 t o r a ，y m o r e n o ，m c h a v e za dd u h w a n gc o m p l e xn e t - w o r k s ：s t r u c t u r ea n dd y a m i c sp h y s i c sb 耙p o r t4 2 4 ，1 7 5 3 0 8 ，2 0 0 6 5 硕士学住论文 m a s t e r st h e s i s 第二章复杂网络基本概念及其性质 复杂网络是一门包括各种学科的新兴领域，这个领域可以追溯到f 1 0 r y 1 】、 p a p o p o 州2 ，3 ，4 】、e r d j s 和r e n y i 5 ，6 ，7 】最早期的工作，只是现在才开始关注 到这个领域。网络的兴起源于真实世界的网络远远不同于纯粹的随机网络，它 有丰富的圈和幂率连接度分布行为。这些现象鼓动了两个重要的研究成果的发 现：w i t t s 和s t r o g a t z 的小世界网络模型【8 】以及b n r 0 6 0 甙和a l b e r t 的无标度网络模 型f 9 j 。虽然图论是一个在数学和计算机理论科学中早已成熟发展的学科，但是最近 的大量的网络研究领域涉及到社会科学和物理中，这些领域的科学家们不仅仅是应 用这些发展着的工具和概念来考察真实网络的数据和情形，还对网络的拓扑演化产 生了浓厚的兴趣。随着计算机的计算能力的提高以及对真实网络的数据搜集能力的 加强，类似于发现的i n t e r n e t 1 0 】和w w w 1 1 ，1 2 1 的标度无关性使得网络新兴领域 的研究逐步成为热门。 网络研究成为一个热门的主要原因还因其灵活性和表示任何自然结构的广泛 性，包括经历着拓扑变化的动力学。事实上，每个离散结构，诸如树、网格，都可 以用图来表示，这样对于用网络这样的工具来研究就不足为奇了。另外一个感兴趣 的原因是研究演化的网络行为，这样可以特征出研究的结构在过程中的变化行为。 这两类都是基于研究网络的拓扑特征。另外一个相关的应用是用得到的测量量来区 分不同的网络类型，这个是属于方式重组中的问题f 1 3 j 。即使是模拟这些网络，也 有必要把模型和真实网络进行对比。假设测量量是易于理解的，那么如果模拟的网 络的测量量得到的结果类似于真实情况，这样更加说明了模型的可信度。 故而，网络的研究中，网络测量变成了一个直接的办法。如平均的连接度，平 均的聚集系数，网络的直径等。 2 1 复杂网络基本类别及其相互关系 图2 1 展示了四种主要的复杂网络类型，包括带权重的有向网络，无权重的有向 网络，带权重的无向网络和无权重的无向网络。 对称操作可以看成为把一个有向图变成无向图，极限操作可以应用到把有 权重的图变为无权重的图。这些图和操作定义如下，以带权重有方向图为例。 一个有权重有方向的图，g ，由个点集( g ) 和n 条边集e ( g ) 定义。每个点用 6 硕士学位论文 m a s t e r st h e s i s 图2 1 ：四类复杂鲻络及其相互转换 整数 = l ，2 ，区分；边则用( i ，矗w ) 袭示从点i 弱轰有授重为钾的边联系。 在网络语言中，没有自连接或者重飘逢接存在；也就怒说，不存在边的形式 为( 1 ，j ， ) 的( ，j 1 ，w 1 ) 和( 2 ，j 2 ，训2 ) 使得n i 2 ，血= j 2 。搬无权重的有向图中。 连接是没有权重，并且只用考虑存在或者不存在连接。对于无向图，连接是没青方 囊魏，在( g ) 孛豹一祭透( ，) 表示存在麸要貊或蠹扶j 曩i 戆连接。 一个蒂较重蠢囱豳可鞋完全露英较熬矩阵表示，英中元素峨i 表示觖点i 戮 点的权重联系。极限操作可以应用到把带权重的有向图生成一个无权重的副 本。这种操作表示为a = 西( w ) ，慰对矩阵的每个元索作用，生成了矩降a 。 在l 蜘订 t 的情况下，我们有啦f = 1 ，否则，o 订= o 。得刹的矩阵a 可以看为用 极限操作褥至8 的焉投重有向图静连接矩降。任f | 可带权重匏蠢向图可以使用对称操 律口( 秽) = + 渺? 变袋无毂重霾，冀中r 是静转萋。辩予无自强，著穗拜0 娜点i 帮j 是连接的，对于有向图，相废的概念为前辈和继承者，若a ；，b 这样g 是j 的前辈，7 是的继承者。连接的概念可以用到有向图中，点i 的邻居用u ( i ) 表示 对于与点 相连接的点的集合。圈的定义为一序列的连线，从f 开始并且从t 结束， 并且每个点只是经过一次。 点i 戆连接溲，氟，遣帮窝点i 连接瓣遽线戆数疆，帮，鬃”国魏势。在有弱网络 中有两种连接度：滋。连接度，等予国外连接酌连线条数，和久一连接度，矽， 对应于向内连接的造线条数。注意一妒+ p 。对于有权重的网络，连接度的 定义如上所述。但是也有一种量s 称为t 的强度，定义为对j 擞连线的权重之和f 14 ， 7 彩 、，囊飞 顾士学住论史 m a s t e r st h e s l s “= 嘲 s 尹= 铷t 符号 黧g 终点鹣察舍 圈g 连线的集合 结点的数髓 较重矩簿 权重矩阵的单位元素 连接矩降 连接矩阵的单位元素 结点i 的连接度 终点 豹窭连接度 结点z 的入连接度 结点i 的强废 终点i 邻器爨含 集台s 的辩 表2 ，l ：文中健耀豹蕊零蒋号列袁 2 2 复杂网络基本定义 ( 2 1 ) ( 2 2 ) 躐离：一般而言，复杂网络中的任意两点不一定相德。事实上，许多网络都是 稀疏的，即，只是存在一部分所有可能连接的连线。两个非连接的点i 和j 可以通过 彦魏饿袈遮舀，凳1 ) ，( 蠢l ，勃) ，( 喃j ) 连绞；这样豹遴线稔为 秘j 豹路，并显m 称为路的长度。我们称两点连通的条件是有且至少存在条连通的路，许多测量都 是基于连通路的长度上的。 辩于无方融滗权重网络，连接点和点j 的连线酶数嚣称为路斡长度。点稻点j 之间的测地线( 最短路径) 是连接这两点的最短的路长；测地线的长度慰点e 和 点j 之间豹测髓线距离东。若图带权重，可以搜用同撵豹定义，但是要考感到权 重。这样就出娥了两种可能：首先，连线的投重可能正比与物理鞭离，例如若点对 8 粥脚a畸酽舻以秭例 硕士学位论文 m a s t e r s t h e s i s 应于城市以及权重对应于城市之间的高速公路。这样，距离可以看成路的权重之 和。第二，连线的权重可以反映出点的连接强度，例如，点是i n t e r n e r t 的路由器， 权重是连线的带宽，每条边的距离对应于权重的倒数，路长就是路的连线权重倒数 之和。如果没有点i 到点j 的路，则d i f = o 。对于有向图，可以使用同样的定义， 但是一般来说，d “咄，因为从i 到j 的路不同于从j 到i 的路。 我们可以计算屯的平均值，称为平均测地线距离( 也被称为平均最短距离) ： 1 b 而哥芥 ( 2 3 ) ”、” 1 ，t 刊 这样的定义存在的问题是如果在网络中存在不连通的节点，则平均测地线将发 散。为了解决这个问题，求和中只是包括连通的节点对。这样虽然解决了发散问 题，但是对网络中许多不连通的节点对没有考虑入内，得到有很大的连接的网络有 较小的平均距离。l a t o r a 和m a r c h i o r i 1 5 1 提出了一种称为全局效率的相关测量量： e = 志善亳 皿a ， 其中求和是考虑到了所有的节点对。这个测量量在做了假设节点 和j 之间的效 率正比与他们的距离后，量化了节点间传递信息的效率。全局效率的倒数是测地线 的哈密顿平均： = 寺( 2 5 ) 因为上述方程不会出现发散问题，故而更适合做非全连通图的测量量。 聚集系数：随机网络( e r 模型) 【5 ，6 ，7 1 的一个特点就是节点的局域结构是 数。更确切的说，在大网络极限下，包含节点的圈的概率是趋于0 的。这个和现实 网络包含大量的圈是相反的，一种刻画这样的圈的量是聚集系数。通常用到了两种 聚集系数。b a r r a t 和w e i g h t 【1 6 】提出了对于无向无权重的网络的如下定义： e ：挲 ( 26 ) v 3 其中是网络中三角形的数目，3 是三个点连通的数目。因子3 是考虑到每个 三角形可以看作是三个不同的三连通点。一个三角形是每对点之间都是有连线的三 点集，而三连通点则是每个点都是可以从另外的点到达的三点集，也就是说，每两 个点都是连接到第三个的： = ；巧n 神 ( 2 7 ) 9 硕士学位论文 m a s t e r st h e s i s 3 = o 玎蛳 ( 2 8 ) ( i j ，k ) 其中求和是对所有不同的点t ，j ，女的三点集( t ， 七) 。同样可以定义给定点i 的 聚集系数1 3 7 ： g = 篇 ( 2 9 ) 其中_ ( i ) 是包含了点i 的三角形的数目，3 ( ) 是点i 做为中心点的三连通节点 的数目： ( i ) = o “n 讯吣 0 k ) ( 2 1 0 ) 3 = o 玎n ( 2 1 1 ) ( j ) 若是节点e 的邻居的数目，则3 = 缸( 一1 ) ；同样，( t ) 是i 点的邻居之间 的连线的数目，用“表示邻居之间的连线的数目，则方程可以写为： 蘸b ( 2 1 2 ) 使用g ，则有另外一种网络的聚集系数的定义： 召= 寺a ( 2 t 1 3 ) 这两种定义的不同在于第一个给出网络中三角形都是赋予相同的权重， 而第二种则是赋予每个节点相同的权重，得到的是不同的结果。这是源于有 高连接度的点比连接度低的点更容易出现在较多的三角形中对于带权重的 图，b a r t h e l e m y 1 8 】引入了权重聚集系数的概念： 晖2 可习轰半町e ( 2 1 4 ) 其中归一化因子吼( 一1 ) 保证了o5qs1 ，由这个方程，整个网络的带权重 的聚集系数定义为： 1 口2 专q ( 2 - 1 5 ) 给定了节点的聚集系数后，我们可以计算聚集系数做为连接度的函数： g = 紫 ( 2 1 6 ) 1 0 对于一些网络，这个函数有形式：g ( ) 。( 一，这个行为和网络中的等级结构 相关联，其指数a 称为等级指数【1 9 】。 连接度相关量的测量：连接度是节点的一个重要特征，知道了节点的连接度 后，可以构造网络的测量量。一种最简单的量是最大连接度： 女。a x = m a x ( 2 1 7 ) 更多的细节则是由表示连接度为的节点所占的比重的连接度分布p ( 】给出。 对有向网络，存在出一连接度分布。( 。) 和入一连接度p i 。( ) 以及联合出入一连接 度只。( 缸。，) ，对于有权重的网络，可以使用类似的节点强度定义。有些人会对 不同节点之间的连接度的关联感兴趣，这样的关联在许多网络结构和动力学性质 中发现有很重要的影响2 0 1 。最常见的是研究一条连线连接的两个节点之间的关 联。这样的关联可以用联合连接度分布- p ( ，7 ) 表示，即，连线连接的两节点连接 度为女和，的概率。另外种表达方式是给定任意一个连接度为的邻居连接度 为7 的条件概率： p ( 1 ) = ! 菩* ￥ ( 2 1 8 ) 1l “， 对于无方向的网络，尸，女7 ) = p ( 7 ，) ；对于有方向的网络，一般p ( ，) _ p ( ，1 ，为一边的连接度，7 为另一边的连接度，并且，7 可以为出、入或者总 共连接度。对带权重网络强度s 可以代替。这个分布可以很详细给出点的连接度的 关联描述，但是对于无标度网络，因为不太准确的大尾巴连接度统计分布使得很难 求值。在给定连接度条件下邻居的平均连接度的较好的统计计算【2 1 】，可以给为： 。( ) = 7 p ( k 似) ( 2 1 9 ) 一个相关的标度测量2 2 1 为p e a r s o n 关联系数： r 一熹黧嚣隅 z 。， 其中；一，表示对网络中的所有连线求和，礼是连线的总条数。 协调性：一些网络的节点属于不同的类型，例如，在社会关系网中，节点表示 人，连线表示人和人之间的社会关系，有人会提出这样的问题：对于不同经济层次 的人之间存在友谊的概率为多大? 这样的节点并不是均匀的，而是分为了不同的类 别的。 硕士学位论文 m a s t e r s t h e s l s 对于不同类型的节点，可以定义混合矩阵，其元素m 。表示类型s 和类型t 节点 之间的连线数目。归一化为： 髓= 嵩 其中i | m l | 表示矩阵所有元素之和。 一个类型为s 的节点有邻居类型为t 的点的概率为： 咖叱啦) = 轰 注意到tp ( 咖8 ) ( t l s ) = 1 。 p ( 劬e ) ( s ，z ) 和髓可以量化网络中同样类型的点连接的趋势， 定义协调系数为 2 3 】： q 三! 竺! ! = 兰坐上! t 一1 ( 2 2 1 ) ( 2 2 2 ) 称为协调性。我们 ( 2 2 3 ) 其中t 是各种不同类型节点的数目。0 q 1 ，其中q = 1 对应于完全的协调 网络，0 = o 对应于随机混合连接。但是每种类型点不论其数量有多少，在q 中有 相同的权重。另外一种定义 2 4 】是： r ：里丝二! i 丝! !( 2 2 4 ) 1 一l l 肘。0 把点的类型和点的连接度相联系是比较有意思的事情。而p e a r s o n 关联系数可以 看成协调系数的情形。这样的理解下，若r o ，高连接度的点趋于和高连接度点 相连，我们称为协调混合：若r 0 ，高连接度的点趋于和低连接度点相连，我们 称为非协调混合；若r = o ，则连接度之间无关联。 抗攻击性：在复杂网络中，了解哪些元素对于其功能起到重要作用是很有必要 的。直觉上，网络中的中心点是关键点，但是它们不一定必须是最重要的点。例 如，所有二元树形式的点有相同的连接度，故而不存在中心点，但是接近根部分的 点和在根节上的节点比在树叶上的节点要重要些。这个暗示了网络有阶级结构也 就是说越重要的点越处于阶层中的高端。 一种找到网络关键部位的方法是寻找网络中最弱势的点。网络的抗攻击性定义 为当除去一个点及其和此点相连的所有连线后的功能差别f 2 5 】 k ：学 ( 2 2 5 ) 1 2 碛圭学位论文 m a s t e r st h e s i s 其中嚣蹩全弱效率，韪是移狳点及其点靛连线爱的全蜀效豢。瓣络麴拣竣击 性f 2 6 】也虢楚所有点中缀大的抗攻击慷： v = m 9 x k( 2 2 6 ) 楚：瘫绦戆结稳秘蒸霹靠洼与毽