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

大连珲j ：大学博上学位论文 摘要 复杂网络作为近几年国内外学术界研究的薪热点，正吸引着越来越多的来自各学 科领域学者们的关注。它的发展引发了网络建模的复兴，人们开始用各种组成网络因 素不断变化的观点来重新认识网络，建立模型模拟网络的演化过程及再现其拓扑属 性。因为现实系统的复杂性，如何真实合理地再现网络的演化过程，以及网络结构对 其整体动态行为有何影响已经成为复杂网络研究的核心问题。以往的研究工作主要是 围绕拓扑意义下的嘲络展开，有关加权网络的研究工作甚少。在本文中，我们将加权 网络的演化机制及系统动力学行为作为研究对象，通过建立模型来模拟真实世界网络 性质，同时利用统计理论分析方法结合大量计算机模拟实验，探讨了加权网络结构与 网络动力学行为之间的关系。这些问题的研究对认识网络功能及了解网络微观结构变 化对网络整体性质的影响方向具有一定的理论及现实指导意义。 第一章概述了复杂网络的研究现状和若干热点问题，尤其是对加权网络的模型及 动力学性质的研究进展进行了重点综述。另外，作为预备知识，我们介绍了有关复杂 网络的度量标准，阐述了复杂网络研究工作的意义和实用价值。 第二章提出了两个加权网络的演化模型。首先，通过双向择优的方法，构造了一 个边权动态增长的网络演化模型，给出该模型点权和边权分布的解析过程和数值模拟 结果，并将这两个结果与实证数据作出比较，证实了该模型符合在真实网络中发现的 许多拓扑特征，结果表明模型主要适合用来模拟真实世界中的技术网和生物网。其 次，又通过点权非线性择优的方法构造一个网络演化模型，通过该模型主要探讨了连 接机制对网络中边权分布以网络相关性的影响。对这一个模型我们给出了其数值模拟 结果。 第三章在局部世界( l w ) 模型的基础上，提出了基于局部信息的从无权到加权网 络的演化模型。通过局部世界模型和内部双向择优机制，建立了该模型，并给出了点 权和边权的分布以及两个极限情况下的解析结果。同时，对该模型进行了数值模拟， 扩展的数值模拟结果与理论预测一致。该模型可以通过增加局部信息量实现网络从度 度正相关向度度负相关的转化，还可根据择优点在局部世界多少的变化实现度、点 权、边权从指数分布向幂律的过渡。模型显示出的这些广泛可调的性质使该模型可以 模拟许多真实删络，具有良好的应用前景。 第四章讨论了加权网络的同步能力与权之间的对应关系。通过权分布的调节，分 加权复杂嘲络演化机制及若十动力学行为研究 析权分布对网络同步能力的影响，得出权的分布越均匀网络同步能力也越强的结论， 即权的同质分布比异质分布更能提高网络的同步能力。通过第二章和第三章所建立模 型的模拟计算分别证实了该结论的可靠性。 关键词：复杂网络；加权网；优先连接：同步；。动力系统 大连理l 大学博 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 nw e i g h t e d n e t w o r k s a b s t 阳c t c o m p l e xn e t w o r k sh a v eb e e nm u c hi n t e r e s tf r o ma ur e s e a r c hc i r c l e si nt h el a s tf e wy e a r s i t sd e v e l o p m e n tc a u s e dt h en e t w o r kt os e tu pt h e1 - e i c wo fm o d e l p e o p l es t a r tu s i n gv a r i o u s s t a n d p o i n tw h i c hc o n s t i t u t ean e t w o r kf a c t o rt oc h a n g ec o n t i n u o u s l yt o 聆一k n o wan e t w o r k , b u i l d i n gu pm o d e le m u l a t i o nan e t w o r kt oe v o l v ep r o c e s sa n dr e a p p e a r i n gi t st o p o l o g i c a la t - t r i b u t e s b e c a u s et h ec o m p l e x i t yo fw o r l d ，h o wt h er e a l i t yr e c o n s t r u c t san e t w o r kt oe v o l v e p r o c e s sr e a s o n a b l y , a n dn e t w o r ks t r u c t u r e 鹧t oi t sw h o l ed y n a m i cs t a t eb e h a v i o r sh a v i n g i n f l u e n c eh a v ea l r e a d yb e c o m et h ec o r ep r o b l e mt h a tt h ec o m p l e xn e t w o r ks t u d i e s f o r m e r 一 s e a r e l aw o r km a i n l yi st h ec i r c u m a m b i e n e er u s h e st o w a r dm e a n i n gu n d e ro f t h en e t w o r kl a u n e l a , r e l e v a n tt h er e s e a r c hw o r kw h i c ha d d sap o w e l n e t w o r kv e r yf e w i nd a i st e x t , w ew i l la d da p o w e rn e t w o r ko fe v o l v em e c h a n i s ma n ds y s t e md y n a m i c sb e h a v i o ra sr e s e a r c ho b j e c t s ，p a s s e s t a b l i s k m e n tm o d e lt oi m i t a t ear e a lw o r l dn e t w o r kp r o p e r t y , i nt h em e a n t i m em a k eu s eo f c o v a r i a n c et h e o r i e sa n a l y t i c a lt h em e t h o dc o m b i n eag r e a td e a lo fe a l e u l a t o rt oi m i t a t ea ne x p e r i m e n t i n q u i r yi nt oa d dt h er e l a t i o no f o f t h ep o w e r n e t w o r k $ 1 1 u e t u r ea n dn e t w o r kd y n a m i c s b e h a v i o r t h e s er e s e a r c hw i t hp r o b l e mh a v et ot h ei n f l u e n c ed i r e e t i o nw h i c hk n o w sn e t w o r k f u n c t i o na n du n d e r s t a n d i n gn e t w o r kt i n yv i e ws t r u e t t l t r ev a r i e t yt ot h en e t w o r kw h o l ep r o p e r t y c e r t a i nt h e o r i e sa n dr e a l i t yg u i d em e a n i n g i nc h a p t e r1 t h ep r e s e n tc o n d i t i o na n ds 啪eh o tp r o b l e m so ft h ec o m p l e xn e t w o r ka r e ： i n t r o d u c e d i ti sc a r r i e do i lap o i n to v e r v i e wt o w a r d sa d d i n gap o w e rn e t w o r ko ft h er e s e a r c h p r o g r e s so f m o d e la n dd y n a m i c sp r o p e r t y m o r e o v e r , c o n d u c ta n da c t i o n sp r e p a r e sk n o w l e d g e ， w ei n t r o d u c e dc o n c e r n i n gt h ec o m p l e xn e t w o r ko f t h eg e n e r o u sc h a r a c t e ri ss t a n d a r d , e l a b o r a t - i n gt h ec o m p l e x n e t w o r kt 0s t u d yaw o r ko f m e a n i n gw i t hp r a c t i c a lv a l u e i nc h a p t e r2 t w oe v o l v i n gm o d e l sa r cp r o p o s e d f i r s t l y , t h r o u g ht h ed o u b l ep r e f e r e n t i a la t t a c h m e n tc h o o s em e t h o d , t h en e t w o r kw h i c bc o n s t r u c t st h ed y n a m i cs t a t eg r o w t ho fa s i d ep o w c 1 - e v o l v e sm o d e l ，g i v i n gt h a tm o d e lo r d e r sr e s o l u t i o np r o c e s sa n dn u m b e rt h a tw e i g h t d i s t r i b u t et oi m i t a t ear e s u l t , a n dm a k et h e s et w or e s u l t sa n ds u b s t a n t i a le v i d e n c ed a t aac o r n 一i 加权复杂网络演化机制及若十动力学行为研究 p a r i s o n , c o n f i r m e dt h a tm o d e lt om a t c hm a n yo fd e t e c t i o ni nt h et r u en e t w o r kr u s ht o w a r da c h a r a c t e r i s t i c ，t h er e s u l te n u n c i a t i o nm o d e lm a i n l ys u i t st ou s et oi m i m t et h et e c h n i c a ln e t w o r k i nt h er e a lw o r l da n d l i v i n gc r e a t u r en e t w o r k s e c o n d l y , a n dt h e nt h r o u g h t h ed o u b l ep r e f e r - e n t i a la t t a c h m e n tc h o o s em e t h o dc o n s t r u c t san e t w o r kt oe v o l v em o d e l ，p a s s i n gt h a tm o d e lt o m a i n l yi n q u i r yi n t oac o n j u n c t i o nm e c h a n i s mt on e t w o r k t h ee d g ew e i g h td i s t r i b u t e sw i t ht h e i n f l u e n c eo f t h en e t w o r kr e l a t i v i t y t ot h i sm o d e lw eg a v ei t sn u m b e re m u l a t i o nr e s u l t s i nc h a p t e r3 ，b a s e do nl o c a lw o r l d ( l v 0m o d e l ，t h em o d e le v o l v e sn e t w o r kf r o mu n - w e i g h t e dt ow e i g h t e dw i t hl o c a li n f o r m a t i o ni sp r o p o s e d t h r o u g hl o c a lw o r l dm o d e la n di n t e m a ld o u b l ep r e f e r e n t i a la t t a c h m e n tc h o o s em e t h o d , b u i l tu pt h a tm o d e l ，a n dg i v et h es 仃e n g t h a n dw e i 【g h td i s t r i b u t e ，t w oe x t r e m el i m i tc i r c u m s t a n c e so fa n a l y z ear e s u l t c a m e do nn u m b e r e m u l a t i o nt ot h a tm o d e li nt h em e a n t i m e t h en u m b e re x p a n d e di m i t a t e d 船ar e s u l tp r e d i c tw i t h t h e o r i e sc o n s i s t e n t l y t h a tm o d e le x h i b i t sa l la l t e r a t i o nf r o ma s s o r t a t i v en e t w o r k st od i s a s s o r - t a t i v en e t w o r k s a c c o r d i n gt oc h a n g i n gt h ea r e ao fl o c a lw o r l d , i ta l s oe x h i b i t sac r o s s o v e r b 创t 3 v e e ne x p o n e n t i a la n ds c a l e - f l e ew e i g h t e dn e t w o r k s ，t h e s ee x t e n s i v e l ya d j u s t a b l ep r o p e r t i e s t h a tt h em o d e ld i s p l a y sn l a k et h a tm o d e lb ea b l et oi m i t a t em a n yt r u en e t w o r k s ，w h i c hn l a k ei t h a v i n g9 0 0 da p p l i e df o r e g r o u n d i nc h a p t e r4 ，t h er e l a t i o nb e t w e e nt h es y n c h r o n o u sa b i l i t ya n dw e i g h t si sd i s c u s s e d w e a n a l y z eh o wt h ew e i g h t s d i s t r i b u t ei n f l u e n c et h en e t w o r ks y n c h r o n o u sa b i l i t y , a n dg e tac o n - c l u s i o nw h i c hw e i g h t sd i s t r i b u t em o r ee v e nn e t w o r ks y n c h r o n o u sa b i l i t ym o r es t r o n g ，n a m e l y t h ew e i g h t sd i s t r i b u t e 、j l ，i 也q u a l i t yt od i s t r i b u t ea n dc a ne v e ni m p r o v et h es y n c h r o n o u sa b i l - i t yo fn e t w o r kt h a nt h ed i f f e r e n c e s b u i l du pm o d e lt h r o u g hc h a p t e r2a n dc h a p t e r3i m i t a t e d e x p e r i m e n ta n dc a l c u l a t i o nt oc o n f i r mt h ec r e d i b i l i t yo f t h a tc o n c l u s i o nr e s p e c t i v e l y k e y w o r d s ： c o m p l e xn e t w o r k s ；w e i g h t e dn e t w o r k s ；p r e f e r e n t i a la t t a c h m e n t ；s y n - c h r o n i z a t i o n ；d y n a m i c a ls y s t e m ； 一 独创性说明 作者郑重声明：本博士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理工大学 或者其他单位的学位或证书所使用过的材料与我一同工作的同志对本研 究所做的贡献均已在论文中做了明确的说明并表示了谢意 作者签名：叠2 透蒸日期：五翌z ：芝：全 大连理。【：大学博l j 学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文版 权使用规定”。同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件 和电子版，允许论文被查阅和借阅本人授权大连理工大学可以将本学位论文的全部或 部分内容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编 学位论文 作者签名 导师签名 丑鱼蓬 丝墨乡 2 型2 年f 里月旦 日 6 7 大连理j ：大学博l 学位论文 1绪论 摘要：随着复杂性科学的发展以及对复杂系统研究的日渐深入，基于复杂网络的 复杂系统研究工作正迅速兴起，并逐渐发展成为集系统科学、物理学、数学、生物学 等多学科为一体的全新研究方向，该方向具有很强的跨学科特点。本章简要地综述了 复杂网络的研究历史和发展现状，重点介绍了加权网络的研究进展及一些当前的热点 问题。同时，作为本文的预备知识，我们也解释了复杂网络常用的各种度量标准，本 章最后介绍了本文的主要工作。 1 1 复杂网络概述 在现代社会中，我们每个人每时每刻都生活在各种各样的网络中，比如社 会关系网r l - 6 】、航空网 7 - 9 、万维网( w w w ) u 0 、新陈代谢网【n ，1 2 、因特 网( i n t e r n e 0 1 3 1 4 等等，针对这些自然和人工网络的认识和理解已经成为近几年国 内外学者们关注的热点。在此之前人们对于网络的认识十分有限，但随着计算机技术 的发展，人们对大型数据分析能力的提高，使得科研人员获得了许多真实网络的特征 数据【4 一1 4 1 ，这些数据呈现出人们从未意识到的许多特殊性质，比如：小世界性( s m a l l w o r l d ) f 1 5 1 、无标度性( s c a l e f r e e ) 1 6 等等，这些特性的发现进一步推动了人们对网络 复杂性的认识和研究工作的展开。另外，这些真实网络之所以被称为复杂网络( c o m p l e x n e t w o r k s ) 1 7 1 ，主要是指其规模庞大、结构复杂、动力学行为多样，更适合描述和表达 各类系统的复杂性。 复杂网络的研究历史一般认为应该从欧拉创建的图论学科开始算起。第一个重 要发展阶段是从2 0 世纪5 0 年代匈牙利数学家p a u le r o d o s 和a l f r e dr e n y i 弓i 入随机图论开 始。第二个重要发展阶段是从2 0 世纪末小世界网络和无标度网络研究开始。 运用图论的方法开展对网络的研究是从数学家欧拉解决”哥尼斯堡( k o n i g s b e r g ) 七桥问题”开始的，即：找到一条经过普鲁士哥尼斯堡城的每一座桥回到起点的回路，并 且每座桥只走一次。欧拉将这一个实际问题抽象为一个简单的图形，从而轻松地获得 问题的解，这种新的思维方法开创数学中一个重要分支，即图论( g r a p ht h e o r y ) 图 论的研究为许多实际问题的解决提供了很好的工具。如：如何用最少种类的颜色为地 图着色并保证相邻区域的颜色均不同；网络的最大交通流问题、旅行商问题等。 加权复杂嘲络演化机制及若十动力学行为研究 图l ，1一维有限规则图 f i g 1 1ar e g u l a rr i n gl a t t i c e 引自文献1 5 而e r d o s 和r e n y i 两位数学家建立的随机图理论( r a n d o mg r a p ht h e o r y ) 被认为是复 杂网络理论研究的另一个重要阶段的开始。在他们建立的e r 髓机图模型中，网络的规 模( 即节点总数) 预先给定为n ，任意两个节点之间有一条边相连接的概率为p ，网络 中边的数目是一个随机变量m ，其取值范围为0 一n ( n 一1 1 2 。由此可得，产生n 个节 点，掰条边的e r 随机图概率为矿( 1 一p ) v ( 一1 ) 2 一m 。e r d o s 和r e n y i 对e r 随机图的性质 进行了广泛的研究，发现了随机图的许多重要性质。在他们之后的4 0 9 时间中，随机 图论一直是复杂网络的基本理论。甚至到了今天，他们的思想依然占据着许多数学家 的头脑。在这个时期，人们也在不断的思考这样的问题：真实网络确实是随机的吗? 它们还有哪些不为人知的特性? 为什么在有几亿人的国度中两个陌生人相见经常会发 出：“这个世界真是太小了”的感慨呢? 带着这样的质疑，1 9 6 7 年，美国哈佛大学的 社会心理学家s t a n l e ym i l g a m 做了一个有趣的实验：在美国将一封信通过熟人找熟人方 式从始发者传递到目标者，他发现平均最多通过6 个人就可以相互联系起来，他断定在 美国大多数人之间相互认识途径的典型长度为六，由此提出了著名的“六度分离”概 念。这项研究揭示了社会网络中的小世界特性。而后在对互联网的研究中发现，平均 只需要点击中1 9 次超级链接就可以将任意两个网页联系起来 1 0 】。这些普遍存在的真实 网络特性促使人们去探讨和揭示其内部形成的重要机理。 在1 9 9 8 年，w a t t s 和s t r o g a t z 1 5 1 两位学者在规则网络中引入随机性，建立了著名 的w s d , 世界网络模型，很好地摘述了真实世界的小世界性。小世界网络模型的基本 算法描述如下：i ) 给定规则网：网络节点总数为n ，每个节点与它最近邻的k = 2 七 2 人连王甲 火学博j j 学位论文 个节点相连，其中k 1 ；2 ) 改写连线：以概率p 对建立的规则网重新连接， 将该连线的一个端点随机地放到一个新位置上，不允许自身与自身相连和重复连 线。w a t t s 和s t r o g a t z 得出了小世界网络在p 值较小的一个范嗣内具有大的集聚系数 和小的平均距离现象，即被称为小世界现象( 效应) 。另外，于1 9 9 9 年，美国学 者b a r a b a s i 和他的学生a l b e r t 1 6 1 在对万维网的数据统计分析中发现万维网节点的度分布 并不服从原先预想中的泊松分布( 图1 2 ) ，而是意外地服从幂律分布( 图1 3 ) 。由于幂 律分布缺乏一个典型的特征标度，因此称这种度分布为无标度( s c a l e f r e e ) 分布。他们 将这一发现公布在当年的科学杂志上，在随后的几年里，学者们对大量各种真实 世界网络的研究中相继发现了这种无标度分布几乎是一种普适规律，这些看似纷繁复 杂的网络却有着许多共同的特性，其中包括各种生物网、社会网、技术网等。上述这 些重要特性的发现，标志着对复杂网络研究的进入另一个重要发展阶段。人们开始根 据这些新发展探索隐藏在这些现象背后的内在机制。有关复杂网络的研究工作也再次 迅猛发展，其工作主要集中在对网络结构及演化机制的研究、实证研究、动力学行为 研究等诸多方面。研究成果也与日俱增，发表在各级各类国际杂志上的文章也触手可 及。 在这里我们所说的网络是指节点和连线的集合。如果节点按确定的规则连线所得 到网络就称为规则网络( 图1 1 ) 。如果结点不是按研究的规则连线( 比如按随机方式 连线) 所得到的网络就称为随机网( 图1 2 ) 。在大量研究中人们还习惯将复杂网络划 分为无向网、有向网、加权网三个层次。前期的研究成果主要集中在无向网上，而近 期关于加权网1 8 - 2 4 】和有向网的研究也愈来愈引起学者们的注意。 目前，对复杂网络的研究工作已经触及和拓展到诸多领域，来自不同学科包括物 理、数学、计算机、生物、系统工程等方面的科研工作者试图从各种不同角度认识和 解读复杂网络的本质，建立进一步的研究理论工作也迫在眉睫。同时，将复杂网络的 理论应用于实践也指日可待，或者说它们可能已经有意无意地正在指导着实践应用。 这些成果可以广泛地应用到计算机、生物、社会学、经济学等各类学科领域中，用来 解决各种各样的实际问题，比如：疾病或病毒的传播、交通拥塞、网络搜索算法的设 计等。开辟了对这些领域研究工作和实际应用的新方法和新思路。 3 加权复杂嗍络演化机制及若十动力学行为研究 1 - 2 复杂网络基本定义 一般地，我们如果用复杂网络来刻划一个真实系统，都可以把系统中的元素看成 是网络中的节点，而元素间的相互关系、相互作用看成是网络的边。比如：在不考 虑权的情况下，人际关系网是每个节点代表一个人或一个团体，边则代表人与人之 问或团体之间的各种关系：对于航空网来说，节点通常是指机场，而边可以指航线。 对于加权网入际关系中的边可以代表两个人之间关系的紧密程度，航空网中的边还 可以指航班的数量或为乘客提供的座位数等【7 ，l8 】。在数学中我们通常用图( 鲫h ) 来 描述复杂网络，图g 可以由一个顶点集v 和一个边集e 所组成，l i p c r - - ( v , e ) 。其中顶点 集v ( g ) = 1 ，2 ，3 ，边集e ( g ) = ( i l ，j 1 ) ，( t 2 ，2 2 ) ，( i e , j e ) ，其中e 为边的总数。如 果( 让，靠) = ( 靠，i k ) 则图为无向图( u n d h c t e d n e t w o r k ) ，否则为有向 ( d i r e c t e d n e t w o r k ) 。 如果边集e 中的元素值均为0 或l ，则代表一个无权图( u n w e i g h t e dn e t w o r k s ) ，否则表示 加权 ( w e i g h t e dn e t w o r k ) 。一般地，在图论中我们用邻接矩阵 啦f ，来描述一个无权网 络，其中i ，= 1 ，2 ，3 ，n 为网络规模。元素a i f 的值为喊l ，a i i 的值为l 表示节点岳与 节点f 之间有边相连，为o 则表示无边。无权图主要表示节点之间的连接关系，而加权 图除连接关系外还可以包含更多的信息。 1 2 。1 节点的度与度分布 在图g 中，一个节点的度( d e g r e e ) 通常是指与该节点相连接的边的数目，即该节 点的邻居数，可定义为= f a o 。而如果要讨论的是有向图，节点的度可以分为 了 入度( i n - d e g r e e ) 和出度( o u t - d e g r e e ) ，即从该节点出发的边数和汇入该节点的边数。一 般认为在一个网络中，一个节点的度越大，这个节点对于整个网络就越重要。网 络中所有节点度的平均值称为网络( 结点) 的平均度( a v e r a g ed e g r e e ) ，记为 。 度分布( d e g 呜ed i s t r i b u t i o n ) p ( 七) 是表示节点度分布情况的函数，它的含义是我们在网 络中随机选择一个节点，其度为k 的概率，也可以等价于描述为网络中度为七的节点 数占网络中节点总数的比例。对于有向图，其度分布还可以分为入度分布( i n d e g r e e d 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 o i s s o n ) 分布，其形状如图1 2 。近年来对大量真实网络的实证研究表明，许多实 际网络的度分布都不同于随机网的泊松分布。它们火都遵循幂律分布 1 p p ( k 1 。k - ，其 中1 的值介于是2 到3 之间。与泊松分布相比，幂德分布曲线如图1 3 下降速度要慢缛多， 4 大连瑁，l 大学博j j 学位论文 图1 2泊松分布与箍机图 f i g 1 2p o i s s o nd i s t r i b u t i o na n dr a n d o mg r a p h 引自文献4 7 幂律分布曲线在双对数坐标系下是一条下降的直线。如果一个网络中的度分布符合幂 律分布，表示在这个网络中存在大量度很低的节点，同时有少数度较大的节点，我们 通常称这些度较大的节点为集散节点( h u bn o d e ) 。研究还发现并非所有的真实网络度 分布都符合幂律分布，还存在其他形式的度分布。比如美国高速公路网就近似均匀分 布，而电力网的度分布却服从指数分布 1 5 】，还有一些网络度分布是两种分布的结合， 比如蛋白质相互作用网就是幂律分布加指数截断的形式 2 5 1 无标度网络概念的提出者b a r a b a s i 和a l b e r t 1 6 将这种幂律分布的形成机理归结为增 长和择优两种方式的共同作用结果，并据此提出了著名的b a 演化模型。b a 模型的算法 描述如下： i ) 初始条件：给定0 个节点开始。 i i ) 增长：在每个时间步增加一个新的节点和m ( m n o ) 条边。 i i n 择优：新节点按照概率 ( ) = 意 ( 1 1 ) 厶j 。y j 来选择与原有节点i 相连，其中是节点i 的度。后经过理论与模拟实验证明增长和择优 这两种机制对于构造无标度分布的网络缺一不可【1 6 】。继b a 网络模型之后，又有大量 一5 加权复杂叫络演化机制及若十动力学行为研究 的扩展模型被学者们提出，他们试图通过这些模型来研究真实世界网络的形成的各种 机理。 图i 3幂律分布与b a 模犁网 f i g 1 3s c a l e f r e ed i s t r i b u t i o na n db am o d e l 引自文献4 7 1 2 2 平均最短距离 网络中两个节点的距离屯定义为连接这两个结点的最短路径的边数。而所有节点 间距离的最大值定义为网络的半径( n e t w o r kd i a m e t e r ) 。面网络的平均最短距离( a v e r a g e p a t hl 锄g t h ) 是指网络中任意两个节点之间距离的平均值，即 2 而与；东奶 ( 1 2 ) 研究发现，大多数真实网络都具有较小的平均最短距离。比如：对于有1 5 万个节点 的w w w 网，它的平均最短距离约为3 1 。一般地，在网络平均度 一定的前提下， 平均最短距离与网络规模的对数成正比。 1 2 3 簇系数 簇系数也称作集聚系数( c l u s t e 咖gc o e f f i c i e n t ) 1 5 ，它主要是用来衡量网络集团化程 度，是网络定义中的一个重要度量参数。在社会网中，集团通常指朋友圈或熟人圈； 一6 一 大连理上大学博l j 学位论文 在经济合作网中通常指一些经济合作联盟，比如欧盟、东盟等。集团内部的成员往往 相互熟悉或合作密切，为衡量这种集群现象，科学家们提出了簇系数的概念。节点i 的 簇系数e 定义为节点i 的邻接点( 即节点i 直接相连的节点) 之间实际存在的边数与所有可 能边数的比值，表达式为 a 2 南0 3 ) 其中，表示节点i 的度，岛表示节点i 的邻接点之间实际存在的边数。而整个网络的簇 系数定义为所有节点簇系数的算术平均值。表示为： c 2 专a ( 1 4 ) 其中，为网络规模。真实网络往往具有较大的簇系数和较小的平均最短距离，较大 的簇系数是指与随机网络相比而言。从这点上我们可以说明真实网络不是完全的随机 网。 如果一个网络同时具有较小的平均最短距离和较大的簇系数，我们把这种特性定 义为网络的“小世界效应”( s m a l l - w o r l de f f e c t ) 1 5 】。 1 2 4 度度相关性 度分布、簇系数、平均最短距离是衡量网络最基本结构特性的三个参数。除了这 三个重要的参数外，网络还有其它一些特征度量标准。比如度度相关性、簇度相关性 等。 度度相关性( 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 2 6 2 7 等人利用节点 的一阶邻接点的平均度( 也称最近邻居平均度) k 。与该节点的度七之间的关系来描述度度 相关性。一阶邻接点的平均度定义如下 其中r t 是i 的邻接点集。 。j = i 1 - k j “j e f 。 7 一 ( 1 5 ) 加权复杂嘲络演化机制及若十动力学行为研究 如果惫。是随k 递增的曲线，则网络是度度正相关的：当网络是度度负相关的 则。是随后递减的曲线。n e w m a n 2 8 ，2 9 等人进一步给出了计算边的两端节点的度 的p e a r s o n 相关系数( a s s o r t a t i v i t ye o e t i i c i e n t ) r n - 玎以描述网络的度度相关性，相关系数r 的 定义如下： m - 1 j i k i 一【m - 1 瓴+ ) 2 r = 面忑霜西啊f 面置噩丽 o 6 其中五，觑表示第i 条边的两个端点j ，枷冉度，m 表示网络的总边数，相关系数r 的取值范 围为：一1 r o ) 代表相 邻节点问的边权。权重可分为相异权( d i s s i m i l a r i t yw e i g h t ) 和相似权( s i m i l a r i t yw e i g h t ) 两 种。相异权是指权重越大两点间的关系越疏远或距离越大；在相似权中，权重的含义 与相异权正好相反，权重越大表示两点间的关系越亲密，距离越小。在本文的后继工 作中，除非特殊说明，主要以相似权为标准，即0 表示两节点无连接。以下我们介绍有 关加权网的度量： 1 3 1 1 点权，点权分布，单位权 在加权网中，加权邻接矩阵每个元素存放着两个节点间的边权( e d g e w e i g h t ) ，用来 表示两个节点间连接的紧密程序。节点强度或点权( n o d es 仃e n g t h ) 的则定义为： 8 i = 蚴 j r l ( 1 9 ) 其中n 是节点i 的近邻集。点权集中了节点的邻居信息和该节点所有连接边的权重。当 网络退化为一个无权网时，某节点的点权和该节点的度相等即s 。= 。如果用 表 示网络边权的平均值，则度为k 的节点权和度之间有如下关系：s k = 缸。 同样，与度分布定义相似地，我们也可以定义点权分布( s t r e n g t hd i s t r i b u t i o n ) p ( s ) 为 随机抽取一个节点其点权为s 的概率。根据近两年的实证研究【1 8 】表明，网络中的点权 和边权分布也和网络的度分布一样符合幂律分布特