（理论物理专业论文）复杂网络理论在哈尔滨公交系统中的应用研究.pdf

大连理工大学硕士学位论文 摘要 本文首先综述和介绍了复杂网络的理论、基本概念、典型模型。其次将复杂网络理 论运用到哈尔滨公交系统现实网络当中，就其在哈尔滨公交网络中的应用进行了研究。 本文主要工作分为三部分。 第一部分介绍了复杂网络的基本概念和复杂网络研究的历史。复杂网络是对复杂系 统的一种抽象模型，i n t e r n e t 、交通网、电力网等是显而易见的网络，像细胞的新陈代谢， 恒星及星际气体中的化学反应，科学研究中的合作关系等也都可以看成网络。 第二部分综述了复杂网络模型的演化和性质，以及复杂网络的主要特征。复杂网络 模型的演化模型包括规则图、随机图、w s 小世界模型、b a 无标度网络模型、适应度 模型等等。复杂网络的主要特征除小世界效应外，还包括网络的鲁棒而又脆弱性、网络 的自相似性。 第三部分将复杂网络理论运用到哈尔滨公交系统现实网络当中。在公交网络中引入 了复杂网络中的基本静态几何量，结合哈尔滨市公交网络的实际数据，验证了哈尔滨公 交网络的小世界特性和无标度特征。 结合哈尔滨市实际公交网络数据建立了哈尔滨市公交停靠站点网络模型和哈尔滨 市公交换乘网络模型。这两个模型反映了公交网络的自然拓扑特征以及公交网络的可达 性。这两个模型的理论意义可能给出促进交通科学与技术发展的新方案与模式，对公交 网络的设计、改建有一定启发。 最后，本文对公交网络的鲁棒性与脆弱性进行了研究，针对公交停靠站点网络及相 同规模的髓机网络，分别比较了其上的鲁棒性与脆弱性，并在随机故障与蓄意攻击的情 况下研究了公交停靠站点网络上的鲁棒性与脆弱性，发现公交网络对于随机故障并不是 有很强的鲁棒性，但是对于蓄意攻击却有很大的脆弱性。 关键词：复杂网络；公交系统；应用 复杂网络理论在哈尔滨公交系统中的应用研究 t h e a p p l i c a t i o nr e s e a r c h o fc o m p l e xn e t w o r k st h e o r yf o rt h e p u b l i ct r a f f i cs y s t e mi nh a r b i n a b s t r a c t i nt h i sp a p e r , b a s i cc o n c e p t i o n sa n dt y p i c a lm o d e l sa b o u tc o m p l e xn e t w o r k sa r e o v e r v i e w e df i r s t l y t h e n , t h et h e o r i e sa n da p p l i c a t i o n sa b o u tc o m p l e xn e t w o r k sa r e r e s e a r c h e df o rt h ep u b l i ct r a f f i cs y s t e mo fh a r b i n t h et h e s i si sc o m p o s e do ft h r e ep a r t s i nt h ef i r s tp a r t ，t h eb a s i cc o n c e p t i o na n dt h eh i s t o r ya b o u tc o m p l e xn e t w o r k si s i n t r o d u c e d t h ec o m p l e xn e t w o r k sa r ea na b s t r a c tm o d e la c c o r d i n gt ot h er e a lc o m p l e x s y s t e m ，a n dt h ei n t e r n e t 、c o m m u t a t i o nn e t w o r k sa n de l e c t r i cn e t w o r k sf o re x a m p l e sa r e o b v i o u s l yr e a ln e t w o r k s ，a n dt h em e t a b o l i s mo fc e l l s 、t h ec h e m i c a lr e a c t i o no fs t a r sa n d i n t e r s t e l l a rg a s 、t h es c i e n t i s tc o o p e r a t i o ns h i pa r ei n c l u d e di ni ta l s o i nt h es e c o n dp a r t , t h ef e a t u r e sa n de v o l u t i o no fc o m p l e xn e t w o r km o d e la r eo v e r v i e w e d t h ee v o l u t i o nm o d e li s c o m p o s e do fs e v e r a li t e m s ：r e g u l a rg r a p h s 、r a n d o mg r a p h s 、 s m a l l - w o r l dn e t w o r k s 、s c a l e - f r e en e t w o r k s ，e t c t h em a i nf e a t u r e si n c l u d en ot h er o b u s ta n d f r a g i l e ，s e n - s i m i l a rn a t u r eb e s i d e st h es m a l l - w o r l de f f e c t i nt h et h i r dp a r t ，t h et h e o r i e sa b o u tc o m p l e xn e t w o r k s a r eu t i l i z e dt ot h ep u b l i ct r a f f i c s y s t e mo fh a r b i n t h i st h e s i si n t r o d u c e st h eb a s i cs t a t i cc h a r a c t e r i s t i c so fc o m p l e xn e t w o r kt o t h ep u b l i ct r a f f i cn e t w o r k c o m b i n i n gt h er e a ld a t a , t h ep u b l i ct r a f f i cn e t w o r ko fh a r b i nh a s t h es m a l l - w o r l da n ds c a l e f r e ep r o p e r t i e s t h et w op u b l i ct r a f f i cn e t w o r km o d e l sa r ec r e a t e da c c o r d i n gt ot h er e a ld a t a o n ei st h e p u b l i ct l a f 五cc h a n g en e t w o r km o d e l ；t h eo t h e ri st h ep o r to fc a l ln e t w o r km o d e l t h et w op r o p e r t i e so f t h em o d e l sm a yg i v es o m en e wp r o j e c t sa n dp a t t e r n st oi m p r o v et h ed e v e l o p m e n t so ft h e t r a f f i cs c i e n c ea n dt e c h n o l o g y ，a n dm a y h a v es o m es u g g e s t sf o rt h ed e s i g na n dr e b u i l d i n go f p u b l i ct r a f f i cn e t w o r k f i n a l l y ，w em a k er e s e a r c h e so i lt h er o b u s t n e s sa n df r a n g i b i l i t y0 fu r b a nt r a n s i tn e t w o r k w ec o m p a r et h er o b u s t n e s sa n df r a n g i b i t i t yo nt h es t o pc o m p l e xn e t w o r ka n dt h es a m es i z e r a n d o mn e t w o r kr e s p e c t i v e l y ，a n da l s ow em a k er e s e a r c h e so nt h er o b u s t n e s sa n df r a n g i b i l i t y o ft h es t o pc o m p l e xn e t w o r kf o rt h er a n d o mf a i l l ea n da t t a c k w ef i n dt h a tt h ep u b l i ct r a f f i c n e t w o r kd o e s n th a v es t r o n gr o b u s t n e s sf o rt h er a n d o mf a i l u r e ，b u ti s v e r yf r a g i l ef o rt h e 础a c k k e yw o r d s ：c o m p l e xn e t w o r k s ：t h ep u b f i ct r a f f i cs y s t e m ；a p p l i c a t i o n i i 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名：日期：坦：圭：，矿 人连理。i ：人学硕十研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位 论文版权使用规定”，同意大连理工大学保留并向国家有关部门或机构送 交学位论文的复印件和电子版，允许论文被查阅和借阅。本人授权大连理 工大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，也 可采用影印、缩印或扫描等复制手段保存和汇编学位论文。 作者签名： 导师签名： 大连理工大学硕士学位论文 1 绪论 1 l 引言 从某种意义上说，网络是世界存在和沟通的基础。无论是现实中的人，还是其他客 观事物，都是世界的一个元素。显然这样的元素成千上万甚至难以计数，以人为例，全 世界就超过6 0 亿个个体。与此同时元素之间总存在直接或间接的联系，两个人可以相 互认识，也可以通过第三人或更多人认识。元素与元素之间的联系共同构成的客体，即 是网络。 元素的种类繁多，联系的复杂多样，决定了网络存在的多样性和复杂性。例如发电 站与传输线路构成了电力网络、交通站与道路构成了交通网络、神经元细胞和神经构成 了神经网络、计算机服务器与信息电缆构成计算机网络等等。人本身也是网络中的一员， 同时又生活在各种各样复杂网络并存的空间当中。人类社会的日益网络化需要人类对各 种人工和自然的复杂网络的行为有更好的认识，这便是人们深入研究复杂网络的动机， 而寻找各种看上去互不相同的复杂网络之间的共性和处理他们的普适方法是人们研究 的目的。 就目前而言，科学家们还没有给出复杂网络精确严格的定义，之所以称其为复杂网 络，大致上包含以下几层意思：首先，它是大量真实复杂系统的拓扑抽象；其次，它至 少在感觉上比规则网络和随机网络复杂，因为我们可以很容易地生成规则和随机网络， 但就目前而言，还没有一种简单方法能够生成完全符合真实统计特征的网络f 1 】。 复杂网络之所以复杂，主要表现在以下三个方面 2 - 3 1 ： ( 1 ) 结构复杂性 网络连接结构看上去错综复杂、极其混乱。并且，网络的连接结构可能是随时间变 化的，例如互联网每天都不停有新的页面和链接产生，旧的页面和链接被删除。此外节 点( 元素) 之间的连接可能具有不同的权重和方向，例如公交网络中就存在干线和支线、 上行和下行等具体问题。 ( 2 ) 节点( 元素) 的复杂性 网络中的节点可能具有分岔和混沌等复杂非线性行为的动力系统。例如，基因网络 中的每个节点具有复杂的时间演化行为。同时，一个网络中可能存在多种不同类型的节 点。例如控制哺乳动物中细胞分裂的生化网络就包含各种各样的基质和酶。 复杂网络理论在哈尔滨公交系统中的应用研究 a量 图1 1 复杂网络连接图实例( 摘自文献【3 】) f i g 1 1e x a m p l e so fc o m p l e xn e t w o r k s ( 3 ) 各种复杂因素的互相影响 实际的复杂网络会受到各种各样因素的影响和作用。例如，耦合神经元重复地被同 时激活，那么他们之间的连接就会加强，这被认为是记忆和学习的基础。此外各种网络 之间也存在密切的联系，这使得对复杂网络的分析变得更为艰难。 图1 2 几种不同类型的复杂网络( 摘自文献【3 1 ) ( a ) 一个淡水湖中物种之间掠食者及被掠食者之间关系的食物链；( b ) 一个研究所的科学家之间的 一个合作网：( c ) 由p o r e r a t 等研究的人类之间的性接触网络。 f i g 1 2 硼1 r e ek i n d so fr e a lc o m p l e xn e t w o r k s ( a ) af o o dw e bo fp r e d a t o r - p r e yi n t e r a c t i o n sb e t w e e ns p e c i e si naf r e s h w a t e rt a k e ；( b ) t h en e t w o r ko f c o u a b o r a t i o n sb e t w e e ns c i e n t i s t sa ta p r i v a t er e s e a r c hi n s t i t u t i o n ；( c ) an e t w o r ko fs e x u a lc o n t a c t sb e t w e e n i n d i v i d u a l si nt h es t u d yb yp o a e r a te ta 1 一2 一 大连理工大学硕士学位论文 1 2 复杂网络研究简史 关于网络的研究，可以追溯到1 8 世纪伟大数学家欧拉( e i i l e r ) 对著名的 “k 6 n i g s b e r g 七桥问题”的研究。在此之后的两百年中，数学家们一直致力于对简单的 规则网络和随机网络进行抽象的数学研究【3 1 。 莹 图1 3k i l n i g s b e r g 难题( 摘自文献【3 】) ( a ) 在这个问题中欧拉不关注距离参数，而只研究边( a 点和c 点) ，岛屿( b 点和d 点) 和 桥( 红色标记) 三者之组成的联系。( b ) 该城的几何示意图。每一条线表示一座桥，并通过他们将 被p r e g e l 河分成四部分的k 艿n i g s b e r g 吉城连接在一起。 1 3k i ；n i g s b e r gp u z z l e ss o l u t i o n s ( a ) e i i l e rn o t e dt h a td i s t a n c e sa l en o ti m p o r t a n ti nt h i sp r o b l e m ，t h u sh ef o c u s e do nt h e 础t r a i n t s t h em a r g i n s ( aa n dc ) ，t h ei s l a n d s a n dd ) a n dt h eb r i d g e s ( i nr e d ) ( b ) g x a p hr e n d e x i 虹g t h ec i t y e a c h l i n ki sab r i d g ea n dn o d e sa r ct h ef o u ra r e a si nw h i c ht h er i v e rp r e g e ld i v i d e s k i ；n i g s b e r g 真正在数学上系统性研究复杂网络理论是从2 0 世纪6 0 年代，匈牙利数学家e r d z i s 和 r e n y f 建立的随机图理论( r a n d o mg r a p ht h e o r y ) 4 1 。在e r d 6 s 和r e n y i 建立的随机图模型 中( e r 随机图) ，任意两个节点之间有一条边相连接的概率都为p 。因此，一个含有n 个节点的e r 随机图中，边的总数是一个期望值为e n o v 一1 ) 2 的随机变量。由此可以推 得，产生一个有n 个节点和m 条边的e r 随机图的概率为p j i ，f 1 p ) m - 1 ) 2 - u 。 在2 0 世纪的后4 0 年中，人们开始设计揭示复杂网络性质的一些实验，其中最著名 的就是小世界实验( s m a l lw o r l de x p e r i m e n t ) 。2 0 世纪6 0 年代美国哈佛大学的社会心理 学家s t a n l e ym i l g r a m 通过一些社会调查后给出的推断是：地球上任意两个人之间的平 均距离是6 。也就是说，平均中间只要通过5 个人，你就能与地球上任何一个角落的任 复杂网络理论在哈尔滨公交系统中的应用研究 何一个人发生联系。这就是著名的六度分离( s i xd e g r e e so f s e p a r a t i o n ) 推断。这个推断 反映了复杂网络的“小世界”( s m a l lw o r l d ) 特征。继m i l g r a m 的实验之后，“k e v b tb a c o n 游戏”、“e r d 6 s 数游戏 、i n t e r n e t 实验也都对个论断进行证实【酗，6 】。 2 0 世纪6 0 年代末，哈佛大学的研究生m a r kg r a n o v e t t e r 发现，人们在寻找工作时， 那些关系紧密的朋友( 强连接) 反倒没有那些关系一般的甚至只是偶尔见面的朋友( 弱 连接) 更能发挥作用。1 9 7 3 年g r a n o v e t t e r 撰写的弱连接的强度( s t r e n g t ho f w e a kt i e s ) 发表于美国社会学杂志，这篇论文被认为是有史以来最有影响的社会学论文之w 7 1 。 1 9 9 8 年，学者w a t t s 和s t r o g a t z 在规则网络中引入随机性，建立了著名的小世界网 络模型o r s 小世界网络模型v 8 】，很好地描述了真实网络的小世界性质。1 9 9 9 年，学者 b a r a b d s i 和a l b e r t 通过对万维网的数据进行统计分析发现万维网的度分布服从幂律分 布，在双对数坐标系下是一条下降的直线，由于幂律分布具有标度不变性，缺乏一个特 征度值，因此称这种度分布服从幕律分布的网络为无标度网络( s c a l e - f r e en e t w o r k ) p j 。之 后的研究表明，许多社会网络如科学家合作网络、生物网络中的新陈代谢网络、技术网 络中的i n t e r n e t 网络等都是无标度网络。这些来自不同领域的大规模系统呈现了共阿的 普适规律，促使人们去探索隐藏在这些表象后的内在演化机制，从此掀起了研究复杂网 络的热潮。 物理学家的进入只有7 8 年的历史，研究对象特殊的尺度效应是召唤物理学家到来 的根本原因。数学家经典的网络理论，要么是分析包含几十数百个顶点，可以画在一张 纸上从而形成直观印象的网络；要么是讨论不含有限尺度效应，可以精确求解的网络性 质。“随机移走一个顶点会对网络的性能产生什么样的影响? 这个问题对于研究有限 规则网络的数学家是有意义的，但对于拥有几千万个节点，连接方式复杂多样的真实网 络而言，或许“随机移走3 的顶点会对网络性能产生什么样的影响? ”这个问题更有 意义。这个尺度的网络，是被物理学家称作“足够大 的网络，对它们的研究，需要使 用统计物理的方法。 从统计物理学来看，网络是一个包含了大量个体及个体之间相互作用的系统。它可 以用来描述人与人之间的社会关系，物种之间的捕食关系，计算机之间的网络连接等等， 而电网则是一个典型的复杂网络。网络与现象结合还可以用来讨论网络的稳定性等结构 与功能的关系，在不同的网络模型上讨论扰动( 例如社会网络的传染病、电网中的设备 故障等) 的传播和控制。此外，网络本身的演化过程也是一个有趣的问题。总结起来， 研究网络的几何性质、阿络的形成机制、网络演化的统计规律、网络上的模型性质、网 络的结构稳定性以及这些特性在具体网络中的特性分析是复杂网络研究的中心内容。而 统计物理和图论是有力的研究工具。 大连理工大学硕士学位论文 随着近年来大型数据库的建立和计算机存储与运算能力的迅速提高，复杂网络的研 究进程大大加快。人们对社会系统、大型基础性设施和生物系统中大量的真实网络数据 库进行了系统的分析，寻找呈现表象的内在机铡和模式，试图发现支配和影响这些复杂 系统的动力学和演化规律的内在本质。复杂网络的理论及实证研究的发展将会对网络安 全、网络控制、疾病传播的控制与防御、社会中人的行为动力学的研究、生物网络的演 化机制的研究等产生重要影响。 表1 1 不同领域内复杂网络理论的研究内容 t a b 1 1r e s e a r c h e so fc o m p l e xn e t w o r k si nd i 量e e r e n tf i e l d s 1 3 复杂网络研究的基本概念 人们在刻画复杂网络的结构的统计特征上提出了许多概念和方法，其中有四个具有 统计意义的基本概念：平均路径长度( a v e r a g ep a t hl e n g t h ) 、聚类系数( c l u s t e r i n g c o e f f i c i e n t ) 和度分布( d e g r e ed i s t r i b u t i o n ) 、节点负荷。 复杂网络中节点：组成复杂网络的基本元素，物理上也称为站点，计算机科学中称 为节点，社会学中也称为参与者；边：连接节点之间的线，使得复杂网络中的元素之间 有相互作用。 有向网络：所有连线都有方向的复杂网络称有向网络。无向网络：所有的连线都是 双向连接的复杂网络称无向网络。无向网络可以用这样一个相应的有向网络来代替，即 有向网络中每对相连的节点之间有两条连线连接，每条连线代表一个方向。 ( 1 ) 平均路径长度 网络中的两个节点f 和歹之阗的距离出定义为连接这两个节点的最短路经上的边数。 网络中任意两个节点之间的距离的最大值称为网络直径( d i a m e t e r ) ，记为口。号警4 。 复杂网络理论在哈尔滨公交系统中的应用研究 网络的平均路径长度l 被定义为任意两个节点之间的距离的平均值，可表示为： ! 弋出； 三( + d 厶_ 。其中n 为网络节点数。网络的平均路径长度也称为网络的特征 2 t z j 路径长度( c h a r a c t e r i s t i c p a t hl e n g t h ) 。近期研究发现，实际的复杂网络的节点数巨大， 但平均路径长度却小的惊人，这表明复杂网络具有“小世界”效应。 ( 2 ) 聚类系数 一般地，假设网络中的一个节点f 有硒条边将和其他节点相连，这忽个节点成为节 点f 的邻居。显然，在岛个节点之间最多可能有 一1 ) 2 条边。而这岛个节点之间实际 存在的边数易和总的可能的边数也假一1 ) 2 之比，就定义为节点i 的聚类系数g ，可表 示为：c j 一2 e , 阮盹- 1 ) 】。 整个网络的聚类系数c 就是所有节点f 的f 的聚类系数g 的平均值。很明显， 0s cs1 。两种特殊情况：c = o ，当且仅当所有节点为孤立节点，没有任何连接边；c = t ， 当且仅当网络是全局耦合的，即网络中任意两个节点都直接相连。 聚类系数概念源于社会科学。其在社会网中一个最基本的特性就是派系形式，它代 表了一个朋友圈，在这个朋友匿中每个人都互相认识，这种内在的性质就可以由聚类系 数来描述。在某种程度上反映“物以类聚，人以群分”的特性【2 】。 ( 3 ) 度与度分布 节点f 的度忽定义为该节点连接到其他节点的边数。对于有向网络，一个节点的度 又可以分为出度( o u t - d e g r e e ) 和入度( i n - d e g r e e ) 。直观上看，一个节点的度越大就意 味着这个节点在某种意义上越“重要”。网络中所有节点f 的度岛的平均值成为网络平 均度，记为如。网络中节点的度的分布情况可用分布函数月来描述，表示一个随机 选定的节点的度恰好为k 的概率。 许多网络的度分布可以用幂律形式p ( 七) 篮七一，幂律分布也称为无标度( s c a l e - f r e e ) 分布，具有幂律分布的网络也称为无标度网络。学术上，网络的度分布满足幂律分布的 情况己经得到足够的重视。现实中电话呼叫网、科学引文网属于此类。还有一些网络度 分布为指数分布的，例如电力网络，铁路网络，其度分布可以用指数形式p 似) e 以店来 表示。还有一些是它们两者的混合，例如一些合作网络。 由于幂律分布在对数坐标系中对应一条直线，而指数分布在半对数坐标系中对应一 条直线，因此可以通过分别采用对数坐标和半对数坐标来识别幂律和指数分布。 ( 4 ) 节点负荷 节点负荷是与最短路径长度有关的另一个参量。在整个网络中，从一个节点沿着最 大连理工大学硕士学位论文 短路径到另一个节点时，会经过一些节点。如果我们考虑任何一对节点在沿着最短路径 行走时经过某个点的次数，我们会发现网络中有一些重要的节点会比其它节点经过的次 数多。这种现象可以由节点负荷来定量表示。节点f 的负荷b ；定义“为两络中任何一对 节点之间的最短路径经过节点i 的次数。 设工 是从节点i l l 到j 的路径长度，工，为节点 与节点j 经过节点i 的路径 ， 长度，那么节点f 的负荷为岛- 华，其中h j 。为了表示这个量的统计性质，我 “。 督l 们有时更关注平均节点负荷：6 二墨。 1 4 本论文的主要内容 本文综述和介绍了复杂网络的理论、有关概念、典型模型，将复杂网络理论运用到 哈尔滨公交系统现实网络当中，就其在哈尔滨公交网络中的应用进行了研究。全文主要 工作包括： 1 介绍了复杂网络的基本概念和复杂网络研究的历史。 2 综述了复杂网络模型的演化和性质以及复杂网络的主要特征。复杂网络模型的演 化模型包括规则图、随机图、w s 小世界模型、b a 无标度网络模型、适应度模 型等等。复杂网络的主要特征除小世界效应外，还包括网络的鲁棒而又脆弱性、 网络的自相似性。 3 将复杂网络理论运用到哈尔滨公交系统现实网络当中，在公交网络中引入了复杂 网络中的基本静态几何量，结合哈尔滨市公交网络的实际数据，验证了哈尔滨公 交网络的小世界特性和无标度特征。 4 结合哈尔滨市实际公交网络数据建立了哈尔滨市公交停靠站点网络模型和哈尔 滨市公交换乘网络模型。这两个模型反映了公交网络的自然拓扑特征以及公交网 络的可达性。这两个模型的理论意义可能给出促进交通科学与技术发展的新的方 案与模式，对公交网络的设计、改建有一定意义上的启发。 5 对公交网络的鲁棒性与脆弱性进行了研究，发现公交网络对于随机故障并不是有 很强的鲁棒性，但是对于蓄意攻击却有很大的脆弱性。 复杂网络理论在哈尔滨公交系统中的应用研究 2 复杂网络模型演化及其性质 2 1 规则网络 一维链、二维正方晶格等称为规则网络。推而广之，一般晶格或者一些完全树图都 可以称为规则网络。常见的规则网络包括全局耦合、最临近耦合和星形网络等。 & 。，勿 么联螺 、 组 靛 凝 f | ，、遗 一 i abc 图2 1 三种规则网络模型 ( a ) 全局耦合网络；( b ) 最临近耦合网络；( c ) 星形网络 f i g 2 1m e m o d e l so ft h er e g u l a rn e t w o r k ( a ) g l o b a l l yc o u p l e dn e t w o r k ；( b ) a d j a c e n c yc o u p l e dn e t w o r k ：( c ) s t a rc o u p l e dn e t w o r k 在具有相同节点数的所有网络中，全局耦合网络中具有最小的平均路径( 工r a i n ；j ) 和最大的聚类系数( g 呲= j ) ，反映了部分实际网络的聚类和小世界特性，但他有明显 的局限性：有n 个接点的全局耦合网络应该有笪笔条边，而大多数实际网络很稀疏， z 他所拥有的边一般至多是o ( ) ，而不是0 ( 舻) 。 另一个规则网络模型是最邻近耦合网络，即其中每个节点只与周围的邻居节点相 连。具有周期边界条件的最邻近耦合网络包含n 个围成一个环的点，其中每个节点都与 他左右m 个邻居点相连，k 为偶数a 最邻近网络的聚类系数为：c 一爱 暑三，( k 取较大值时) ，显然这类网络是高聚类的，但并非是小世界网络，因为该网络的平均路 径长度随着节点数的增加面迅速增加：三一三一，n 一。 在星形网络中，有一个中心点，其余的n - 1 个节点都只与这个中心点相联接，他们 彼此不连接。星形网络的平均路径长度为l = 2 一号篙啬一2 ，_ ，聚类系数为 大连理工大学硕士学位论文 c 。n - - 1 - 1 。星形网络具有简单的结构，可以看成部分实际网络( 复杂网络) 构成的 代 基本单元。 2 2 随机图 与完全规则网络相反的是完全随机网络，其中一个典型的模型是e r d 6 s 和r e n y i 建 立的随机图模型中( e r 随机图) 1 4 1 ：任意两个节点之间有一条边相连接的概率都为p ， 一个含有n 个节点的e r 随机图中，边的总数是一个期望值为删一1 ) 2 】的随机变量。 由此可以推得，产生一个有n 个节点和m 条边的职随机图的概率为一。一p ) n c r - 1 ) 2 一m p = 0p = 0 10 p = 0 15 圈2 2 e r 模型演化示意图( 摘自文献 4 】) f i g 2 2i 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 c e s sf o rt h e 脯一脚m o d e l 随机图理论的一个主要研究课题是，概率p 的取值与随机图的特殊属性之间的关 系。e r d i ；s 和r e n y i 系统地研究了当n 一时，e r 随机图的性质，定义：如果当n 一 时产生一个具有性质q 的随机图的概率为1 ，那么就称几乎每个e r 随机图都具有性质q 。 职随机图的许多重要性质都是突然涌现的，也就是说，对于任一给定的概率p ，要么几 乎每个图都具有某个性质，要么几乎每个图都不具有该性质。 由于实际复杂网络的聚类系数要比相同规模的e r 随机图的聚类系数高得多，将e r 随机图作为实际复杂网络模型存在局限。但是人们可以从多个角度对e r 随机图进行扩 展以使其更接近真实的网络，因此其基本思想在目前的复杂网络研究中仍然很重要。 复杂网络理论在哈尔滨公交系统中的应用研究 2 3 小世界网络模型 2 3 ，1 小世界模型的构造 1 9 9 8 年w a t t s 和s t r o g t z 于1 9 9 8 年引入了小世界模型，成为w s 模型【踟。其构造算法如 下； 从规则图开始：考虑一个含有n 个节点的最临近耦合网络，他们围成一个环，其中 每个节点都与他左右相邻的各k 2 - ? 节点相连，k 为偶数。随机化重连：以概率p 随机地 重连网络中的每一个边，即将边的一个端点保持不变，而另一个端点取为网络中随机选 择的一个节点。其中规定，任意两个不同的节点之间至多只能有一条边，并且每一个节 点都不能有边与自身相连。 在这个模型中，p - 0 x 寸应于完全规则网络，p = i n 对应于完全随机网络，通过调节p 值就可以控制从完全规则网络到完全随机网络的过渡。 ai ， 餐- 4 ( 图2 3 随机图演化示意图 ( 随机化熏连) f i g 2 3i l l u s t r a t i o no ft h er a n d o m - g r a p he v o l u t i o np r o c e s s 由于w s 模型中构造算法中的随机化过程可能破坏网络的莲通性，1 9 9 9 年n c w n m n 和w a t t s 又通过随机化加边的方法构造出的小世界模型，成为啾型【圳。其构造算法如 下： 从规则图开始：考虑一个含有n 个节点的最临近耦舍网络，他们围成一个环，其中 每个节点都与他左右相邻的各k 2 个节点相连，k 为偶数。随机化加边：以概率p 随机选 择一对节点之间加上一个边。其中规定，任意两个不同的节点之间至多只能有一条边， 并且每一个节点都不能有边与自身相连。 大连理工大学硕士学位论文 a 图2 4 隧机图演化示意图 ( 随机化加边) f i g 2 4i l l u s t r a t i o no ft h er a n d o m - g r a p he v o l u t i o np r o c e 翳 2 。3 2 小世界模型的统计性质 ( 1 ) 聚类系数【1 1 j w s 模型的聚类系数为c ( p ) - i 3 ( k f - 面2 ) ( 1 一p ) 3 ，n w 模型的聚类系数为： 0 。) - 丽再3 ( k 丽- 2 ) ( 2 ) 平均路经长度 人们目前还没有得到w s 模型平均路经长度的精确表达式，不过利用重正化群的方 法可以得到如下公式l ( p ) 等f ( n k p 2 ) ，其中f o ) 为一普适标度函数，当球1 时 满足，m ) - c o n s t a n t ；当“1 时满足f o ) - 1 n “) u 。 n 册趾等人基于均场方法给出了如下近似表达式1 1 0 】： ，( 小丽删a n 壶 ( 3 ) 度分布 基于随机化重连机制的w s 小世界模型，当k k ，2 时有1 1 ： 蹦) - r a i n ( k - 磊k7 2 剧2 刚”加n ( k 1 2 ) - n 面( p k 丽2 ) k - ( s 可：2 ) - e 删2 ， 复杂网络理论在哈尔滨公交系统中的应用研究 p ( k ) 1 0 。2 1 0 4 1 0 瑚 图2 5 当k 音8 时以不同概率p 随机化重连的w s 模型度分布( 取自文献【1 2 】) f i g 2 5d e 伊e ed i s t r i b u t i o no f t h ew a t t s - s t r o g a t zm o d e lf o rk = 8a n dv a r i o u s p 在w s 模型中，如果使概率p 从。逐渐增加到1 ，我们就可以从一个规则的点阵劬= o ) 过渡到随机图p = 1 ) 。我们可以把聚类系数c 0 ) 和平均路长l 0 ) 看成是概率p 的函数。 规则的最近邻网络印= 0 ) 是高聚类的，聚类系数c ( o ) 一( 七- 1 ) k ，但具有长的平均路 长工( o ) 一n 2 k 1 。研究发现，对于一个较小的重新连接概率p ，聚类系数改变很小， 但平均路长却减小很快1 8 】。 p 图2 6w s 模型的聚类系数和平均路径长度随重连概率p 的变化关系( 摘自文献【8 】) f i g 2 6 卫圮r e l a t i o n s h i pb e t w e e nc l u s t e r i n gc o e f f i c i e n ta n da v e r a g ep a t hl e n g t h f o rt h ew sm o d e ld i f f e r e n tr e w i r i n gp r o b a b i l i t i e sp 大连理工大学硕士学位论文 基于随机化加边机n 的r , r w d , 世界模型中，每个节点的度至少为k 。因此当k k 时，一个随机选取的节点的度为k 的概率为【1 1 】： 川- 艮) c 钞u 耖杜 当k k 时，e ( k ) 一0 。 2 4 无标度网络模型 2 4 1b a 无标度网络 e r 随机图和w s 小世界模型的一个共同特征就是网络的连接度分布可以近似用泊 松( p o i s s o n ) 分布来表示，其形状在远离峰值( k 处呈指数下降。这表明当k 时， 度为k 的节点几乎不存在。这类网络也称为均匀网络或指数网络。但许多实际复杂网络 的连接度分布函数具有幂律形式，剑如i n t e r n e t 、新陈代谢网络。由于这类网络的节点 的连接度没有明显的特征长度，故称为无标度网络i 射。 为解释幂律分布产生的机理，b a r a b d s i 和a l b e r t 提出了一个无标度网络模型，简称 为b a 模型。这个模型考虑到了许多实际网络的两个重要特性： ( 1 ) 增长：即网络的规模是不断扩大的。例如互联网上每天都有大量的网页增加 或删除。：j ( 2 ) 优先连接：即新的节点更倾向于与那些具有较高连接度“大”的节点相连接。 这种现象也称为“富者更富( r i c hg e tr i c h e r ) 或“马太效应( m a t t h e we f f e c t ) 。例 如网页中的超文本连接更可能指向搜狐、新浪等大的网站。 b a 无标度网络模型的构造： 增长：从一个具有辫。个节点的网络开始，每次引入一个新的节点，并且连到捌个 已存在的节点上，这里m m o 。 优先连接：一个新节点与一个已经存在的节点i 相连接的概率n j 与节点i 的度k f 、 节点歹的度k i 之间满足如下关系：n t 。j 弦。 七： 复杂网络理论在哈尔滨公交系统中的应用研究 在经过f 步后，这种算法产生一个有；fa r m o 个节点、m t 条边的网络。图2 7 显示 了当m 一所。= 2 时的b a 无标度网络的演化过程。初始有两个节点，每次新增加一个节 点按优先连接机制与网络中已存在的两个节点相连。 寸可冈黔 汰潞屎倦瓜 图2 7 初始两个节点的b a 无标度网络的演化 f i g 2 7i 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 c e s sf o rt h eb am o d e lb e g i nw i t ht w on o d e s b a 无标度网络模型的统计性质1 1 3 彤】： ( 1 ) 聚类系数 b a 无标度网络模型的聚类系数为：c 竺篆眦譬) 嘉】坚譬 这表明与e r 随机图类似，当网络规模充分大时b a 无标度网络不具有明显的聚类特性。 ( 2 ) 平均路径长度 l o g n b a 无标度网络模型的平均路径长度为：l l o g l o g n ，表明该网络也具有小世界 特性。 ( 3 ) 度分布 目前对b a 无标度网络的度分布的理论研究主要有三种方法：连续场理论【9 】、主方 程法f 1 6 】和速率方程法【1 7 1 。这三种方法得到的渐进结果都是相同的。其中主方程法和速率 方程法是等价的。由主方程法得到的结果如下： 定义p ，f ) 为在时刻加入的节点f 在t 时刻的度恰好是七的概率。在b a 模型中， 当一个新的节点加入到系统中来时，节点f 的度增加1 的概率为历1 - l - k 2 t ，否则该节 点的度保持不变。由此得到如下递推关系式： p ，f f ，f + 1 ) 。生 p ( k l t ，f ) + ( 1 一丢咖 ，力，而网络分布的度为： 大连理工大学硕士学位论文 p b ) ；l i m c ：p ( 七，f ，f ) ) ，他满足如下递推方程： t - r 一 州。 晕聊曲加斛1 ，从而栅m 型的度分布函黼 【而2 ，b 册 p ) 一面2 m 丽( m + 1 ) 蕊锄。3 这表明b a 网络模型的度分布可由幂指数为3 的幂律函数近似描述。 图2 8b a 无标度网络的度分布 f i g 2 8d e g r d i s t r i b u t i o no ft h e b as c a l e - f r e em o d e l 2 4 ，2 适应度模型 b a 无标度网络模型是把实际复杂网络的无标度特性，归结为优先增长和优先连接 这两个非常简单明了的机制，很好地体现了科学研究中从复杂现象提取简单本质的特 点。但是b a 无标度网络模型只能生成度分布的幂律指数固定为3 的无标度网络，而实 际复杂网络的幂律指数则不甚相同，且大都属于2 3