（运筹学与控制论专业论文）复杂网络的演化机制及若干动力学行为研究.pdf

大连理工大学博士学位论文 摘要 近年来，国内外掀起了研究复杂网络的热潮许多来自物理、生物、数学、计算机领域 的研究者都开始致力于复杂网络的研究复杂网络的研究以系统学的观点来看待真实系统， 如i n t e r n e t 网络、电力网，新陈代谢网络等这些大规模网络在社会系统中的广泛存在，促 使人们对这些网络的拓扑结构以及网络上发生的动力学行为展开了广泛的研究本论文利 用统计理论分析方法、结合优化方法对复杂网络中的若干动力学行为进行了研究，探讨了网 络的拓扑结构和网络的若干功能之间的关系其中包括网络的拓扑结构和网络的容错能力 之间的关系，网络的拓扑结构和网络的同步能力之间的关系等问题这些问题的研究为设计 一个具有良好性能的网络提供了一定的理论依据和现实的指导意义主要工作如下t 1 提出了一类可调簇系数的无标度网络演化模型理解无标度网络的演化机制是研究复 杂网络动力学行为的基础本文在b a 无标度网络模型的基础上，考虑了更为详细的 网络演化过程从社会网络中具有局域集团的性质出发，结合网络中加边、加点的事 件以一定的概率发生，提出了一类可调簇系数的无标度网络演化模型利用平均场方 法计算了网络的度分布的幂指数以及网络的簇度相关性的表达式解析计算和数值结 果表日月网络的度分布是幂律分布的，网络的簇系数可以通过参数p 来调节解析表 达和数值模拟结果比较吻合 2 熵优化无标度网络的容错能力 c o h e n 等学者利用逾渗理论研究了无标度网络的容 错能力本文直接从网络的异质性出发，利用信息论的观点，发现网络的异质程度可 以由度分布的熵来度量，而网络的异质程度与网络的容错能力密切相关通过最大化 度分布的熵，得到了度分布的熵与网络的规模、网络中节点的最小度、网络的度分布 的幂指数这些参数之间的关系，给出了具有高度容错能力的无标度网络的可能设计方 案最后，对度分布的熵与传统的逾渗阈值做了比较，发现二者之间成正相关的关系 因此，度分布的熵可以做为衡量网络容错能力的有效度量 3 服从任意度分布的网络的容错能力的优化考虑到网络的结构和网络的性能之间的关 系，网络的性能可以通过改变其拓扑结构来提高研究了在给定网络费用的条件下， 如何设计一个具有高度容错能力的网络。给出了这种网络具有的统计性质通过分析 网络的异质性与网络的容错能力网络的效率之间的关系，发现网络的异质性越强， 复杂阿络的演化机制及若干动力学行为研究 网络的容错能力越好，网络的效率越高因此，以网络的效率为优化的目标，运用禁 忌搜索算法寻找具有最强容错能力的网络的统计特性数值结果表明，一个具有少量 集散节点、节点之间度度负相关的网络具有较强的容错能力结合最优网络具有的统 计特性结果。构建了一个非增长的网络模型，该模型很好的地符合了最优网络所具有 的统计性质分析最优网络模型的性质，发现经过优化后，网络的容错能力和网络的 信息传输效率显著提高了。但是网络的同步能力却下降了 4 ，网络的同步能力的优化网络的拓扑结构对网络i - _ 削j 动力学行为具有重要影响目前 为止，已有的研究主要针对某一拓扑性质对网络的同步能力的影响，如网络的平均最 短距离、网络的簇系数、节点之间度度相关性等本文从优化的恩想出发，分别在拓 扑意义下和空间意义下优化网络的同步能力，研究最优网络所具有的统计特性 首先，在拓扑意义下，只考虑网络中节点之间的作用关系的有无，研究影响网络同 步能力的特征量确定优化的目标函数为网络的拉普拉斯矩阵的最大特征值和最小非 零特征值之间的比值，运用禁忌搜索算法，通过随机交叉重连一对边的方式改变网络 的拓扑结构来提高网络的同步能力对于给定的服从某种度分布的网络，在度分布保 持不变的条件下，网络的同步能力仍然能够得到提高数值结果表明，经过优化后， 与初始网络相比。网络的簇系数和模块性都减少丁，网络中节点之间的度度相关性变 为负相关，即网络中度大的节点更倾向于与度小的节点进行连接同时分析最优网络 的结构特性，发现最优网络中包含较少数目的低阶环 其次，在空间意义下对无标度网络的同步能力的优化在空间意义下，网络中的 节点具有一定的位置，节点之间具有一定的欧氏距离将无标度网络嵌入到二维网格 后。优化网络的同步能力数值结果表明，经过优化后，网络中节点之间的连接方式 改变了，节点更倾向于与位置较远的节点连接这个结果会很自然的导致网络的簇系 数减少同时，分析在拓扑意义下和空间意义下，网络的最大介数和网络的同步能力 之间的关系，发现网络的最大介数与网络的同步能力成负相关，即网络的最大介数越 大，网络的同步能力越弱这个结论无论是在拓扑意义下还是在空间意义下都成立 关键词： 复杂网络；无标度网络；小世界网络；网络的容错能力；网络的同步；禁忌搜索 复杂网络的演化机制及若干动力学行为研究 e v o l u t i o nm e c h a n i s ma n ds o m ed y n a m i c a lp r o c e s s e so n c o m p l e xn e t w o r k a b s t r a c t t h er e c e n td e c a d eh a sw i t n e s s e dt h eb i r t ho fan e wm o v e m e n to fi n t e r e s ta n dr e s e a r c h i nt h es t u d yo fc o m p l e xn e t w o r ki nd o m e s t i ca n di n t e r n a t i o n a la r e a t h er e s e a r c h e r si n p h y s i c s ，b i o l o g y , m a t h e m a t i c sa n dc o m p u t e ra l ld e d i c a t et ot h es t u d yo fc o m p l e xn e t w o r k s i t sf r o mt h ep o i n to fs y s t e m a t i cv i e wt os t u d yr e a ls y s t e m s ，s u c ha st h ei n t e r n e t ，p o w e r g r i dn e t w o r k sa n dt e l e p h o n ec a l ln e t w o r k s ，e t ci nt h i sd i s s e r t a t i o n ，w eu s es t a t i s t i c a lt h e o r y a n do p t i m i z a t i o na p p r o a c h e st oi n v e s t i g a t ean u m b e ro fp r o b l e m si nc o m p l e xn e t w o r k t h e m a i nw o r ki st os t u d yt h er e l a t i o n s h i pb e t w e e nt h en e t w o r ks t r u c t u r ea n di t sf u n c t i o n s ， e s p e c i a l l yt h ee f f e c t so ft h en e t w o r ks t r u c t u r eo nt h ed y n a m i c a lp r o c e s s e so ni t ，s u c ha s n e t w o r kr o b u s t n e s st or a n d o mf a i l u r e sa n dn e t w o r ks y n c h r o n i z a b i l i t y t h em a i nw o r ki s s u m m a r i z e da sf o l l o w s ： l _ p r o p o s eas c a l e - f r e en e t w o r km o d e lw i t ht u n a b l ec l u s t e r i n g t h ef u n d e r m e n t a lw o r k t os t u d yc o m p l e xn e t w o r ki st ou n d e r s t a n da n dm o d e lt h en e t w o r ks t r u c t u r e ，w h i c h w o u l dl e a dt oab e t t e ru n d e r s t a n d i n go fi t sd y n a m i c a lp r o c e s s i nt h i sp a p e r ，b a s e do n t h eb am o d e l ，w ep e r f o r mam o r er e a ln e t w o r ke v o l u t i o np r o c e s s c o m b i n e dw i t ht h e c h a r a c t e ro f l o c a lc o m m u n i t ya n dt h ep r o c e s so fa d d i n ge d g e sa n dn o d e sw i t hp r o b a b i l i t y p w ec o n s t r u c tan e wc l a s so fs c a l e - f r e en e t w o r km o d e lw i t ht u n a b l ec l u s t e r i n g w i t h t h em e a n - f i e l dt h e o r y , w eg e tt h ep o w e r - l a wd e g r e ed i s t r i b u t i o na n dt h er e l a t i o n s h i p b e t w e e nt h ed e g r e ea n dc l u s t e r i n g a n a l y t i c a le x p r e s s i o na n dn u m e r i c a lr e s u l t si n d i c a t e t h a tt h ed e g r e ed i s t r i b u t i o nf o l l o w sp o w e rl a wa n dt h ec l u s t e r i n gc o e f f i c i e n tc a r lb e t u n e dw i t hp a r a m e t e rp t h er e s u l t so fa n a l y t i c a le x p r e s s i o na n dn u m e r i c a lr e s u l t sa r e i nc o n s i s t e n t 2 ，e n t r o p yo p t i m i z a t i o no fs c a l e - f r e en e t w o r k sr o b u s t n e s st or a n d o mf a i l u r e s 、c o h e ne t a 1 u s e dp e r c o l a t i o nt h e o r yt os t u d ys c a l e - f r e en e t w o r k sr o b u s t n e s st or a n d o mf a i l u r e s t h em a i nc h a r a c t e ro fs c a l e - f r e en e t w o r ki si t sh e t e r o g e n e i t y w eo b s e r v e dt h a t t h em o r eh e t e r o g e n e o u st h ed e g r e ed i s t r i b u t i o ni s t h em o r er o b u s tt h en e t w o r ki s s o i i i 大连理工大学博士学位论文 h e t e r o g e n e o u sd e g r e ec a l lb em e a s u r e db ye n t r o p yo ft h ed e g r e ed i s t r i b u t i o n b yo p - t i m i z i n gt h ee n t r o p yo ft h ed e g r e ed i s t r i b u t i o n ，w eg e tt h er e l a t i o n s h i pb e t w e e nt h e e n t r o p yv a l u e ，t h ed e g r e ed i s t r i b u t i o ne x p o n e n t ，t h en e t w o r ks c a l ea n dt h em i n i m a l d e g r e e ，w h i c hc a l lp r o v i d eap o s s i b l ed e s i g nf o rar o b u s ts c a l e - f r e en e t w o r k c o m p a r e d w i t ht h ep e r c o l a t i o nv a l u e ，w ef i n dt h a tt h e ya l ei np o s i t i v ec o r r e l a t i o n s ot h ed e g r e e d i s t r i b u t i o ne n t r o p yc 8 2 1b ea ne f f e c t i v em e a s u r eo ft h en e t w o r kr o b u s t n e s s 3 o p t i m i z a t i o no fn e t w o r kr o b u s t n e s st or a n d o mf a i l u r e s c o n s i d e r e dt h ee f f e c to ft h e n e t w o r ks t r u c t u r eo nt h en e t w o r kp e r f o r m a n c ea n dt h en e t w o r kp e r f o r m a n c ec a l lb e i m p r o v e db yc h a n g i n gt h en e t w o r ks t r u c t u r ew es t u d yt h ep r o b l e mo fh o wt oi m p r o v e t h en e t w o r kp e r f o r m a n c ea n dw h a tc h a r a c t e rt h en e t w o r ks h o n l dh a v ew h e nt h en e t w o r k c o s ti sg i v e n b ya n a l y s i z i n gt h er e l a t i o n s h i pb e t w e e nt h en e t w o r kr o b u s t n e s st or a n d o m f a i l u r e s ，t h eh e t e r o g e n e i t ya n dt h en e t w o r ke f f i c i e n c y , w ef i n dt h a tt h em o r er o b u s tt h e n e t w o r ki s ，t h eh i g h e rt h en e t w o r ke f f i c i e n c yi s b yo p t i m i z i n gt h en e t w o r ke f f i c i e n c y w i t ht a b us e a r c h ，t h es t a t i s t i c a lp r o p e r t i e so ft h em o s tr o b u s tn e t w o r kt or a n d o m f a i l u r e sh a v eb e e no b t a i n e d t h en u m e r i c a ir e s u l t si n d i c a t et h a tan e t w o r kw i t hl e s s n u m b e ro fh u bn o d e sa n dn o d e sc o n n e c ti nad i s a s s o r t a t i v ep a t t e r nw i l lb em o r er o b u s t t or a n d o mf a i l u r e s t h e n ，w i t ht h eo p t i m i z a t i o nr e s u l t s ，an o n g r o w i n gm o d e lh a sb e e n c o n s t r u c t e d a n a l y s i z i n gt h ec h a r a c t e r so ft h em o d e l ，t h er e s u l t si n d i c a t et h a tt h e n e t w o r kr o b u s t n e s st or a n d o mf a i l u r e sa n dt h ee 最c i e n c yo ft h ei n f o r m a t i o ne x c h a n g e h a v eb e e ng r e a t l yi m p r o v e d ，w h i l et h en e t w o r ks y n c h r o n i z a b i l i t yh a sb e e nr e d u c e d 4 o p t i m i z i n gs y n c h r o n i z a b i l i t i e so fn e t w o r k s t h en e t w o r ks t r u c t u r ea f f e c t st h ed y n a m - i c a ip r o c e s sg r e a t l y u pt on o w ，t h ep r e v i o u sw o r k so nn e t w o r ks y n c h r o n i z a b i l i t yh a v e b e e nf o c u s i n go nt h ei s s u eo f8p a r t i c u l a rs t a t i s t i c a lp r o p e r t y se f f e c to nt h en e t w o r k s y n c h r o n i z a b i l i t y , s u c ha st h ea v e r a g ep a t hl e n g t h t h ec l u s t e r i n gc o e f f i d e n ta n dt h e d e g r e ec o r r e l a t i o n i n s p i r e db yt h ei d e ao ft h eo p t i m i z a t i o na p p r o a c h ，t h en e t w o r k s t r u c t u r a lp r o p e r t i e sc o r r e s p o n d i n gt ot h ea p p r o x i m a t e l yb e s ts y n c h r o n i z a b i h t yh a v e b e e ni n v e s t i g a t e dw i t ht a b us e a r c hi nt h em e a n i n go ft o p o l o g i c a la n dg e o g r a p h i c a l n e t w o r k s ，r e s p e c t i v e l y i nt h em e a n i n go ft o p o l o g i c a ln e t w o r k ，t h en e t w o r ki sa n e n t i t yd e f i n e di na n a b s t r a c ts p a c e t h eo b j e c t i v ef u n c t i o ni st h ee i g e n v a l u er a t i oro fl a p l a c i a nm a t r i x ， i v 复杂网络的演化机制及若干动力学行为研究 w h i l et h ec o n s t r a i n tc o n d i t i o ni st ok e e pt h ed e g r e ed i s t r i b u t i o nu n c h a n g e d ，w h i c hc a n b er e a l i z e db yi n t e r c r o s s i n gap a i ro fe d g e sr a n d o m l y t h en u m e r i c a lr e s u l t si n d i c a t e t h a te v e nt h ed e g r e ed i s t r i b u t i o ni sg i v e n ，t h en e t w o r ks y n c h r o n i z a b i l i t yc a ns t i l lb e i m p r o v e d a f t e ro p t i m i z a t i o n ，c o m p a r e dw i t ht h ei n i t i a ln e t w o r k ，t h eo p t i m a ln e t w o r k i st h eo n ew i t hl o w e rc l u s t e r i n g ，l o w e rm o d u l a r i t ya n dt h ed e g r e ec o r r e l a t i o nd e c r e a s i n g t on e g a t i v er e a l s ，t h a ti s ，t h en o d e sc o n n e c ti nad i s a s s o r t a t i v ep a t t e r n t h e n ，t h e s u b g r a p h so ft h eo p t i m a ln e t w o r kh a v ea l s ob e e ni n v e s t i g a t e d t h er e s u l t ss h o wt h a t t h eo p t i m a ln e t w o r kc o n t a i n sl e s sn u m b e ro fl o o p so fs i z e3t o5 ，c o m p a r e dw i t ht h e i n i t i a ln e t w o r k ， i nt h em e a n i n go fg e o g r a p h i c a ln e t w o r k ，t h eg e o g r a p h i c a ld i s t a n c eb e t w e e nn o d e s h a sb e e nc o n s i d e r e d ，w h i c hc a nb er e a l i z e db ye m b e d d i n gas c a l e - f r e en e t w o r ki n t o 2 - d i m e n s i o n a lm e s h a f t e ro p t i m i z a t i o n ，t h ec o n n e c t i o np a t t e r na m o n gn o d e sa l s o c h a n g e d t h en o d e sw o u l dp r e f e rc o n n e c t i n gw i t ht h eo n e sf u r t h e ra w a yf r o mt h e m i ng e o g r a p h i c a ls p a c e ，w h i c hw i l ln a t u r a l l yr e d u c et h ec l u s t e r i n gc o e f f i c i e n t t h em a x - i m a lb e t w e e n e s sh a sa l s ob e e ni n v e s t i g a t e di nt o p o l o g i c a la n dg e o g r a p h i c a lm e a n i n g ， r e s p e c t i v e l y t h en u m e r i c a lr e s u l t si n d i c a t et h a tt h em a x i m a lb e t w e e n e s sh a sn e g a - t i r ec o r r e l a t i o nw i t ht h en e t w o r ks y n c h r o n i z a b i l i t y t h a ti s ，t h el a r g e rt h em a x i m a l b e t w e e n e s s ，t h ew o r s et h en e t w o r ks y n c h r o n i z a b i l i t y , w h i c hh a sb e e no b s e r v e di nb o t h t o p o l o g i c a la n dg e o g r a p h i c a ln e t w o r k s k e yw o r d s ：c o m p l e xn e t w o r k ；s c a l e - f r e en e t w o r k ；s m a l l - w o r l dn e t w o r k ；n e t w o r kr o b u s t n e s st or a n d o mf a i l u r e s ；n e t w o r ks y n c h r o n i z a t i o n ；t a b us e a r c h v 独创性说明 作者郑重声明：本博士学位论文是我个人在导师指导下进行的研究工作及取 得研究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写的研究成果，也不包含为获得大连理工大学或其他单位 的学位或证书所使用过的材科。与我一同工作的同志对本研究所做的贡献均已 在论文中做了明确的说明并表示了谢意。 作者签名；至盎日期。鲨：! ! 大连理工大学博士学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硬士、博士学位论文版权使用规 定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子 版，允许论文被查阅和借阅本人授权大连理工大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学 位论文 作者签名； 导师签名 至逛 鸿缴 坦巨年目j f f _ e j 大连理工大学博士学位论文 1 绪论 1 1 复杂网络的研究概况 近年来，国内外掀起了研究复杂网络的热潮传统的对网络的研究最早起源于著 名的欧拉七桥问题之后的近两百年中，数学家们一直致力于对简单的规则网络和随 机网络进行抽象的数学研究随着近年来计算机存储能力和处理数据能力的增强，以 及一些大规模系统的数据库的建立，人们重新获得了真实网络的特征数据，发现真实 网络既不是规则的，也不是随机的，而是呈现一定规律的复杂网络复杂网络之所以 复杂，不仅在于网络规模的巨大，网络结构的复杂，而且网络在时间、空间上都具有 动态复杂性，网络行为也具有复杂性 许多真实系统都可以用网络的形式加以描述，一个典型的网络是由许多节点与连 接节点之间的边组成的节点代表系统中的个体，边则表示节点之间的作用关系如 w w w 网络可以看成是网页之间通过超级链接构成的网络【l 】；i n t e r n e t 网络可以看作 不同的计算机通过光缆连接构成的网络【2 】；科学家合作网络可以看作不同的科学家合 作关系构成的网络【3 4 j ；基因调控网络可以看成是不同的基因通过调控与被调控关系 构成的网络| 5 j 这些真实网络的普遍存在，促使来自不同学科领域的科学家共同致力于复杂网络 的研究这些学科领域包括复杂性科学、数学、物理、生物、计算机等复杂网络的 研究不仅具有学术意义，而且具有重大的实际意义复杂网络的研究可以使人们更好 的了解现实世界的复杂系统，为设计具有良好性能的网络提供理论依据同时复杂网 络的理论成果将会广泛地应用到生物、计算机等各个学科领域众所周知，还原论一 直在生物学研究中占有重要地位。利用还原论的方法人们已经获得了大量的生物信 息，但生物是一个系统，基因和蛋白质很少单独作用，而是相互耦合共同作用的因 此，需要以系统生物学的观点来重新看待这些生物信息复杂网络理论的发展为系统 生物学的研究提供了一个新的平台，将复杂网络理论应用到系统生物学的研究将会对 生物学的发展产生重大影响复杂网络理论的研究也将会对互联网系统中各种重大问 题的解决，如网络安全和网络控制，提供一定的理论指导 复杂阿络的研究大致可以描述为三个密切相关但又依次深入的方面：大量的真 实网络的实证研究，分析真实网络的统计特性；构建符合真实网络统计性质的网络演 复杂网络的演化机制及若干动力学行为研究 化模型，研究网络的形成机制和内在机理；研究阿络上的动力学行为，如冈络的鲁棒 性和同步能力，网络的拥塞及网络上的传播行为等 当把一个系统描述为网络的形式后，就可以通过分析网络的统计性质，如网络的 度分布、网络的簇系数、网络的平均最短距离等来描述真实网络 6 - a o 大量的实证研 究表明许多真实世界的网络具有两个基本性质；小世界特性( s m a l l - w o r l dc h a r a c t e r ) “1 和无标度特性( s c a l e - f r e ec h a r a c t e r ) “】小世界特性是指与相同规模的随机网络相比， 该网络具有较小的平均最短距离和较大的簇系数1 9 6 7 年，美国啥佛大学社会心 理学家s t a n l e ym i l g a m 傲了一个实验，在美国将一封信通过熟人找熟人的方式传递 到目标者，发现平均最多经过6 人就可到达，这就是著名的“六度分离( s i xd e g r e eo f s e p a r a t i o n ) ”现象，它揭示了社会网络的小世界特性而在互联网( w w w ) 中，平均 只需点击1 9 次超级链接，就可以从任意一个网页到达其它网页m 大量的小世界网络的普遍存在，促使人们探讨形成这种网络的内在机理 1 9 9 8 年，学者w a t t s 和s t r o g a t z 在规则网络中引入随机性，建立了著名的小世界网络模型 ( w s 小世界网络模型) 【1 l l ，很好地描述了真实网络的小世界性质 1 9 9 9 年，学者b a r a b 缸i 和a l b e r t 通过对万维网的数据进行统计分析发现万维网 的度分布服从幂律分布，在双对数坐标系下是一条下降的直线，由于幂律分布具有标 度不变性，缺乏一个特征度值，因此称这种度分布服从幂律分布的网络为无标度网络 ( s c a l e - f l e en e t w o r k ) 1 2 1 之后的研究表明，许多社会网络如科学家合作网络【3 4 】、生物网 络中的新陈代谢网络、技术网络中的i n t e r n e t 网络1 2 】等都是无标度网络。这些来 自不同领域的大规模系统呈现了共同的普适规律，促使人们去探索隐藏在这些表象后 的内在演化机制，从此掀起了研究复杂网络的热潮 随着近年来大型数据库的建立和计算机存储与运算能力的迅速提高，复杂网络的 研究进程大大加快人们对社会系统、大型基础性设旌和生物系统中大量的真实网络 数据库进行了系统的分析，寻找呈现表象的内在机制和模式，试图发现支配和影响这 些复杂系统的动力学和演化规律的内在本质复杂网络的理论及实证研究的发展将会 对网络安全、网络控制、疾病传播的控制与防御、社会中人的行为动力学的研究、生 物网络的演化机制的研究等产生重要影响 1 2 复杂网络的基本性质 一般地，按照是否考虑网络中节点之闯的相互作用的方向性，可以把网络分为无 向网络( u n d i r e c t e dn e t w o r k ) 和有向网络( d i r e c t e dn e t w o r k ) ；按照是否考虑网络中节点之 2 大连理工大学博士学位论文 间的作用强度，可以把网络分为无权网络( u n w e i g h t e dn e t w o r k ) 和加权网络( w e i g h t e d n e t w o r k ) 对于w w w 网络和人际关系网络而言，网络中的边只表示节点之间作用关 系的有无，而不涉及节点间的位置关系或作用强度，通常将这种网络视为无权网络 而对于交通运输网络，边的权重代表节点之间实际的欧氏距离；科学家合作网络中边 的权重代表不同科学家之间合作的亲密关系等，通常将这种网络视为加权网络本文 介绍的有关复杂网络的基本特性主要是针对无向、无权网络，对于加权网络的更为细 致的描述可以参见文1 4 1 9 1 1 2 1 真实网络的圈的表示 首先，简单介绍有关图的定义和基本概念图g 可以表示为集合( v ，妒) ，v ( a ) = 1 ，2 ，) 表示图g 的顶点集合，表示网络的顶点总数，1 】f 1 ( g ) = ( ，j 1 ) ( i 2 , j 2 ) ， ( i e ，如) ) 代表边集合，e 表示总边数如果( ，j ) = ( j ，i ) ，则图是无向图，否则为有向 图当网络是无向无权网络时，邻接矩阵a = 吼f ) 是一个o - 1 对称矩阵，表示图中顶 点之间的连接关系如果顶点i ，j 之间有连接，则a 玎= 1 ；否则a t f = 0 当网络是有向 图时，邻接矩阵4 是非对称的o - 1 矩阵；当网络是加权网络时，a 中的非零元素代表 边权 1 2 2 度分布 度分布是描述网络性质的一个重要统计量节点i 的度定义为与节点t 连接的边 的数目度分布p ( k ) 定义为随机地选择一个节点，度为k 的概率，或者等价地描述为 网络中度为k 的节点数占网络节点总数的比例当然，对于有向网络，其度分布还可细 致地分为网络的入度分布( i n - d e g r e ed i s t r i b u t i o n ) 和出度分布( o u t d e g r e ed i s t r i b u t i o n ) 近年来大量的实证研究表明，许多真实网络的度分布都遵循幂律分布，数学形式 为：p ( k ) 一k 一，其中7 一般介于2 到3 之间幂函数在双对数坐标系下是一条下降 的直线，如w w w m 的度分布，见图1 1b 与指数函数相比，幂函数下降速度较慢， 使得网络中存在度较大的节点，通常称这些节点为集散节点( h u bn o d e ) 研究发现除 了幂律分布，真实网络中还存在其它形式的度分布，如电力网络i n 的度分布服从指 数分布，在单对数坐标系下是一条下降的直线；也存在幂律加指数截断的度分布的网 络，如电影演员合作网络| 1 2 l ，图11a ，以及蛋白质相互作用网络1 2 1 1 2 3 网络的平均最短距离和顶点的介数 3 复杂网络的演化机制及若干动力学行为研究 k f i g 1 1 不同类型的大规模阿络的度分布 a ：电影演员合作网络，网络规模为兰2 1 2 ，2 5 0 ， ( ) = 2 8 7 8 ；b ：w 7 w 阿络，网络规模为n = 3 2 5 ，7 2 9 ，( k ) = 5 4 6 度分布的幂指数。= 2 3 ， ”= 2 1 ，引自文f 1 2 】_ f i g 1 1t h ed i s t r i b u t i o nf u n c t i o n so fc o r m e c t i v i t i e sf o rv a x i o u sl a r g en e t w o r k s a ：a c t o r c o l l a b o r a t i o ng r a p hw i t hn = 2 1 2 ，2 5 0v e r t i c e sa n da v e r a g ec o n n e c t i v i t y ) = 2 8 7 8 b ：w w w ， = 3 2 5 ，7 2 9 ，( 奄) = 5 4 6 t h ed a s h e dl i n e sh a v es l o p e sa ： a c t o r = 2 3 ，b ：1 = 2 1r e f 1 2 l 网络的平均最短距离( a v e r a g ep a t hl e n g t h ) 定义为网络中任意一对节点之间的最 短距离的平均值，数学表达式为： 妒高j ：蠹 ( 1 1 ) 其中如为节点i ，j 之间的最短路径的长度所有节点间的最短路径长度的最大值称 为网络半径( n e t w o r kd i a m e t e r ) 大多数真实网络具有较小的平均最短距离，如具有 1 5 3 1 2 7 个节点的万维网( w w w ) 的平均最短距离为3 1 ，e c o l i 的代谢网络的平均最 短距离为2 4 6 p “ 网络中不相邻的节点j 和k 之间的路径主要依赖于连接节点j 和的路径上所经 过的节点，如果某个节点被其它许多路径经过，则表示该节点在网络中很重要，定量 地描述某个节点在网络中的影响力或重要性可以用顶点的介数( n o d eb e t w e e n e s s ) 来衡 量，这一定义最早由f r e e m a n 在1 9 7 7 年提出| 2 4 1 顶点i 的介数最定义为t 且一要，警， ( 1 z ) 土t 】 j “ 其中m r 表示节点j 、之间的最短路径的个数，n j k ( i ) 表示节点j 、k 之间的最短 铲 铲 矿 铲 铲 大连理工大学博士学位论文 路径中经过节点i 的个数研究表明，顶点的最大介数与网络的同步能力密切相关 顶点的最大介数越大，网络的同步能力越弱，这将在1 5 2 节中详细介绍 1 2 4 网络的簇系数 网络的簇系数( c l u s t e r i n gc o e f f i c i e n t ) 是衡量网络集团化程度的重要参数，是一个 局部特征量节点i 的簇系数g 定义为节点i 的邻接点之间实际存在的边数与所有可 能的边数的比值，数学表达为： g 2 蘸与， ( m ) 其中，表示节点 的度，e i 表示节点 的邻接点之间实际存在的边数网络的簇系 数定义为对所有节点的簇系数做和求平均t ( 1 4 ) 许多真实网络具有较大的簇系数和较小的平均最短距离这里。较大的簇系数”指真 实网络的簇系数远远大于相同规模的随机网络的簇系数“较小的平均最短距离”指 平均最短距离随网络规模的增加呈对数或者更小增长 除上述三种复杂网络研究的最基本的特性外，真实网络还具有其它的统计特性， 下面分别做简单介绍 1 2 5 网络的度度相关性 网络的度度相关性( d e g r e ec o r r e l a t i o n ) 描述了网络中度大的节点和度小的节点之 间的关系如果度大的节点倾向于和度大的节点连接。则网络是度度正相关的( a s - s o r t a t i v e n e s s ) ；反之，如果度大的节点倾向于和度小的节点连接。则网络是度度负相 关的( d i s a s s o r t a t i v e n e s s ) p a s t o r - s a t o r r a s 等学者利用顶点的一阶邻接点的平均度k 。 与该顶点的度k 之间的关系来描述度度相关性当网络是正相关时，k 。是随k 递增的曲线j 当网络是负相关时，k 。是随k 递减的衄线【2 5 1 学者n e w m a n 指出计 算边的两端顶点的度的p e a r s o n 相关系数r 可以描述网络的度度相关性。具体定义为： ，一 m 一1 l 一【m - 1 ，；