（应用数学专业论文）基于复杂网络的时间离散系统的演化分析.pdf

基于复杂网络的时间离散系统的演化分析 基于复杂网络的时间离散系统的演化分析 摘要 自然世界和人文世界中都存在着大量的复杂系统，而复杂网络是用来描述从 技术到生物乃至社会各类开放复杂系统的有力工具之一，因此人们致力于揭示复 杂网络的拓扑结构和功能的形成机制、演化规律、临界相变和动力学过程，从而 进一步研究复杂系统。 本文主要从两个角度讨论了基于复杂网络的时间离散系统的演化过程。 第一，网络自身是随时间的改变而生长变化的，即点或者边在生长。这里主 要讨论了一类基于b a 模型生成机理的特殊的生长网络模型，模型简单但应用非 常广泛。从理论的角度利用率方程方法计算了该生长网络模型的度分布，得知其 是节点度分布符合幂律分布的无标度网络，幂指数为2 。阐明了这个生长网络模 型与b a 模型由于拓扑结构的不同而造成宏观性质的差异，并将这个模型应用于 高校人才吸引网络，利用s p s s 和m a t l a b 模拟仿真说明了该生长网络模型中节点 正r 度的数学期望关系式e ：= 竺f 的j 下确性及生长网络模型的有效性。 。 “ 第二，网络自身不发生变化，即点或者边不生长，但网络中节点间相互产生 影响，研究了节点随时间演化的动力学过程。首先基于广义合作网络理论建立了 企业竞争网络，以企业竞争网络和投资为载体在相应的数学建模中考虑到了非线 性和多维性等因素得到了一个时间离散的非线性动力学模型： x f ，一+ 1 一( 1 一r ) x f ，一 + 善曙m ( 1 - x l n b ) 】 基于李亚普诺夫直接法和不动点分析法对模型中企业个体投资行为的同步稳定 性做出分析，分析得到了同类企业的投资行为是否保持同步稳定增长与企业竞争 对手的数量( 即节点的度) 以及刺激因子有关。并以该投资动力学模型的二维和 三维系统为例对不动点的稳定性做出具体分析验证。结果还表明当同类企业的投 资行为不再保持均衡态势时，参与竞争的双方或三方，在不同初始投资额度的条 件下，一方的投资竞争力会迅速上升，而其他方的投资竞争力会迅速下降。最后 将控制自然系统的自适应控制方法应用于二维离散系统，从经济学的角度对控制 基丁复杂网络的时间离散系统的演化分析 结果进行了解释，从而为企业的投资决策提供有益参考。 关键词：复杂网络无标度网络生长网络投资竞争同步稳定性 青岛科技人学研究生学位论文 e v o l v l n ga n a iy s i s0 fd i s c r e t e t i m e s y s t e m e sb a s e do nc o m p l e xn e t w o r k s a b s t r a c t t h e r ea r eam a s so fc o m p l e xs y s t e m si nt h ew o r l do fn a t u r ea n ds o c i e t y c o m p l e x n e t w o r k sa r eo n eo fu s e f u li n s t r u m e n t st od e s c r i b ea l lk i n d so fo p e n e dc o m p l e x s y s t e m sf r o mt e c h n o l o g y , b i o l o g yt os o c i e t y t h e r e f o r e ，p e o p l ed e d i c a t et h e m s e l v e st o t h ef o r m a t i o nm e c h a m s mo ft o p o l o g i c a ls t r u c t u r ea n df u n c t i o n ，t h er u l e so fe v o l u t i o n ， c r i t i c a lp h a s ea n dt h ep r o c e s so fd y n a m i c so fc o m p l e xn e t w o r k s ，i no r d e rt of u r t h e r r e s e a r c hc o m p l e xs y s t e m s i nt h i sp a p e rt h ee v o l u t i o no fc o m p l e xn e t w o r k si sd i s c u s s e df r o mt w oa s p e c t s t h em a i no o n t e n t sa r eo u t l i n e da sf o l l o w s ： f i r s t l y , t h en e t w o r ki t s e l fi sc h a n g i n go v 钌t i m e ，s u c ha st h eg r o w t ho fn o d e so r e d g e s h e r e ，o nt h eb a s i so ft h et w og r o w t hc h a r a c t e r so fb am o d e l ，as p e c i a lg r o w t h n e t w o r ki si n t r o d u c e d ，w h i c hi ss i m p l eb u tw i d e l yu s e d i t sd e g r e ed i s t r i b u t i o ni s c o m p u t e dt h r o u g hr a t ee q u a t i o nm e t h o da n di sp r o v e dt h a ti to b e y sp o w e r - l a wf o r m w i t l lt h ee x p o n e n t2 t h e nt h ed i s c r e p a n c yo fm a c r o s c o p i c a l l yp r o p e r t yb e t w e e nb a a n dt h em o d e li sa n a l y z e da sar e s u l to ft h ed i f f e r e n c eo ft h e i rt o p o l o g i c a ls t r u c t u r e t h em o d e lw i l lb ea p p l i e dt ot h en e t w o r ko fu n i v e r s i t ya t t r a c t i n gt a l e n t s s i m u l a t i o n s o b t a i n e df r o ms p s sa n dm a tl a bs h o wc o r r e c t n e s so ft h em a t h e m a t i c a le x p e c t a t i o n f o r m u l ae 鼻翌a n da v a i l a b i l i t yo ft h em o d e l 。 气 一 s e c o n d l y ，t h en e t w o r ki t s e l fd o e sn o tc h a n g e ，b u tt h e r ei sa ni m p a c to ne a c ho t h e r a m o n gt h en o d e so fn e t w o r k t h ed y n a m i cp r o c e s s e so ft h en o d e sa t es t u d i e do v e r t i m e f i r s to fa l l ，t h ec o r p o r a t i o nc o m p e t i t i o nn e t w o r k sa r es e tu po nt h eb a s i so ft h e g e n e r a l i z e dt h e o r yo fc o o p e r a t i o nn e t w o r k s c o r r e s p o n d i n g l y ，ad y n a m i ci n v e s t m e n t m o d e l 工z ，露+ ，；( 1 - y ) x r 。矗+ 考【薹( 口盯( 1 - x , n ) 戈，川) 】 i se s t a b l i s h e dt a k i n gi n t oa c c o u n ts u c hf a c t o r sa sn o n l i n e a ra n dm u l t i d i m e n s i o n a l m 基于复杂网络的时间离散系统的演化分析 n a t u r e s l y a p u n o vf u n c t i o na n df i x e d p o i n ta n a l y s i sa r ea p p l i e dt oa n a l y z et h es t a b i l i t y o ft h es y n c h r o n o u sb e h a v i o ra b o u tc o r p o r a t i o ni n v e s t m e n t t h er e s u l t ss h o wt h a ti t r e l a t e st ot h en u m b e ro fb u s i n e s sc o m p e t i t o r s ( o rt h ed e g r e eo fn o d e s ) a sw e l la s s t i m u l a t i n gf a c t o r t 0 d i m e n s i o n a la n dt h r e e d i m e n s i o n a ls y s t e m sa r et a k e na s e x a m p l e st os p e c i f i c a l l yv e r i f yt h ef o r m e rr e s u l t a sa n o t h e rr e s u l t ，o nt h ec o n d i t i o no f d i f f e r e n ti n i t i a li n v e s t m e n ta m o u n t ，w h e nt h ei n v e s t m e n tb a l a n c eo fs i m i l a re n t e r p r i s e s c a n tb ek e p t ，t h ec o m p e t i t i v e n e s so fo n ec o r p o r a t i o nw i l lr a p i d l yi n c r e a s e ，w h i l et h e o t h e r sw i l ld r a m a t i c a l l yd e c l i n e f i n a l l y , t h ea d a p t i v ec o n t r o li sa p p l i e dt o t w o d i m e n s i o n a ld i s c r e t e t i m es y s t e m s t h ec o n t r o lr e s u l t sa r ee x p l a i n e df r o mt h e a n g l eo fe c o n o m i c s ，w h i c hc a nb ep r o v i d e db e n e f i c i a lg u i d a n c ef o rt h ei n v e s t m e n t s t r a t e g yo fe n t e r p r i s e k e yw o r d s ：c o m p l e xn e t w o r ks c a l e f r e en e t w o r k g r o w t hn e t w o r k i n v e s t m e n tc o m p e t i t i o n s y n c h r o n o u ss t a b i l i t y i v 青岛科技大学研究生学位论文 独创新声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中 不包含其他人已经发表或撰写过的研究成果，也不包含本人已用于其他学位申请 的论文或成果。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了 明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：够姥 日期： 2 洲了年 苦月1 5 n 关于论文使用授权的说明 本学位论文作者完全了解青岛科技大学有关保留、使用学位论文的规 定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文 被查阅和借阅。本人授权学校可以将学位论文的全部或部分内容编入有关数 据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 本人离校后发表或使用学位论文或与该论文直接相关的学术论文或成果时， 署名单位仍然为青岛科技大学。( 保密的学位论文在解密后适用本授权书) 本学位论文属于： 保密口，在年解密后适用于本声明。 不保密口。 ( 请在以上方框内打“) 本人签名： 导师签名： 日期：m 7 年占月j 6 日 日期：弘吣7 年6 月j 5 日 青岛科技人学研究生学位论文 1 1 背景与意义 1 绪论 2 0 0 0 年，爱虫病毒侵犯了英国议会的电子邮件系统。同年，一场暴风雨袭击 了芝加哥，致使机场关闭，影响了全美航班。2 0 0 3 年，美国电网的大崩溃事故让 纽约人感到惶恐不安【1 1 。同年，非典型性肺炎对中国宏观经济和人类的生命安全 都产生了巨大的负面影响。当前，甲型h 1 n 1 流感由墨西哥发端正全球蔓延，引起 人类的高度重视。这些现象都可以自然的提出如下问题：计算机病毒是如何在互 联网上传播的? 大城市的交通堵塞问题是如何引起的? 局部故障是如何触发大 面积停电事故的? 各种传染病( 艾滋病、非典、甲型h 1 n 1 流感等) 是如何在人类 和动物中流行的? 这些问题尽管看起来各不相同，但每一个问题都涉及到复杂网 络。复杂网络的研究已经成为当前复杂性科学和信息科学等多个学科共同的研究 热点【2 。5 1 。其研究者来复杂性科学、非线性科学、电路与系统、计算机科学、控制 理论、理论物理、数学、生物学等各个学科领域。随着复杂网络的小世界效应及 无标度性征的发现，对复杂网络的定性与定量的深入探索、科学理解，将成为二 十一世纪网络时代复杂性科学研究中一个极其重要的挑战性课题【2 6 l 。 同时，复杂网络的研究也呈现出非常广阔的应用前景【7 1 。它可以应用于保护 许多现实系统的正常运行。现在，人们对因特网、电力网和食物链等网络的依赖 程度同益增强，那么这些网络的可靠性就成为人们关注的问题。因此加强复杂网 络稳定性的研究，对于设计某些技术网络和保护基础设施网络具有重要的意义。 复杂网络理论可以应用于社会领域。例如：通过构建社会中人与人的关系网 络模型去研究传染病在人群中的流行，以及进一步去描述这种传播行为，揭示它 的特性，寻找出对该行为进行有效控制的方法等。 复杂网络理论还可以应用于经济、管理领域。利用复杂网络理论了解公司、 产业与经济之间的连接方式，有助于预防大规模的经济衰退。另外，扩散理论的 研究可应用于市场营销领域，出于各种商业目的，营销人员需要引发流行而不是 遏制流行，于是他们提出了所谓的病毒式营销。 复杂网络的广泛的应用前景为系统科学的研究开拓了视野，提供了全新的视角。 以复杂网络形式研究复杂系统，可以加深人们对系统结构的深入了解。复杂网络研 究得到的结论还可以被用来具体指导各种现实网络模型的构建和对网络中各种动力 基于复杂网络的时间离散系统的演化分析 学行为的研究，并以此推动对复杂网络的进一步研究与应用。复杂网络的深入研究 可以使我们更好地了解和解释现实世界的复杂网络，而了解自然、了解我们所生存 的现实世界是科学研究的最主要目的之一。 1 2 复杂网络的基本概念 近年来，人们在刻画复杂网络结构的统计特性时提出了许多概念和方法，其 中有三个基本的概念：度分布( d e g r e ed i s t r i b u t i o n ) 、群集系数( c l u s t e r i n g c o e f f i c i e n t ) 和平均路径长度( a v e r a g ep a t hl e n g t h ) 在复杂网络的研究中扮演了重 要的角色。 ( 1 ) 节点度分布 网络中节点度( d e g r e e ) 的概念是指与该节点相连接的边的条数，度是描述局 域特征的基本参数。 假i 发p k ( k - l 2 ，) 为网络中任意一点度数为k 概率。对于任意一个给定的网 络，玩可用节点度的直方图来表示，这个直方图就是网络的节点度分布。 度分布在某种程度上决定了复杂网络上的动力学行为。网络中节点度分布的 计算方法归纳起来可分为两类：一类是动力学方法，有平均场方法和率方程方法； 另一类是概率论方法，有主方程方法和马氏链方法。 ( 2 ) 群集系数 群集系数( c l u s t e r i n gc o e f f i c i e n t ) 是用来衡量网络节点类聚情况的参数，例 如一个人的朋友中相互也可能是朋友。 定义( n e w m a n ，s t r o g a t z 和w a t t s f s l ) ：网络三角形指网络中包含的两两相连 的三个顶点的集合。节点关联三点组指：一个节点有边与其他两个节点相连的三 个节点的集合。群集系数为： c = 3 网络中三角形的个数 虿丽面匡面丽研面 分子乘以3 是因为每个三角形在顶点关联三点组的个数中需要计算三次。 举例说明，如图1 - 1 所示： 2 ( 1 1 ) 青岛科技大学研究生学位论文 图1 1 群集系数c 定义的说明 f i g 1 1t h ee x p l a n a t i o nt ot h ed e f m i t i o no fc l u s t e r i n gc o e f f i c i e n t 用定义计算为c = 等寺 ( 3 ) 平均路径长度 网络中两个节点f 和之间的距离吒定义为连接这两点的最短路所包含的边 的数目。把所有的节点对距离取平均值定义为网络的平均路径长度三，即 扛而矗f ， ( 1 2 ) n 州+ q 包 其中为网络节点数，式( 1 2 ) 中包含了节点到自身的距离。网络的平均路径长 度也称为网络的特征路径长度( c h a r a c t e r i s t i cp a t hl e n g t h ) 。 1 3 复杂网络模型 复杂网络根据拓扑结构的不同可以分类为规则网络，随机网络，小世界网络， 无标度网络等。常见的规则网络有全局耦合网络( g l o b a l l yc o u p l e dn e t w o r k ) 、最 近邻耦合网络( n e a r e s t n e i g h b o rc o u p l e dn e t w o r k ) 和星形耦合网络( s t a rc o u p l e d n e t w o r k ) 。与完全规则网络相反的是完全随机网络( c o m p l e t er a n d o mn e t w o r k ) ， 随机网络是由一些节点通过随机布置的连接而组成的复杂网络，其中一个典型的 模型是e r d o s 和r e n y i 于5 0 多年前开始研究的e r 随机网络模型【9 1 。下面主要是 对小世界网络模型与无标度网络模型的简要介绍。 1 3 1 小世界网络模型 规则网络虽具有群集性但平均路径长度却较大，而随机网络则正好相反，具 有小的平均路径长度，但群集系数却相当小。作为从完全规则网络向完全随机图 的过渡，w a t t s 和s t r o g a t z 于1 9 9 8 年引入了一个单参数的小世界网络模型，称为 w s 小世界模型i 姗。w s 小世界模型的构造算法如下： ( 1 ) 给定规则网络：设节点总数为，每个节点与它最近邻的k = 獗个 结点相连线的一维有限规则网，通常要求n k 1 ； ( 2 ) 改写旧连线：以概率p 将规则网络的每条旧连线重新布线，方法是将 该连线的一个端点随机地连接到一个新位置上，但需要排除自身到自 身的连线和重复连线。 3 基于复杂网络的时间离散系统的演化分析 由于随机性的缘故，这些改写的连线可能会出现远距离的连线，它们被称为 捷径( s h o r tc u t s ) 。显然，当p = 0 时仍为给定的规则网络，当p = 1 时，我们将得 到一个特殊的随机网络。随着p 的增加，人们可以看到从规则网络向随机网络的 变化过程。这样得到的小世界网络模型同时具有大的群集系数和小的平均最短路 径长度，反映了实际网络所具有的一些特性，例如朋友关系网中，每个人与他周 围的人认识是很自然的事，而也存在一些机会有人与住得很远的人相互认识。这 种情形好比w s d , 世界模型中通过重新连线产生的远程连接。 下面介绍小世界网络模型1 1 1 的一些统计性质。 ( 1 ) 群集系数 w s 小世界模型的群集系数为 c ( p ) = 砸3 ( k 面- 2 ) ( 1 一p ) 3 。 ( 1 3 ) ( 2 ) 度分布 对于基于“随机化重连 机制的w s 小世界模型，当k k 2 时有 p c 七，= ( j z 2 ) o p ，n p ( r 2 ) - n ；篇e 一雎2 ， c 1 4 ， 当七 元2 苫名( 1 8 ) 为其外耦合矩阵a i + c a 的特征根。如果下面的n 一1 个胛维的线性时变系统是 指数稳定的： w ( k + 1 ) to f ( s ( k ) ) 五th 七) ，k12 ，n ， 5 ( 1 9 ) 基于复杂网络的时间离散系统的演化分析 那么网络的同步流形( 1 7 ) 也是指数稳定的。 定理1 3 【1 3 l 对于离散动态网络( 1 6 ) ，如果 _ 1 - e - m 1 蜂，(110)c_ ， l1 ftfl 厶f 那么网络的同步流形( 1 7 ) 指数稳定的。 对于连续时间时不变耦合动态网络，如果内部耦合矩阵为单位阵，那么只 要耦合强度足够大必可以使得网络实现同步。但在离散时问域上分析网络的同步 性能时发现，即使节点间的内耦合矩阵为单位矩阵，离散耦合网络也必须满足一 定的条件，才可能找到适当的耦合强度使得网络同步流形稳定。 1 4 1e r 随机网络的同步 考虑一个由n 个相同节点组成的离散时间e r ( e r d o s - - r e n y i ) 随机网络的同 步( r a n d o m g r a p hn e t w o r ks y n c h r o n i z a t i o n ) 问题【1 6 1 7 1 ，其模型为 i 以= 厂( 工：) + c 罗a 可，联) ，i 一1 弘，n ， ( 1 1 1 ) 一 其中，节点之间的连接概率为0 p o 是网络耦合强度，a = 丢，这里t 是第f 个节点的度数， f _ k ； f - j r 牡 1 琏街 iof 不连街 是网络的内耦合矩阵 如果下面的条件成立，那么这个e r 随机网络的同步流形是稳定的f 1 8 1 1 - - e - # c 生竺，( 1 1 2 ) c 一， l 1 1 z ， 灭2元n 其中，0 一厶 如墨s 以是网络外耦合矩阵的特征根，是，( ) 的最大l y a p u n o v 指数当较大时，这个条件近似成为 1 一e u1 + e 一 1 2 4 0 一p ) ( n p ) c ：= = = ：= = = = = = = = = = 1 一e ，与全局耦合( 混沌) 网络的结果一 6 青岛科技大学研究生学位论文 致【1 9 1 。 ( 2 ) 当0 k = 坳和c = 1 ，上述条件可改为k 4 e 知，与网络的尺寸无关， 表明只要耦合强度足够大，这种e r 随机( 混沌) 网络总能达到同步。 因为随机网络的形成依赖于概率，许多结果都不能用确定性的公式写出来， 通常只能用随机分析和仿真来验证。 1 5 论文研究的目的、主要内容及研究思路 复杂网络的研究主要集中在三个方面： 一、网络生成机制及自身的演化模型，即通过生成机制建立模型，模拟真实 网络行为。二、复杂网络上的动力学过程，如复杂网络上的同步，疾病、信息、 知识、舆论如何在复杂网络上的传播等等。它超越了网络拓扑结构，掌握建立在 这些网络上的系统的工作方式和机理，认识复杂系统内部节点的动力学过程。三、 复杂网络的稳定性，研究限制条件对网络几何特性的影响，如复杂网络承受意外 故障和蓄意攻击的能力等。 本文的研究主要集中在第一、二方面，即网络的生成机制与自身的演化模型 及网络上的动力学过程。各章概要如下： 第一章为绪论。论述了本文选题的研究背景，在此基础上阐述了复杂网络的 广阔的应用前景。并对复杂网络的基本概念、常见模型以及时间离散耦合网络的 研究现状进行了综述，进而给出本文的研究内容及章节安排。 第二章讨论了一类基于b a 模型生成机理的特殊的生长网络模型，该生长网 络模型简单但概括面广，可作为b a 模型的扩展模型；分析了生长网络模型与b a 模型拓扑结构的异同及原因；介绍了节点度随时间的演化可能得到的数学期望公 式，给出了不同情况下的意义：还将其应用于高校人才吸引网络通过模拟仿真进 行验证。 第三章我们将利用企业之间的共同因子产品作为关联建立企业竞争网络，以 企业竞争网络和投资为载体在数学建模中考虑到了非线性和多维性等因素得到 一个时间离散的非线性动力学模型。基于李亚普诺夫直接法和不动点分析法对模 型中企业个体投资行为的同步稳定性做出分析，分析得到同类企业的投资行为是 否保持同步稳定增长与企业竞争对手的数量( 即节点的度) 以及刺激因子有关， 7 基于复杂网络的时间离散系统的演化分析 解释了其经济学意义。另外将自适应控制方法应用于该模型，得到了模型中一个 参数的控制矩阵。 第四章是针对第三章的投资模型进行特例分析。首先介绍了二维时间离散的 投资模型的一些结论并着重对三维时间离散的投资模型运用稳定性理论以及非 线性方法进行分析，通过对两个模型的结论比较验证第三章的结论。同时将第三 章得到的控制矩阵应用于对二维时间离散的投资模型，根据计算以及模拟给出了 控制强度的选取方法。最后从经济学角度对控制结果进行了解释，得到了一些有 用结论，从而为企业的投资策略提供了有益的理论参考。 第五章概括和总结了本论文的工作，同时展望了今后与本课题有关的研究内 容和方向。 8 青岛科技大学研究生学侥论文 2 1 b a 模型 2 基于离散时间的生长网络模型 第一个无标度网络模型是由b a r a b 缸i 和a l b e r t 1 2 】提出的b a 模型，该模型是由 网络的生长性( g r o w t h ) 和择优连接性( p r e f e r e n t i a la t t a c h m e n t ) 两部分组成，具 体算法描述如下f 1 2 】： 1 ) 生长性；开始给定i 1 。个结点，在每个时闯步重复增加一个新节点和 m ( ms ) 条新连线； ( 2 ) 择优连接性：新节点按照择优概率兀( 屯) 一k i k ，选择旧结点f 与之连 ， 线，其中k ；是 舀节点 的度数。 图2 1 显示所= 一2 时的b a 模型的演化过程。 | 飞 国伪 蹯曝醒鼢珠 僻卿m 俩 胬2 - 1b a 模型的演化过程 f i g 2 1i l l u s t r a t i o no ft h eg r a p he v o l u t i o np r o e e s sf o rt h eb a m o d e l 下面介绍b a 模型的一些统计性质： ( 1 ) 度分布 b a 模型生成的网络的度分布是幂律分布，因为网络中的每一个节点有k 条 边的概率p c k ) 一2 m 2 k 一，如图2 - 2 所示。 9 譬冈柳 基于复杂网络的时间离散系统的演化分析 图2 2b a 无标厦网络的度分布 f i g 2 2t h ed e g r e ed i s t r i b u t i o no fb a m o d e l ( 2 ) 平均路径长度 b a 无标度网络的平均路径长度【刎为 三! 堡壁，( 2 1 ) l o g l o g n 平均路径长度比较小，表明该网络具有小世界特性。 ( 3 ) 群集系数 b a 无标度网络的群集系数【2 1 】为 c ：她f 1 n ( 玛一上 咝， ( 2 2 ) 4 ( m di 、m 7 m + 1t 当网络规模充分大时，b a 无标度网络不具有明显的聚类特征。 b a 模型的提出是复杂网络的又一重大突破，标志着人们对客观世界认识的深 入。同时也出现了推广b a 模型的一个小高潮，原因是b a 模型的度指数( d e g r e e e x p o n e n t ) 是一个常数3 ，而大多数实际网络的度指数在( 1 ，4 ) 之间。基于b a 模型 的内在生成机制，本章讨论了一个特殊的生长网络模型，该生长网络模型简单但 应用却十分广泛。 2 2 基于离散时间的特殊生长网络模型 2 2 。1 生长网络模型的介绍 ( 1 ) 生长性考虑具有个点构成的网络，网络中各点互不相连但每点具有 1 0 青岛科技大学研究生学位论文 一定的顶点度，每一时间步长，有一条新边进入此网络，与网络中的某点相连( 见 图2 3 ) 。例如个生产同种产品的企业，企业即为节点，顾客选择这个企业的 产品就相当于与这个企业做了一个连接，企业的节点度为选择这个企业产品的顾 客数目。而企业之间并无连接，但他们之间存在制约关系，所以这个网络也可看 作是一个系统。 ( 2 ) 择优连接性一条新边与一个节点相连的概率与这一节点的顶点度成正 比。例如一个企业的顾客数目越多，其他顾客选择这一企业的概率越大，这在实 际生活中是合理的。 图2 - 3 生长网络模犁结构示意图 f i g 2 - 3t h eg r a p ho fg r o w t hm o d e l 用这个生长网络模型描述聚集过程【2 2 】，因它比较简单但却有广泛的代表性。 这些点可以代表候选人，一个选举者将手中的票投给一个候选人，意味着在该候 选人节点连出一条边，节点的度也就是候选人得票的数量。另外第一轮投票后的 得票的数量，将影响下一轮选举者的投票趋向；这些点可以代表企业，不同的企 业对人才有着不同的吸引力，企业中优秀人才的多少对后期人才对该企业的选择 产生一定影响，等等。 2 2 2 生长网络模型与b a 模型比较 这个生长网络模型虽然与b a 模型有着相同的生长机制但在拓扑结构上又不 同于b a 模型，首先网络模型内部各点互相不连接，且边的定义很特别，它只与 网内一点连接，即在这个网络中边只有一个端点，这与传统的网络模型是有所区 别的。另外在生长过程只添加新边而不添加点，即只是边在生长而点不生长( 见 图2 3 ) 。根据第一章中平均路径长度和聚类系数的定义可知这个模型不存在计 算平均路径长度和聚类系数问题。但每一节点的度是存在的，因此可以计算它的 度分布，这罩采用率方程方法( r a t e e q u a t i o na p p r o a c h ) 进行计算1 2 3 1 。 ， ，1 = 兰生= 【a 1 巩- l a k m 】+ 哦1 ， ( 2 3 ) “ 式中：盈，为初始条件；帆为f 时刻度为k 的节点数目； 为新边与度为k 的节 1 1 基于复杂网络的时间离散系统的演化分析 点连接的概率。 对上述模型，t 时刻总度数为f ，引入的新点与原生长网络模型中的度数为k 的点连接的概率为生。这时，相应的率方程为 t 警书一) n k - 1 巩m ， 按照大数定律f 2 4 】有眠p ) 一魄，则 n k = 【( 七一1 ) 加k - 1 一a n k l + 哦1 ， 化简得 k - i n k 2 。k + l n k - 。 由于碍：i 1 ，所以 驴南以。2 。 可见生长网络模型中度为k 的节点数大致服从幂律分布，所以这个生长网络 模型与b a 模型一样是无标度网络，这主要是由于它们具有相同的生长机制。但 这个特殊的生长网络模型度分布服从幂指数为2 的幂律分布，而b a 模型度分布 服从幂指数为3 的幂律分布，这种宏观性质的差异主要是由于模型拓扑结构的不 同造成的。该生长网络模型可以视为b a 模型的扩展模型。 2 2 3 生长网络模型的演化分析 本章介绍的生长网络模型相对简单，可能不能精确描述所概括的问题，但如 何对模型展开演化分析是看模型是否有效的关键。 设初始时刻t of i r 0 ，由于每一时刻有一条新边进入网络，所以r 时刻生长网络 模型的总度数为f 。按照择优连接的思想，设度数为k 的点得到新边的概率与度数 l k 成线性关系，设为! 。在t + l 时刻节点s 度数要为k ，可由两种情形得到：在时 t 刻f 时葶点的度已经为k ，则要求其得不到新边，而若j 点的度为k 一1 ，则要求其 得到新边。设砭，为点s 在f 时刻度为k 的概率。可由主方程法( m a s t e r - e q u a t i o n a p p r o a c h ) 2 5 1 建立方程： 青岛科技大学研究生学位论文 掰= 臣，芦( k - f1 ) + p l ( 1 一争) ， ( 2 4 ) 在文献【2 2 】中推演出了网中任何一点在任何时间r 时的数学期望，以计算，时 刻此点可能吸引到的度数。记e 一点s 在f 时的数学期望。我们重复文献【2 刁的关 于数学期望的推导过程，据式( 2 4 ) ，有： e t 4 1m 薹张一毫c 争+ 毫娥。0 一争 2 詈【荟 一1 ) + 善娥s p 一七) 】 = - 【1 t ( f + 1 ) + 2 乏。( f + 1 ) + + ( 卜1 ) o + 1 ) + 屹( f + 1 ) 】， = 孚套 ：= t + - 3 e ： 依次诀代可得： t + l = t + ，l 百t ”再t o + 2 下t o + 1 e ，= 等口， 上式近似可写成 e ，2 丢础， 或 e = 瞰+ 2 艺+ + 七。恐+ 硌】。 o 如果在初始条件中，对于点s ，只是硪- 1 ，其他均为o ，所对应的度数七记 做屯，又将有 弘缸 眨5 ， 从上式中我们可以看到以下规律： 生长网络模型中的每个节点都以看作一个“吸引核 ，蔓表示它的初始吸引 t o 能力，对最后的结局起着关键作用。，是f 时刻模型中总的度数，可理解为总的聚 基于复杂网络的时间离散系统的演化分析 集量。式( 2 5 ) 表明每个点可能吸引到的聚集量，为总聚集量的! 。可以理解笠 f of o 的值越大，节点s 可能吸引到的聚集量就越大。这也就是富者更富( t h er i c hg e t r i c h e r ) 的现象，例如一个人在获得众多荣誉之后，再获得其他荣誉的可能性更大。 经济领域中，布赖恩阿瑟( b r i a na r t h u r ) 提出的收益递增论( i n c r e a s i n gr e t u r n ) f 御，也可用式( 2 5 ) 这样机制进行解释。 2 2 4 生长网络模型的应用 现在越来越多的项尖人才愿意选择高校作为发展基地。影响人才选择高校的 因素很多，例如；地理位置，学术氛圉等等。抛开地理位置，我们去考虑如何去 衡量一所高校的学术氛围，衡量的因素很多。但其中一个非常重要因素，那就是 在这所高校里有多少优秀的人才。容易理解一所高校越好，它拥有的优秀人才就 会越多，那它对人才的吸引力也就越大。由此，考虑将该生长网络模型应用于高 校对人才的吸引网络。 我们以高校作为节点，每个节点具有一定的初始顶点度，代表高校此时拥有 人才的数目。人才选择了这所高校就意味着与这所高校建立了一个连接。人才选 择一所高校的概率与高校人才的多少成正比。为便于取得数据，本文以高校中具 有博士学位的教师作为是否是人才的衡量标准。 在初始条件中，l o 的意义是初始时刻高校教师中具有博士学位的教师数目， f 表示网络模型演化到t 时刻时高校教师中具有博士学位的数目。k 。表示节点j 在 初始时刻具有博士学位教师的数日。譬表示高校5 经过演化后在t 时刻具有博士 五r 学位的教师数目的数学期望。从e ：= 量f 可以看出：高校s 中具有博士学位教师 。 f o 的数目与时间成j 下比，与高校初始的博士数目成正比( 数据来源：0 4 年与0 6 年 的中国大学评价研究报告) 。下面通过通过具体数据对模型来做模拟仿真。 表2 1 六所高校在2 0 0 4 年与2 0 0 6 年具有博士学位的教师数目 4 1 1 赢 一一 o。 谜 中国海洋大复虽煳 山表筛范大蕾融燃烟台艚 潍甥学院， 学学 2 g 0 4 军矿5 5 0 , 7 0 7 2 8 q , ，3 8 9 , ；1 5 盼l l 2 0 0 6 年# 5 7 弦8 m p3 孓p 4 2 2 0 归 1 2 鼢 1 4 青岛科技大学研究生学位论文 可以看出，= 2 1 8 8 ，f = 2 5 0 8 ，用式( 2 5 ) 计算可以求出各点的数学期望： 砰5 0 8 = 6 3 0 4 4 ，霹5 = 8 10 4 0 ，霹5 = 3 2 0 9 5 ，霹5 0 8 = 4 4 5 8 9 ， 霹5 明= 1 7 1 9 4 ，露5 0 81 2 8 3 8 我们用s p s s ( s t a t i s t i c a lp a c k a g ef o rt h es o c i a ls c i e n c e ) 将网络模型中各节点 的数学期望与各节点的实际度数进行线性回归分析，所得结果如下： m o d e ls u m m a r y m o d e lrr s q u a r ea d j u s t e drs q u a r es t d e r r o ro ft h ee s t i m a t e 1 9 9 3 ( a ) 9 8 69 8 3 3 4 8 7 2 3 0 c o e f f i c i e n t s ( a ) u n s t a n d a r d i z e d s t a n d a r d i z e d m o d e l t s i g c o e f f i c i e n t sc o e f f i c i e n t s bs t d e r r o rb e t a 1 c o n s t a n t1 4 0 7 82 9 2 1 44 8 26 5 5 x1 0 3 40 6 19 9 31 6 9 3 70 0 0 其回归方程为：y = 1 ，0 3 4 x 一1 4 ，0 7 8 ，y 代表网中各节点度数的数学期望，x 代表各节点的实际度数。 利用m a t l a b 做模拟仿真( 见图2 4 ) 网中各点的实际度数 基丁复杂网络的时间离散系统的演化分析 图2 _ 4 高校人才吸引网络中各节点度与其数学期望的拟合曲线 f i g 2 - 4t h en u m e r i e a ls i m u l a t i o no fn o d e sd e g r e ea n de x p e c t a t i o ni nt h en e t w o r ko f u n i v e r s i t ya t t r a c t i n gt a l e n t s 图2 _ 4 可以说明用实际数据与式( 2 5 ) 计算出来各节点的数学期望可以大致 地吻合。从而，验证了该公式的正确性。虽然实际结果与理论结果有一定的定量 上的差别，这主要是因为近年来具有博士学位的人越来越多，高校新引进的教师 多数都具有博士学位。但是在统计意义上仍不失正确性。 2 3 结语 本章主要讨论了一类特殊的生长网络模型，从b a 模型的生成机理角度重新 考虑了该模型的生长和择优连接两个机制。生长网络模型简单但概括面很广，例 如可描写选举、科学论文的引用、食物源对蚁群蜂群的吸引等等。从理论的角度 利用率方程方法计算该生长网络模型的度分布，分析得到其与b a 模型都是无标 度网络，这是因为它们有着相同的生成机制。但生长网络模型的度分布的幂指数 是2 ，有别于b a 模型，这是因为它们具有不同的拓扑结构而造成这种宏观性质 的差异。 本章还介绍了利用主方程的方法推演出生长网络模型中各节点可能得到的 聚集量。设s 表示网络中某节点，岛是初始时间，k ，是t 。时点s 的顶点度，f 是任 何时间，f 也是此时网络中节点的总度数，或总聚集量，则生长网络模型中各节 ，r 点度的数学期望公式为e ：= 笠f 。其中笠表征点s 初始优势或初始吸引能力， 。t at o 厶 节点可称为吸引核，生可称为吸引系数，它在整个生长网络模型的演化过程中起 f 0 着关键的作用，并决定着最后的结局。 最后将模型应用于高校对人才的吸引网络，利用s p s s 对具体数据得到了线 性回归方程为：y = 1 0 3 4 x 一1 4 0 7 8 ，y 代表网中各点度数的数学期望，x 代表各 点实际度数。利用m a t l a b 进行模拟仿真得到高校人才吸引