(控制理论与控制工程专业论文)复杂网络上的交通动力学研究.pdf_第1页
(控制理论与控制工程专业论文)复杂网络上的交通动力学研究.pdf_第2页
(控制理论与控制工程专业论文)复杂网络上的交通动力学研究.pdf_第3页
(控制理论与控制工程专业论文)复杂网络上的交通动力学研究.pdf_第4页
(控制理论与控制工程专业论文)复杂网络上的交通动力学研究.pdf_第5页
已阅读5页,还剩49页未读, 继续免费阅读

(控制理论与控制工程专业论文)复杂网络上的交通动力学研究.pdf.pdf 免费下载

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

摘要 摘要 以t c p i p 为基础的通信网络在过去的二十年中取得了巨大的发展,网络规 模和用户数量都呈爆炸式的增长。随着网络应用的不断深入,人类已经进入了一 个以网络为基础的信息时代。拥塞是一种无法完全避免的基本网络现象,严重的 拥塞会造成传输时延,传输速率和吞吐量等性能指标的恶化。所以如何缓解拥塞, 提高通信网络通信能力( 亦即网络吞吐量) 已成为复杂网络交通动力学研究的重 要课题。通常网络通信能力受几个因素影响:路由策略,节点通信能力和网络拓 扑结构。而且当大量信息涌入网络时,有限的内存也会对网络阻塞产生重要影响。 现在通信网络中最基本的路由策略是以最快传输为目标,也就是说它是基于 从源地址到目的地的估计最短路径。i n t e r n c t 和其它一些通信网络采用这种基本 路由策略,并正常可靠的运行,但是这种基本路由策略在遇到网络通信拥塞时, 通信效率会快速下降。因此第三章介绍一种新的路由策略,它引入局域交通负载 信息( 邻居节点的负载信息) 。新算法部分克服了基本路由算法的缺点,但是它 并没有考虑邻居节点到目的地节点的负载情况。第四章利用通信的历史信息对这 一点进行改进。b a 无标度网络的仿真结果显示,改进后的算法不但提高了网络 的通信能力,而且增强了算法对于网络链路随机故障的适应能力。 第五章,我们提出一个新的单节点通信能力分配策略,使得当整个网络所有 节点的通信能力之和固定时,网络通信效率比平均分配节点通信能力时更高。在 这个模型中,度为k ;的单节点i 的通信能力与七尸成正比,其中是可控参数,并 使用最短路径路由算法。模拟仿真结果显示存在最佳的值,使得网络的通信能 力达到最大值。 最后对全文工作进行了总结,并指出了下一步可深入研究的方向。 关键词:复杂网络;拥塞;路由算法 a b s t r a c t t h et c p i p - b a s e dc o m m u n i c a t i o nn e t w o r k sh a v ed e v e l o p e de n o r m o u s l yo v e rt h e p a s tt w od e c a d e s b o t ht h es i z eo fn e t w o r k sa n dt h en u m b e ro fu s e r sh a v ei n c r e a s e d e x p l o s i v e l y w i t ht h ee m e r g e n c e o fm o r ea n dm o r ei n d e p t hn e t w o r ka p p l i c a t i o n s ,t h e h u m a n k i n dh a si n v o l v e di n t oan e t w o r k - b a s e di n f o r m a t i o ne r a m e a n w h i l e , c o n g e s t i o ni sa b a s i cn e t w o r kp h e n o m e n o nt h a tc a n n o tb ec o m p l e t e l ya v o i d e d s e v e r e c o n g e s t i o nc a l lc a u s et h ed e t e r i o r a t i o no fs o m ep e r f o r m a n c ei n d i c e s ,i n c l u d i n gt h e t i m ed e l a y , t h et r a n s m i s s i o ns p e e da n dt h en e t w o r kt h r o u g h p u t h o wt oi m p r o v et h e t r a n s p o r tc a p a c i t yo ft h e s en e t w o r k sa n da l l e v i a t et h et r a f f i cc o n g e s t i o nh a sb e e na n i m p o r t a n tt o p i ci nc o m p l e xd y n a m i c a ln e t w o r k s i ng e n e r a l ,t h ec a p a c i t yi si n f l u e n c e d b yt h r e ef a c t o r s :r o u t i n ga l g o r i t h m ,t h en o d ep a c k e t - d e l i v e r i n gc a p a c i t ya n dt h e t o p o l o g yo fan e t w o r k f u r t h e r m o r e ,w h e nl a r g en u m b e ro fi n f o r m a t i o np a c k e t sr u s h i n t ot h en e t w o r k , c o n g e s t i o nw i l la l s oo c c u rd u et ot h ef i n i t em e m o r y t h eb a s i cr o u t i n gp r o t o c o li nc o m m u n i c a t i o nn e t w o r k sa i m sa tt h ef a s t e s t t r a n s m i s s i o n ,w h i c hi sb a s e do nt h ee s t i m a t eo ft h es h o r t e s tp a t hf r o mag i v e ns o u r c e n o d et ot h ed e s t i n a t i o n a l t h o u g ht h ei n t e m e ta n do t h e rc o m m u n i c a t i o nn e t w o r k s w o r ki nar e l i a b l ew a yu n d e rt h eb a s i cp r o t o c o l ,i tw i l lb el e s se f f i c i e n tw h e nn e t w o r k e n t e r si n t ot h es e v e r ec o n g e s t i o np h a s e t h e r e f o r e , w ef i r s t l yi n t r o d u c eag e n e r a l s t r a t e g yt h a ti n c o r p o r a t e dl o c a lt r a f f i ci n f o r m a t i o ni n t ot h eb a s i cs h o r t e s tp a t hr o u t i n g p o l i c yw h i c hi sc o n t r o l l e db ya t u n a b l ep a r a m e t e r b ys i m u l a t i o n , c o m b i n i n gw i t ht h e k n o w l e d g eo ft h et o p o l o g ya n dt h el o c a lt r a f f i ci n f o r m a t i o no ft h en e t w o r k ,t h en e w s t r a t e g yb e h a v e sm o r ee f f i c i e n t l yc o m p a r e dw i t ht h eb a s i cr o u t i n gp r o t o c 0 1 b u tt h e n e w r o u t i n gp o l i c yi g n o r e st h ei n f o r m a t i o nb e t w e e nt h en e i g h b o r sa n dt h ed e s t i n a t i o n i nt h ef o l l o w i n gb ye s t i m a t i n gt h ei n f o r m a t i o nf r o mn e i g h b o r st od e s t i n a t i o n , w e p r o p o s ea l li m p r o v e dr o u t i n gs t r a t e g yw i t hat u n a b l ep a r a m e t e r w ei n v e s t i g a t et h e e f f e c t i v e n e s so ft h ep r o p o s e dr o u t i n gs t r a t e g yf o rb as c a l e - f r e en e t w o r kw i t hd i f f e r e n t t u n a b l ep a r a m e t e r c o m p a r e dt ot h en e ws t r a t e g yi n c o r p o r a t e dl o c a lt r a f f i c i n f o r m a t i o n , t h es i m u l a t i o ns h o w st h a tt h ei m p r o v e dr o u t i n gs t r a t e g yn o to n l yh a s h i g h e rt r a n s p o r tc a p a c i t y , b u ta l s ob e h a v e sm o r ee f f i c i e n t l yi n t h et o l e r a n c e 复杂网络上的交通动力学研究 a g a i n s t r a n d o ma t t a c k so fl i n k s s e c o n d l y , w ep r o p o s eal i m i t e dp a c k e t - d e l i v e r i n gc a p a c i t ym o d e l f o rt r a f f i c d y n a m i c si nb a s c a l e f l e en e t w o r k s i nt h i sm o d e l ,t h et o t a ln o d e sp a c k e t d d i v e r i n g c a p a c i t yi sf i x e d ,a n dt h ea l l o c a t i o no fp a c k e t - d e l i v e r i n gc a p a c i t y0 1 1n o d e w i t h d e g r e ek li sp r o p o r t i o n a lt ok ,w h e r epi saa d j u s t a b l e w eh a v ea p p l i e dt h i s m o d e lo nt h es h o r t e s tp a t hr o u t i n gs t r a t e g ya n df o u n dt h a tt h e r ee x i s t sa no p t i m a l v a l u eo fp a r a m e t e rbl e a d i n gt ot h em a x i m a ln e t w o r kc a p a c i t y as u m m a r yo ft h ef u l lt e x ta n dt h ed i r e c t i o n sf o rf u r t h e rs t u d i e sa r eg i v e na tt h e e n do ft 1 1 i st h e s i s k e yw o r d s :e o m p l e xn e t w o r k s ;c o n g e s t i o n ;r o u t i n ga l g o r i t h m 厦门大学学位论文原创性声明 兹呈交的学位论文,是本人在导师指导下独立完成的研究成果。 本人在论文写作中参考的其他个人或集体的研究成果,均在文中以明 确方式标明。本人依法享有和承担由此论文产生的权利和责任。 专篙筹焉擎2 匆呵年7 月多日 厦门大学学位论文著作权使用声明 本人完全了解厦门大学有关保留、使用学位论文的规定。厦门大 学有权保留并向国家主管部门或其指定机构送交论文的纸质版和电 子版,有权将学位论文用于非赢利目的的少量复制并允许论文进入学 校图书馆被查阅,有权将学位论文的内容编入有关数据库进行检索, 有权将学位论文的标题和摘要汇编出版。保密的学位论文在解密后适 用本规定。 本学位论文属于 1 、保密() ,在年解密后适用本授权书。 2 、不保密( 4 ) ( 请在以上相应括号内打“4 ”) 作者签名:隽赙日期:1 ,。j 年7 月2 ,日 导师签名:否a 溯严日期妒77 月岁日 第一章绪论 1 1 复杂网络 1 1 1 复杂网络概述 第一章绪论 自然界中存在的大量复杂系统都可以通过形形色色的网络加以描述。一个典 型的网络是由许多节点与连接两个节点之间的一些边组成的,其中节点用来代表 真实系统中不同的个体,而边则用来表示个体间的关系,往往是两个节点之间具 有某种特定的关系则连一条边,反之则不连边,有边相连的两个节点在网络中被 看作是相邻的。例如,神经系统可以看作大量神经细胞通过神经纤维相互连接形 成的网络n 1 ;计算机网络可以看作是自主工作的计算机通过通信介质如光缆、双 绞线、同轴电缆等相互连接形成的网络乜3 。类似的还有电力网络、社会关系网络 n 3 一、交通网络1 等等。对这些极其复杂的交互作用网络的结构和动力学的理解 已经成为2 1 世纪网络科学和生命科学的关键性研究课题和挑战之一。 一般而言,网络系统的复杂性体现在以下几个方面: ( 1 ) 结构复杂性 网络连接结构看上去错综复杂、极其混乱。而且网络连接结构可能是随时间 变化的,例如,w w w 上每天都不停地有页面和链接的产生和删除。此外,节点 之间的连接可能具有不同的权重或方向。例如,神经系统中的突触有强有弱,可 以是抑制的也可以是兴奋的。 ( 2 ) 节点复杂性 网络中的节点可能是具有分岔和混沌等复杂非线性行为的动力系统。例如, 基因网络和j o s c p h s o n 结阵列中每个节点都具有复杂的时间演化行为。而且,一 个网络中可能存在多种不同类型的节点。例如,控制哺乳动物中细胞分裂的生化 网络就包含各种各样的基质和酶。 ( 3 ) 各种复杂性因素的相互影响 实际的复杂网络会受到各种各样因素的影响和作用。例如,耦合神经元重复 地被同时激活,那么它们之间的连接就会加强,这被认为是记忆和学习的基础。 复杂网络上的交通动力学研究 此外,各种网络之间也存在密切的联系,这使得对复杂网络的分析变得更为 困难。如,电力网络的故障可能会导致i n t e m e t 流量变慢、金融机构关闭、运输 系统失去控制等一系列不同网络之间的连锁反应。 1 1 2 复杂网络中交通动力学研究概述 复杂网络能够描述自然和社会中的非常广泛的系统,因而近年来人们对于这 一领域的兴趣有很快的增长。自从w a t t s s t r o g a t z n l 发现了小世界现象和 b a r a b d s i a l b e r t 1 发现度分布遵循爿尼) 七”的无特征尺度的现象后,物理学家 对于网络上的结构与动力学的演化机制产生了浓厚的兴趣。具有无特征尺度分布 的大的通讯网络诸如互联网和万维网与我们的关系越来越密切,在现代社会中占 据越来越重要的地位。因此发生在网络结构上的各种动力学过程,例如信息流的 交通拥塞问题,越来越受到物理学界和工程界的注意。对于包含互联网、万维网 和全球航空网在内的这一类交通系统,一个不容忽视的问题是:交通动力学是如 何与网络结构演化相互影响的? 以前的一些工作主要是讨论交通的增长如何驱 动网络结构的演化口叫1 ,另一些工作则研究不同种类的网络拓扑如何影响发生于 其上的交通动力学n 卜“1 。 复杂网络上面的随机行走过程已经得到广泛和深入的研究,这一方面是由于 其应用的普遍性,另一方面是由于其基本动力学可以用理论分析进行解释n 卜1 7 1 。 但是,随机行走过于简单,它完全不能够反映真实的交通系统。最近有一些工作 提出了一些模型,通过引入信息包( 粒子) 产生率,和对于每一信息包随机选取 的发源地及目的地,来模拟复杂网络上的交通路由 1 0 , i i , i s , - 2 0 。这些模型也用临界 的信息包产生率来定义网络的通信能力。在临界的信息包产生率处,会发生从自 由交通态转变为阻塞交通态的一个连续相变。所谓自由交通态是指所产生的信息 包数目与到达目的地的信息包数目相抵消而达到信息流的稳态。所谓阻塞交通态 是指每一节点处由于有限的可传送信息包的能力或者有限的可允许等待传送的 信息包排队长度而导致累积的信息包数目随时间增长。 具有重要应用价值的发生在网络上的过程的另一个例子是网络搜索或者网 络导航。以前的一些工作主要集中在无特征尺度网络上基于局域拓扑信息( 每一 节点仅知道其领域的信息) 寻找快速搜索目标靶的最优策略口卜2 引。这种基于局 2 第一章绪论 域信息的策略适合于网络实时搜索需付出高昂通讯代价的情况。网络搜索的研究 对于存在信息包路由和通讯代价的交通系统也是重要的。但是以前的研究很少把 搜索策略与网络的交通过程结合在一起考虑。为此目的,我们来模拟仅仅基于局 域信息而选择传送路由的无尺度网络上的交通动力学,所选取的传送路由既要使 信息包传送时间达到最小,同时要使网络的处理通信能力达到最大一】。 为了研究信息包在网络中的传输动力学,我们假定整个网络中在单位时间内 有尺个信息包产生,并需要从其发源地传送到目的地,发源地和目的地都是随机 选取的,但一经选定,即不再改变。只要信息包未到达目的地,就始终在网络内 游荡。每一节点既是产生信息包和接收信息包的服务器终端,又是中介传送信息 包的路由器。我们假定每一个节点f 送出信息包的速率是e 。当一个节点处等待 送出的信息包数目超过这一常数e ,则未被送出去的信息包就要在该节点处排 队等候,只能在下一时步按照先进先出的原则发送。为了避免信息包在同一路径 中不停的游荡而大大降低传输效率,我们也规定信息包将避免重复地走同一个路 径,这称为路径重复避免规则。当信息包产生速率超过某一临界阈值足,在网 络中排队等候传送的信息包数目就会越来越多地积累,而导致信息传输的交通阻 塞。通讯网络的功能要求信息包在网络中的传输始处于自由交通态,即不发生交 通拥堵,因此,临界的信息包产生速率r ,即是整个网络处理通讯能力的度量。 对于节点连接度分布为幂函数律的无尺度网络,可以证明取最短路径的路由策略 一定不是一种好策略。因为在连接度大的中枢节点( h u b ) 处最容易发生交通堵 塞,而导致整个网络通讯能力兄的下降一】。 基于网络中一个节点的中介性和集中度的度量,我们对于路由算法进行推 广,可以找到一种所谓的“有效路径,这一路径将可能避开沿着实际路径所经 历的某些节点上的交通拥挤。事实上具有最大连接度的节点往往是对于交通拥挤 最敏感的节点。改善交通和控制拥挤的一种最有效的方法就是把中心节点上的交 通负荷分散到其他非中心节点上去。模拟结果显示,如果对于有效路径进行优化 选择,可以使网络整体处理信息传输交通的能力提高十倍以上。数值模拟的结果 与基于网络节点的中介性和集中度度量的分析是一致的哺】。 通讯网络的交通路由的效率应该同时反映在网络通讯能力和信息包的平均 复杂网络上的交通动力学研究 传输时间这两个关键的度量上。我们进一步提出一种可以把局域结构的静态拓扑 信息与交通拥挤的动态信息结合在一起考虑的混合路由策略。通过对于混合路由 策略的控制参数的优化,我们可以在保持网络通讯能力最大的前提下,使得信息 包的传输时间减少到最小。与采取唯一的局域静态信息的路由策略相比较,新的 策略显示出改善通讯系统效率的极大优势。我们对于混合策略进行细致的分析, 来理解这一策略对于交通路由的实际效应。我们的研究表明;有效的利用连接度 较大的节点,对于提高通讯网络和其他无尺度分布交通系统的信息传输速率是至 关重要的啪 0 1 2 本研究课题的背景和动机 人们一直对众多实际的网络缺乏真正的了解,一些一直试图回答的问题是, 究竟系统构件以什么方式构成了具有一定功能的整体? 人们相信,系统的结构总 是影响功能。于是对未知世界的探究早使人们开始关注这些随处可遇的网络。针 对网络的结构与特性提出了很多问题,如:如何理解复杂的基因网络中一些失效 节点之间的作用而导致癌症? 为什么病毒或者疾病在一些社会或通信系统中传 输如此之快? 一些网络如电力网络,在许多甚至多数节点失效的情况下为什么仍 然能够保持正常功能? 网络的拓扑特性和其动态特性之间的关系是什么? 网络 的特别拓扑结构构成根源是什么? 等等 直到当今,数据获取的计算机化导致多领域大型数据库提供了各种实际网络 的拓扑信息,而且访问不同数据库的规则正发生变化以至访问更方便;计算机计 算能力的增强使得探究含有巨量节点的网络成为可能;更重要的是,人们试图超 越简化论的框架去从整体上解释和理解系统的行为。这些都是造成人们热切关注 复杂网络研究的原因。 进一步来说,既然复杂网络存在于如此多的人工和自然系统之中,提示我们 可能比较自然系统和人工系统,探询它们的共性和差别形成的原因。同时借鉴自 然系统的构造去改良人工系统,以及利用逆工程的方式去构造合乎需要的人工系 统。这些都是十分有趣的研究方向。 目前,人们对复杂网络的研究可以划分为几个大的方面: 1 根据真实数据研究实际网络的特性和行为( 基本驱动力) ; 4 第一章绪论 2 探讨和模拟实际网络的结构形成与演化机制; 3 用数学模型描述( 实际) 网络特性和预测网络动态行为; 4 研究人工网络和自然网络的比较,借鉴自然网络的结构特点,用复杂网 络的研究结果改造或建造有特殊特性的网络( 逆工程) ; 5 复杂网络的应用 复杂网络涉及领域宽阔。复杂网络并不是什么纯粹的深奥理论,而和我们周 围实际的世界非常接近。复杂网络研究的各个方面正处于初期阶段,需要更多的 实际观察和积累。包括任何领域,任何理论模型,任何应用的尝试和探索。 通讯网络诸如互联网和万维网在现代社会中占据越来越重要的地位,因而随 着通信网络的日益增大,信息的增长而引发的网络拥塞问题引起了人们的极大关 注。于是本课题试图基于适当的网络模型,寻找缓解通信网络拥塞的方法。一个 非常明显的事实是,影响通信网络的通信能力的三个主要因素是单个节点的通信 能力,网络的拓扑结构和路由搜索策略。在最短路径路由策略中,阻塞通常发生 在中枢节点处,因此要缓解通信网络的拥塞现象,要么改进路由策略,在中枢节 点负载较重时绕过中枢节点;要么提高网络中枢节点的通信能力。因此本文的主 要工作为如下两个方面: 1 在b a 网络中,利用网络通信的历史数据改进一种路由搜索策略,以提高 网络的通信能力( 亦即网络的吞吐量) ; 2 在b a 网络中,当整个网络中所有节点的通信能力之和固定时,怎样合理 的分配单个节点的通信能力才能得到更好的网络通信能力。 1 3 本文的组织方式 本文按照上一节所述的研究逻辑和思路划分为六章,第一章概要性的介绍了 复杂网络以及研究课题的背景和动机。第二章介绍了与本课题相关的一些理论基 础。第三章介绍一种基于局域交通信息的路由算法。随后的第四章和第五章是作 者本人在复杂网络领域的工作。 由于第三章中的路由算法只考虑了邻居节点的负载状况,而忽略了邻居节点 到目的地节点的负载情况。因此第四章利用信息通讯的历史信息来估测邻居节点 到目的地节点的负载情况以改进路由算法,提高了网络通信能力和路由算法对于 5 复杂网络上的交通动力学研究 网络链路随机故障的适应能力。 第五章提出了一个分配单节点通信能力的规则,使得在整个网络中所有节点 的通信能力之和固定时,网络通信效率比平均分配节点通信能力时更高。 在第六章中将对全文进行总结,并指出本文研究的一些不足之处,并对今后 可以研究的一些问题进行了展望。 6 第二论文研究的理论基础 2 1 基本概念 2 1 1 网络的图表示 第二章论文研究的理论基础 一个具体网络可抽象为一个由点集v 和边集e 组成的图g = ( y ,e ) 。节点数 记为n = 州,边数记为m = l 司。e 中每条边都有y 中一对点与之相对应。如果 任意点对( f ,j ) 与u ,f ) 对应同一条边,则该网络称为无向网络( u n d i r e c t e d n e t w o r k ) ,否则称为有向网络( d i r e c t e dn e t w o r k ) 如果每条边都赋予相应的 权值,那么该网络称为加权网络( w e i g h t e dn e t w o r k ) ,否则称为无权网络 ( u n w e i g h t e dn e t w o r k ) 。当然,无权网络也可看作是每条边的权值为1 的等权 网络。此外,一个网络中还可能包含多种不同类型的节点。例如,在社会关系网 络中可以用权表示两个人的熟悉程度,而不同类型的节点可以代表具有不同国 籍,地区,年龄,性别和收入的人。 2 1 2 平均路径长度 网络中两个节点i t f j 之间的距离d 打定义为连接这两个节点的最短路径上 的边数。网络中任意两个节点之间的距离的最大值称为网络的直径( d i a m e t e r ) , 记为d ,即 d = m f ,a j x d 蓼 ( 1 1 ) 网络的平均路径长度三定义为任意两个节点之间的距离的平均值,即 b 丽1 酗 q 卫) 其中为网络节点数。网络的平均路径长度也称为网络的特征路径长度 ( c h a r a c t e r i s t i cp a t hl e n g t h ) 。为了便于数学处理,在公式( 1 2 ) 中包含了 节点到自身的距离( 当然该距离为零) 。如果不考虑节点到自身的距离,那么要 7 复杂网络上的交通动力学研究 在公式( 1 2 ) 的右端乘以因子( i v + 1 ) ( 一1 ) 。在实际应用中,这么小的差别是 完全可以忽略不计的。一个含有个节点和m 条边和网络的平均路径长度可以 用时间量级为d 肼) 的广度优先搜索算法来确定。 2 1 3 聚类系数 在你的朋友关系网络中,你的两个朋友很可能彼此也是朋友,这种属性称为 网络的聚类性。一般地,假设网络中一个节点i 有肛条边将它和其他节点相连, 这毛个节点就称为节点i 的邻居节点。显然,在这墨个节点之间最多可能有 墨阮- 1 ) 2 条边。而这吃个节点之间实际存在的边数巨和总的可能的边数 k i ( k i 一1 ) 2 之比就定义为节点f 的聚类系数g ,即 c = 2 e , ( k ,瓴一1 ) ) ( 1 3 ) 从几何特点上看,上式的一个等价定义为 一 与点i 相连的三角形的数量 c t2 写薪琵碇磊孺 ( 1 4 ) 其中,与节点i 相连的三元组是指包括节点i 的三个节点,并且至少存在从节点i 到其他两个节点的两条边。 整个网络的聚类系数c 就是所有节点f 的聚类系数e 的平均值。很明显, 0 c l 。c = o 当且仅当所有节点均为孤立节点,即没有任何连接边;c = 1 当 且仅当网络是全局耦合的,即网络中任意两个节点都直接相连。对于一个含有 个节点的完全随机的网络,当n 很大时,c = 0 ( 一) 。而许多大规模的实际网络 都具有明显的聚类效应,它们的聚类系数尽管远小于1 但却比d ( - 1 ) 要大得多。 事实上,在很多类型的网络( 如社会关系网络) 中,你的朋友的朋友同时也是你 的朋友的概率会随着网络规模的增加而趋向于某个非零常数,即当j 时, c = 0 0 ) 。这意味着这些实际的复杂网络并不是完全随机的,而是在某种程度上 具有类似于社会关系网络中“物以类聚,人以群分”的特性。 第二论文研究的理论基础 2 1 4 度与度分布 度( d e g r e e ) 是单独节点的属性中简单而又重要的概念。节点f 的度k i 定义 为与该节点连接的其他节点的数目。有向网络中一个节点的度分为出度 ( o u t - d e g r e e ) 和入度( i n d e g r e e ) 。节点的出度是指从该节点指向其他节点的 边的数目,节点的入度是指从其他节点指向该节点的边的数目。直观上看,一个 节点的度越大就意味着这个节点在某种意义上越“重要 。网络中所有节点f 的度 忍的平均值称为网络的( 节点) 平均度( k ) 。网络中节点的度的分布情况可用分 布函数p ( 七) 来描述。爿尼) 表示的是一个随机选定的节点的度恰好为k 的概率。规 则的格子有着简单的度序列:因为所有的节点具有相同的度,所以度分布近似为 d e l t a 分布,它是单个尖峰。网络中任何随机化倾向都将使这个尖峰的形状变宽。 完全随机网络的度分布近似为p o i s s o n ( 图2 1 ( a ) ) ,其形状在远离峰值( 七) 处 呈指数下降。这意味着当k ( k ) 时,度为七的节点实际上是不存在的。因此这 类网络也称为均匀网络( h o m o g e n e o u sn e t w o r k ) 。 图( 2 1 ) 两种度分布的对比【3 1 1 ( a ) p o i s s o n 分布;( b ) 幂律分布( 对数坐标系) 近几年的大量研究表明,许多实际网络的度分布明显地不同于p o i s s o n 分 9 复杂目络上的交通动力学研究 布。特别地,许多网络的度分布可以用幂律形式爿女) * 女”来更好地描述( 图 2l b ) 幂律分布曲线比p o i s s o n 指数分布晦线下降要缓慢得多。 幂律分布也称为无标度( s c a l e f r e e ) 分布,具有幂律度分布的网络也称为 无标度网络,这是由于幂律分布函数具有如下无标度性质。 幂律分布函数的无标度性质:考虑一个概率分布函数,( x ) ,如果对任意给 定常数d ,存在常数b 使得函数,( z ) 满足如下“无标度条件”。 ,k ) = v g ) ( 1 5 ) 那么必有( 假定f o 】,1 n ) o ) ,b ) = ,o 矿,一s o ) i s o ) ( 1 6 ) 也就是说幂律分布是惟一满足“无标度条件”的概率分布函数。 在一个度分布为具有适当幂指数( 通常为2 r 3 ) 的幂律形式的大规模无 标度网络中,绝大部分的节点的度相对很低,但存在少量的度相对很高的节点。 因此,这类网络也称为非均匀网络( in h o m o g e n e o u sn e t w o r k ) 而那些度相对很 高的节点称为网络的“集线器( h u b ) ”,例如,美国高速公路网就可近似看作是 图2 2 随机网络与无标度网络的对比。” ( a ) 随机网络例子:美国高速公路网简化图;( b ) 无标度网络例子:美国航空 网简化图 第二论文研究的理论基础 一个均匀网络,因为不可能有上百条高速公路都经过同一个城市;而美国航空网 则可看作是一个无标度网络,大部分机场都是小机场,但却存在少量连接众多小 机场的非常大的机场,如芝加哥,达拉斯,亚特兰大和纽约机场( 图2 2 ) 2 1 5 序参数 交通系统的一个最有意义的地方就是整个网络对于信息包的处理和递送能 力。值得一提的是网络的通信能力不同于一个节点的通信能力。一个节点i 的通 信能力被设为常数c 。,但整个网络的通信能力则用临界的信息产生率足来度量, 在临界信息产生率尺c 处,发生从自由交通态到拥挤交通态的连续相变。自由交 通态是指在同一时步内所产生的信息包数目可以与被除去的信息包数目相抵消。 而若系统进入拥挤态,则不断产生的数据包中仅有一小部分的数据包可以到达各 自的目的地而能够从系统中去除,大部分数据包将不断地滞留于系统中,最终导 致系统全局交通堵塞瘫痪。为了精确地描述相变临界点,我们引进序参数b 羽: 刁( r ) - - 嫩等掣 7 ) 式中p ( f ) 是f 时刻存在于系统中信息包数目。叱= n ,o + f ) 一n p l 6 f ) 则是从f 时刻到t + 垃时刻系统中增加积累的信息包数目。( 一) 表示对于时间窗口血求平 均。当r r ,即 信息包产生率尺高于临界值疋,有( a p 0 ,序参数,7 一,其中厂是一个大 于零的正常数,这表示滞留积累于系统中的信息包数目会越来越多,最终将导致 系统全局交通瘫痪。所以当信息包产生率r 恰等于临界值r 时:r = 足,会有 一个相变出现。足是在自由交通流状态下允许的最大信息包产生率。信息包产 生速率只要不超过这一阈值,网络上的交通流就可以畅通无阻,通信网络就可以 复杂网络上的交通动力学研究 处理和传输其上的所有信息包,通信网络的功能是正常的,有效的。所以,临界 信息包产生速率可以度量通信网络系统的最大通信能力。 2 1 6 网络通信能力 由前面序参数的介绍可知,当信息包产生率尺恰等于临界值r 时:r = r c , 会有一个相变出现,信息包产生速率只要不超过这一阈值,网络上的交通流就可 以畅通无阻,通信网络就可以处理和传输其上的所有信息包,通信网络的功能是 正常的,有效的。所以,我们用临界信息包产生速率r 来度量通信网络系统的 最大通信能力3 羽。 2 1 7 网络平均传输时间 信息包的平均传输时间( 丁) 描述如下羽: 1 7 11 j v t o m l ( 丁) 2 瓦善互幽 式中儿缸,是在一段时间内网络的信息包总数;互是信息包f 的传输时间( 步数) 2 1 8 网络的介数 衡量网络特性的一个重要指标是介数( b e t w e e n n e s sc e n t r a l i t y ) 口u ,有结 点介数和边介数。 一个节点v 的介数( b e t w e e n n e s sc e n t r a l i t y ) 衡量了通过网络中该节点的 最短路径的数目。 铲萎掣 m9 , 其中0n 是从节点g 到节点t 最短路径的数目。o 矗( v ) 是从节点s 到节点t 并通过 节点v 的最短路径的数目。 边介数是指网络中所有节点对之问的最短路径中经过该边的路径数。 1 2 第二论文研究的理论基础 2 2 网络拓扑基本模型及其性质 要理解网络结构与网络行为之间的关系,并进而考虑改善网络的行为,就需 要对实际网络的结构特征有很好的了解,并在此基础上建立合适的网络结构模 型。在w a t t s 和s t r o g a t z 关于小世界网络,以及b a r a b a s i 和a l b e r t 关于无 标度网络的开创性工作1 之后,人们对存在于不同领域的大量实际网络的拓扑特 征进行了广泛的实证性研究。在此基础上,人们从不同的角度出发提出了各种各 样的网络拓扑结构模型。这里介绍和论文相关的几类基本模型,包括规则网络、 随机网络、小世界网络和无标度网络。 2 2 1 规贝u 网络 在一个全局耦合网络( g l o b a l l yc o u p l e dn e t w o r k ) 哺3 中,任意两个点之间 都有边直接相连。因此,在具有相同节点数的所有网络中,全局耦合网络具有最 小的平均路径长度f = l 和最大的聚类系数c f = l 。虽然全局耦合网络模型反映 了许多实际网络具有的聚类和小世界性质,但该网络模型作为实际网络模型的局 限性也是很明显:一个有个点的全局耦合网络有( 一1 ) 2 条边,然而大多数 大型实际网络都是很稀疏的,它们边的数目一般至多是d ( ) 而不是d 2 ) 。 一个得到大量研究的稀疏规则网络模型是最近邻耦合网络 ( 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 ) 啪1 ,其中第一个节点只和它邻居节点相 连。具有周期边界条件的最近邻网络包含个围成一个环的点,其中每个节点 都与它左右各剐2 个邻居点相连,这里k 是一个偶数。对于较大的k 值,最近 邻耦合网络的聚类系数为 q = 砸3 ( o o ) ( 2 4 ) 星形网络是比较特殊的一类网络。这里假设如果一个节点只有一个邻居节点,那 么该节点聚类系数定义为1 。有些文献中则定义只有一个邻居节点的节点聚类系 数为0 。若依次定义,星形网络的聚类系数则为0 。 2 2 2 随机图 与完全规则网络相反的是完全随机网络,其中一个典型的模型是e r d o s 和 r e n y i 于4 0 多年前开始研究的e r 随机图模型口7 1 。 假设有大量的纽扣( 1 ) 散落在地上,并以相同的概率p 给每对纽扣系上 一根线。这样就会得到一个有个点,约p n ( n 一1 ) 2 条边的e r 随机图实例。 e r 随机图中两个节点之间不论是否具有共同的邻居节点,其连接概率均为 p 。因此,e r 随机图的聚类系数是c = p = ( k n 1 ) 。当p 较小时( 0 p ( 后) 时,度为七的节点几乎不存在。因此,这类网络也称 为均匀网络或指数网络( e x p o n e n t i a ln e t w o r k ) 。近年来复杂网络研究上的另一 重大发现就是许多复杂网络,包括i n t e r n e t 、w w w 以及新陈代谢网络等的连接度 分布函数具有幂律形式。由于这类网络的节点的连接度没有明显的特征长度,故 称为无标度网络。 为了解释幂律分布的产生机理,b a r a b a s i 和a l b e r t 提出了一个无标度网 络模型,现被称为b a 模型阳3 。他们认为以前的许多网络模型都没有考虑到实际 网络的如下重要特性: 增长( g r o w t h ) 特性:即网络的规模是不断扩大的。例如每个月都会有大 量的新的科研文章发表,而w w w 上则每天都有大量新的网页产生。 优先连接( p r e f e r e n t i a la t t a c h m e n t ) 特征:即新的节点更倾向于与那 些具有较高连接度的“大 节点相连接。这种现象也称为“富者更富( r i c hg e t r i c h e r ) 或“马太效应( m a t t h e we f f e c t ) 。例如,新发表的文章更倾向于 引用一些已被广泛引用的重要文献,新的个人主页上的超文本链接更可能指向新 浪、雅虎等箸名的站点。 基于网络的增长和优先连接特征,b a 无标度网络模型的构造算法如下: 增长:从一个具有个节点的网络开始,每次引入一个新的节点,并且 连到m 个已存在的节点上,这里m m 。 1 8 第二论文研究的理论基础 优先连接:一个新节点与一个已经存在的节点f 相连的概率h ,与节点i 的 度也、节点j 的度七,之间满足如下关系: l i l - - 轰j , c 2 n , 在经过f 步后,这种算法产生一个有n = t + m 。个节点、m t 条边的网络。图 2 5 显示了当m = m 。= 2 时b a 网络的演化过程。初始网络有两个节点,每次新增 加的一个节点按优先连接机制与网络中已存在的两个节点相连。 - 趣- 弋:毯风一夺 图2 5b a 无标度网络的演化似= m 。= 2 ) 下面介绍小世界网络模型的一些统计性质。 1 平均路径长度 b a 无标度网络的平均路径长度为h h 捌: 三芘 ! ! 曼型 l o g l o g n ( 2 1 2 ) 这表明该网络也具有小世界特性。 2 聚类系数 b a 无标度网络的聚类系数为“3 3 : c :m 2 ( m + 1 ) 2 【i n 掣) 一上】世坚 4 ( m 1 ) 、m 朋+ 1 。t ( 2 1 3 ) 这表明与e r 随机图类似,当网络规模充分大时,b a 无标度网络不具有明显的 聚类特征。 3 度分布 目前对b a 无标度网络的度分布的理论研究主要有三种方法:连接场理论m 3 、 1 9 复杂网络上的交通动力学研究 主方程法h 4 3

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论