（管理科学与工程专业论文）小世界网络理论在交通网络中的应用研究.pdf

摘要 本文首次将国外交叉学科最新研究成果一s w n ( s m a l lw o r l dn e t w o r k ) 模型引入 管理领域，研究小世界网络的数量特征，移植成熟的数学与物理理论方法，结合 我国社会交通网络的特征，提出了符合国情的降低网络平均路径长度的策略方 案，开发实现了基于网络效率理论的网络评估方法和辅助规划技术 针对我国航空交通网络平均路径长度大，效率低的问题，本文从数量特征的 角度对小世界网络的优越性进行了探讨和研究，并引入遗传算法对固定数目的捷 径配置进行了数字模拟结果表明，当捷径相互连接，并具有一个或几个中心点 时，网络具有较低的平均路径长度 f 在解决网络容错性不高的问题的过程中，本文首先用全局效率和局部效率两 个参数重新对小世界网络进行了定义，指出小世界网络有着高的全局效率和局部 效率，即有着高的全局和局部的传播的效率，引申出提高一般网络效率的原理和 方法然后结合运筹学中图论和网络的理论方法，利用成熟的数学计算语言 m a t l a b ，对一具体的南京市公交网络图进行了仿真和计算，并对此给出分析 和方法，并取得了良好的结果，而为研究建立航空工业企业，市场与宏观经济系 统内外关系的定量分析评价指标体系作出准备 关健词， 小世界网络平均路径长度9 噍爹运筹学交通网络航空运输 a b s t r a c t t h i s p a p e ra p p l l e dt h em o d e lo fs m a l lw o r l dn e t w o r ko v e r s e a st o m a n a g e m e n tf i e l df o rt h ef i r s tt i m ew h i c hw a st h el a s tr e s e a r c hp r o g e n y i ni n t e r c r o s ss u b j e c t 。a n di n v e s t i g a t e dt h eq u a n t i t yc h a r a c t e ro ft h i s k i n do fn e t w o r k t h e ni ta l s op r o v i d e daw a ya c c o r d i n gw i t ho u rs i t u a t i o n t or e d u c et h ea v e r a g ep a t hl e n g t ho fn e t w o r ka n dd e v e l o p e dam e a s u r et o n e t w o r ke v a l u a t i o na n d t e c h n i q u et oa i dn e t w o r kb u i l d i n gb a s e do nt h e e f f i c i e n c yt h e o r yo fn e t w o r kb yt r a n s p l a n t i n gt h em a t u r e dt h e o r yo fm a t h a n dp h y s i a sa n dj o i n i n gt h ec h a r a c t e ro fo u r t r a n s p o r t a t i o nn e t w o r k i no r d e rt or e s o l v et h ep r o b l e mw h i c ha r i s e df r o mt h ea v e r a g ep a t h l e n g t ha n de f f i c i e n c yo fo u ra v i a t i o nn e t w o r k ，w er e s e a r c h e dt h ea d v a n t a g e o fs m a l lw o r l dn e t w o r kf r o mt h e a n g l eo fq u a n t i t yc h a r a c t e r i s t i ca n d a p p l i e dt h eg a ( g e n e t i ca r i t h m e t i c ) t on u m e r i cs i m u l a t i o ni nc o n d i t i o n c o n f i g u r a t i o no fl i m i tn u m b e ro fs h o r t c u t s e x p e r i e n c e ss h o wt h a tt h e n e t w o r kh a sah i g he f f i c i e n c yw h e nith a sa “s i n g l ec e n t e r ”o rs o m ea n d w h e na l1s h o r t c u t sa r ec o n n e c t e dt oe a c ho t h e r i nt h ea s p e c to ff a u l t t 0 1 e r a n c ei nn e t w o r k w er e d e f i n e dt h es m a l l w o r l dn e t w o r ki ng l o b ee f f i c i e n c ya n dl o c a le f f i c i e n c ya n di n d i c a t e dt h a t s w nh a s h i g hg l o b ee f f i c i e n c y a n dl o c a l e f f i c i e n c y ( i e h i g h t r a n s p o r t a t i o ne f f i c i e n c yo fg l o b ea n dl o c a l ) a n dt h e np r o v i d e daw a yt o i m p r o v et h ee f f i c i e n c yo fg e n e r a ln e t w o r k f i n a l l yw es i m u l a t ea n dc a l c u l a t ead e f i n i t et r a n s p o r t a t i o nn e t w o r k o fn a n j i n gb ym a t u r e dm a t ht o o l m a t l a bj o i n i n gt h e o r yo fc h a r ta n dn e t w o r k w i t ha n a l y s i sa n dc o n c l u s i o n e x p e r i e n c e ss h o wt h a te f f i c i e n c yt h e o r yo f s w nc a na i dt h eb u i l d i n ga n de v a l u a t i o no fr e a ln e t w o r kw e l l t h er e s u l t so ft h i st h e s i sc o m ef r o m g e t t i n g ag o o do u t c o m eb ya p p l y i n g t h eq u a n t i t yc h a r a c t e r i s t i ct ob u il d i n ga n de v a l u a t i o no fn e t w o r k i tm a d e a g o o dp r e p a r a t i o n t ot h er e s e a r c ho f b u i l d i n g ai n d e x s y s t e m o f q u a n t i t a t i v ea n a l y s i so fo u t s i d eo ri n n e rr e l a t i o n s h i p b e t w e e ni n d u s t r i a l e n t e r p r i s ea n dm a c r o e c o n o m i cs y s t e m k e yw o r d s s m a l1w o r l dn e t w o r kr e g u l a rn e t w o r kr a n d o mn e t w o r k a v e r a g ep a t h l e n g t h a v i a t i o nt r a n s p o r t a t i o ne f f i c i e n c yr e s e a r c ht h e o r ym a t l a b t r a n s d o r t a t i o nn e t w o r k 南京航空航天大学硕士学位论文 1 1 背景介绍 1 1 1 关于小世界网络 第1 章绪论 在社会上由个人，群体，或组织所构成的某一类型的网络有着与一般拓扑结构的网络 所不同的网络属性，这个属性将这类网络与其他网络区分开来。这个属性即这种网络同时 具有与典型的规则网络与随机网络相似的性质首先，社会网络有着良好的局部性特征， 例如，我们从人群中随机的挑选出两个人a 与c ，调查他们相互之间是否熟悉，如果h 与另 外一人b 熟悉，而b 又与c 熟悉，则很有可能h 与c 也相互认识在这一方面，社会网络显 示出了与规则网络相似的特性，它们都显示了良好的局部性另一方面，大家都知道某一 个人可以通过一系列的中介( 可以是人，也可以是媒体) ，与相隔很远的另全人相互联系 这就是6 0 年代末由美国科学家m i l g r a m 所提出的有名的：六度分离理论用图论与网络学 的术语就是两个相距很远的节点是可以相连的这个特性在规则网络中是没有的。而却是 随机网络的一个重要特征在随机网络中。两个任意选择的节点之间的平均最短路径正比 于l o g n l o g z ，这里n 代表随机网络中的节点总数，而不是网络中的配位数( 即每个节点与 相邻节点的连接数) 因此，社会网络有着规则网络与随机网络两者的共性，又有着两者所 没有的其它重要特性 物理与数学家w a t t s 以及s t r o g a t z 通过研究，就将社会网络抽象为一种介于规则网 络与随机网络两者之间的一种新的网络一小世界网络小世界网络由拓扑结构为规则网络 的底层网络出发，在底层网络的任意两个选定的节点之间添加连接( 即添加两节点连通的 捷径) ，使之向随机网络过渡当捷径增加到了一定程度时。即产生了小世界网络的形态 如图卜1 所示 小世界网络理论在交通网络中的应用研究 图卜l 其中p 是在网络巾随机添加捷径的概率。 这三种网络相互之间的主要区别如下图 、网络类型规则网络 随机网络小世界网络 艄 特征路径长度低高 介于两者之间 类聚度雷高低 介于两者之间 实际距离 则l = 1 ( n ( n 一1 ) ) 1 t ， 聚类度，即两个点都是一点的邻居，而它们也是邻居，即一对点的平均派系化。 表1 - 1 可以看到，小世界网络的两种数字特征差异不大，它具备其余两种网络的优点，所以 说它是一种具有良好特性的网络在现实生活中，不仅由人群构成的社会网络有此种特性 其它嘲络如神经网络，电路系统，交通网络，计算机网络等都具有这样的特性，都可以将它 们抽象为小世界网络因此，研究小世界网络的特性就能更好的理解现实生活中各种网络 的数字特征，掌握它的本质，为提高网络的运行质量，工作环境等打下良好的基础。如果运 用经济学理论进行分析，有助于展现令人耳目新的关于企业资产重组、市场营销、资源、 价值和信息循环等宏微观经济活动的网络形态，以利于对经济活动进行分析和控制。 国外对小世界网络的研究主要集中在运用网络和数学模型相结合分析社会学和自然 科学领域的问题，而国内对s 州的研究还处于起步阶段因此，对小世界网络的研究才具 2 南京航空航天大学硕士学位论文 有更重要的研究意义 1 1 2 小世界网络理论分析中的图论 图论是一门新的科学，至今只有2 0 0 多年的历史，它在运筹学，计算机科学，物理学， 化学等方面有着广泛的应用近几十年来，社会学家开始利用图论来研究社会闯题，成功 地解决了社会学中的各种优化以及其他问题，也使图论理论得到了发展本文主要是从图 论的角度对网络进行数学探讨，研究网络的类聚度，特征路径长度，最段路径等，并绘出了 有关的算法 目前，图已经用来作为与对象的安排有关问题的模型，如计算机科学，运筹学，通讯科 学，电网络分析，量子物理，结构化学，建筑学，经济学，语言学，生物学，社会学，遗传学，法 律学，人类学，和定理证明等 在计算机科学中，利用同的单向树和有序章甘作为一种数据结构：可用于分析算法的好 坏：在编码理论和程序设计中，利用图的霍夫曼树可以得到解决：利用最小树的概念及算 法可以解决数据存放的问题：利用线图结构可处理数据管理系统比如在一个单位的人事 档案中，需要将每个人的姓名，年龄，籍贯及职务等记录下来，把这样的信息存放在存贮装 置中，称为一个记录，记录间有各种各样的联系，可把一个复杂的数据结构通过建立标号 有向图来模拟：用图的顶点表示记录，从顶点v 。到v ，的一条带标号为a 的有向边v tvs 表 示记录i 和j 有关系a ，这个数学模型可反映整个数据结构，利用它可系统地存放和检索 信息 运筹学中许多问题如最段路径，人员配置，生产计划和投资安排等可归结为二元关系 的问题比如用图的点表示某种货物可以贮藏或装船的实际位置，从一边到另一边的一条 有向边和记在这条边上的一个正数代表一条运输货物的水道和它的能力，这个能力给出 同时可以通过的最大允许数目 图与交通网络有极其相似之处因而用图论方法解决交通网络问题很自然，通过图可 以研究交通网络的结构性质，布线设计，控制方法以及阻塞的可能性等问题 因此： 1 )在研究以某种特定方式相互联系的一些物件之间的相互关系时，图论几乎总 是个很有用的工具。在许多实例中，这些物件可以用一个图的顶点来表示， 而它们之间的相互联系可以用顶点之间的连线表示 2 )图很适用于表示系统，不管是数学的，物理的或社会学的等等，这是因为系统 的定义包含了一些元素，而这些元素与其它元素相关联 3 )图可被用于构造模型，但在什么形式下以及解决何种类型的问题具有多样性， 1 小世界网络理论在交通网络中的应用研究 不过只要具体分析，构件模型，总结规律，就可使之成为研究数学模型 的一种得力工具 综上所述，我们可以将小世界抽象成点与线连接成的图，继而对小世界网络 可以从网络与图论的角度对其进行分析和研究 1 - 2 研究的目的与主要内容 小世界网络具有良好的数学特征，特征路径长度小，全局效率和局部效率比 较高，本文研究的主要目的在于从数学特征去研究小世界网络的这些特征，得出 这种网络的本质所在，继而从之抽象出一般网络的模型和评估网络的标准，以及 构建优良网络的一般技术和方法，以提高网络中信息传播的速度，增大网络的容 错性，减少节点之间的平均距离 本硕士论文的选题依据是一项受航空基会资助的研究项目。在研究小世界网 络原理的基础上，重点研究小世界模型及网络理论在运输网络中的应用问题。 在本文的第二章，我们介绍了小世界网络的产生，发展，数学特征，国际上研 究小世界的现状，以及运用小世界网络原理在现实生活中的意义 小世界网络具有很强的数字特征，我们可以使用特征路径长度以及类聚度两 个参数来描述一个网络，但是用它们不能反映现实生活中的真实情况因此在第 三章我们引入了全局效率和局部效率这两个参数重新对网络进行定义 本章的最后对小世界网络的一个重要特性一首序转换进行了叙述和分析 在第四章中，我们叙述了如何提高网络的效率这里，我们结合图论和计算工 具m a t l a b 进行了数学模拟和分析，提出了一种提高网络效率的方法 第五章针对航空交通网络中轴心辐条式网络的规划形式，研究了在一个网络 中如何降低平均路径长度l 的问题，并探索了网络中捷径的分布，以及捷径数目 在固定这一条件下，如何进行有效的配置这一问题最后试图用遗传算法进行数 学模拟，以验证得出的结果 在第最后一章，我们结合航空交通网络的现实情况，叙述了如何提高轴心辐 条式网络的运行效率 最后是全文的总结，总结本文所取得的成果，属于自己的创新，并提出了进一 步研究的方向 南京航空航天大学硕士学位论文 第2 章小世界网络( s w n ) 概论 2 1 小世界网络的产生 美国经济和社会事务部预计到2 1 世纪初世界人口将首次超过6 0 亿。无庸置疑，人 类世界在近期已很庞大。尽管有着全球性的统计数据，但人们依然宣称世界很小。在某 种角度上讲他们是对的，尽管有不计其数的入在这个星球上然而描述人们相互联系的 社会网络的结构表明：人与人之间的相互联系是近接的。 首次关于社会网络结构的定量研究之是6 0 年代末由m i i g r a m 在哈佛大学完成的， 他成功完成了一个著名的试验，得出了一个有名的结论。他拿了许多信，这些信都署上 了他在曼彻斯特的波士顿的一个股票商朋友的名字，他将信分发给在英国尼布鲁斯随机 挑选的一些人，要求他们尽快将信通过熟人传到他的这位朋友手中。被挑选的人通过将 信传送给自己在股票界或商界的朋友，这些朋友又通过熟人将信一一传送下去。最后预 期数量的信件到达了目的地。经统计分析m i i g r a m 发现每封信件平均要通过6 个人才能 把信从尼布鲁斯传到他在波士顿的朋友手中。忽视实验误差，他得出了结论是任意两个 人之间可以平均通过6 个熟人联系在一起，或者说，世界上任何2 个人之间都可以被某 些因素相连。人们称这种特征为“6 度分离”，即：世界上任意2 个随机挑选的人可以由 一条以中间熟人形成的短链所相连，这个结论用物理学术语来说就是“小世界效应”。小 世界效应不仅仅只适用于朋友之间的网络。在二十世纪九十年代，美国的大学校园里曾 经流行着这样一个游戏，将任意两个影视演员通过最多8 个合作影星组成的链条联接起 来，这也是一种小世界效应的反映。 看上去这些游戏和实验都有些无聊，为什么一个严肃的科学家要关心社会网络的结 构呢? 原因就是，这种网络对交流来说是极其重要的。大多数的人类交流从广义上讲也 就是使用语言的地方，通常是在个体之间发生。新闻、传闻、疾病和潮流的流行都发生 在个体与个体之间的交流接触上。一条信息经由平均分离度为6 的社会网从海岸一边传 到另一边时，其速度要比经由平均分离度为二十或更大的社会网络快的多。更重要的是， 疾病的传播也是经由人与人的接触而发生的，这种接触的网络的结构对流行病的传播有 着巨大的促进机制，因此研究此种社会网络有助予了解和控制疾病的传播。不管是流感， 或是计算机h i v 病毒，在一个高度连接的网络，其传播速度要比在个体与个体之间的路 径很长的网络中传播要快的多。如果我们考虑到实验或游戏中的误差，我们可以得到一 个通俗的结论：世界上任意两个随机挑选的人可以由一条以中间熟人所形成的短链所相 5 小世界网络理论在交通网络中的应用研究 连，这种说法已被证实，并被人们广泛接受，学者们统一称之为“小世界网络效应”。我 们每个人都生活在网络的世界之中，世界上的许多复杂的系统，从各个国家组成的民族 林，到由计算机构成的因特网，从青蛙的脊椎神经系统到人类组成的人际圈，如果将系 统中的每个元素，每个单位看成个节点，各个元素、单位间的联系看作边，那么这些 系统都可以抽象为一个网络，而信息在其中的传播，是否也具有上述类似与“六度分离” 的规律呢? 答案是肯定的。 2 2 小世界网络的数字特征及与规则网络和随机网络的比较 在下文中我们将讨论几年来在社会网络理论上的发展，特别是在网络特征及模型化 方面的发展，首先我们看一下随机图。 对小世界效应最简单的解释用到了随机图的思想。假设，世界上有n 个人，平均每 人有z 个熟人。这意味着，在整个人群中有( 1 2 ) n * z 个人与人之间的联结。数字z 就 叫做网络的配位数。 我们可以建立一个非常简单的社会模型，取n 个点，随机地在两点之间连( 1 2 ) n * z 条线以代表联系。这种网络叫随机图( 如图2 - 1 所示) 。随机图被广泛地应用于数学领域 中。在此种图中，如果一个人 有z 个邻居，每个邻居又有z 个邻居，那h 就有大约z 2 个次邻居。如此类推，a 也有z 3 个三级邻居和z 个四级邻居等等。多数人有1 0 0 到1 0 0 0 个朋友，因此，z | 已经在1 0 8 和1 0 ”之间了，这么大的数字已足以和世界人口相比了。通 常为了取到网络中所有的n 个人( n 称为随机图的半径) ，我们要考虑分离度d ，d 由等 式z o = n 给出，或：d = ( 1 0 9 n ) ( 1 0 9 z ) ，分离度随着网络大小而呈对数性的增长，是小 世界效应的典型。我们可以很容易看到，随机图显示出了小世界效应。因为l o g n 只能随 着n 缓慢的增长，即使在一个大的系统中分离度也是很小。作为小世界效应的一个例子， 国外有学者对互联网上文献之间的超链接网络进行了研究。他们指出，尽管在他们研究 的时刻，互联网上有n 约等于8 x 1 0 8 份文献，即n = s x l 0 8 ，但这些文件之间相互链接的的 平均长度却只有1 9 。 6 南京航空航天大学硕士学位论文 图2 - 1 ( 随机图，n = 7 ，z = 2 ) 但对于作为社会网络模型之一的随机图，有一个很重要的问题。这就是人们的熟人 圈总是重叠了很大部分。即你朋友的朋友很可能也是你的朋友，或者换句话说，你的两 个朋友相互之间可能也是朋友。这意味着，在真实社会网络中，如果说一个人a 有z 2 个 二级邻居，这是不对的，因为许多朋友的朋友本身也是a 的朋友。这种特性叫做网络的 类聚性。 一个随机图不显示类聚性。因为在随机图中，两个a 的朋友相互之间是朋友的概率 不会大于两个随机挑选的人是朋友的概率即a 的两个朋友不可能相百熟悉，即不可能 形成集团化。相反，许多真实世界的网络显示出了类聚性。我们可以这样定义聚类系数 c ，即两个点都是一点的邻居，而它们也是邻居，即这一对点的平均派系化。在一个充分 联结的网络中，每个人都彼此认识，此时c = i ，在随机图中，c = z n ，它在大型网络中很 小。在真实世界的网络中，人们发现，尽管c 比1 小的多，但比0 ( n _ i ) 要大的多。 在同一网络中，我们可以定义两点之间的平均长度为l ，这和上面所讨论的网络半 径不同，d 是两点之间的最大长度。但l 可以用随机图中的节点数的对数来衡量。容易 看出，因为平均长度严格她小于或等于最大长度，因此l 不能比d 增长的快。在有演员 所组成的网络，昆虫的神经网络，及美国某一地区的行政网络，这些网络中l 值都很小， 这表明小世界效应起了作用。那么，如果随机图没有很好地吻合真实世界网络特性的话， 是否有一种替代模型呢? 由随机图我们可以引申出小世界模型的概念。 为了建立一个模拟真实世界网络的模型，我们簧寻找一种网络模型，这种网络既有 类聚性，又有小世界特性。正如我们所讨论，随机图显示了小世界效应，具有平均点到 点的距离，这种距离随着点的总数n 对数性地增长，但它们不具有类聚性这种特性 即一个点的两个邻点通常相互之间也是邻点。从某种意义上讲，随机图的反面，是一个 小世界网络理论在交通网络中的应用研究 完全有序的网络，最简单的例子就是一个一维的网络，即一组格点被它安置在一条直线 上( 如图2 2 所示) 。如果我们取一条这样的网格，将每个点和靠近它的z 个点相连，容 易看出，隔着一段距离的直接邻点相互之间也是邻点，即显示了类聚性。通常，为便于 研究我们给网格界定一个圆形的边界，这样它自己形成了一个环。对这样一种网络，我 们可以精确计算它的类聚值c 。如果z ( ( 2 3 ) n ，如几乎所有的图一样，那么我们发现， c = 3 4 ( z - 2 ) ( z - 1 ) ，当z 增大时极限为c = 3 4 。我们也可建立一样更高维的网络结构， 如方形或立方体网络，同样也有着类聚性。在通常维数d 下，类聚系数c 值为c = 3 4 ( z - 2 d ) ( z - d ) ，当z 耋2 d 时，趋向于3 4 。然而低维的规则网络不显示出典型的点到点之间距 离的小世界效应，即这种距离随着系统的大小缓慢地增加。很显然，对一个d 维的规则 网络，因为它是一个有着m 条边的正方形或( 超) 立方体，因而它有n = l d 个点，平均点 到点距离随着l 的增加而增长，即等同于随着妒4 的增加而增大。对于小的d 值这刁i 是 一个小世界的行为。例如，在一维中，这意味着平均距离随着系统大小线形地变化。如 果将网络的维数增大，那么n i d 变成了一个缓慢增长的n 的函数，因此网络此时又显示 了小世界效应。可以将这作为我们在真实网络中所见的解释吗? 可能真实的网络是粗略 的很高维的规则网络。尽管人们还在广泛讨论此种解释，但它实际上不是不合理的。倘 若平均配位数z 比网络维数的2 倍还高的多，那它就很好地起者作用。( 若将z 趋向2 d ， 则类聚系数趋向于0 ，显示网络失去了类聚特性。) 图2 2 一维规则图，每个节点和两个邻点相连。 然而又存在另一种小世界模型，这种模型可能更好地符合我们每天的社会网络特性 的直观理解。首先建立一个模型，这种模型说起来是一维的，但本质上是一种低维规则 网络，但它像随机圈一样，产生小世界效应时本身有某一随机性。如下所述，我们提出 了一种特殊的建模技巧。如图三中的一维网络，我们依次通过网络中的每个链接，再以 概率p ，随机地“重绕”这个大环，即我们将一端末尾移到一个我们从网络的剩余部分 随意挑选的一个新位置。对小的p 来说，这就形成了一个图，图大致是规则的，但有一 些连接，这些连接横穿网络，引出了长长的距离( 如图2 3 所示) 。尽管有一些特殊点的 邻点数可能大于或小于z ，但此网络的配位数如前一样平均是z 。 用社会上的话，我们可以这样说以证明此种模型是合理的。尽管多数人是他们直接 邻居的朋友，这些直接邻居包括：同一街坊的邻居，工作伙伴，经朋友介绍的熟人，但 南京航空航天大学硕士学位论文 有一些人和少数人是朋友，可能是相隔着很远的别的国家的人，可能是其它行业的人， 也可能是生活过的别的地方的熟人，等等。这些远距离的熟人可以由此种模型中的长距 离链来代表。 图2 3 ( 以概率p 断键重联所形成的网络) 很明显，对有着极小值p 的这个模型来说，类聚系数c 值与在上面给出的完全有序 网络的类聚值很接近，那些类聚值在小d 和z 固定时趋向于3 4 。通过数学模拟显示， 平均点到点距离l 是可以与真实随机图中的l 相比较的，甚至当p 值很小时。例如，对 一个随机图，n = 1 0 0 0 ，z = l o ，随机挑选的两点的平均距离大约是l = 3 2 。对于我们的重 绕模型，平均距离稍大一些，当重绕概率p = l 4 时，l = 7 4 ，比随机图值的两倍大了一 些。因而模型同时显示出了类聚性和小世界特性。这个结果已被进一步的模拟和分析所 证实。 2 3 本章小结 在本章中，我们介绍了小世界网络的产生与发展，小世界网络与规则网络和随机网 络相比，具有同时大的类聚值和大的平均点到点的距离，因此具有相对优良的数字特性。 世界上许多复杂的系统，都可以抽象成小世界，因此研究小世界网络的特征，探索它的 本质，对解决现实世界中发生的各种问题具有重要的参考价值。 在本文中，我们将赋予这些网络结构性的特征，如特征路径长度、聚类度等，这样 就能更进一步地理解系统中的动力机制，进而控制信息的传播速度，提高网络的流通效 率，这些将在下面详述。 小世界网络理论在交通网络中的应用研究 第3 章小世界网络模型的数字特征分析 3 1 构建小世界网络模型的基本思路 第二章讨论了小世界网络的产生、小世界效应极其数字特征，这一章将重点讨论如 何构建小世界网络。 对小世界效应最简单的解释用到了随机圈的思想。即我们将n 个点代替n 个人，每个 人平均 有z 个熟人，即每个点有z 个邻点，然后随意地用( 1 2 ) n z 个线条将它们联系在一 起，这样得到的便是一个随机的，无序地网络，称之为随机图，如图3 一l 所示。 图3 一l 随机图 而与随机图相反的，则是一种完全有序的规则网络最简单例子便是一维晶格图， 网络的结点有序地排列在一条直线上，每个节点都与最近的4 个节点相联结。如图3 2 所 示。 图3 - 2 一维晶格图 南京航空航天大学硕十学位论文 图3 - 3 规则网络图 我们可以很清楚地看出一个节点的两个邻节点，相互之间也是邻节点，我们把这种情况 称为聚类现象。” 现在我们将图3 3 中的边以某一小概率p 进行断键重连，或在网络中加键等方法，可 以重新得到一种网络，如图3 - 4 ，这种网络既不是完全随机的，也不是完全有序的，介于 两者之间，我们就称之为小世界网络( s w n s m a l lw o r l dn e t w o r k ) 。研究表明世界 上的大多数系统都能抽象为小世界网络。“】，j 、世界网络是对现实世界的抽象，研究它就 能更好地探索各种现实系统，譬如，对流行病的传播可以抽象成这一类网络，运用网络 的特征路径和效率等特征量，可以有效地控制疾病的传播，反过来，也可运用小世界网 络理论，加速广告信息的传播。小世界网络的应用十分广泛，计算机网络，母公司与子 分公司的联营，疾病的传播，员工的合作，处处有其用武之地。下面我们将从数学的角 度上对小世界进行分析。 ，f 瓣文 j - r 攀 图3 - 4 断键重联后的网络图 、 。t f o 、江 。一 0 ， j x 0 &n0诊y，弭、 小世界网络理论在交通网络中的应用研究 3 2 小世界网络的特征路径长度l 和平均边数c 假设某个普通的拓朴网络图g 是连通图，g 中有n 个节点和k 条无权边，且 k 0 ，为o ，但对p = 0 为一常数。这显 示，将小世界视为阶跃函数，或p = 0 的首序转换都是合情合理的。对首序转换的特征描 写不是建立在t 的间断点的基础上，而是建立在现在我们讨论的t = i d 的结果之上。 在r g 内容中显示出，在一个首序固定点一个本征指数必取值y = d ，因而才能期望出 现l - d 的有限大小的移位，也即，y = d 意味着转换是首序的。本征指数y = d 的存在性导致 了有限了的偏正。由此我们看到一的有限大小的偏正是首序转换的鲜明特征。在小世界 系统中，参数l ( p ) 当l 一一时在p = o 点是一个阶跃函数。但对有限的l ，- ( p ，1 ) = l ( p ，l ) 几非零，不仅在p = o 点，而且在所有的p = c ，可以视为无 穷大。矩阵如图6 2 所示： 图6 2 由图6 1 得出的2 3 维距离矩阵 将图中的数据按如图6 3 所示的流程图进行处理 南京航空航天大学硕士学位论文 图6 3 程序设计流程图 将数据输入m a t l a b 软件，可以得到如下结果：e “= o 1 6 2 5 ，e ，。= o 0 9 8 3 。由前文可 知，因为e ( g ) 表示的是整个网络中的所有点都并发传递消息的效率，从效率的定义我们 可以直观的看出，e 越大越好，也即越接近l 越好，即o e ( g ) 1 ，且越接近1 越好。因此， 此时的e ( g ) 远没有达到满满意的水平，这就需要对现行的网络进行重新构建，可以采 用加键、断键重联以及现行键重联的方法，具体采用那一种，则要视具体情况而论。 由软件得出的结果可以看出。此交通网络的全局效率和局部效率远小于1 ，远没有达 到最优，可以进一步对它进行优化和改进。对上图进行修改，采取的方法是在它的网络 图中进行断键重联，可得e “= o 1 5 2 9 ，e 。c = 0 1 2 1 8 。同理，可以运用此法不断改进和完 善，直至其全局效率和局部效率达到令人满意的程度。 小世界网络理论在交通网络中的应用研究 4 3 本章小结 由于效率参数比特征路径长度和类聚度等能更好的反映现实系统的状况，因此作者 考虑从全局效率和局部效率的角度对网络进行初步的测评和规划。通过选取合适的算法， 本文时某一具体的交通网络即南京市局部公交线路图进行了模拟运算，经过分析证 明，小世界效率理论确实可以对网络优化起到一定的辅助效果。 另外，需要说明的是，本章的目的在于介绍这样一种交通网初步优化的方法，并没 有苟求具体线路调整的精确性。因为实际情况往往相当复杂，本方法的优良与否也往往 需要在实践中去检验。 南京航空航天大学硕士学位论文 第5 章小世界网络路径理论 5 1 再论平均路径长度 在前几章中我们谈到小世界网络模型是一种介于随机网络和规则网络之间的一种网 络，它可以很好的代表现实生活中的真实网络，比如计算机网络，互连网络，交通网络 等。小世界有两个重要的特性，平均路径长度l ，以及类聚系数c 。对于平均路径长度l ， 我们定义为网络中一对点在最短路径方向上的平均长度，它反映了点与点之间的流通效 率，比如说两点之间相互交流信息的快慢，或从此点到那点所花时间的长短。