1、题 目 杭州公交网络的无标度性实证研究专 业 数学与应用数学摘 要复杂网络的无标度性是指网络拓扑结构中边连接的度分布服从幂律分布，而该分布具有标度不变性；其小世界特性是指其网络平均最短路长度与网络规模的对数成比例，且网络聚类系数远大于随机图网络的聚类系数。复杂网络的拓扑特性分析，特别是验证网络的无标度性与小世界特性，对于网络的关键节点发现，网络的抗毁性，网络上信息传播、网络导航等都具有十分重要的理论与现实意义。复杂网络是最近几年新兴的一个研究热点，科学家们发现越来越多的实际网络具有复杂网络的特性，并对复杂网络的模型、容错与抗攻击及其动力学特性做了很多研究。交通网络在实际的生活中有着重要的作用，
2、交通网络的设计、规划与实现对人们出行有着重要的影响。公交网络是交通网络中的重要的组成部分。本文首先介绍了复杂网络的概念及其研究进展，网络演化模型的研究方法，并通过掌握复杂网络获得度分布的三种方法，即速率、主方程、连续理论方法等，分析无标度性与小世界特性的内在形成机理。然后获取杭州公交网络的实际数据，获得网络的度分布，聚类系数，平均最短路长度等拓扑指标，验证网络的无标度性与小世界特性，从而可以根据现有的研究成果针对该网络给出新增公交线路或现有线路改造的合理建议。关键词：无标度网络；小世界特性；聚集性；复杂网络ABSTRACTThe scale-free property of complex n
3、etwork topology refers to the structure of edge-connected degree distribution obeys power-law distribution, and the distribution is scale invariance. The small-world network means that the average shortest path length is proportion to the network size, and the network clustering coefficient is more
4、than random network clustering coefficient. The analysis of topological properties of complex network, especially, scale-free networks and small world properties, has an important theoretical and practical significance to the discovery of network hub nodes, network robustness, network information sp
5、read, and the network navigation, etc. It is a new research hot spot of complex network, and many scientists have discovered that more and more real-world networks have the property of complex network. Many researches aim to the model of complex networks, error toleration, and dynamic behavior. Tran
6、sport network plays an important role in real life and the design, planning and realization of transport network have an important impact to people transportation. And public transportation network is an important transport network.Firstly, the concept of complex network and its research progress ar
7、e introduced in this paper. And the evolving network model is researched and three methods obtaining the degree distribution of complex networks, which are rate equation, master equation, and continuous theories, are presented. The inherent evolution mechanism of forming the scale-free and small-wor
8、ld property is discussed. Then, the data of Hangzhou public transportation network are accessed and the degree distribution, average shortest path length, and clustering coefficient are calculated. We verify scale-free networks and small world properties to this network. So some reasonable advices o
9、f increasing the new bus lines or reconstructing the existing lines can be obtained by the research results. Keywords: scale-free nature of; small-world characteristics; aggregation; complex network目 录1引言.12复杂网络的介绍.22.1 复杂网络的发展.22.2 复杂网络的特性.32.3 复杂网络的区分.32.4 复杂网络的研究意义.43复杂网络的分类.63.1 规则网络.63.2 随机图.63
10、.3 小世界网络模型.73.4 无标度网络模型.74杭州公交网络的建立.94.1 公交网络模型.94.2 杭州公交 网络数据描述.105公交网络无标度性.125.1 公交网络的无标度分布.125.2 公交网络的聚集性.155.3 公交网络平均最短路长度与聚类系数.155.4 结果分析.176结论.19致 谢.20参考文献.21附录.2511引言复杂网络，特别是小世界网络和无尺度网络刚一提出，就呈现出广阔的应用前景。Internet、WWW以及新陈代谢等的连接度分布函数具有幂律形式，而且这类网络的节点的连接度没有明显的特征长度，故称为无标度网络 1。Barabasi和Albert提出的无标度网络
11、模型被称为BA模型。BA模型的两个重要特性是：增长特性和有线连接特性。它表明网络的规模不断扩大，新的链接更倾向于那些具有较高连接度的“大”节点相链接，这种现象也叫“马太效应” 2。随着网络的不断发展，公交网络的不断普及和完善，现实中无标度网络的指的是除了小世界效应外，大量实际网络还存在着另一个突出的结构特征幂律度分布，称其为无标度网络。无标度网络的特点是分布的自相似结构及其高度弥散性，在不相关的无标度性网络必然是小世界的(事实上，比小世界更小)。尽管如此，无标度网络相关度分布可能并非如此。我们描述一个产生具有高对称性但非小世界的无标度性网络模型的演化机理。在公交网络中引入了复杂网络中的基本静态
12、几何量，本文结合杭州市公交网络的实际数据，验证了杭州市公交网络的小世界特性和无标度特征，并在此基础上分析研究了公交网络的有效性和脆弱性 3-4。 首先，根据公交网络的特性，结合杭州市实际公交网络数据建立了杭州市公交网络模型和杭州市公交换乘网络模型。目前，国际上已经形成研究复杂性问题和复杂网络的研究热潮。而复杂网络是研究复杂性问题的有力工具。自然界中存在着大量的复杂系统，如Internet网、计算机网络、神经系统、社会关系网络等等，都可以通过复杂网络进行描述。通过研究这些复杂网络的内在机制和演化规律，从而找到网络上的复杂行为与网络结构的关系，增加对复杂网络系统的自然规律的认识。 度分布是复杂网络
13、问题中研究较多的一个方向，本文主要研究了复杂网络中匀速增长的非线性择优连接的BA 模型度的分布。22复杂网络的介绍2.1 复杂网络的发展万维网上从一个页面到另一个页面平均需要点击多少次鼠标？层出不穷的计算机病毒是如何在互联网上传播的？各种传染病是如何在人类和动物中流行的？全球或地区性的金融危机是如何发生的？大城市的交通阻塞问题是如何引起的？为什么大脑能够具有思维的功能？这些问题看上去各不相同，但每个问题都涉及很复杂的网络，包括WWW、Internet、社会关系网、经济网络、电力网络、交通网络、经济网络等等。由于现实世界网络的规模大，节点间相互作用复杂，其拓扑结构基本上未知或未曾探索。两百多年来
14、，人们对描述真实系统拓扑结构的研究经历了三个阶段。在最初的一百多年里，科学家们认为真实系统要素之间的关系可以用一些规则的结构表示，例如二维平面上的欧几里德格网从20世纪50年代末到90年代末，无明确设计原则的大规模网络主要用简单而易于被多数人接受的随机网络来描述，随机图的思想主宰复杂网络研究达四十年之久直到最近几年，科学家们发现大量的真实网络既不是规则网络，也不是随机网络，而是具有与前两者皆不同的统计特性的网络，其中最有影响的是小世界网络和无尺度网络。这两种网络的发现，掀起了复杂网络的研究热潮。1959-1960年，匈牙利数学家艾尔德（P.Erdos）和莱利（ A.Renyi）建立了随机图（E
15、R模型），被公认为是数学上开创了复杂网络理论的系统性研究。 20世纪60年代美国哈弗大学的社会心理学家Stanley Milgram通过一些社会调查后给出的推断是：地球上任意两个人之间的平均距离是6。也就是说，平均中间只要通过5个人，你就能与地球上的任何一个角落的任何一个人发生联系。1998年，康奈尔大学的社会学家Watts和Strogatz 提出了小世界网络（WS模型） 5。1999年，圣母大学的物理学家Barabsi和Albert提出了无尺度网络（ BA模型） 6。复杂网络研究的快速发展的主要原因包括：1、越来越强大的计算设备和迅猛发展的Internet，使得人们开始能够收集和处理规模巨大
16、且种类不同的实际网络数据。 2、学科之间的相互交叉使得研究人员可以广泛比较各种不同类型的网络数据，从而揭示复杂网络的共性。3、以还原论和整体论相结合为重要特色的复杂性科学的兴起，也促使人们开始从整体上研究网络的结构和性能之间的关系。著名的物理学家霍金认为二十一世纪是复杂性的世纪。复杂网络的研究是复杂性理论研究的一部分，作为研究复杂性科学和复杂系统的有力工具，复杂网络为研究复杂性提供了全新的视角。复杂网络借助于图论和统计物理的一些方法 7-13，可以用来捕捉并描述系统的演化机制、演化规律结构和整体行为功能。32.2 复杂网络的特性2.2.1 结构复杂性网络连接结构看上去错综复杂、极其混乱，而且网
17、络链接结构可能是随时间变化的，例如，WWW 上每天都不停地有页面和链接的产生和删除。此外，节点之间的连接可能具有不同的权重或方向。例如，神经系统中的突触有强有弱，可以是抑制的也可以是兴奋的。2.2.2 节点复杂性网络中的节点可能是具有分岔和混沌等复杂非线性行为的动力系统。例如，基因网络和Josephson结阵列中每个节点都具有复杂的时间演化行为。而且，一个网络中可能存在多种不同类型的节点。例如，控制哺乳动物中细胞分裂的生化网络就包含各种各样的基质和酶。2.2.3 各种复杂性因素的相互影响实际的复杂网络会受到各种各样因素的影响和作用。例如，耦合神经元重复地被同时激活，那么它们之间的连接就会加强，
18、这被认为是记忆和学习的基础。此外，各种网络之间也存在密切的联系，这使得对复杂网络的分析变得更加困难。例如，电力网络的故障可能会导致Internet流量变慢、金融机构关闭、运输系统失去控制等一系列不同网络之间的连锁反应。2.3 复杂网络的区分根据节点度的分布情况，可以将复杂网络分为指数网络和无尺度网络两大类。指数网络中的节点是同质的，它们的度大致相同，绝大部节点的度都位于网络节点平均度附近，网络节点度分布随度数的增加呈指数衰减，使得网络中不存在度数特别大的节点，最经典的两种指数网络是 ER 随机图模型和小世界网络模型。随机图与小世界网络的主要区别是前者的簇系数小，而后者的簇系数大。目前，把具有较
19、小平均路径长度和较大簇系数的网络统称为小世界网络，这一说法己得到学术界的公认。无尺度网络中的节点是异质的，其节点度服从幂律分布。最著名的无尺度网络模型是 1999 年Barabasi 和 Albert 建立的无尺度网络模型模型 3。在无尺度网络中，大部分节点只与少数几个其它节点连接，但网络中存在为数不多的度数特别大的节点，称为集散节点或节点，它对无尺度网络的特性起着主导和支配作用。从生成方式上可将复杂网络分成随机性网络和确定性网络。顾名思义，随机网络的生成是随机的，尽管生成规则相同，每次在电脑上模拟生成的网络却存在差异性确定性网络的生成规则是确定的，其结构特性可以精确求解。从边的方向性上可将网
20、络分为无向网络和有向网络，无向网络的边不存在方向性，有向网络的边却有方向。4从边有无权值可将网络分为加权网络和 0-1 网络。2.4 复杂网络的研究意义复杂网络，特别是小世界网络和无尺度网络刚一提出，就呈现出广阔的应用前景，其应用领域涉及工程技术、社会、政治、医药、经济、管理等不同方面 4。在过去几年里，不同领域的研究者发现，包括万维网、细胞代谢系统、好莱坞的演员网络在内的许多现实网络，都是无尺度网络，它们由少数几个具有众多连结的节点所支配，这些重要节点通常称为集散节点。无尺度网络对意外故障具有惊人的承受力，但面对协同式攻击时则很脆弱。这些新发现极大地改变了人们对复杂外部世界的认识，让人们认识
21、到了以前的理论尚未涉及的问题各种复杂系统具有相同的严格结构，都受制于某些基本的法则，这些法则似乎可同等地适用于细胞、计算机、语言和社会。认识这些法则，可以将其应用到不同领域，帮助人们解决一系列重要问题。首先，复杂网络理论可以用于保护许多现实系统的正常运行。因特网、电力网、航空网、万维网、电子邮件网、食物链网等网络与我们的生活息息相关，人们对这些网络的依赖程度日益增强，凸现了一个广受关注的问题，这些网络到底有多可靠呢？2000年，爱虫病毒侵犯了英国议会的电子邮件系统，导致该系统瘫痪；2003年，美加电网的大崩溃事故让纽约人感到惶恐不安当前，人类赖以生存的生态系统不断遭到破坏己经危及到人类的生存环
22、境，等等。从这些现象可以自然地提出下面的问题计算机病毒如何在万维网上传播而导致流行病毒如何通过电子邮件传播，人们如何控制病毒传播？面对黑客的攻击，应该采取何种对策？怎样设计出承受意外故障较强的网络如电力网、航空网？怎样保持当前不断恶化的生态系统的平衡？这些问题的解决都与复杂网络的研究有关，开展好复杂网络稳定性的研究，对于互联网、电力网、航空网等技术网络的设计保护及基础设施网络的保护具有重要的意义，也可以有效地防止黑客侵入互联网、阻止病毒在万维网上传播蔓延。复杂网络在社会领域也有广阔的应用。传染病如艾滋病、非典、禽流感等对人类的威胁很大艾滋病让人们不寒而栗年的非典对于宏观经济和人类的生命安全都产
23、生了巨大的负面影响目前，禽流感也己成为世界关注的一个焦点。那么在特定的社会网络中，传染病如何通过接触关系传播而导致流行呢？决策者如何控制这些疾病，将损失降到最低限度呢这些问题或许可以从复杂网络那里寻找答案。最近几年，科学家们考虑了不同现实系统的主要特征，提出了许多有针对性的疾病免疫方法晰一，为疾病的预测、预防和免疫提供了科学的方案。譬如，用复杂网络理论可以很好地预测非典爆发的多样性、了解疾病传播的动态性，为决策者控制流行病蔓延、改善公共卫生提供有效的手段。复杂网络在经济、管理领域也有着重要的实际意义 5。利用复杂网络理论了解公司、产业与经济之间的连结方式，有助于监控和预防大规模的经济衰退。在管
24、理领域，决5策对经济的发展起着关键性的作用，同一个人可以在多个组织内兼任董事。建立公司董事网，使得分析决策的动态性成为可能。经济网络恰好刻画了经济系统中微观个体之间存在相互作用的关系结构，这种关系可以是经济个体之间的信息交流、商品或股票交易、投资关系、信用关系或者隶属控制关系等等。1999 年，Barabsi 与 Albert 作出了对复杂网络里程碑式的研究，他们揭示了许多现实网络的连接具有无标度性的这个引人注目的结果。受这一研究结果的激励，人们开始关注经济与经济网络的结构，开展了许多关于经济与金融系统网络结构的实证研究。结果显示：在经济的多个方面人们观测到了经济网络具有无标度性和小世界等性质
25、。63复杂网络的分类3.1 规则网络在很长一段里，人们认为真实系统各因素之间的关系可以用一些规则网络表示，如一维链、二维平面上的欧几里德格网等。用得最多的规则网络是由N 个节点组成的环状网络，网络中每个节点只与它最近的K个节点连接。在规则网络中，每个节点具有相同的度和簇系数。节点的度分布为 函数，即 。节点簇系数为()PkK（d为网络维数），集聚程度较高 6。3(2)4C在一个全局耦合网络中，任意两个点之间都有边直接相连（图3.1）。在具有相同节点数的所有网络中，全局耦合网络具有最小的平均路径长度L=1和最大的聚类系数C=1。图 3.1 规则网络3.2 随机图与完全规则网络相反的是完全随机网络
26、，其中一个典型的模型是 ER 随机图模型。ER 随即图的性质与概率之间的关系，采用以下定义：如果当 时产生一个具有性N质 Q 和 ER 随机图的概率为 1，那么就称几乎每一个 ER 随机图都具有性质 ER 随机图的节点度服从泊松分布，它具有较小的平均路径长度和较小的簇系数。ER 模型提出后，从 20 世纪 50 年代末到 90 年代末的近四十年里，无明确设计原则的大规模网络主要用这种简单而易于被多数人接受的随机图的拓扑结构来描述，即认为大规模网络的形成过程中，节点间的连接是完全随机的。期间，一些数学家对随机图进行了非常好的研究，通过严格的数学证明，得到了许多近似和精确的结果。ER 模型的思想支配人们研究复杂网络长达四十年之久，直到最近几年，由于计算机数据处理和运算能力的飞速发展，科学家们发现大量的现实网络不是完全随机的网络，而是具有其他统计特征的网络 7。
