《杭州公交网络的无标度性实证研究毕业论文.doc》由会员分享，可在线阅读，更多相关《杭州公交网络的无标度性实证研究毕业论文.doc（25页珍藏版）》请在三一办公上搜索。
1、 本科毕业论文（2009届）题 目杭州公交网络的无标度性实证研究学 院理学院专 业数学与应用数学班 级学 号学生姓名指导教师完成日期摘 要复杂网络的无标度性是指网络拓扑结构中边连接的度分布服从幂律分布，而该分布具有标度不变性；其小世界特性是指其网络平均最短路长度与网络规模的对数成比例，且网络聚类系数远大于随机图网络的聚类系数。复杂网络的拓扑特性分析，特别是验证网络的无标度性与小世界特性，对于网络的关键节点发现，网络的抗毁性，网络上信息传播、网络导航等都具有十分重要的理论与现实意义。复杂网络是最近几年新兴的一个研究热点，科学家们发现越来越多的实际网络具有复杂网络的特性，并对复杂网络的模型、容错与
2、抗攻击及其动力学特性做了很多研究。交通网络在实际的生活中有着重要的作用，交通网络的设计、规划与实现对人们出行有着重要的影响。公交网络是交通网络中的重要的组成部分。本文首先介绍了复杂网络的概念及其研究进展，网络演化模型的研究方法，并通过掌握复杂网络获得度分布的三种方法，即速率、主方程、连续理论方法等，分析无标度性与小世界特性的内在形成机理。然后获取杭州公交网络的实际数据，获得网络的度分布，聚类系数，平均最短路长度等拓扑指标，验证网络的无标度性与小世界特性，从而可以根据现有的研究成果针对该网络给出新增公交线路或现有线路改造的合理建议。关键词：无标度网络；小世界特性；聚集性；复杂网络ABSTRACT
3、 The scale-free property of complex network 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 ne
4、twork clustering coefficient is more 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, netwo
5、rk robustness, network information spread, 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 t
6、oleration, and dynamic behavior. Transport 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
7、 network and its research progress are 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
8、 forming the scale-free and small-world 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
9、network. So some reasonable advices of 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复杂
10、网络的分类63.1规则网络63.2随机图63.3小世界网络模型73.4无标度网络模型74杭州公交网络的建立94.1公交网络模型94.2杭州公交网络数据描述105公交网络无标度性125.1公交网络的无标度分布125.2公交网络的聚集性155.3公交网络平均最短路长度与聚类系数155.4结果分析176结论19致谢20参考文献21附录251引言复杂网络，特别是小世界网络和无尺度网络刚一提出，就呈现出广阔的应用前景。Internet、WWW以及新陈代谢等的连接度分布函数具有幂律形式，而且这类网络的节点的连接度没有明显的特征长度，故称为无标度网络1。Barabasi和Albert提出的无标度网络模型被称
11、为BA模型。BA模型的两个重要特性是：增长特性和有线连接特性。它表明网络的规模不断扩大，新的链接更倾向于那些具有较高连接度的“大”节点相链接，这种现象也叫“马太效应”2。随着网络的不断发展，公交网络的不断普及和完善，现实中无标度网络的指的是除了小世界效应外，大量实际网络还存在着另一个突出的结构特征幂律度分布，称其为无标度网络。无标度网络的特点是分布的自相似结构及其高度弥散性，在不相关的无标度性网络必然是小世界的(事实上，比小世界更小)。尽管如此，无标度网络相关度分布可能并非如此。我们描述一个产生具有高对称性但非小世界的无标度性网络模型的演化机理。在公交网络中引入了复杂网络中的基本静态几何量，本
12、文结合杭州市公交网络的实际数据，验证了杭州市公交网络的小世界特性和无标度特征，并在此基础上分析研究了公交网络的有效性和脆弱性3-4。 首先，根据公交网络的特性，结合杭州市实际公交网络数据建立了杭州市公交网络模型和杭州市公交换乘网络模型。目前，国际上已经形成研究复杂性问题和复杂网络的研究热潮。而复杂网络是研究复杂性问题的有力工具。自然界中存在着大量的复杂系统，如Internet网、计算机网络、神经系统、社会关系网络等等，都可以通过复杂网络进行描述。通过研究这些复杂网络的内在机制和演化规律，从而找到网络上的复杂行为与网络结构的关系，增加对复杂网络系统的自然规律的认识。 度分布是复杂网络问题中研究较
13、多的一个方向，本文主要研究了复杂网络中匀速增长的非线性择优连接的BA模型度的分布。2复杂网络的介绍2.1复杂网络的发展万维网上从一个页面到另一个页面平均需要点击多少次鼠标？层出不穷的计算机病毒是如何在互联网上传播的？各种传染病是如何在人类和动物中流行的？全球或地区性的金融危机是如何发生的？大城市的交通阻塞问题是如何引起的？为什么大脑能够具有思维的功能？这些问题看上去各不相同，但每个问题都涉及很复杂的网络，包括WWW、Internet、社会关系网、经济网络、电力网络、交通网络、经济网络等等。由于现实世界网络的规模大，节点间相互作用复杂，其拓扑结构基本上未知或未曾探索。两百多年来，人们对描述真实系
14、统拓扑结构的研究经历了三个阶段。在最初的一百多年里，科学家们认为真实系统要素之间的关系可以用一些规则的结构表示，例如二维平面上的欧几里德格网从20世纪50年代末到90年代末，无明确设计原则的大规模网络主要用简单而易于被多数人接受的随机网络来描述，随机图的思想主宰复杂网络研究达四十年之久直到最近几年，科学家们发现大量的真实网络既不是规则网络，也不是随机网络，而是具有与前两者皆不同的统计特性的网络，其中最有影响的是小世界网络和无尺度网络。这两种网络的发现，掀起了复杂网络的研究热潮。1959-1960年，匈牙利数学家艾尔德（P.Erdos）和莱利（A.Renyi）建立了随机图（ER模型），被公认为是
15、数学上开创了复杂网络理论的系统性研究。20世纪60年代美国哈弗大学的社会心理学家Stanley Milgram通过一些社会调查后给出的推断是：地球上任意两个人之间的平均距离是6。也就是说，平均中间只要通过5个人，你就能与地球上的任何一个角落的任何一个人发生联系。1998年，康奈尔大学的社会学家Watts和Strogatz 提出了小世界网络（WS模型）5。1999年，圣母大学的物理学家Barabsi和Albert提出了无尺度网络（BA模型）6。复杂网络研究的快速发展的主要原因包括：1、越来越强大的计算设备和迅猛发展的Internet，使得人们开始能够收集和处理规模巨大且种类不同的实际网络数据。2
16、、学科之间的相互交叉使得研究人员可以广泛比较各种不同类型的网络数据，从而揭示复杂网络的共性。3、以还原论和整体论相结合为重要特色的复杂性科学的兴起，也促使人们开始从整体上研究网络的结构和性能之间的关系。著名的物理学家霍金认为二十一世纪是复杂性的世纪。复杂网络的研究是复杂性理论研究的一部分，作为研究复杂性科学和复杂系统的有力工具，复杂网络为研究复杂性提供了全新的视角。复杂网络借助于图论和统计物理的一些方法7-13，可以用来捕捉并描述系统的演化机制、演化规律结构和整体行为功能。2.2复杂网络的特性2.2.1 结构复杂性网络连接结构看上去错综复杂、极其混乱，而且网络链接结构可能是随时间变化的，例如，
17、WWW上每天都不停地有页面和链接的产生和删除。此外，节点之间的连接可能具有不同的权重或方向。例如，神经系统中的突触有强有弱，可以是抑制的也可以是兴奋的。2.2.2 节点复杂性 网络中的节点可能是具有分岔和混沌等复杂非线性行为的动力系统。例如，基因网络和Josephson结阵列中每个节点都具有复杂的时间演化行为。而且，一个网络中可能存在多种不同类型的节点。例如，控制哺乳动物中细胞分裂的生化网络就包含各种各样的基质和酶。2.2.3 各种复杂性因素的相互影响 实际的复杂网络会受到各种各样因素的影响和作用。例如，耦合神经元重复地被同时激活，那么它们之间的连接就会加强，这被认为是记忆和学习的基础。此外，
18、各种网络之间也存在密切的联系，这使得对复杂网络的分析变得更加困难。例如，电力网络的故障可能会导致Internet流量变慢、金融机构关闭、运输系统失去控制等一系列不同网络之间的连锁反应。2.3复杂网络的区分根据节点度的分布情况，可以将复杂网络分为指数网络和无尺度网络两大类。指数网络中的节点是同质的，它们的度大致相同，绝大部节点的度都位于网络节点平均度附近，网络节点度分布随度数的增加呈指数衰减，使得网络中不存在度数特别大的节点，最经典的两种指数网络是ER随机图模型和小世界网络模型。随机图与小世界网络的主要区别是前者的簇系数小，而后者的簇系数大。目前，把具有较小平均路径长度和较大簇系数的网络统称为小
19、世界网络，这一说法己得到学术界的公认。无尺度网络中的节点是异质的，其节点度服从幂律分布。最著名的无尺度网络模型是1999年Barabasi和Albert建立的无尺度网络模型模型3。在无尺度网络中，大部分节点只与少数几个其它节点连接，但网络中存在为数不多的度数特别大的节点，称为集散节点或节点，它对无尺度网络的特性起着主导和支配作用。从生成方式上可将复杂网络分成随机性网络和确定性网络。顾名思义，随机网络的生成是随机的，尽管生成规则相同，每次在电脑上模拟生成的网络却存在差异性确定性网络的生成规则是确定的，其结构特性可以精确求解。从边的方向性上可将网络分为无向网络和有向网络，无向网络的边不存在方向性，
20、有向网络的边却有方向。从边有无权值可将网络分为加权网络和0-1网络。2.4复杂网络的研究意义复杂网络，特别是小世界网络和无尺度网络刚一提出，就呈现出广阔的应用前景，其应用领域涉及工程技术、社会、政治、医药、经济、管理等不同方面4。在过去几年里，不同领域的研究者发现，包括万维网、细胞代谢系统、好莱坞的演员网络在内的许多现实网络，都是无尺度网络，它们由少数几个具有众多连结的节点所支配，这些重要节点通常称为集散节点。无尺度网络对意外故障具有惊人的承受力，但面对协同式攻击时则很脆弱。这些新发现极大地改变了人们对复杂外部世界的认识，让人们认识到了以前的理论尚未涉及的问题各种复杂系统具有相同的严格结构，都
21、受制于某些基本的法则，这些法则似乎可同等地适用于细胞、计算机、语言和社会。认识这些法则，可以将其应用到不同领域，帮助人们解决一系列重要问题。首先，复杂网络理论可以用于保护许多现实系统的正常运行。因特网、电力网、航空网、万维网、电子邮件网、食物链网等网络与我们的生活息息相关，人们对这些网络的依赖程度日益增强，凸现了一个广受关注的问题，这些网络到底有多可靠呢？2000年，爱虫病毒侵犯了英国议会的电子邮件系统，导致该系统瘫痪；2003年，美加电网的大崩溃事故让纽约人感到惶恐不安当前，人类赖以生存的生态系统不断遭到破坏己经危及到人类的生存环境，等等。从这些现象可以自然地提出下面的问题计算机病毒如何在万
22、维网上传播而导致流行病毒如何通过电子邮件传播，人们如何控制病毒传播？面对黑客的攻击，应该采取何种对策？怎样设计出承受意外故障较强的网络如电力网、航空网？怎样保持当前不断恶化的生态系统的平衡？这些问题的解决都与复杂网络的研究有关，开展好复杂网络稳定性的研究，对于互联网、电力网、航空网等技术网络的设计保护及基础设施网络的保护具有重要的意义，也可以有效地防止黑客侵入互联网、阻止病毒在万维网上传播蔓延。 复杂网络在社会领域也有广阔的应用。传染病如艾滋病、非典、禽流感等对人类的威胁很大艾滋病让人们不寒而栗年的非典对于宏观经济和人类的生命安全都产生了巨大的负面影响目前，禽流感也己成为世界关注的一个焦点。那
23、么在特定的社会网络中，传染病如何通过接触关系传播而导致流行呢？决策者如何控制这些疾病，将损失降到最低限度呢这些问题或许可以从复杂网络那里寻找答案。最近几年，科学家们考虑了不同现实系统的主要特征，提出了许多有针对性的疾病免疫方法晰一，为疾病的预测、预防和免疫提供了科学的方案。譬如，用复杂网络理论可以很好地预测非典爆发的多样性、了解疾病传播的动态性，为决策者控制流行病蔓延、改善公共卫生提供有效的手段。复杂网络在经济、管理领域也有着重要的实际意义5。利用复杂网络理论了解公司、产业与经济之间的连结方式，有助于监控和预防大规模的经济衰退。在管理领域，决策对经济的发展起着关键性的作用，同一个人可以在多个组
24、织内兼任董事。建立公司董事网，使得分析决策的动态性成为可能。经济网络恰好刻画了经济系统中微观个体之间存在相互作用的关系结构，这种关系可以是经济个体之间的信息交流、商品或股票交易、投资关系、信用关系或者隶属控制关系等等。1999年，Barabsi与Albert作出了对复杂网络里程碑式的研究，他们揭示了许多现实网络的连接具有无标度性的这个引人注目的结果。受这一研究结果的激励，人们开始关注经济与经济网络的结构，开展了许多关于经济与金融系统网络结构的实证研究。结果显示：在经济的多个方面人们观测到了经济网络具有无标度性和小世界等性质。3复杂网络的分类3.1规则网络 在很长一段里，人们认为真实系统各因素之
25、间的关系可以用一些规则网络表示，如一维链、二维平面上的欧几里德格网等。用得最多的规则网络是由N个节点组成的环状网络，网络中每个节点只与它最近的K个节点连接。在规则网络中，每个节点具有相同的度和簇系数。节点的度分布为函数，即。节点簇系数为（d为网络维数），集聚程度较高6。在一个全局耦合网络中，任意两个点之间都有边直接相连（图3.1）。在具有相同节点数的所有网络中，全局耦合网络具有最小的平均路径长度L=1和最大的聚类系数C=1。图3.1 规则网络3.2随机图 与完全规则网络相反的是完全随机网络，其中一个典型的模型是ER随机图模型。ER随即图的性质与概率之间的关系，采用以下定义：如果当时产生一个具有
26、性质Q和ER随机图的概率为1，那么就称几乎每一个ER随机图都具有性质ER随机图的节点度服从泊松分布，它具有较小的平均路径长度和较小的簇系数。ER模型提出后，从20世纪50年代末到90年代末的近四十年里，无明确设计原则的大规模网络主要用这种简单而易于被多数人接受的随机图的拓扑结构来描述，即认为大规模网络的形成过程中，节点间的连接是完全随机的。期间，一些数学家对随机图进行了非常好的研究，通过严格的数学证明，得到了许多近似和精确的结果。ER模型的思想支配人们研究复杂网络长达四十年之久，直到最近几年，由于计算机数据处理和运算能力的飞速发展，科学家们发现大量的现实网络不是完全随机的网络，而是具有其他统计
27、特征的网络7。3.3小世界网络模型 实证研究表明，许多现实网络特别是社会网络都表现出集群现象，由此引发人们对小世界网络的研究。最早的小世界网络模型是Watts和Strogatz在1998年提出的网络模型（WS模型），该模型由一个具有N个节点的环开始，环上每一个节点与两侧各有条边相连，然后对每条边以概率p随机进行重连自我连接和重边除外，这些重连的边叫“长程连接”，长程连接大大地减小了网络的平均路径长度，而对网络的簇系数影响较小。WS模型的建立和生成有其深刻的社会根源，因为在社会系统中，大多数人直接和邻居、同事相识，但个别人也有远方甚至国外的朋友。作为从完全规则网络向完全随机图的过渡，Watts和
28、Strogtz于1998年引入了一个有趣的小世界网络模型，称为WS小世界模型。在该模型中，对应于完全规则网络，则对应于完全随机网络，通过调节的值就可以控制从完全规则网络到完全随机网络的过渡（图3.2）8。图3.2 小世界网络3.4无标度网络模型 ER模型和WS模型的度分布与许多现实网络都不相符，用它们来描述这些现实网络，具有很大的局限性，因此科学家们只好寻求另一种模型，来更好地描述这些现实网络。1999年，Barabsi和Albert通过追踪万维网的动态演化过程，发现了许多复杂网络具有大规模的高度自组织特性，即多数复杂网络的节点度服从幂律分布，并把具有幂律度分布的网络称为无尺度网络9。Bara
29、bsi认为，增长和择优连接是无尺度网络形成的两种必不可少的机制，这一观点已被学术界普遍接受。 最原始的无尺度网络模型称为BA模型10，它是第一个随机的无尺度网络模型。在BA模型生成的初始时刻，假定系统中己有少量节点，在以后的每一个时间间隔中，新增一个节点，并与网络中己经存在一定数目的不同节点进行连接。当在网络中选择节点与新增节点连接时，假设被选择的节点与新节点连接的概率和被选节点的度成正比，人们将这种连接称为择优连接。BA网络最终演化成标度不变状态，即节点度服从度指数等于3的幂律分布。BA模型的平均路径长度很小，簇系数也很小，但比同规模随机图的簇系数要大，不过当网络趋于无穷大时，这两种网络的簇
30、系数均近似为零。ER随机图和WS小世界模型的一个共同特征就是网络的连接度分布可近似用Poisson分布表示，该分布在度平均值k处有个峰值，然后呈指数快速衰减。这类网络的节点的连接度没有明显的特征长度，具有增长特性和优先链接特性1112。BA网络的度分布函数可近似描述13（图3.3）。图3.3 无标度网络4杭州公交网络的建立4.1公交网络模型城市公交系统是城市交通运输系统的重要组成部分。城市公交系统规划的好坏直接影响着整个城市交通运输系统的交通状况，因此，公交网络模型是整个公交网络设计的基础，模型的好坏直接影响网络设计的效果。关于公交客流的分配问题，国外有大量的文献和研究成果。其中最为典型的理论
31、是80年代提出的出行略理论。出行策略理论不仅抓住了乘客出行的特点，而且使得已有的适用于机动车的平衡分配模型，通过改进而适用于公交网络。基于出行策略理论的典型分配模型是Spiess 和Florian（1984、1989）提出的适用于非拥挤公交网络的客流分配模型。针对传统网络表示方法的不足， Pallottino 在1988年引入了超级路径的概念。超级路径理论的引入再次推动了公交客流分配技术的发展。基于超级路径和策略优化理论的非平衡分配模型的最新研究成果是Nguyen提出的基于有效超级路径的Logit分配模型，Kikuchi等提出了应用模糊逻辑设计公共交通网络。Pattnaik等提出了运用遗传算法
32、设计公交线网。国内研究现状早在80年代初期，张启人等就在长沙市对公交线网的优化问题进行了研究，他们提出了以直达乘客量最大为优化目标，以线路长度、线路重复系数等为约束条件的公交线网优化模型。该模型在长沙得到了较好的应用。张启人等还提出了运用层次分析法（AHP）构造公共交通大系统的理论和方法。刘清等提出了基于人工智能理论的广义A*算法。广义A*算法，以客流总交通时间、客流直达率等为目标，确立估计函数表达式，采用启发式搜索技术，从每对端点搜索出满足有关约束条件的备选线路，然后以此为基础按二进制理论组合成若干优化网络比较而定。林柏梁等基于组合优化的角度，提出了公交网络优化设计的非线性0-1规划模型，以
33、乘客的出行时间和实现公交网络的资金投入为目标函数，在满足车站容量限制的条件下，最小化目标函数，以获得公交线路的优化决策。王志栋提出了以乘客总出行时间最小、客流直达率最高、线网覆盖率最高、线路重复系数最低、公交经济效益最高为目标，以路网、线路长度、线路非直线系数、线路最大客流量限制、道路流量限制、站点客流量限制和换乘次数为约束条件的公交网络优化模型。针对垂直交叉路段与笔直路段，分别提出了城市公共汽车停靠点选址的离散型模型和连续型模型，并给出了相应的算法和软件。在公交线网站点优化技术领域比较有新意的是唐利民等通过对上海市公交问题的分析，提出的FLAPT模型，该模型按照一定的标准将上海市划分成23个
34、层次，运用蛙跳式转移和渗透式转移的方法，对选定的梯度中心和区域进行布线，并以客流直达率为优化目标，进行网络布局优化。计算结果表明，运用FLAPT模型能明显缩短乘客出行时间。学者四兵锋等在城市道路交通均衡配流模型的基础上，探讨公交网络的均衡原则，提出一种较为简单的城市公共交通网络描述方法，并给出公交网络配流问题的均衡模型及求解算法。夏志浩等把由路段交通量推算道路网中车辆出行O-D分布的方法移植到公交系统，根据各线路各车站调查的上下车人数推算公交客流的O-D分布，成功地应用于成都市的公交客流O-D推算。曾小明等对影响公共交通系统服务质量的要素进行了研究，应用模糊数学方法，给出了评价公共交通服务质量
35、的模糊评定法，用它对佛山市城市公共交通服务质量进行综合评价。孙芙灵对公交调度优化中的发车间隔问题进行了研究，通过研究得到控制发车间隔的四个目标是：根据乘客需求确定一个可供选择的发车间隔；当车辆供给受到约束时，相应地改变发车间隔；在相邻的时间段使用平滑法调节发车间隔；在一个发车时刻表中综合利用各种间隔设置法。在实践中最常用的公交客流需求预测模型有三种：即增长率法、概率模型法、重力模型法。（1）增长率法增长率法是在考虑各小区发生量、吸引量的增长率的基础上，用现状O-D表来直接推算未来的O-D表。该法基于两点基本假设：在预测年以内城市交通运输系统没有明显的变化和区间的出行与路网的改变相对独立。它又分
36、为均匀增长率模型，平均增长率模型等。（2）概率分布模型法概率分布模型是将小区的发生量以一定的概率分布到吸引小区的方法。这是一种以出行个体效用最大为目标的非集合优化模型，从理论上讲是一种更为精确的方法，但在实际应用上，这种模型结构复杂，需要的样本容量很大，难于求解和标定。（3）重力模型法重力模型引用了牛顿万有引力定律来描述城市居民的出行行为，是国内交通规划中使用最广泛的模型。此法综合考虑了影响出行分布的出行空间、时间阻碍因素，它的基本假设为：交通小区i 到交通小区j 的出行分布量与小区i 的出行分布量为标准。4.2杭州公交网络数据描述4.2.1数据描述本文通过对杭州公交网络实地调查取样，在杭州1
37、000多条公交线路中进行数据统计分析，把数据整理绘制成表格形式，对统计出来的每条线路的各个站点以不同的四位数字；在有序的情况下替代各个站点，然后把数据加工整理，在这样的基础上用每特来不进行编程，把整理的数据进行处理，最后绘制出图形，以用来进行研究分析。本文在整理的数据中选出十五个车次的部分数据做为样本，以供参考，如下表（4.1）。表4.1 15条公交线路数据线路名称一二三四五六1/K110011002100310041005100610/K1010161002100310041005100611/K1110301031103210331034103512/K121049105010511052
38、1053105413/K1310701071107210731074107514/K1410841085108610871088108915/K15109410951096109710981099151/K15111111112111311141115111618/K1811311132113310901134113519/K1911401141114211431144114520/K2011541155115611571158107021/K2110301167116811691163113522/K2211821183118411441145118523/K2311791041104011
39、771194119424/K24119911181183118211751176 4.2.2三地最优路线路线根据实地考察和收集的信息。结合杭州市区的实际情况，我们如下表下表列出了3个城市在Space P和Space L方法中的平均路径长度和聚类系数从表中可以看出在Space P中，三地的平均路径长度，即两站点之间的平均最短路径长度都介于2.6-3.1之间。因为Space P定义为：两个站点之间若有直达交通线路，那么就有连边，所以平均通过2次(北京和杭州)或3次(上海)换乘就可以到达目的地。如下图所示，S1和S4之间的为3，那么从S1到S4只要换乘2次即可(在S2站点从L1换到L2，再在S3站点
40、换另外，聚类系数也都在0.7以上，这说明整个交通网络的连通性好，集团化程度高。综合考虑和可知，3个城市的公交网络都具有明显的小世界特性。在Space L中，三地的介于10-16间，比Space P中的大的多，同时C也小得多。这是因为在Space L中，只有当两个站点在同一条线路上相邻才有连边。如某一条线路的始发站S1和终点站S2，在Space P中，它们之间有连边，L为1；在Space L中，它们之间却没有连边，中间要经过很多站点，而不同线路上的站点之间往往存在更多的站点。根据上面的数据可知，这3个城市的公交网络规模都很大，京沪杭平均每条公交线路分别有27.940， 19.867， 17.49
41、7个站点。所以，在Space L中，3个城市的公交网络平均距离都很小，为平均最短路长度，如图4.1所示。 图4.1 六大城市各参数数据统计 5公交网络无标度性5.1公交网络的无标度分布5.1.1阈值的选用相关系数。在公交系统众多的车次之中，有些车次间的联系很密集。在公交网络中，它们之间就没有连通的边。为了简化网络图，我们将的阈值设定为0.89。在此范围类，模拟的结果很符合现实的情况。5.1.2公交网络站点的度分布通过设定的阈值，可以得到公交网络系统的网络图。由于网络中的节点太多，在图上显示不太清楚，所以我们直接用表格将每个车次站点显示出来。我们采用以下matlab程序来实现各个站点的计算。%
42、采用的相关系数的阈值此时为0.89for i=1:length(A) for j=1:length(A) if abs(C(i,j)=0.89 D(i,j)=1; else D(i,j)=0; end endendlineDsum=(sum(sum(D)-1265)/(1265*2);% 采用的相关系数的阈值此时为0.89%下面求度分布for i=1:length(A) Degree_line(i)=sum(D(i,:)-1;enddegree_min=min(Degree_line);%最少的度数degree_max=max(Degree_line);%最多的度数for j=1:1:degr
43、ee_max-degree_min degree_distribution(j)=0; for i=1:length(A) if Degree_line(i)=(j+degree_min) degree_distribution(j)=degree_distribution(j)+1; end endendk=1:degree_max-degree_min;loglog(k,degree_distribution/1265)图5.1 matlab程序来实现各个站点的计算有向网络中一个节点的度分为出度和入度。直观上看，一个节点的度越大就意味着这个节点在一定意义上越重要。完全随机网络的度分布近似为
44、Poisson分布，其图形在远离峰值处呈指数下降。这意味这当k时，度为的节点实际上是不存在的。因此，这类网络也称为均匀网络。研究表明，许多实际网络的度分布明显地不同于Poisson分布。幂律分布曲线比Poisson指数分布曲线下降要缓慢得多。幂律分布也称为无标度分布，具有幂律度分布的网络也称为无标度网络。我们研究的公交市场的复杂网络的度分布也不同于Poisson分布。 通过运算，我们可以看出站点间度数最少的为0，即该站点时间变动不影响其它车次的，现实中这车次是很少存在的。结合杭州市实际公交网络数据建立了公交停靠站点网络模型和公交换乘网络模型。这两个模型反映了公交网络的自然拓扑特征以及公交网络的
45、可达性。 其次，本文在两个公交网络模型上进行了复杂网络的特性分析，针对公交停靠站点网络，通过其上的复杂网络基本几何特征量，验证了其上的小世界特性及无标度特征。这两个特性可能给出促进交通科学与技术发展的新的方案与模式，该分布大致符合无标度网络的度分布。目前，国际上已经形成研究复杂性问题和复杂网络的研究热潮。而复杂网络是研究复杂性问题的有力工具。自然界中存在着大量的复杂系统，如Internet网、计算机网络、神经系统、社会关系网络等等，都可以通过复杂网络进行描述。通过研究这些复杂网络的内在机制和演化规律，从而找到网络上的复杂行为与网络结构的关系，增加对复杂网络系统的自然规律的认识。 度分布是复杂网
46、络问题中研究较多的一个方向。而且在网络非常重要。5.1.3 BA网络模拟 BA模型的两个重要特性：1、增长特性：即网络的规模是不断扩大的。例如每个月都会有大量的新的科研文章发表。2、有线连接特性：即新的节点更倾向于那些具有较高连接度的大节点相连接。这种现象也称为“马太效应”。例如新发表的文章更倾向于引用一些已被广泛引用的重要文献。BA无标度模型构造算法：1、增长：从一个具有个节点的网络开始，每次引入一个新的节点，并且连到个已存在的节点上，这里。2、优先连接：一个新节点与一个已经存在的节点相连接的概率与节点的度、节点的度之间满足如下关系： (5.2) 在经过步后，这种算法产生一个有个节点、条边的网络。图5.2显示了当时的BA网络的演化过程。初始网络有两个节点，每次新增加的一个节点优先连接机制与网络中已存在的两个节点相连。图5.2 BA网络演化过程图%下面得到度分布与双对数坐标下的度分布。 并计算其度指数。a0size=length(degree_distribution);Deg=1:1:a0size;Num=degree_distribution;Numsum=sum(Num);Num=Nu
