（应用数学专业论文）对有向网络理论及应用的一些研究.pdf

武汉理工大学硕士学位论文 摘要 自一些研究者通过实证分析发现许多现实复杂网络具有小世界效应和无标 度特征之后，复杂网络逐渐受到了来自科学各个领域研究者们越来越多的关注， 成为了近年来科学界的一个研究热点。可喜的是，人们对无向网络的拓扑结构 和模型已进行了比较广泛的研究，并取得了许多令人兴奋的成果。其实同无向 网络一样，自然界和社会中也蕴涵着大量的现实有向网络，它们广泛的存在于 科技、信息、生物、社会等领域中。例如，科技领域中的w w w 网、信息领域 中的引文网、生物领域中的食物网及社会经济领域中的货物网等等。然而令人 遗憾的是，至今为止我们还不能找到比较系统地介绍有向网络基本理论的文章 或书籍。鲜有研究者从事有向网络理论及应用的研究，许多人认为有向网络只 不过是无向网络的自然扩充，他们把本属于有向网络的问题统统简化为无向网 络问题，这当然使得我们不能真实地把握这些问题。于是，本文利用复杂性科 学、非线性动力学、统计学、微分学、控制论及矩阵论等知识，借助计算机这 一强大的分析、计算及模拟工具，对有向网络的基本理论及其应用做了如下几 点综述及拓展研究。 i 对有向网络的一些主要的定义、主要静态拓扑特征、一般结构及矩阵理 论傲了比较全面的综述和拓展。特别对有向网络的邻接矩阵、关联矩阵及其应 用进行了较为深入的研究。 2 基于某些现实网络具有等级结构、集团结构及统计意义上的自相似性， 本文以迭代的方式，建立了一个具有确定度分布的有向网络模型。分析了它的 一些拓扑性质，并讨论了它在某些现实有向网中的一些潜在应用。 3 根据因特网、货物配送网等现实网络的特点，在纯b a 模型的基础上提 出了一个有向演化网络模型。特别研究了该模型的度分布，并讨论了它在某些 现实有向网络中的一些潜在应用。 本文的主要创新点如下： 1 以确定的迭代方式构造了一个比较符合食物网等现实系统的有向等级结 构网络模型，解析计算了该模型的度分布等拓扑性质。这个模型克服了随机模 型难以解析的不足，具有重要的理论意义。 2 提出了一个基于b a 模型的有向网络模型，它的出、入度的幂律指数在 区间【2 ，m ) 内连续可调，该模型可以较好的描述因特网等现实系统。 关键词：复杂网络；小世界效应：无标度网络；演化模型；扩展 武汉理工大学硕士学位论文 a b s t r a c t a f t e r f i n d i n gt h es m a l l - - w o r l de f f e c ta n ds c a l e ，f r e ep r o p e r t yo f m a n y r e a lc o m p l e x n e t w o r k sb ye m p i r i c a ls t u d i e s ，c o m p l e xn e t w o r k sh a v eg r a d u a l l ya t t r a c t e dp a r t i c u l a r a t t e n t i o nf r o ma l lf i e l d so fs c i e n c e t h er e s e a r c ha b o u tc o m p l e xn e t w o r k si sb e c o m i n g ah o ti s s u eo v e rr e c e n ty e a r s f o r t u n a t e l y , p e o p l eh a v ec a r r i e dt h r o u g hk i n d so f c o m p r e h e n s i v er e s e a r c h e si nt o p o l o g ys t r u c t u r ea n dm o d e lo fu n d i r e c t e dn e t w o r k s a n dh a v ea t t a i n e dm a n ye x c i t i n gr e s u l t s i nf a c t , t h e r ea r em a n yr e a ld i r e c t e dn e t w o r k s b e s i d e su n d i r e c t e dn e t w o r k si nn a t u r ea n ds o c i e t yw h i c he x i s ti naw i d er a n g eo f t e c h n o l o g y , i n f o r m a t i o n , b i o l o g i c a l ，s o c i a la n do t h e rf i e l d s f o re x a m p l e s ，t h ew o r l d w i d ew e b ( w e bp a g e sa sn o d e s t h eh y p e r l i n k sb e t 、】1 1 e e l ld i f f e r e n tp a g e sa se d g e s , t h e e d g e sa r eo b v i o u s l yd i r e c t i o n a l ) ；t h ec i t a t i o nn e t w o r k ( p a p e r sa sn o d e s ，t h ec i t a t i o n r e l a t i o n s h i p sb e t w e e nd i f f e r e n tp a p e r s a sd i r e c t e de d g e s ) ；t h ef o o dw e bi n e c o s y s t e m ( e a c hs p e c i e si sr e p r e s e n t e da san o d eo ft h en e t w o r k ，ad i r e c t e de d g ei s p l a c e db e t w e e nt w os p e c i e sw h e n e v e ro n eo f t h e mf e e d st h eo t h e r ) ；t h eg o o d sw e b i n e c o n o m yf i e l d ( t h ea r t i c l e sa sn o d e s ，t h ep r o d u c t i o nr e l a t i o n s h i p sb e t w e e na r t i c l e sa s d i r e c t e de d g e s ) h o w e v e r , i ti sap i t yt h a tw es t i l lc a l l tf i n dap a p e ro rab o o kw h i c h h a sas y s t e m a t i ci n t r o d u c t i o nt ot h eb a s i ct h e o r yo fd i r e c t e dn e t w o r k s 。f e wo f r e s e a r c h e sf o c u s e do nt h et h e o r ya n da p p l i c a t i o no fd i r e c t e dn e t w o r k s ，a n dm o s to f t h e mt r e a t e dd i r e c t e dn e t w o r k sa san a i v ee x t e n s i o no fu n d i r e c t e dn e t w o r k s t h e y s i m p l i f i e dt h ep r o b l e m sb e l o n g i n gt od i r e c t e dn e t w o r k sa s t h o s eo fu n d i r e c t e d n e t w o r k s ，w h i c hm a k e su su n a b l et ot r u l yg r a s pt h ep r o b l e m s u s i n gt h ec o m p l e x i t y s c i e n c e ，n o n l i n e a rd y n a m i c s ，s t a t i s t i c s ，d i f f e r e n t i a lc a l c u l u s ，c y b e m e t i c s ，m a t r i x t h e o r ya n dt h ec o m p u t e rw h i c hi sap o w e ra n a l y s i s ，c a l c u l a t i o na n ds i m u l a t i o nt o o l ， w ed oas u m m a r ya n db r o a d e nr e s e a r c ht ot h et h e o r ya n da p p l i c a t i o no fd i r e c t e d n e t w o r k sf r o mt h ef o l l o w i n gs e v e r a la s p e c t s ： 1 w ed oas u m m a r ya n db r o a d e nr e s e a r c ht ot h et h e o r yo fd i r e c t e dn e t w o r k s ， i n c l u d i n gt h ep r i m a r yd e f i n i t i o n s ，t h ep r i m a r yt o p o l o g yc h a r a c t e r i s t i c s ，t h eb a s i c s t r u c t u r ea n dm a t r i xt h e o r yo fd i r e c t e dn e t w o r k s e s p e c i a l l y , w ed oam o r ei n - d e p t h s t u d y t ot h ea d j a c e u tm a t r i xa n dc o r r e l a t i o nm a t r i xo f d i r e c t e dn e t w o r k s 2 b a s eo ns o m er e a ln e t w o r k sw i t hh i e r a r c h i c a ls t r u c t u r e ，g r o u ps t r i l c t u r ea n d s t a t i s t i c a ls e l f - s i m i l a r i t y ，w eb u i l dad i r e c t e dn e t w o r km o d e lw i t hd e t e r m i n i s t i cd e g r e e 武汉理工大学硕士学位论文 d i s t r i b u t i o n , a n a l y z es o m eo fw h o s et o p o l o g yp r o p e r t ya n dd i s c u s ss o m eo fw h o s e p o t e n t i a la p p l i c a t i o n si ns o m e r e a ld i r e c t e dn e t w o r k s 3 a c c o r d i n gt ot h ec h a r a c t e r i s t i c so fs o m er e a ln e t w o r k ss u c ha st h ei n t e m e ta n d t h eg o o d sd i s t r i b u t i o nn e “v d r kw eb u i l da ne v o l v i n gd i r e c t e dn e t w o r km o d e lo nt h e b a s eo ft h eb am o d e l i np a r t i c u l a r , w es t u d yi t sd i s t r i b u t i o na n dd i s c u s ss o m eo f w h o s e p o t e n t i a la p p l i c a t i o n si ns o m er e a ld i r e c t e dn e t w o r k s t h em a i ni n n o v a t i o np o i n t so f t h i sp a p e ra r ea sf o l l o w s ： 1 u s i n gd e t e r m i n i s t i ci t e r a t i v em e t h o d w eb u i l dal f i e r a r c h i c a ld i r e c t e dn e t w o r k m o d e lw h i c hc a l la p p r o x i m a t e l ys i m u l a t es o m er e a ls y s t e m ss u c ha st h ef o o dw e ba n d a n a l y z es o m eo fi t st o p o l o g yp r o p e r t i e ss u c ha sd e g r e ed i s t r i b u t i o n t h em o d e l o v e r c o m e st h ed e f e c tt h a tt h es t o c h a s t i cm o d e li sd i f f i c u l tt oa n a l y z e ，w h i c hh a sg r e a t t h e o r e t i c a ls i g n i f i c a n c e 2 w eb u i l da ne v o l v i n gd i r e c t e dn e t w o r km o d e lo nt h eb a s eo ft h eb am o d e l w h i c ho b e y sp o w e r l a wd i s t r i b u t i o na n di t si n d e xi st u n a b l ei n 2 ，) t h em o d e lc a n a p p r o x i m a t e l ys i m u l a t es o m er e a ls y s t e m ss u c ha st h ei n t e r a c t k e yw o r d s ：c o m p l e xn e t w o r k s ；s m a l l - w o r l de f f e c t ；s c a l e - f r e en e t w o r k s ； e v o l v i n gm o d e l ，e x t e n d i n g 1 1 1 独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得武汉理工大学或其它教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 签名：遑良蛘日期：j 塑颦越 关于论文使用授权的说明 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即学校有权保 留、送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或 部分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：餐冲师签名：半日期：半、y 武汉理工大学硕士学位论文 1 1 研究背景 第1 章绪论 1 1 1 复杂网络的研究现状简介 复杂网络的研究近年来受到了来自物理学、数学、生物学、管理学、经济 学等几乎所有学科领域的研究人员的广泛关注，已经成为了科学界的一个研究 热点“_ 岫。所谓网络是由一些基本的单元( 我们通常称之为节点或顶点) 和它们 之间的连接( 我们通常称之为边或连接) 所组成。根据边是否有确定的方向， 我们可以将复杂网络分成有向网络和无向网络两类。毫无疑问，现实世界( 包 括自然界和社会) 中大量的复杂系统都可以用形形色色的复杂网络模型来加以 表示和研究。例如，万维网( w w w ) 是由网页及它们之间的超链节所组成的网络； 因特网( i n t e r n e t ) 是由域或路由器组成的网络；脑可以看成神经元组成的网 络：人类社会是由人组成的网络。此外常见的复杂网络还有通信网络、电力网 络、电路网络、蛋白质网络、公路网络、铁路网络、航空网络及科研合作引文 网等。图1 - 1 中给出了两个典型的现实中的复杂网络。 盯 一般来说，复杂网络的复杂性主要体现在以下几个方面啪： ( 1 ) 结构的复杂性 网络的连接结构看上去错综复杂、混乱无序。并且网络的连接结构可能是随 武汉理工大学硕士学位论文 着时间变化而发生变化的，例如，万维网上每天都不停地有页面和链节的产生 和删除。另外，节点之间的连接可能具有不同的权重或方向。如神经系统中触 突之间的连接有强有弱，可能是抑制的也可以是兴奋的。 ( 2 ) 节点的复杂性 网络中的节点可能是具有分岔和混沌等复杂非线性行为的动力系统。如基因 网络结阵中的每个节点都具有复杂的时间演化行为。并且，一个网络中可能存 在多种不同类型的节点。例如，控制哺乳动物中细胞分裂的生化网络中就包含 各种各样的基质和酶。 ( 3 ) 各种复杂因素的相互影响 各种实际复杂网络往往会受到各种各样的因素的影响和作用。例如，耦合神 经元重复地被同时激活，那么它们之间的连接就会加强，这被认为是记忆和学 习的基础。此外，各种网络之间也存在着密切的联系，这使得对复杂网络的分 析变得更加困难。例如，电力网络的故障可能会导致因特网流量变慢、金融机 构关闭、运输系统失去控制等一系列不同网络之间的连锁反应。 由于复杂网络的无处不在，所以我们有必要对复杂网络的各种特性进行广 泛而深入的研究。主要的课题有定义各种网络特征量来刻画真实复杂系统的宏 观性质；建立网络模型以帮助人们理解真实系统中各种宏观性质的微观生成机 制；研究在具有不同结构的网络中发生的各种动力学过程的特征，比如研究流 行病的传播行为在无标度网络和指数网络中分别具有什么特征等。 传统上对网络的研究一般采用数学上图论的方法。但是经典图论所考虑的 一般是规则图。只是到了2 0 世纪5 0 年代末6 0 年代初，两位匈牙利数学家e r d o s 和r 6 n y i ( e r ) 在图论领域做出了一个重要的突破，他们在文献 7 9 中提出了随 机图理论。他们用随机图来描述网络的拓扑结构，这为复杂网络的研究奠定了 一个坚实的数学理论基础。在e r 的随机网络模型中，首先给定网络的节点数， 然后任意两点之间以相同的常数概率连接在一起完全随机地构成网络该模型 自提出以来一直在网络研究中扮演重要的角色，被广泛应用于社会学和生态学 的研究之中直到现在还有人在做这方面的研究。但是随机图理论是否能准确的 描述现实世界中的网络呢? 大量的观察和实验结果告诉我们：现实世界中的网 络既不是完全规则的也不是完全随机的。e r 随机图理论虽然不能准确的描述现 实世界中的网络，但是却能被人们使用这么多年，主要还是由于过去我们缺乏 对现实世界中的网络数据的分析能力和对现实世界网络的拓扑结构的准确认 识。 可喜的是，在过去的几年里这种状况发生了根本性的变化。由于科学领域， 特别是计算机领域的高速发展，使我们获得了越来越多的刻画现实世界网络特 2 武汉理工大学硕士学位论文 征的数据，另外超级计算机的发展为我们提供了非常强大的计算和数据分析能 力，以及各学科之间的相互交叉和融合趋势在不断加强，使得研究人员有能力 在对各种不同类型网络的数据分析和比较的基础上，揭示复杂网络的一些公有 的特征和性质，从而激起了人们以理论、计算机仿真和实际数据验证等三种手 段研究复杂网络的浓厚兴趣。于是，经过最近几年人们在这一研究方向上的坚 持不懈的探索和努力，终于在复杂网络研究领域中获得了两项重要的发现：大 多数现实复杂网络具有小世界效应和无标度特征“”。 一个网络称为具有小世界效应指的是：不管网络的规模多大，固定网络节点 的平均度，在网络的任意两个节点之间都有一条相对于网络规模而言的很短的 路径。很多人可能有这样的经历：偶尔遇到一个陌生人，同他聊了一会儿后发 现你认识的某个人居然他也认识，然后你们一起发出“这个世界真小”的感叹。 小世界的另一个代名词就是著名的“六度分离”的推断。2 0 世纪6 0 年代美国哈 佛大学的心理学家m i l g r a m 的著名的小世界实验( 社会调查) 得出的推断是： 地球任意两个人之间的平均距离是6 ( 即平均经过5 个人的传递，一个人就能与 地球上任何一个角落的另一个人建立联系) 。1 9 9 8 年6 月，为了描述规则网络 到随机网络之间的情形，博士生w a t t s 和他的导师提出了小世界网络的概念， 并开创性的建立了小世界网络模型。 无标度特征是复杂网络中另一项重要的发现。b a r a b a s i 和a l b e r t 率先发现 在很多大规模的现实复杂网络中节点的度呈现一种幂律( p o w e rl a w ) 分布。并 把这类网络称之为无标度网络。他们于1 9 9 9 年1 0 月基于现实中的w 啊网提出 了著名的b a 模型。 小世界效应和无标度特征的发现是复杂网络研究领域的重要进展，开创了复 杂网络研究的新纪元。其后，在这两项重要发现的推动下人们又相继提出了多 种复杂网络模型，并研究了一些相关的性质。从而掀起了一股研究复杂网络的 新热潮。 当前，各国研究人员在无向网络的拓扑结构特征；建立无向网络模型以帮助 人们理解真实系统中各种宏观性质的微观生成机制；研究具有不同结构的无向 网络中发生的各种动力学过程的特征，比如研究流行病的传播行为在无标度网 络和指数网络中分别具有什么特征等方面已经取得了很大的进展，获得了许多 令人兴奋的结果。但是对有向网络的研究仍然处于起步阶段，鲜有研究者从事 有向网络的研究。在国内主要有：大连理工大学刘建国等人在改进b a 模型的基 础上提出了一个有向w w w 网络模型，其中重点研究了节点出入度之间的相关关 系；上海交通大学卢悠悠等人基于反馈机制研究了节点重要性指标在社会地位 网，科研论文影响力网及w w w 网中网页排序中的应用；中国科学技术大学汪秉宏 3 武汉理工大学硕士学位论文 等人研究了增长有向网络中的组织和动力学等问题。同国内相比，国外研究者 们对有向网络进行了相对广泛的研究，他们通过实证万维网、细胞网络、电话 网、引文网及食物网等有向网络而发现了它们的一些特征 见表1 1 ，并在此基 础上提出了一些有向网络模型，并研究了这些模型的特点及其简单应用“”。例 如，b t a d i c 等人提出了一个表示w w 网的有向网络模型；a r a m e z a n p o u r 等人对 发生在有向网络中的传播进程进行了研究；n s c h w a r t z 等人研究了有向无标度 网络中的逾透问题；日本的t e t s u r om u r a i 等人对有向网络的谱的性质进行了初 步的研究。 表1 1各种实际有向网络的基本统计数据旧 有向网络 nml y c 社会电子邮件 5 9 9 1 28 6 3 0 01 4 44 9 5 1 5 2 0 0 1 6 领域电子邮件地址 1 6 8 8 15 7 0 2 93 3 85 2 20 1 3 聊m ( n d e d u ) 2 6 9 5 0 41 4 9 7 1 3 55 5 51 1 3 2 1 2 4 0 2 9 信息w 孵( a l t a v i s t a ) 2 0 3 5 4 9 0 4 62 1 3 1 0 91 0 51 6 22 1 2 7 领域 引文网 7 8 3 3 3 96 7 1 6 1 9 88 5 7 3 0 f 一 罗氏字典 1 0 2 25 1 0 34 9 94 8 7o 1 5 技术软件包 1 4 3 91 7 2 3 1 22 4 2 1 6 1 40 0 8 领域软件类1 3 7 72 2 1 31 6 l1 5 l0 0 1 生物 海洋食物网 1 3 55 9 84 4 32 0 50 2 3 淡水食物网 9 29 9 71 0 81 90 0 9 领域 神经网络 3 0 72 3 5 97 6 83 9 7o 2 8 注：n ：节点总数，m ：总边数， ：平均度，l ：平均路径长度，7 ：入、出度 幂律指数，“一”不是幂律分布，表中的空格表示没有可靠的数据。 但令人遗憾的是，同无向网络的研究现状相比，国内外研究者们仅仅了解 了有向网络的一些零碎的特征。许多人只是对一些特殊的有向网络做了研究， 而更多的人则天真的认为有向网络只不过是无向网络的自然扩充。他们把本该 利用有向网络来研究的问题通通简化为无向网络问题来研究，这当然使得我们 不能真实地把握这些问题。至今为止，我们还不能找到比较系统地介绍有向网 络基本理论的文章或书籍，可见当前对有向网络的研究仍然处于起步阶段。的 确在复杂网络的研究中，对有向网络结构特征及应用的研究己成为复杂网络研 究中最具挑战性的课题之一。 4 武汉理工大学硕士学位论文 1 。1 2 复杂网络的研究意义 复杂网络的研究涉及多个学科，其中包括复杂性科学、非线性动力学、物理 学、数学、生物学、化学、管理学、经济学、计算机科学、控制论等自然科学 和社会科学领域。为什么对复杂网络的研究会引起各个学科领域的研究者们的 广泛兴趣呢? 这是因为复杂网络( 特别是小世界网络和无标度网络) 刚一提出， 就呈现出广阔的应用前景，其应用涉及工程技术、社会、政治、医药、经济、 管理等不同的方面。 在过去的几年里，来自不同领域的研究者们发现，包括因特网、细胞新陈代 谢网、好莱坞演员合作网在内的许多现实网络，都是无标度网络，它们被少数 几个中枢节点( 通常被称为集散节点) 所支配。无标度网络对意外的随机故障 具有惊人的鲁棒性，但是它们面对外界的恶意攻击则很脆弱。这些最近的新发 现极大地改变了人们对复杂网络外部世界的认识，让人们认识到了以前的理论 尚未涉及到的问题：各种复杂系统具有相同的严格结构，都受到了某些基本法 则的制约，这些法则可同等地适用于细胞、计算机、语言及社会。认识这些法 则，可以将其其用到不同的领域，帮助人们解决一系列的问题。 首先，复杂网络理论可以用于保护许多实际复杂系统的正常运行”“。如因 特网、电力网、航空网、万维网、交通网、电予邮件网、食物链网等网络都与 我们的生活息息相关，人们对这些网络的依赖程度日益增强，这样出现了一个 广受人们关注的问题：这些网络到底有多可靠呢? 2 0 0 0 年，爱虫病毒侵犯了英 国议会的电子邮件系统，导致该系统瘫痪；2 0 0 3 年美加电网的大崩溃，至今仍 让纽约人心有余悸：当前，人类生存的生态系统不断地遭到破坏已经危机到人 类的生存环境，这样的例子还有很多。从这些现象可以自然地提出下面的问题： 计算机病毒是如何在万维网上传播而导致流行的? 病毒如何通过电子邮件传 播? 人们如何控制病毒传播? 面对黑客的攻击，人们应该采取何种对策? 怎样 设计出承受意外故障较强的网络( 如交通网、电力网、万维网) ? 怎样保持当 前不断恶化的生态系统的平衡? 对这些问题的解决都与复杂网络的研究有关， 开展复杂网络稳定性的研究，对万维网、电力网、交通网等技术网络的设计保 护及基础设施网络的保护具有重要的意义，也可以有效地防止黑客侵犯万维网， 阻止病毒在万维网上传播和蔓延。 复杂网络在社会领域也有广阔的应用前景”8 。如传染病( 艾滋病、非典、 禽流感等) 对人类的威胁很大；艾滋病让人们不寒而栗；2 0 0 3 年的非典对于宏 观经济和人类的生命安全都产生了巨大的负面影响；目前禽流感也已成为世界 关注的一个焦点。那么在特定的社会网络中，传染病如何通过接触关系传播而 导致流行的呢? 决策者们如何控制这些疾病，以将损失将到最低限度呢? 这些 5 武汉理工大学硕士学位论文 问题或许可以从复杂网络中寻找到答案。最近几年，科学家们考虑了不同现实 系统的主要特征，提出了许多有针对性的疾病的免疫方法，为疾病的预测、预 防和免疫提供了科学的方案。例于，利用复杂网络理论可以很好的预测非典爆 发的多样性、了解疾病传播的动态性，为决策者控制流行病的传播、改善公共 卫生提供有效的手段。在当今社会，稳定是经济发展的基础，流言飞语往往影 响社会的安定。复杂网络理论也可以用于模拟社会上谣言的传播过程，对控制 流言的扩散、降低其副作用具有一定的借鉴意义。 除了社会领域外，复杂网络在政治领域也开始显示出实际的应用价值”1 。在 当今世界上，恐怖主义已被列入人类2 1 世纪的十大危害之一，发生在美国的9 1 1 事件让全美至今仍有害怕。对于恐怖主义、犯罪组织这些需要破坏的网络，人 们可以用复杂网络理论，通过捉拿和逮捕其主要人物，就可以摧毁其网络，使 其功能失常，以维护人类社会政治的稳定。网络理论还可以用于揭示政府议员 的组织及层次关系，甚至可以成功模拟政治选举，分析一些因素对选举结果的 影响。 在医药领域，复杂网络同样有其重要的应用价值4 ”1 。许多传染病的疫苗 价格昂贵，而且数量有限，不可能对每个人都接种疫苗。如何充分利用数量有 限的疫苗呢? 对非典、天花等严重疾病，如果能采取措施直接或间接地针对集 散节点( 即那些与很多人具有连结关系的) 接种疫苗，可以达到很好的效果， 复杂网络为这一做法提供了科学的依据。在分配艾滋病、天花等成本很高的疫 苗时，对于那些无力照顾到全民的国家和地区而言，这种做法可能是最适用的。 在制药业方面，细胞对集散节点的依赖，给药物研究者提供了新的方法；有可 能找到这样的药物，能针对性地攻击细胞或者细菌的集散节点，以便杀死它们 而又不会影响健康的组织。例如，癌症是当今最让人头疼的一种疾病，在复杂 的基因网络中，如果知道故障节点相互作用癌症的病理，就可能研制出针对癌 症集散节点的药物，对癌症的治疗也许有很好的效果。此外，弄清人体细胞内 的网络结构，有助于研究者发现和控制药物的副作用。 复杂网络也为人们认识语言文字、获取知识提供了新的有力的工具，是人们 研究知识管理的新途径啪“。语言是人类区别动物的主要标志之一，可是我们 今天使用的语言是如何演化的呢? 为什么只有人类才具有复杂语言呢? 人脑为 什么接触到某一事物后，可以很快的联想到其它事物呢? 现实复杂网络中的语 言演化研究的新方法与新尝试，其在认识科学中的意义很大，如语言网的小世 界特性可以部分地解释人脑具有很快的联想功能等。目前正处在信息时代，信 息时代需要时代信息，可是在信息网络( 如w 啊网) 中信息如何传播呢? 人们 如何尽快获取所需要的信息呢? 复杂网络不但对于专家领域知识的发现及表示 6 武汉理工大学硕士学位论文 方法有一定的意义，而且在知识学习与获取方面，复杂网络也可以一显身手。 另外，根据w w w 网特殊的复杂结构，人们可以提出相应的搜索算法，为获取所 需要的信息提供方便。 复杂网络在经济、管理领域也有着重要的实际意义睁。利用复杂网络理论 了解公司、产业与经济之间的连接方式，有助于监控和预防大规模的经济衰退。 在管理领域，决策对经济的发展起着关键性的作用，同一个人可以在多个组织 内兼任董事。建立公司董事网，使得分析决策的动态性成为可能。另外，研究 流行病在复杂网络中的传播现象，可以为市场人员传播新产品和新时尚提供新 的方法、新理论。许多市场营销专家都在研究扩散理论，出于商业目的，他们 需要引发流行而不是抑制流行，于是他们提出了所谓的病毒式营销，这一方法 适用可行，但一直没有公认的理论基础，新近流行的复杂网络研究，为更严谨 地探导这些现象，提供了一个科学的框架和数学工具。利用网络理论，还可以 分析公司组织内部及组织之间的信息传播、信息交换、组织间的战略同盟、组 织的综合评价及排名。在复杂的市场环境下，复杂网络还可以用于对金融产品 进行定价等。 除了以上应用外，复杂网络的研究，对于其他许多领域也是有价值的。”。例 如，将小世界的思想用于b p 网络，可以减少b p 网络的学习时间和学习误差， 使用b p 网络可以更好地用于数据挖掘、语音识别、图像处理及模式识别等多个 领域，另外，将复杂网络用于h o p f i e l d 网络，可以改变神经网络的联想记忆功 能。 特别地，复杂网络对于系统科学有着及其重要的理论意义和工程应用价值， 中国系统科学学会将复杂网络对系统工程与系统科学的贡献作了深远的展望 恤“。众所周知，结构是客观事物的基本属性，也是各科学领域研究的一个重要 问题。虽然每门学科在其研究对象的结构方面，都有非常丰富的具体成果，但 从系统学的高度，横跨物质系统、生物系统和社会经济系统的具体研究成果， 也就是系统学层面的成果还不多，其系统层面的内涵迄今还没有完备的阐述。 复杂网络是综合以往的自组织理论、非线性理论与复杂性理论研究成果而形成 的崭新的理论。复杂网络的兴起，为系统科学的研究开拓了新视野，提供了全 新的视角。复杂网络作为复杂系统的一般抽象和描述方式，作为加深人们对系 统结构的深入了解，随着复杂网络研究的深入以及用网络理论研究系统演化工 作的深入展开，复杂系统演化的研究必将出现的突破性结果；反过来，复杂网 络的研究成果对探索复杂性具有一定的启发和借鉴意义；当然也可以从系统科 学的角度来研究网络，这也是网络的新视角。可见，利用网络理论对系统进行 研究，是系统科学一种新的研究手段。本文从理论及应用两个方面对有向网络 7 武汉理工大学硕士学位论文 系统进行研究，因此本文的研究也是十分有意义的。 1 2 本文的研究内容、研究方法 同无向网络一样，自然界和社会中同样蕴涵着大量的有向网络，它们广泛 的存在于科技、信息、生物、社会等领域中。例如，w w w 网( 其中将网页看作节 点，不同的网页之间的超链接作为边显然是有方向的) ；引文网( 其中将文章看 作节点，不同的文章之间的引用关系作为边是有方向的) ；生态系统中的食物网 ( 其中生物类型是节点，不同生物类型之间的捕食关系也是有方向的) ；经济领 域中的货物网( 其中物品是节点，它们之间的生成关系作为边同样是有方向的) 。 目前，对有向网络的研究是复杂网络中最具挑战性的课题之一，还处在几 乎停滞不前的状况迄今为止，我们还不能找到比较系统地介绍有向网络基本 理论的文章或书籍。本文在前人的研究成果基础之上，对有向网络的基本理论 及其在生态等网络中的应用进行了若干研究。其内容主要包括有向网络的拓扑 特征、基本结构及矩阵理论等理论的综述及拓展；建立网络模型并在生态等网 络中进行实证分析。 本文所采用的研究方法主要有：( 1 ) 利用统计的方法研究实际网络数据， 得到网络的特征；( 2 ) 根据现实网络中的潜在的演化规则，得到新的网络模型； ( 3 ) 利用现实网络对模型进行实证分析。 1 3 本文的组织结构 本文共分五章内容来对有向网络理论及其在生态等现实网络中的应用进行 了阐述。主要从理论、建模、实例应用等几个方面来进行。 第1 章：简介了课题的研究背景、研究内容及研究方法，主要是复杂网络的 发展现状及复杂网络的潜在的应用范围和重要的应用价值，以提高人们对复杂 网络( 特别是其中的有向网络) 研究的重视。 第2 章：对有向网络理论( 主要包括有向网络的静态拓扑特征、基本结构、 矩阵理论及等级网络的基本结构) 做了比较详细的综述和拓展。 第3 章：运用迭代的方法提出了一个有确定度分布的有向演化网络模型，特 别讨论了它在食物网等现实网络中的意义及应用。 第4 章：提出了一个基于b a 模型的有向演化网络模型，详细推导了它的度 分布，并讨论了其在因特网等现实网络中的意义及应用。 第5 章：总结和展望。总结全文的主要创新点，指出存在的不足，并指出后 续的发展方向和后续价值。 8 武汉理工大学硕士学位论文 1 4 小结 本章对本文的研究背景、主要研究内容、研究方法及结构安排做了概述。 其中特别强调了复杂有向网络潜在的应用价值，以此突出本文的研究意义。 9 武汉理工大学硕士学位论文 第2 章有向网络的基本理论 2 1 有向网络、有向道路及有向圈蚋刀 定义2 1 1 一个有向网络d 可定义为一个偶对d = ( 矿，e ) ，其中： 1 矿是个非空的集合，其中的元素称为节点( 或顶点) ，节点数记为n = jvl ； 2 e 是有序积v v 的一个子集，其元素称为边( 或弧) ，边数记为m = 4 e i 根据有向网络的定义，与一条边相关联的两个节点具有一定的次序关系， 即边p = ( “，v ) 是节点”和v 的有序对。我们称u 为p 边的起点，v 为终点。这就说， 有向向网络中的每条边都有确定的方向，方向是从边的起点指向它的终点。 图2 - 1 给出的是一个含有5 个节点和7 条有向边的简单有向网络 c 图2 - 1 一个简单的有向网络 定义2 1 2 对一个有向网络，忽略其中每条边的方向所得到的无向网络，我 们称这个无向网络为这个有向网络的基础网络 显然一个基础网络所对应的有向网络不是唯一的 定义2 1 3 有向网络中，以节点v 为起点弧的数目，叫做节点v 的出度( o u t d e g r e e ) ，记作d e g + ( v ) ，以节点v 为终点弧的数目，叫做节点v 的入度( i n d e g r e e ) ，记作d e g ( v ) 显然，对有向网络中的任意节点v ，总有它的度d e g ( v ) = d e g + ( v ) + d e g 一( v ) 定义2 1 4 有限非空系列m = v o a 。v ，v 。吼v 。，它的项交替地是节点和弧， 弧a ，的起点是v j _ 。，终点是h ( j l 协j 、且同一条弧不用两次，则称肘是一条有向链 ( d i r e c t e dc h a i n ) 。和v t 分别称为这条有向链的起点和终点，后称为链的长。 有向链喁v l 一。a k v k 通常用它的地点序y i j r o y ，h 一。唯来表示。 本身是一条道路( 其中的节点都不相同) 的有向链，称为有向道路( d i r e c t e d p a t h ) 。 起点和终点重合的有向链，称为有向闭链。 本身是一个圈的有向闭链，称为有向圈。 武汉理工大学硕士学位论文 节点和弧的交替序列v o qv l 叱一吒v k ，其中节点均不相同，但每条弧口，可能 是一一。v ，也可能是v ，v 。，这样的序列称为半道路。 例如，在图2 一l 中，b e d b c 是有向链，a b c d 是有向道路，a b c d b e a 是有向闭 链，a b e a 是有向圈，a b d e 是半道路。 我们知道，对于无向网络，它只有连通和不连通两种情况。但是对于有向网 络，则有不同的连通方式。 定义2 1 5 如果在有向网络d 中，有一条( “，v ) 有向道路，则称v 是从“可 达的，或者说，从“可达v 。 ( 1 ) 如果有向网络d 中的任何两点都互相可达，则称d 是强连通的( s t r o n g l yc o n n e c t e d ) 。 ( 2 ) 如果有向网络d 中的任何两点至少有一个节点由另一个节点可达，则 称d 是单向连通的( u n i l a t e r a lc o n n e c t e d ) 。 ( 3 ) 如果有向网络d 中的任何两点由一条半道路连接，则称d 是弱连通的 ( w e a k l yc o n n e c t e d ) 。 ( 4 ) 对有向网络d 中的任何两个节点“和v ，都存在节点w ，w 可达节点“ 及v ，则称d 是拟强连通的。 最近，j e o n g y o ok i m ，t a c k s e u n gj u n 等人在文献 3 6 中基于一类有向通讯 网络而提出了一种不同于上述弱连通的有向网络弱连通的定义，并在此基础上 给出了该类有向网络的一个分配规则。他们的这种连通性的定义似乎为我们研 究有向通讯网络带来了方便。 关于强连通有向网络，有下面的定理： 定理2 1 1 有向网络d 是强连通的，当且仅当d 的每一条弧都在某一有向 圈中。 证明：设d 是强连通有向网络，设e = ( “，v ) 是d 中的任意一条弧。按定义由 v 也可达“，即存在一条( v ，u ) 有向道路尸，于是p u ( ”，v ) 是一个有向圈，反之， 若d 中的每一条弧均在某一有向圈中，则d 中任意两点之间显然是相互可达的， 即d 是强连通的。 另外，k e v i nc o s t e l l o 等人在文献 3 7 q u i i e s 羽了下列任意条件成立，都町以推 出有向网络d 是强连通的： ( 1 ) 将d 划分为任意两个非空分离集a 和b 有一条从a 到b 的有向边，也 有条从b 到a 的有向边。 ( 2 ) d 的邻接矩阵是不可约的。 ( 3 ) d 的转移概率矩阵是不可约的。 类似地我们可以得到： 武汉理工大学硕士学位论文 定理2 i 2 有向网络是单连通的，当且仅当d 的每一条弧都在某一有向道 路中。 下面我们给出有向网络中含有向道路和有向圈的一些条件，它们也是一些显 而易见的不需给出证明的定理。 定理2 1 3 设p 是有向网络中的一个子网络，如果对户中的两个节点“，v 满 足： ( 1 ) d e g + ) = 1 , d e g 一( ”) = o ，d e g + ( v