（控制理论与控制工程专业论文）基于派系的复杂网络及其在公交网络上的应用研究.pdf

第1 章绪论 著名物理学家霍金认为：二十一世纪是复杂性的世纪。复杂网络( c o m p l e x n e t w o r k ) 的研究是复杂性理论研究的一部分，作为研究复杂性科学和复杂系统的 有力工具，复杂网络为研究复杂性提供了全新的视角。复杂网络是近十年来随着 计算机技术迅猛发展而兴起的一门综合性交又学科，它同时也反映了在以信息科 学为砥柱的新世纪中，各学科理论和应用的交叉、渗透及融合的发展趋势。因此， 复杂网络刚一出现便受到中外研究学者极大的关注，并且呈方兴未艾之势。 本章中，我们讨论了所选课题的研究背景及意义、复杂网络中的基本概念及 研究内容等，较为全面地分析了目前国内外有关复杂网络的研究状况。同时，我 们也提出了一些自己的观点，并列出了全文的研究内容、组织框架以及本文所做 的工作 1 1 研究的背景及意义 2 0 世纪9 0 年代以来，以i n t e m e t 为代表的信息技术的迅猛发展使人类社会大 步迈入了网络时代。从i n t e r n e t 到w w w ，从大型电力网络到全球交通网络，从生 物体中的大脑到各种新陈代谢网络，从科研合作网络到各种经济、政治、社会关 系网络，可以说，人们已经生活在一个充满着各种各样的复杂网络的世界中。人 类社会的网络化是一把“双刃剑 ：它既给人类社会生产与生活带来了极大的便利， 提高了人类生产效率和生活质量，但也给人类社会生活带来了一定的负面冲击， 如传染病和计算机病毒的快速传播以及大面积的停电事故等。因此，人类社会的 日益网络化需要人类对各种人工和自然的复杂网络的行为有更好的认识。 1 9 9 8 年w a t t s 和s t r o g a t z 提出的小世界网络模型( w s 模型) l lj 和1 9 9 9 年 b a r a b a s i 和a l b e r t 提出的无标度网络模型( b a 模型) 1 2 1 激发了复杂网络研究的热 潮。w s 网络模型说明了少量的随机连接会对网络性能产生重大的影响。而b a 网 络模型则揭示了增长和择优机制在复杂系统自组织演化过程中的普遍性。由于计 算机科学的飞速发展，对许多开放复杂系统的实证研究发现，这两类网络的特性 在现实的网络拓扑结构中具有一定的普适性。 浙江工业大学博士学位论文 目前，复杂网络已经成为国际上一个十分引人注目的新兴研究领域1 3 - 1 2 1 。对复 杂网络的研究，可以帮助我们解决很多一直困扰着我们的，引起我们强烈兴趣的， 我们希望并必须解决的问题。如地球上任意两个人之间要通过多少个朋友才能互 相认识? 万维网( w w w ) 上从一个页面到另一个页面平均需要点击多少次鼠标? 层出不穷的计算机病毒是如何在互联网( i n t e m e t ) 上传播的? 各种传染病( 艾滋 病、非典型性肺炎和禽流感等) 是如何在人类和动物中流行的? 为什么流言蜚语 会散布得很快? 大城市的交通堵塞问题是如何引起的? 应该如何建立合理的公共 卫生与安全网络? 为什么大脑能够具有思维的功能? 这些问题尽管看上去各不相 同，但每一个问题中都涉及很复杂的网络，包括w w w 、i n t e m e t 、社会关系网络、 经济网络、电力网络、交通网络、神经网络等等。更为重要的是，越来越多的研 究表明，这些看上去各不相同的网络之间有着许多惊人的相似之处。 复杂网络是一门结合了众多学科的交叉学科。长期以来，通信网络、电力网 络、生物网络和社会网络等分别是通信科学、电力科学、生命科学和社会学等不 同学科的研究对象，而复杂网络理论所要研究的则是各种看上去互不相同的复杂 网络之间的共性和处理它们的普适方法。从2 0 世纪末开始，复杂网络研究正渗透 到数理学科、生命学科和工程学科等众多不同的领域，对复杂网络的定量和定性 特征的科学理解，已经成为网络时代科学研究中的一个极其重要的挑战性课题， 甚至被称为“网络的新科学( n e ws c i e n c eo f n e t w o r k s ) ”1 1 3 ，1 4 1 。 1 2 复杂网络中的一些基本概念 1 2 1 网络的图表示 一个具体网络可抽象为一个由节点集v 和边集e 组成的图g = ，e ) 1 5 - 1 7 】。节 点数记为n 刊vl ，边数记为m = el 。e 中每条边都有v 中一对节点与之相对应。 如果任意节点对( f ，) 与( ，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 d n e t w o r k ) 。当然，无权网络也可看作是每条边的权值都为1 的等权网络。此外，一 个网络中还可能包含多种不同类型的节点。例如，在社会关系网络中可以用权表 第1 章绪论 示两人的熟悉程度，而不同类型的节点可以代表具有不同国籍、地区、年龄、性 别和收入的人。图1 1 给出了几个不同类型的实际复杂网络的网络图【”】。 ( a ) 糖 ( b ? 洱黪 囊：j o t ：叠： l 委骥 = 鬻鬈i 枣 坷i ( c )( d ) 抽) 酵母茁体内的蚩白质交互作h 构成的复杂网络，历蚩白庙z 问有交互作_ 【| j 使有连边；( b ) 美国一所学校中的学生的朋友关系阿络两学生是朋友便有连边：( c ) 计算机蠕虫病毒相互作 用构成的阿络；( d ) r a s hc 0 1 1 1 阿页上的万维网链接网络。 22 平均路径长度 圈】一1 儿个实际复杂网络的嗍络国 网络中两个节点j 和j 2 _ b q f r o , 7 葛以定义为连接这两个节点的最短路径上的 边数。网络中任意两个节点之间的距离的最大值称为网络的直径，记为d ，即 d 2 m a 】( 矗 ( 1 1 ) 浙江t 业大学博士学位论文 网络的平均路径长度定义为任意两个节点之间的距离的平均值，即 k 志吾乃 ( 1 2 ) 其中n 为网络节点数。网络的平均路径长度也称为网络的特征路径长度 ( c h a r a c t e r i s t i cp a t hl e n g t h ) 。 1 2 3 聚类系数 聚类系数( c l u s t e r i n gc o e f f i c i e n t ) 表征的是网络的聚类特性，也就是群落特性。 一般地，假设网络中的一个节点f 有岛条边将它和其他节点相连，这屯个节点称为 节点j 的邻居。显然，在这屯个节点之间最多可能有乞( 岛- 1 ) 2 条边。而这乞个节 点之间实际存在的边数巨和总的可能的边数岛( 向- i ) 2 之比就定义为节点i 的聚 类系数g ，即 g = 蒜 ( 1 3 ) 而对网络中所有节点的聚类系数取平均值，就是整个网络的聚类系数c ，即 c ：一1 nq (14)n 智。 。 其中n 为网络节点数。很明显，0 c 1 。c = 0 当且仅当所有的节点均为孤立节 点，即没有任何连边；c = 1 当且仅当网络是全局耦合的，即网络中任意两个节点 之间都有连边。 1 2 4 度与度分布 度( d e g r e e ) 是单独节点的属性中简单而又重要的概念。节点f 的度岛定义为 与该节点相关联的边的条数，也指与该节点连接的其他节点的数目。度分布( d e g r e e d i s t r i b u t i o n ) 是指网络中节点的度的分布，一般记作p ( k ) 。p ( k ) 也等于在随机一 致的原则下挑选出的节点其度数为k 的概率1 1 9 1 。 1 2 5 其他统计特性 平均路径长度、聚类系数和度分布是刻画复杂网络的基本统计特性，随着对 第1 章绪论 复杂网络研究的深入，更多的网络统计特性被人们提出来用以表征网络的性质。 例如度度相关性、度簇相关性、核数、介数和模块性等等。 度度相关性( d e g r e e d e g r e ec o r r e l a t i o n ) 2 0 , 2 1 】，描述的是网络中不同节点之间 的连接关系。如果度大的节点倾向于连接度大的节点，则称网络是正相关的；反 之，如果度大的节点倾向于和度小的节点连接，则称网络是负相关的。西班牙的 p a s t o r - s a t o r r a s 等人【2 2 2 3 1 给出了度相关性个简洁直观的刻画，即计算度为k 的节 点的邻居的平均度，其值为k 的函数。对于正、负相关的网络，函数图形分别是七 的递增、递减曲线；对于不相关的网络，函数值为常数。随后，n e w m a n 进一步简 化了度相关性的计算方法【2 4 】，指出只需计算网络的同配性系数( a s s o r t a t i v i t y c o e f f i c i e n t ) ，就可以描述网络的度相关性，的定义为： m 。1 工向一【m 。1 去( 五+ 向) 】2 ，= - 二二1 一 ( 1 5 ) m i 舢2 + k i 2 ) - 【m 。1 去( 石+ 岛) 】2 f ， 其中，五和磅分别为第f 条边的两个端点的度数，m 为网络中边的条数。，的取值 范围为一l 厂1 ，当厂 0 时，网络是正相关的，也称网络是同配的( a s s o r t a t i v e ) ； 当厂 0 时，网络是负相关的，也称网络是异配的( d i s a s s o r t a t i v e ) ；当，= 0 时，网 络是不相关的。 度簇相关性( d e g r e e c l u s t e r i n gc o r r e l a t i o n ) 2 5 1 ，指的是网络中节点的聚类系 数与度的关系。假如度高的节点的平均聚类系数也较高，则称该网络是度簇正相 关的，反之则称该网络是度簇负相关的。 一个网络的k 一核( k c o r e ) 是指反复去掉度小于或等于k 的节点后，所剩余 的子图【2 6 1 。若一个节点存在于k 一核，而在( 七+ 1 ) 一核中被移去，那么此节点的核 数( c o r e n e s s ) 为k 。而节点核数中的最大值称为网络的核数【2 0 1 。 介数( b e t w e e n n e s s ) 分为节点介数和边介数两种，它是一个全局变量，反映 了节点或边的作用和影响【2 7 1 。如果一对节点问共有b 条不同的最短路径，其中有b 条经过节点f ，那么节点积寸这对节点的介数的贡献为b b 。把节点f 对所有节点对 的贡献累加起来再除以节点对的总数，就可以得到节点f 的介数。类似的，边的介 数定义为所有节点对的最短路径中经过该边的数量比例。研究表明，节点的介数 与度之间有很强的相关性，不同类型的网络，其介数分布也大不一样【2 8 】。 浙江工业大学博士学位论文 网络的模块性( m o d u l a r i t y ) 1 2 9 】也指网络的社团特性( c o m m u n i t yp r o p e r t y ) ， 指的是网络中各节点聚集成群的特性，即可将网络划分为若干个社团，这些社团 内部的连边相对较稠密，而社团之间的连边相对较稀疏。 1 3 复杂网络的研究内容与现状 1 3 1 网络模型 复杂网络研究的兴起正是因为1 9 9 8 年w a r s 和s t r o g a t z 提出了小世界网络模 型( w s 模型) 【l 】以及1 9 9 9 年b a r a b a s i 和a l b e r t 提出了无标度网络模型( b a 模型) 【2 1 。因此，网络模型的研究一直以来都是复杂网络研究的热点之一【3 0 4 0 l 。以下我们 将对近些年来复杂网络模型的研究作一个回顾。 1 小世界网络模型 小世界网络模型最早由w a t t s 和s t r o g a t z 提出来，也称为w s 模型【l l 。此模型 的构造算法分为两步。第一步，从一个规则网络开始：考虑一个含有个节点的 最近邻耦合网络，它们围成一个环，其中每个节点都与它左右相邻的各k 2 节点 相连，k 是偶数。第二步，随机化重连：以概率p 随机地重新连接网络中的每条 边，即将边的一个端点保持不变，而另一个端点取为网络中随机选择的一个节点。 其中规定，任意两个不同的节点之间至多只能有一条边，并且每一个节点都不能 有边与自身相连。 在w s 模型中，p = 0 对应于完全规则网络，p = l 则对应于完全随机网络，通 过调节p 的值就可以控制从完全规则网络到完全随机网络的过渡，如图1 2 所示。 由此算法得到的网络模型的聚类系数c ( p ) 和平均路径长度l ( p ) 的特性，都可 看作是重连概率p 的函数。图1 3 显示了网络的聚类系数和平均路径长度随重连 概率p 的变化关系( 图中对两个值做了归一化处理，c ( o ) 和t ( o ) 指的是规则网络 的聚类系数和平均路径长度) 。一个完全规则的最近邻耦合网络( 对应于p = 0 ) 是 高聚类的，但平均路径长度很大。当p 较小时( 0 p 1 ) ，重新连接后得到的网 络与原始的规则网络的局部属性差别不大，从而网络的聚类系数变化不大，但其 平均路径长度却下降很快。这类既具有较短的平均路径长度又具有较高的聚类系 数的网络就称为小世界网络。 第1 章绪论 八 胁杰 随机化重连 图1 2w s 小世界网络图 图l 一3w s 小世界网络的聚类系数和平均路径长度随重连概率p 的变化 w s 小世界网络模型构造算法中的随机化重连过程有可能破坏网络的连通性。 为了保证网络的连通性便于理论分析，n e w m a n 和w a t t s 提出了一个改进的小世界 网络模型，一般称n w 模型4 。该模型是通过用“随机化加边取代w s 小世界 网络模型构造中的“随机化重连 而得到的，如图1 4 所示。 在n w 小世界模型中，p = 0 对应于原来的最近邻耦合网络，p = 1 则对应于一 个规则网路和随机网络的叠加。当p 足够小和足够大时，n w 小世界模型本质 上等同于w s 小世界模型4 1 , 4 2 】。图1 5 显示了n w 小世界网络的聚类系数和平均 路径长度随随机化加边概率p 的变化关系( 图中对两个值做了归一化处理) 。 浙江工业大学博士学位论文 八瓜 么匿彬糅氧 廷猬爹 随机化加边 图l 一4 n w 小世界网络图 图1 5n w 小世界网络的聚类系数和平均路径长度随加边概率p 的变化 w s 和n w 小世界网络模型是提出最早且研究最多的小世界网络模型，随后人 们还提出了很多小世界模型的其他变形1 4 1 。文献 4 3 】提出用类似n w 小世界模型的 随机化加边方法构造小世界网络，并对其进行光谱分析。文献 3 5 1 提出了一个保持 网络节点度不变的小世界网络模型，并分析了模型的聚类系数和平均路径长度。 文献【4 0 1 提出了一个不需要加边，且能保证网络连通性的小世界网络模型，并进一 步分析了模型的度分布、聚类系数和平均路径长度。 2 无标度网络模型 无标度网络的概念是由b a r a b a s i 和a l b e r t 提出来的，他们还构造了一个无标度 第1 章绪论 网络的模型，一般称为b a 模型【2 , 4 4 1 。此模型的构造算法也分为两步。第一步，增 长：从一个具有个节点的网络开始，每次引入一个新的节点，并且连到m 个已 存在的节点上，这里朋m o 。第二步，优先连接：一个新节点与一个已存在的节 点f 相连接的概率n 与节点f 的度毛、节点的度七，之间满足如下关系： n ，2 轰 ( 1 6 ) l 在经过t 步后，这种算法产生一个有n = t + r n o 个节点、m t 条边的网络。图1 6 显示了当m = m 0 = 2 时的b a 网络的演化过程。初始网络有两个节点，每次新 增加的一个节点按优先连接机制与网络中已存在的两个节点相连。图l 一7 给出了 当朋= m 0 = 5 ，t = 1 0 0 0 和2 0 0 0 时的b a 网络的度分布。 一一强一冒尉 ，_ 、 & l 钆 图1 6b a 无标度网络的演化( m = m o = 2 ) 图1 7b a 无标度网络的度分布( m = m 0 = 5 ，t = 10 0 0 和2 0 0 0 ) 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 ) 【2 】o 这是从万维 网实际形成过程中抽象出来的，万维网每时每刻都有新的网页增加，并且新网页 总是倾向于和知名的网页相链接。人们对增长和优先连接这两个网络演化机理进 浙江工业大学博士学位论文 行了改变，提出了很多无标度网络模型的变形 5 , 4 5 - 5 0 】。 文献【5 l 】改变了b a 模型中优先连接的机制，提出了适应度( f i t n e s s ) 模型。 此模型的构造算法也分为两步。第一步，增长：从一个具有个节点的网络开始， 每次引入一个新的节点，并且连到m 个已存在的节点上，这里m m 0 。每个节点 的适应度按概率分布p ( q ) 选取。第二步，带有适应度的优先连接：一个新节点与 一个已存在的节点f 相连接的概率1 7 f ，与节点i 的度岛、节点的度七，和适应度仍 之间满足如下关系： n ，2 丽r l i k i ( 1 7 ) 厶一ij ”j j 在适应度模型中，优先连接概率与节点的度和适应度之积成正比。这样，在 适应度模型中，如果一个年轻的节点具有较高的适应度，那么该节点就有可能在 随后的网络演化过程中获取更多的边。取决于适应度分布p ( r 1 ) 的形式，适应度模 型表现出两类不同的行为【5 l 】。如果该分布具有有限支撑，那么与原始的b a 模型 一样，网络具有幂律度分布；如果该分布具有无限支撑，那么适应度最高的那个 节点就会获得占整个网络总边数的一定比例的边数，形成一种所谓“赢者通吃 ( w i n n e rt a k e sa 1 1 ) 的现象。 文献 5 2 】将局域世界优先连接机制代替b a 模型的全局优先连接机制，提出了 局域世界演化模型( 1 0 c a l - w o r l de v o l v i n gn e t w o r km o d e l ) 。模型的构造算法由增长 和局域世界优先连接组成，增长机制与b a 网络一致：网络初始时有个节点和e 0 条边，每次新增加一个节点和附带的m 条边。局域世界优先连接：随机地从网络 已有的节点中选取m 个节点( m m ) ，作为新加入节点的局域世界。新加入的节 点根据优先连接概率 鹏) _ n ( i e l w ) 忐l o c a l 三羔0 忐l o c a l , - y ( 1 8 ) 厶“j m l 厶 jl 来选择与局域世界中的坍个节点相连，其中l i v 由新选的m 个节点组成。 在每一时刻，新加入的节点从局域世界中按照优先连接原则选取m 个节点来 连接，而不像b a 模型那样从整个网络中来选择。当m = m 时，新加入的节点与 其局域世界中所有的节点相连，这意味着在网络增长过程中，优先连接机制实际 上已不发挥作用。此时，网络度分布服从指数分布：p ( k ) o ce 加。当m = ，+ 时， 第1 章绪论 每个节点的局域世界就是整个网络。此时，局域世界模型完全等价于b a 模型。 文献【5 3 】改变了b a 模型中平稳增长的机制，提出了幂律增长( p o w e rl a w g r o w t h ) 模型。模型中每一时刻增加的节点附带m ( t ) 条边，m ( t ) 满足： r e ( t ) = m t f ，0 p l( 1 9 ) 文献 5 4 】理论推导了这个幂律增长模型的度分布，并且提出了一个对数增长 ( 1 0 9 a r i t h m i cg r o w t h ) 模型。模型中每一时刻增加的边满足： m ( t ) = 聊i n t ，f 2( 1 1 0 ) 它的度分布没有解析解，利用马氏链法进行了数值计算。 文献 5 5 】和 5 6 】改变了增长机制中每次增加一个节点的原则，分别每次增加一 个社团和一个派系，并理论分析了模型的度分布，给出了解析解。 3 加权网络模型 前面我们所讨论的网络模型都是无权网络模型，无权网络只能表示节点间的边 存在或不存在两种情况。显然，无权网络只能给出节点问的相互作用存在与否的 定性描述，这种定性描述反映了相互作用最主要的信息。但在许多情况下，节点 之间的关系或相互作用强度的差异起着至关重要的作用。例如，神经网络中的连 接权重对于网络功能的实现至关重要【5 7 1 ，在关于大脑皮层微回路的研究中，发现 神经元突触之间的连接在学习和认知过程中并不改变，只是突触之间连接强度的 变化使大脑皮层产生了新的功能【5 8 】。因此，加权网络模型的研究已经成为复杂网 络研究的一个重要领域f 5 9 缶3 1 。 文献【6 4 】提出了一个简单的考虑权重的无标度网络演化模型。在演化过程中， 网络拓扑结构的演化规则与无权网络演化的b a 模型完全相同。当每一时刻，类似 b a 网络新增加了一个节点和朋条边后，给节点j 的每条边赋予权重( = w j i ) ： 2 琢i f 代表新节点所要连接的节点的集合，因此新节点的点强度为s j = ，= 1 。 显然，此模型的拓扑结构与b a 模型相同，生成网络的度分布和强度分布都符合幂 律分布，并且在f 寸o o 时的渐进情况下，点强度分布会渐渐逼近度分布。此模型的 关键是在b a 无标度网络的基础上为边赋权，提供了一个简单的建模思路。 文献【6 5 】对以上模型进行了推广，在给连接赋予权重时，综合考虑了节点的度 浙江工业大学博士学位论文 和适应度。首先给每个节点赋予一个适应度r i ，且刁，服从【o ，1 】之间的均匀分布 p ( 7 7 ) 。在给新的连接赋权时，以概率p 按公式( 1 1 1 ) 赋予权重，以1 一p 的概率按节 点的适应度赋权： ，2 j r 7 l r r ( 1 1 2 ) 当p = 1 时，该模型就退化为文献【6 4 】中的模型；当p = 0 时，边权的赋予完全由节 点的适应度决定。此模型的点强度分布也符合幂律分布。 文献【6 6 】提出了一个加权网络的演化模型，改进之处是在演化过程中考虑了边 权对网络结构演化的影响。模型的演化规则如下：每一时刻有一个新节点，加入到 网络中，并选择一个老节点蔟皂立一条连接，其连接概率正比于节点的强度： 卟轰 ( 1 1 3 ) 该演化规则改变了依据度值的优先连接机制，而是关注点强度对连接的驱动作用， 即点强度越大的点被连接到的概率高。 以上加权网络模型都属于边权固定模型，而文献【6 7 】提出了一个边权演化模 型，此模型是基于点强度驱动和边权逐渐加强机制建立的网络演化模型，可以模 仿现实系统中相互作用强度的变化。首先，给定一个包含个节点的小网络，其 中每条边都赋予权重峋；然后，在每一时刻带有m 条边的新节点加入到网络中， 其中每条边的权重为，每条边根据公式( 1 1 3 ) 以点强度驱动的方式选择老节点f 与之相连。新边p ，f 的加入会导致节点f 与其邻居，之间的边权重新分配，分配规则 如下： 一w i t + a w | ，v i f( 1 1 4 ) 其中 挑= 艿丝 ( 1 1 5 ) 本规则考虑权重为w o 的新边的加入会给节点f 带来一个小的流量增量占，然后在所 有与i 相连的边中按权重所占比例分配增量占。此模型生成的网络的度分布、点强 度分布和边权分布均为幂律分布，并且幂指数依赖于参数万和。 文献 6 8 1 也提出了一个边权演化模型，此模型的演化规则如下：网络演化开始 第l 章绪论 于任意的一组节点和边，例如条权重为1 的边开始；在每一时刻，首先，根据 与权重成正比的概率选择一条边，并且令该边的权重增加一个小量6 ；其次，一个 新节点连接到该边的两个端点上，新边的权重设为1 。该模型生成的网络的边权分 布、度分布和点强度分布均为幂律分布。 文献 6 9 1 基于技术网络的性质，提出了一个流驱动的加权网络模型。该模型不 仅考虑了新节点加入的影响，同时考虑了边权随时间的演化和老节点之间新边的 生成。其演化规则如下：在每一时刻，所有可能的连接都会根据如下机制改变连 接的权重： 坳专附w u + 1 瑟臻 ，6 ， 助：害l ( 1 1 7 助2 荔 u j7 ) w = 为每一步所增加的权重值的平均值；同时，带有m 条边的新节点 _ 一i ， 刀按下面的规则与老节点随机连接： n f = 袁2 丽s n s i li ( 1 1 8 ) 每条新边的权重值为。该模型生成的网络的边权分布、度分布和点强度分布均 为幂律分布。 1 3 2 网络实证 复杂网络的研究可以说是由w s 小世界网络模型和b a 无标度网络模型的提出 引起的，而无论是w s 模型还是b a 模型，都来自于对实际网络的研究和抽象。 w s 模型是根据实际的社会网络提出来的【l 】，b a 模型则是根据实际的互联网构建 的【2 1 。因此，对实际复杂网络的实证研究一直以来都是复杂网络研究的一个重要方 面【1 9 1 。实际的复杂网络广泛的存在于我们生活当中，人们对实际复杂网络的研究 主要集中在生物网络1 7 0 7 5 1 、社会网络【7 6 8 0 1 和技术网络【8 1 。8 6 1 等等。 1 生物网络 生物网络主要研究以下四个基本性质： 幻生物网络的结构性质( n e t w o r ks t r u c t u r e ) ，包括基因调控网络、生物化学 浙江工业大学博士学位论文 反应途径和网络的连接结构性质，网络中的基本结构模块或模式。 b ) 生物网络的动态特征( s y s t e md y n a m i c ) ，即在不同条件下，生物系统随时 间的演化过程和动态性质。对于连续变量的网络模型，可以利用非线性动力学中 的相图、敏感性分析、分叉点分析等方法研究系统的动力学规律，以理解生物系 统的内在动力学机制。 c ) 生物网络的控制方法( c o n t r o lm e t h o d ) ，研究正反馈、负反馈和时间延迟 等控制机制在生物调控网络中的应用。 d ) 生物网络的设计方法( d e s i g nm e t h o d ) 。 文献【9 】利用酵母细胞的蛋白质蛋白质相互作用数据，研究了酵母蛋白质作用 网络的整体结构性质，发现其中蛋白质的连接度服从幂律分布，越是重要的蛋白， 与它连接的线段数目越多。对该网络中的节点进行随机敲除，发现网络具有稳定 性；但如果敲除网络中的关键高连接度节点，网络很容易被破坏。 文献【1 0 】进一步研究发现，越是古老的蛋白质，越具有高的连接度，这说明蛋 白质网络结构上的无标度网络分布性质可能与基因调控网络的形成和进化存在一 定的联系。 文献【8 7 】研究了人类免疫系统中细胞间的通信过程，把这一过程抽象为加权有 向网络，其中节点代表不同种类的细胞，边代表细胞间的响应关系，权重，则表 示细胞f 所分泌的能影响细胞，的可溶性介质的种类数。研究结果表明，免疫细胞 加权网络是一个高度非均匀的网络，极少数的可溶性介质在调解不同细胞种类间 的相互作用中起着中枢作用。 2 社会网络 科学家合作网、电影演员合作网、e m a i l 网以及人际关系网络等等都是典型的 社会网络，其中许多网络的拓扑性质，如科学家合作网络和电影演员合作网，都 得到了深入的研究。 文献 8 8 】给出了科学家合作网络的基本统计特性，发现科学家合作网既有小世 界网络的性质，又有无标度网络的特征。文献 7 6 贝j j 主要研究了科学家合作网络的 演化性质。在无权的科学家合作网中，科学家是网络中的节点，如果两位科学家 至少合作过一篇文章，则对应的节点之间连有边。在实际情况中许多科学家之间 合作过多次，无权网络仅用边的存在与否给出了他们之间的定性关系，不足以说 明他们的亲密程序，因此人们建议把科学家间的合作次数转化为权重来区分亲密 第1 章绪论 程度的差异性。 文献【8 9 】根据电子网站a r x i v o r g 上1 9 9 5 至1 9 9 8 年之间关于凝聚态方面的文章， 将科学家合作网络建模成一个加权复杂网络进行研究。研究发现网络的点强度分 布与度分布情况类似，都有胖尾( h e a v yt a i l ) 现象。并且发现点强度的平均值与度 的关系表现为线性关系，表明权重与网络的拓扑结构之间是相互独立的；而关于 聚类系数的实证结果表明，度值小的节点的聚类系数会更高，表明合作者较少的 科学家之间在一起合作的机会更大一些。 文献 9 0 1 根据m t i m e 网站上的数据，对中国的演员合作网络进行了实证研究， 分析了网络特性，表明演员合作网络也具有小世界性质。文献【9 1 】根据电影数据库 的数据，再次报道了对中国演员合作网络的实证研究。并且将影片的主要演员定 义为项目，他主演的影片定义为这个项目的参与者，进一步研究了影片为了吸引 观众而进行的竞争。 3 技术网络 i n t e r n e t 、铁路网络、地铁网、航空网和公共交通网络等都属于技术网络，对 各种技术网络的研究从复杂网络研究的初期就开始了，人们希望通过对技术网络 的研究达到认识、了解并改进网络的目的，使之能更好的为人类服务。 文献 9 2 1 通过研究1 9 9 7 年1 1 月至1 2 月自治系统( a u t o n o m o u ss y s t e m ，a s ) 层面i n t e m e t 的统计特性，首次揭示了i n t e m e t 拓扑的一些幂律分布特性，开拓了 i n t e m e t 拓扑研究的新方向。然后，他们又针对1 9 9 7 年9 月至2 0 0 2 年2 月的a s 层面i n t e m e t 拓扑演化情况作了进一步研究，指出a s 层面i n t e m e t 拓扑满足以下 四种幂律分布【9 3 1 ： 幂律分布i ： 4 r j 尺( 1 1 9 ) 其中4 是节点f 的度，是将网络中节点按度降序排列节点i 的序列号，r 是秩指 数常数。 幂律分布i i ： 仍o cd d ( 1 2 0 ) 其中岛表明度大于d 的节点在整个网络中所占的百分比，d 是度指数常数。可以 推得r ；1 d 。 浙江工业大学博士学位论文 幂律分布i i h 允，o c j ( 1 2 1 ) 其中兄，为网络对应的邻接矩阵的特征值，为将特征值按降序排列时的序列号。 特征值指数s 和连接度指数d 问存在近似关系占0 5 d 。 幂律分布i v ： 尸( g ) 芘g u ( g 万)( 1 2 2 ) 其中p ( g ) 为距离不超过g 的节点对的数目( 也称为h o p 内的节点对的数目) ，其中 包括自节点对，并对其他节点对记数两次，g 是h o p 指数常数。 铁路网络包含两个基本单元：火车站和火车车次。铁路网络有三种空间的网 络定义：s p a c ep 、s p a c er 和s p a c el 。在s p a c ep 中，网络节点定义为火车站，如 果至少有一个火车车次停靠两个车站，则这两个车站之间连接一条边。在s p a c er 中，网络节点定义为火车车次，如果两条火车车次停靠至少同一个火车站，则这 两条车次之间连接一条边。在s p a c el 中，网络节点仍旧定义为火车站，如果两个 车站在至少一个火车车次运行中作为相邻的两个站点，则这两个车站之间连接一 条边。在s p a c el 中，铁路网络的网络图就类似于火车站内常有的运行示意图。文 献 9 4 1 5 1 文献 9 5 1 分别对s p a c el 的波士顿地铁网络和s p a c ep 的印度铁路网进行了 实证研究，给出了铁路网络的一些统计性质。文献 9 6 1 对s p a c el 的波士顿和维也 纳地铁网络做了进一步的研究。文献 9 7 1 对所有三个空间的中欧铁路网络和瑞士铁 路网络做了实证研究，并且比较了不同铁路系统在不同空间中的一些统计性质。 另外，文献 9 8 ，9 9 1 对s p a c ep 的中国铁路网络进行了实证研究，文献 1 0 0 1 对s p a c el 和s p a c ep 的中国铁路网络进行了实证研究。 航空网络也同样有相应的三个空间的网络定义，但是，由于大多数航班直飞 终点站，少数也仅仅途经很少几个中间飞机场，所以s p a c ep 和s p a c er 的航空网 研究意义不大。目前的研究文献一般都定义飞机场或者城市为网络节点，如果两 个飞机场之间至少通一个航班，就连接一条边。这相当于s p a c el 下的网路，很像 常见到的航线图。文献 1 0 1 ，1 0 2 】对这样定义的美国航空网络做了实证研究，文献 【8 1 ，1 0 3 5 f j 这样定义的中国航空网络做了实证研究，文献1 8 2 ，8 9 ，1 0 4 ，1 0 5 1 对这样定 义的北美航空网络和全世界航空网络进行了实证研究。 公共交通网络包含公交站点和公交线路两个基本单元。每一条公交线路就是 第1 章绪论 一个派系( 完全图) i s 5 】，公交站点就是这个派系的参与者，以这种方式映射得到 的公交网络就是s p a c ep 下的公交网络。具体的说就是将公交站点定义为网络节点， 如果至少有一条公交线路停靠两个公交站点，则这两个公交站点之间连接一条边。 公交网络还可以在s p a c er 和s p a c el 中进行描述。在s p a c er 中，将公交线路定义 为网络节点，如果两条公交线路停靠至少同一个公交站点，则这两条线路之间连 接一条边。在s p a c el 中，网络节点仍定义为公交站点，如果两个公交站点在至少 一条公交线路中作为相邻的两个站点，则这两个站点间连接一条边。文献1 1 0 6 1 对 波兰二十二个城市的实际公交网络进行了实证研究。文献 1 0 7 对世界十四个大城 市的公交网络进行了实证研究。文献 8 5 ，1 0 8 1 1 2 分别对中国的几个大城市的公交 网络进行了实证研究，并且还分别提出了对应的公交网络模型用以对实际公交网 络进行模拟，最后还对模型进行了理论分析，得到了度分布等网络统计量的解析 解。 1 3 3 网络搜索 随着小世界特性在网络中的发现，人们进一步对复杂网络的可搜索性，或者 说是可快速搜索性进行了研究【l7 1 。一般而言，网络的小世界特性并不一定意味着 网络是可以快速搜索的。在一个大规模的网络中，连接两个节点之间的路径可能 有很多条。网络中的一个节点是否能找到它与任一其他节点之间的较短甚至最短 的路径，依赖于节点所了解的网络结构信息、节点所使用的搜索算法和整个网络 的实际结构。k l e i n b e r g 首先在理论上研究了复杂网络的搜索能力，即在网络中能 够实现快速搜索的性质【1 1 3 1 1 4 】。此后，w a t t s 等人又对此问题作了进一步的研究【1 15 1 。 复杂网络搜索策略通常用一个消息传递的过程来描述。从一个给定的源节点 开始，为了寻找所需要的信息，按照一定的规则向它的一个或多个邻居传递查询 消息。如果收到查询的邻居节点上不含有源节点所需要的信息，那么这些邻居节 点再将查询传递给它们各自的邻居，重复这个过程直到存储着指定信息的目标节 点被寻找到为止。如果网络的全局连接信息是已知的，也就是说，每个节点都知 道其他各个节点上存储了哪些信息，并且还知道怎样在最少的步数内到达对方， 那么消息从源节点s 依次经过最短路径，。，上的各个节点，一直传递到目标节点t 。 由于对于规模为j 7 v 的小世界网络来说，“芘l o g ，因此搜索步数以及网络中的查 浙江工业大学博士学位论文 询消息流量都很小。然而在许多实际网络中，单个节点无法充分掌握整个网络的 全局结构，甚至于不知道目标节点在网络中的位置。此时，个最简单的搜索策 略就是广度优先搜索( b r e a d t h f i r s ts e a r c h ，b f s ) 策略。 1 广度优先搜索策略 在源节点s 应用b f s 策略搜索目标节点t 时，首先判断自己的邻居节点中有无 目标节点。若有，则中止搜索；若无，则向每个邻居查询它们的邻居节点中有无 目标节点。重复这个过程一直到寻找到目标节点的任一个邻居为止。如图l 一8 所 示【1 7 1 。 t 一一一) ，t ， 一( b ：， 、古7 图1 8b f s 策略的搜索过程 b f s 策略还可以用来寻找任意两点之间的最短路径6 】。即从一个源节点出发， 其所有的邻居节点与源节点之间的距离为l ，所有邻居的邻居节点与源节点的距离 为2 ，以此类推。因此，在图1 8 中b f s 策略所得到的源节点s 与目标节点t 之间 的路径长度等于两点之间的最短路径长度l s l = 3 。由于在小世界网络中， ，盯芘l o g n ，因此b f s 策略在寻找节点之间的路径时是很有效的，并且由于查询是 并行的，因此搜索范围将以几何级数增长，通常短短几步之内查询就将遍布整个 网络，搜索速度相当快。但是，随着网络规模的扩大，这样的处理方式会在网络 中产生大量查询消息流量，造成网络流量急剧增加，从而导致网络拥塞。因此， 在实际应用中，需要设计出更经济的搜索策略：随机游走( r a n d o mw a l k ，r w ) 策 略和最大度( h i g hd e g r e es e e k i n g ，d s ) 策略。 2 随机游走搜索策略 当源节点s 应用随机游走策略搜索目标节点f 时，s 首先判断自己的邻居节点 中有无目标节点t ：若有，则中止搜索；若无，则向任一个邻居查询它的邻居节点 中是否有目标节点。重复这个过程一直到寻找到目标节点，的任一个邻居为止，如 图l 一9 所示。与b f s 策略相比，随机游走的搜索步数要大很多，但由于每一步只 。只、9， 了，吁叮 、9 ，l 6 = 二 o 聍蹬 。只b， 。7穹b 鼢盐 第1 章绪论 前传一个查询消息，因此大大减少了网络中的消息流量。 图1 9r w 策略的搜索过程 随机游走是一个基础的动态过程，也是研究复杂网络结构的一个很有用的工 具。文献【1 1 7 1 研究了规则网络和随机网络中的随机游走。近来，小世界网络中的 随机游走8 。1 2 以及无标度网络中的随机游走【1 2 2 1 冽都引起了人们的关注。随机游 走搜索主要又分为以下三种不同的搜索策略1 2 0 ，1 2 5 】： a ) 无限制的随机游走( u n r e s t r i c t e dr a n d o mw a l k ，u r w ) 搜索策略：每一步 中，当前节点不加任何限制地在其所有邻居中随机选择一个邻居节点将查询传递 过去，一直到搜索到目标节点的任一个邻居为止。 ”不返回上一步节点的随机游走( n o - r e t r a c i n gr a n d o mw a l k ，n r r w ) 搜索策 略：除了刚刚将查询传递过来的上一步节点外，每一步中，当前节点在其余的所 有邻居中随机选择一个邻居节点将查询传递过去，一直到搜索到目标节点的任一 个邻居为止。 c ) 不重复访问节点的随机游走( s e l f - a v o i d i n gr a n d o mw a l k ，s a r w ) 搜索策略： 已经被查询过的节点不允许再被查询，且每一步中当前节点在其所有未被查询过 的邻居中随机选择一个邻居节点将查询传递过去，直到搜索到目标节点的任一 个邻居为止。 3 最大度搜索策略 最大度搜索策略最初由a d m i c 等人提出，对g n u t e l l a 网络的统计表明，其连 接度是呈幂律分布的，他们在此基础上提出了利用节点度的幂律分布特性来搜索 的最大度搜索策略，并在g n u t e l l a 网络上验证了其有效性【1 2 2 ，1 2 6 】。 。只多， 。7呵_b 一 、 r、寸，久，rq、o， 五u一一抄 矗= = 抄五m 旷叶，a，。a、o， 。ao， 。7彳盯 一 ， 、9 ，t 卜s 浙江工业大学博士学位论文 文献 1 2 7 禾1 j 用最大度搜索策略研究了幂律分布网络中的路径寻找问题。假设每 个节点都认识自己的邻居并知道每个邻居的度。当源节点s 应用最大度搜索策略寻 找其与目标节点t 之间的路径时，s 首先判断自己的邻居节点中有无目标节点，：若 有，则中止搜索；若无，则向其度最大的邻居查询它的邻居节点中是否有目标节 点。重复这个过程一直到寻找到目标节点t 的任一个邻居为止，如图1 1 0 所示。 去掉初始路径上的环以及原路返回的步数之后，就得到源节点和目标节点之间用 d s 策略寻找到的路径，使得两个节点可以重复通过这条路径取得联系。对所有两 点之间用d s 策略寻找到的路径求平均之后，就可以得到网络的实际平均路径长 度。 图1 1 0d s 策略的搜索过程 假定每个节点仅仅知道自己邻居节点的信息，即每个邻居节点的度的大小。 d s 策略寻找两个节点之间的路径的步骤如下【1 7 】： 初始时选取源节点f 与目标节点_ ，。 从节点f 出发，判断自己的邻居节点中有无目标节点：若无，则将其中度 最大的邻居节点设为当前节点；若有，则中止搜索。 可以多次访问同一个节点，但是同条边只能被访问一次，如果与当前节 点相连的所有的边都被访问过，则返回到上一个节点。 重复和两个步骤，直到当前节点为目标节点的任一个邻居节点，目标 节点即被找到，搜索完成。 第1 章绪论 1 3 4 社团结构 社团结构是人们随着对网络性质的深入研究而发现的许多实际网络都具有的 一个共同性质【1 2 8 都6 1 。也就是说，整个网络是由若干个“群( g r o u p ) 或“团( c l u s t e r ) ” 构成的。每个群内部的节点之间的连接相对非常紧密，但是各个群之间的连接相 对来说却比较稀疏，如图1 1