本科毕业论文

《本科毕业论文》由会员分享，可在线阅读，更多相关《本科毕业论文（26页珍藏版）》请在装配图网上搜索。

1、本科毕业论文（2009届）题 目杭州公交网络的无标度性实证研究学 院理学院专 业数学与应用数学班 级学 号学生姓名指导教师完成日期杭州电子科技大学本科毕业论文杭州电子科技大学本科毕业论文摘 要复杂网络的无标度性是指网络拓扑结构中边连接的度分布服从幂律分布，而该分布具有标度不变性；其小世界特性是指其网络平均最短路长度与网络规模的对数成比例，且网络聚类系数远大于随机图网络的聚类系数。复杂网络的拓扑特性分析，特别是验证网络的无标度性与小世界特性，对于网络的关键节点发现，网络的抗毁性，网络上信息传播、网络导航等都具有十分重要的理论与现实意义。复杂网络是最近几年新兴的一个研究热点，科学家们发现越来越多的

2、实际网络具有复杂网络的特性，并对复杂网络的模型、容错与抗攻击及其动力学特性做了很多研究。交通网络在实际的生活中有着重要的作用，交通网络的设计、规划与实现对人们出行有着重要的影响。公交网络是交通网络中的重要的组成部分。本文首先介绍了复杂网络的概念及其研究进展，网络演化模型的研究方法，并通过掌握复杂网络获得度分布的三种方法，即速率、主方程、连续理论方法等，分析无标度性与小世界特性的内在形成机理。然后获取杭州公交网络的实际数据，获得网络的度分布，聚类系数，平均最短路长度等拓扑指标，验证网络的无标度性与小世界特性，从而可以根据现有的研究成果针对该网络给出新增公交线路或现有线路改造的合理建议。关键词：无

3、标度网络；小世界特性；聚集性；复杂网络杭州电子科技大学本科毕业论文ABSTRACT 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 p

4、roportion to the network size, and the network 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

5、the discovery of network hub nodes, network 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

6、to the model of complex networks, error toleration, 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 transpor

7、t network.Firstly, the concept of complex 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 prese

8、nted. The inherent evolution mechanism of 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 net

9、works and small world properties to this 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复杂网络的

10、发展22.2复杂网络的特性32.3复杂网络的区分32.4复杂网络的研究意义43复杂网络的分类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以及新陈代谢等的连接度分布函数具有幂律形式，而且这类网络的节点的连接度没有明显的特

11、征长度，故称为无标度网络1。Barabasi和Albert提出的无标度网络模型被称为BA模型。BA模型的两个重要特性是：增长特性和有线连接特性。它表明网络的规模不断扩大，新的链接更倾向于那些具有较高连接度的“大”节点相链接，这种现象也叫“马太效应”2。随着网络的不断发展，公交网络的不断普及和完善，现实中无标度网络的指的是除了小世界效应外，大量实际网络还存在着另一个突出的结构特征幂律度分布，称其为无标度网络。无标度网络的特点是分布的自相似结构及其高度弥散性，在不相关的无标度性网络必然是小世界的(事实上，比小世界更小)。尽管如此，无标度网络相关度分布可能并非如此。我们描述一个产生具有高对称性但非小

12、世界的无标度性网络模型的演化机理。在公交网络中引入了复杂网络中的基本静态几何量，本文结合杭州市公交网络的实际数据，验证了杭州市公交网络的小世界特性和无标度特征，并在此基础上分析研究了公交网络的有效性和脆弱性3-4。 首先，根据公交网络的特性，结合杭州市实际公交网络数据建立了杭州市公交网络模型和杭州市公交换乘网络模型。目前，国际上已经形成研究复杂性问题和复杂网络的研究热潮。而复杂网络是研究复杂性问题的有力工具。自然界中存在着大量的复杂系统，如Internet网、计算机网络、神经系统、社会关系网络等等，都可以通过复杂网络进行描述。通过研究这些复杂网络的内在机制和演化规律，从而找到网络上的复杂行为与

13、网络结构的关系，增加对复杂网络系统的自然规律的认识。 度分布是复杂网络问题中研究较多的一个方向，本文主要研究了复杂网络中匀速增长的非线性择优连接的BA模型度的分布。222复杂网络的介绍2.1复杂网络的发展万维网上从一个页面到另一个页面平均需要点击多少次鼠标？层出不穷的计算机病毒是如何在互联网上传播的？各种传染病是如何在人类和动物中流行的？全球或地区性的金融危机是如何发生的？大城市的交通阻塞问题是如何引起的？为什么大脑能够具有思维的功能？这些问题看上去各不相同，但每个问题都涉及很复杂的网络，包括WWW、Internet、社会关系网、经济网络、电力网络、交通网络、经济网络等等。由于现实世界网络的规

14、模大，节点间相互作用复杂，其拓扑结构基本上未知或未曾探索。两百多年来，人们对描述真实系统拓扑结构的研究经历了三个阶段。在最初的一百多年里，科学家们认为真实系统要素之间的关系可以用一些规则的结构表示，例如二维平面上的欧几里德格网从20世纪50年代末到90年代末，无明确设计原则的大规模网络主要用简单而易于被多数人接受的随机网络来描述，随机图的思想主宰复杂网络研究达四十年之久直到最近几年，科学家们发现大量的真实网络既不是规则网络，也不是随机网络，而是具有与前两者皆不同的统计特性的网络，其中最有影响的是小世界网络和无尺度网络。这两种网络的发现，掀起了复杂网络的研究热潮。1959-1960年，匈牙利数学

15、家艾尔德（P.Erdos）和莱利（A.Renyi）建立了随机图（ER模型），被公认为是数学上开创了复杂网络理论的系统性研究。20世纪60年代美国哈弗大学的社会心理学家Stanley Milgram通过一些社会调查后给出的推断是：地球上任意两个人之间的平均距离是6。也就是说，平均中间只要通过5个人，你就能与地球上的任何一个角落的任何一个人发生联系。1998年，康奈尔大学的社会学家Watts和Strogatz 提出了小世界网络（WS模型）5。1999年，圣母大学的物理学家Barabsi和Albert提出了无尺度网络（BA模型）6。复杂网络研究的快速发展的主要原因包括：1、越来越强大的计算设备和迅猛

16、发展的Internet，使得人们开始能够收集和处理规模巨大且种类不同的实际网络数据。2、学科之间的相互交叉使得研究人员可以广泛比较各种不同类型的网络数据，从而揭示复杂网络的共性。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作出了对复杂网络里程碑式的研究，他们揭示了许多现实网络的连接具有无标度性的这个引人注目的结果。受这一研究结果的激励，人们开始关注经济与经济网络的结构，开展了许多关于经济与金融系统网络结构的实证研究。结果显示：在经济的多个方面人们观测到了经济网络具有无标度性

25、和小世界等性质。3复杂网络的分类3.1规则网络 在很长一段里，人们认为真实系统各因素之间的关系可以用一些规则网络表示，如一维链、二维平面上的欧几里德格网等。用得最多的规则网络是由N个节点组成的环状网络，网络中每个节点只与它最近的K个节点连接。在规则网络中，每个节点具有相同的度和簇系数。节点的度分布为函数，即。节点簇系数为（d为网络维数），集聚程度较高6。在一个全局耦合网络中，任意两个点之间都有边直接相连（图3.1）。在具有相同节点数的所有网络中，全局耦合网络具有最小的平均路径长度L=1和最大的聚类系数C=1。图3.1 规则网络3.2随机图 与完全规则网络相反的是完全随机网络，其中一个典型的模型

26、是ER随机图模型。ER随即图的性质与概率之间的关系，采用以下定义：如果当时产生一个具有性质Q和ER随机图的概率为1，那么就称几乎每一个ER随机图都具有性质ER随机图的节点度服从泊松分布，它具有较小的平均路径长度和较小的簇系数。ER模型提出后，从20世纪50年代末到90年代末的近四十年里，无明确设计原则的大规模网络主要用这种简单而易于被多数人接受的随机图的拓扑结构来描述，即认为大规模网络的形成过程中，节点间的连接是完全随机的。期间，一些数学家对随机图进行了非常好的研究，通过严格的数学证明，得到了许多近似和精确的结果。ER模型的思想支配人们研究复杂网络长达四十年之久，直到最近几年，由于计算机数据处

27、理和运算能力的飞速发展，科学家们发现大量的现实网络不是完全随机的网络，而是具有其他统计特征的网络7。3.3小世界网络模型 实证研究表明，许多现实网络特别是社会网络都表现出集群现象，由此引发人们对小世界网络的研究。最早的小世界网络模型是Watts和Strogatz在1998年提出的网络模型（WS模型），该模型由一个具有N个节点的环开始，环上每一个节点与两侧各有条边相连，然后对每条边以概率p随机进行重连自我连接和重边除外，这些重连的边叫“长程连接”，长程连接大大地减小了网络的平均路径长度，而对网络的簇系数影响较小。WS模型的建立和生成有其深刻的社会根源，因为在社会系统中，大多数人直接和邻居、同事相

28、识，但个别人也有远方甚至国外的朋友。作为从完全规则网络向完全随机图的过渡，Watts和Strogtz于1998年引入了一个有趣的小世界网络模型，称为WS小世界模型。在该模型中，对应于完全规则网络，则对应于完全随机网络，通过调节的值就可以控制从完全规则网络到完全随机网络的过渡（图3.2）8。图3.2 小世界网络3.4无标度网络模型 ER模型和WS模型的度分布与许多现实网络都不相符，用它们来描述这些现实网络，具有很大的局限性，因此科学家们只好寻求另一种模型，来更好地描述这些现实网络。1999年，Barabsi和Albert通过追踪万维网的动态演化过程，发现了许多复杂网络具有大规模的高度自组织特性，

29、即多数复杂网络的节点度服从幂律分布，并把具有幂律度分布的网络称为无尺度网络9。Barabsi认为，增长和择优连接是无尺度网络形成的两种必不可少的机制，这一观点已被学术界普遍接受。 最原始的无尺度网络模型称为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分配模型，K

32、ikuchi等提出了应用模糊逻辑设计公共交通网络。Pattnaik等提出了运用遗传算法设计公交线网。国内研究现状早在80年代初期，张启人等就在长沙市对公交线网的优化问题进行了研究，他们提出了以直达乘客量最大为优化目标，以线路长度、线路重复系数等为约束条件的公交线网优化模型。该模型在长沙得到了较好的应用。张启人等还提出了运用层次分析法（AHP）构造公共交通大系统的理论和方法。刘清等提出了基于人工智能理论的广义A*算法。广义A*算法，以客流总交通时间、客流直达率等为目标，确立估计函数表达式，采用启发式搜索技术，从每对端点搜索出满足有关约束条件的备选线路，然后以此为基础按二进制理论组合成若干优化网络

33、比较而定。林柏梁等基于组合优化的角度，提出了公交网络优化设计的非线性0-1规划模型，以乘客的出行时间和实现公交网络的资金投入为目标函数，在满足车站容量限制的条件下，最小化目标函数，以获得公交线路的优化决策。王志栋提出了以乘客总出行时间最小、客流直达率最高、线网覆盖率最高、线路重复系数最低、公交经济效益最高为目标，以路网、线路长度、线路非直线系数、线路最大客流量限制、道路流量限制、站点客流量限制和换乘次数为约束条件的公交网络优化模型。针对垂直交叉路段与笔直路段，分别提出了城市公共汽车停靠点选址的离散型模型和连续型模型，并给出了相应的算法和软件。在公交线网站点优化技术领域比较有新意的是唐利民等通过

34、对上海市公交问题的分析，提出的FLAPT模型，该模型按照一定的标准将上海市划分成23个层次，运用蛙跳式转移和渗透式转移的方法，对选定的梯度中心和区域进行布线，并以客流直达率为优化目标，进行网络布局优化。计算结果表明，运用FLAPT模型能明显缩短乘客出行时间。学者四兵锋等在城市道路交通均衡配流模型的基础上，探讨公交网络的均衡原则，提出一种较为简单的城市公共交通网络描述方法，并给出公交网络配流问题的均衡模型及求解算法。夏志浩等把由路段交通量推算道路网中车辆出行O-D分布的方法移植到公交系统，根据各线路各车站调查的上下车人数推算公交客流的O-D分布，成功地应用于成都市的公交客流O-D推算。曾小明等对

35、影响公共交通系统服务质量的要素进行了研究，应用模糊数学方法，给出了评价公共交通服务质量的模糊评定法，用它对佛山市城市公共交通服务质量进行综合评价。孙芙灵对公交调度优化中的发车间隔问题进行了研究，通过研究得到控制发车间隔的四个目标是：根据乘客需求确定一个可供选择的发车间隔；当车辆供给受到约束时，相应地改变发车间隔；在相邻的时间段使用平滑法调节发车间隔；在一个发车时刻表中综合利用各种间隔设置法。在实践中最常用的公交客流需求预测模型有三种：即增长率法、概率模型法、重力模型法。（1）增长率法增长率法是在考虑各小区发生量、吸引量的增长率的基础上，用现状O-D表来直接推算未来的O-D表。该法基于两点基本假

36、设：在预测年以内城市交通运输系统没有明显的变化和区间的出行与路网的改变相对独立。它又分为均匀增长率模型，平均增长率模型等。（2）概率分布模型法概率分布模型是将小区的发生量以一定的概率分布到吸引小区的方法。这是一种以出行个体效用最大为目标的非集合优化模型，从理论上讲是一种更为精确的方法，但在实际应用上，这种模型结构复杂，需要的样本容量很大，难于求解和标定。（3）重力模型法重力模型引用了牛顿万有引力定律来描述城市居民的出行行为，是国内交通规划中使用最广泛的模型。此法综合考虑了影响出行分布的出行空间、时间阻碍因素，它的基本假设为：交通小区i 到交通小区j 的出行分布量与小区i 的出行分布量为标准。4

37、.2杭州公交网络数据描述4.2.1数据描述本文通过对杭州公交网络实地调查取样，在杭州1000多条公交线路中进行数据统计分析，把数据整理绘制成表格形式，对统计出来的每条线路的各个站点以不同的四位数字；在有序的情况下替代各个站点，然后把数据加工整理，在这样的基础上用每特来不进行编程，把整理的数据进行处理，最后绘制出图形，以用来进行研究分析。本文在整理的数据中选出十五个车次的部分数据做为样本，以供参考，如下表（4.1）。表4.1 15条公交线路数据线路名称一二三四五六1/K110011002100310041005100610/K1010161002100310041005100611/K11103

38、01031103210331034103512/K1210491050105110521053105413/K1310701071107210731074107514/K1410841085108610871088108915/K15109410951096109710981099151/K15111111112111311141115111618/K1811311132113310901134113519/K1911401141114211431144114520/K2011541155115611571158107021/K2110301167116811691163113522/K221

39、1821183118411441145118523/K2311791041104011771194119424/K24119911181183118211751176 4.2.2三地最优路线路线根据实地考察和收集的信息。结合杭州市区的实际情况，我们如下表下表列出了3个城市在Space P和Space L方法中的平均路径长度和聚类系数从表中可以看出在Space P中，三地的平均路径长度，即两站点之间的平均最短路径长度都介于2.6-3.1之间。因为Space P定义为：两个站点之间若有直达交通线路，那么就有连边，所以平均通过2次(北京和杭州)或3次(上海)换乘就可以到达目的地。如下图所示，S1和S

40、4之间的为3，那么从S1到S4只要换乘2次即可(在S2站点从L1换到L2，再在S3站点换另外，聚类系数也都在0.7以上，这说明整个交通网络的连通性好，集团化程度高。综合考虑和可知，3个城市的公交网络都具有明显的小世界特性。在Space L中，三地的介于10-16间，比Space P中的大的多，同时C也小得多。这是因为在Space L中，只有当两个站点在同一条线路上相邻才有连边。如某一条线路的始发站S1和终点站S2，在Space P中，它们之间有连边，L为1；在Space L中，它们之间却没有连边，中间要经过很多站点，而不同线路上的站点之间往往存在更多的站点。根据上面的数据可知，这3个城市的公交

41、网络规模都很大，京沪杭平均每条公交线路分别有27.940， 19.867， 17.497个站点。所以，在Space L中，3个城市的公交网络平均距离都很小，为平均最短路长度，如图4.1所示。 图4.1 六大城市各参数数据统计 5公交网络无标度性5.1公交网络的无标度分布5.1.1阈值的选用相关系数。在公交系统众多的车次之中，有些车次间的联系很密集。在公交网络中，它们之间就没有连通的边。为了简化网络图，我们将的阈值设定为0.89。在此范围类，模拟的结果很符合现实的情况。5.1.2公交网络站点的度分布通过设定的阈值，可以得到公交网络系统的网络图。由于网络中的节点太多，在图上显示不太清楚，所以我们直

42、接用表格将每个车次站点显示出来。我们采用以下matlab程序来实现各个站点的计算。% 采用的相关系数的阈值此时为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);%最少的度数degre

43、e_max=max(Degree_line);%最多的度数for j=1:1:degree_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、优先连接：一个新节点与一个已经存在的节点相连接的概率与节点的度

47、、节点的度之间满足如下关系： (5.2) 在经过步后，这种算法产生一个有个节点、条边的网络。图5.2显示了当时的BA网络的演化过程。初始网络有两个节点，每次新增加的一个节点优先连接机制与网络中已存在的两个节点相连。图5.2 BA网络演化过程图%下面得到度分布与双对数坐标下的度分布。 并计算其度指数。a0size=length(degree_distribution);Deg=1:1:a0size;Num=degree_distribution;Numsum=sum(Num);Num=Num/Numsum;figure;loglog(Deg,Num,+);xlabel(连接数（个）);ylabe

48、l(结点数（个）);title(双对数坐标系度分布曲线);hold on;% plot_end=round(length(Deg)*scale); plot_end=12;plot_begin=6;lDeg=log10(Deg(plot_begin:plot_end);lNum=log10(Num(plot_begin:plot_end);pDegree=polyfit(lDeg,lNum,1);pNum=10(pDegree(2)*(Deg).(pDegree(1);loglog(Deg,pNum,k:);pNum=pDegree(1)*lDeg+pDegree(2);%axis(0 100

49、 1 1250);gtext(lambda=,num2str(pDegree(1);legend(度分布曲线,拟和结果);图5.3 BA模型度指数计算大量的实证研究表明，真实网络几乎都具有小世界效应，同时科学家还发现大量真实网络的节点度服从幂率分布，这里某节点的度是指该节点拥有相邻节点的数目，或者说与该节点关联的边的数目。节点度服从幂律分布就是说具有某个特定度的节点数目与这个特定的度之间的关系可以用一个幂函数近似地表示。幂函数曲线是一条下降相对缓慢的曲线，这使得度很大的节点可以在网络中存在。对于随机网络和规则网络，故其平均度可以被看作其节点度的一个特征标度。我们把节点度服从幂律分布的网络叫做无

50、标度网络（scale-free networks），并称这种节点度的幂律分布为网络的无标度特性。1999年，Barabasi 和Albert给出了构造无标度网络的演化模型，他们所用的方法与Price的方法是类似的。Barabasi 和Albert把真实系统通过自组织生成无标度的网络归功于两个主要因素：生长和优先连接，而他们的网络模型（BA网络）正是模拟这两个关键机制设计的。5.2公交网络的聚集性集群即集聚程度(clustering coefficient)的概念，就好比在社会网络中总是存在熟人圈或朋友圈，其中每个成员都认识其他成员。集聚程度的意义是网络集团化的程度；这是一种网络的内聚倾向。连通

51、集团概念反映的是一个大网络中各集聚的小网络分布和相互联系的状况。例如，它可以反映这个朋友圈与另一个朋友圈的相互关系。复杂网络的聚集性反映了当代公交网络在发展过程中的一些问题，以至与通过对其研究更好的来服务于公交网络。 复杂网络的研究，为我们提供了一种复杂性研究的新视角、新方法，并且提供了一种比较的视野。可以在复杂网络研究的旗帜下，对各种复杂网络进行比较、研究和综合概括。现实中的公交网络也是复杂网络的一种演变形式， 类的演化就是在给自己增加着的各种网络的演化。人的存在方式就是技术的存在。人的“此在”就是“已在”的叠加、取代和更新，就是复杂网络未来存在到演化的展开。5.3公交网络平均最短路长度与聚

52、类系数5.3.1 公交系统数据的采集 城市公共交通是城市整体发展中不可缺少的物质条件和基础产业，是解决城市交通拥堵问题和居民出行问题的有效手段。我国公交部门和交通学科研究人员也在公共交通领域内进行了很多研究，如公交线路网优化、客流分配技术、站点规划方法等，并取得了一定成果。为次，我们以杭州公交系统为基础、根据公交网络系统通过调查，取样。采集了一部分杭州公交线路的数据，以用来做为参考。5.3.2 快速公交网路和最短换成线路算法的定义快速公交系统（Bus Rapid Transit）简称BRT，是一种介于快速轨道交通（Rapid Rail Transit，简称RRT）与常规公交（Normal Bu

53、s Transit，简称NBT）之间的新型公共客运系统，是一种大运量交通方式，通常也被人称作“地面上的地铁系统”。它是利用现代化公交技术配合智能交通和运营管理，开辟公交专用道路和建造新式公交车站，实现轨道交通运营服务，达到轻轨服务水准的一种独特的城市客运系统。一个城市进行基础设施建设的核心思想，应该是提高居民生活质量和保护环境并重。发展建设公共交通系统，可以顺应以上两点需要。一个高效、可靠的公共交通系统，通过减少小汽车的使用率、减缓交通拥堵，减少车辆污染物排放，降低能耗，以及大容量地集散乘客， 可以保护环境，节省自然资源，节约居民出行时间，保护公众健康，刺激经济发展，降低对原油的依赖，促进社会

54、平等，维护城市和谐，加强社区凝聚力。最短线路换乘算法说白了就是在任何一个城市里，在到达相同公交站点，希望自己所乘线路为最短路径，所需时间为最少的一种理想乘车途径，它的具体算法如下车最短路经算法：系统首先需要获取各个站点的信息，也就是连接信息了，保存到文件系统中，站点就是图的顶点了，连接信息就是边了一般来说，这里面的图我们应该认为是有向图，因为很多情况下，一个公交线路是：A-B-C-D -E-F-A，这种情况只能采用有向图。具体的算法：实际上乘客不一定要找最短，里面还涉及到换乘次数最少，费用最少等问题，因此，边向量的权值要分多种情况考虑，所以如果真的要开发实用的系统应该给出多种最佳选择，我们以通

55、常意义上的最短路径为例；可以采用教科书上的算法，但是需要注意的是，应该保留经过的边，毕竟结果需要显示出来的。5.3.3 公交网络的相关系数 通过研究公交网络中各种不同线路之间的交叉关联，以真实的公交线路的各个站点数据时间序列计算不同站点之间的交叉关联矩阵。并以站点交叉矩阵的矩阵元作为相应站点之间的相互作用快慢，构造站点之间的加权网络。我们将研究这一公交公司加权网络的连接度分布特征，从而揭示对于实际的公交网络系统价格的波动，不同车次究竟起多大的影响程度，以及他们彼此之间又是如何地相互影响。我们利用前面介绍的公交线路模型对杭州车次几天数据进行处理。我们定义每个车次作为一个点。然后求出更多车次每天的

56、各个站点数据。如下图（5.4）图5.4相关系数分布图5.4结果分析5.4.1外界因素对公交网络的影响 对于公交市场，外部经济环境对公交系统也起着很大的影响。考虑到金融危机，通货膨胀指数，油价和时间等外界因素，为提取公交价格变化中关联的内在性质，必须考虑第公司在时刻线路价格相对于所考虑公交系统所有车次价格在时刻平均值的相对涨落。 对公交系统数据的处理重新计算后，公交网络的度分布数最小，度分布数最大都可以得出。其峰值为7.5左右，比模型修正前的峰值更为符合现实情况。市现实中比较幂律分布表现为一条斜率为幂指数的负数的直线，这一线性关系是判断给定的实例中随机变量是否满足幂律的依据。实际上，幂律分布广泛

57、存在于物理学，地球与行星科学，计算机科学，生物学，生态学。如下图（5.5）图5.5 度分布图5.4.2阈值的调节 在不同的阈值下，计算公交网络站点的度分布情况，其度分布图（图5.6）图5.6 度分布图国际上已经形成研究复杂性问题和复杂网络的研究热潮。而复杂网络是研究复杂性问题的有力工具。自然界中存在着大量的复杂系统，如Internet网、计算机网络、神经系统、社会关系网络等等，都可以通过复杂网络进行描述。通过研究这些复杂网络的内在机制和演化规律，从而找到网络上的复杂行为与网络结构的关系，增加对复杂网络系统的自然规律的认识。度分布是复杂网络问题中研究较多的一个方向。 复杂网络的度分布与其拓扑结构

58、紧密相关。绝大多数复杂网络具有无标度性(Scale free)，其幂律度分布完全由度分布指数所确定。文中全面研究了复杂网络的度分布指数与其拓扑结构、形成原因以及传播动力学之间的关系，获得了下列结论：实际网络的度分布指数不会低于1；度分布指数介于1-2之间的复杂网络中存在数量较多的HUB节点，其边数与节点数之间的关系是非线性的，节点数的增加将导致边数的大幅度增加；度分布指数介于2-3之间的复杂网络中存在一定数量的HUB节点，其边数与节点数之间的关系是线性的，大多数受成本制约的网络属于这种类型;度分布指数大于3的复杂网络近似于均质网络；度分布指数3构成了复杂网络中病毒防治方式的临界点。如果是这种情

59、况，根据步骤3.1产生另一种新的学位，否则不可以作为学位新的节点。第4步。每一个连接新的节点的网络分类。通过应用一个原则，我们连接新的节点，与现有的节点是相同的。如果不存在，我们将它连接到节点 ，其程度是较高或较低是由N = 1决定 。如果失败了，保值增值的N 或者1重复。该算法保证，由新节点一次一个连接到现有的网络 ，由此造成的网络连接，并连接多个不同的边缘接点，两个节点将不会发生这个类型的网。6结论从本文的论述的内容总结可的出， 复杂网络的研究，为我们提供了一种复杂性研究的新视角、新方法，并且提供了一种比较的视野。可以在复杂网络研究的旗帜下，对各种复杂网络进行比较、研究和综合概括。首先，网

60、络的现象涵盖极其广泛，可以对本文所关注的焦点问题公交网络的无标度性更好的分析研究。其次，复杂网络的研究，在大量网络现象的基础上抽象出两种复杂网络：一种即小世界网络，另一种即无标度网络。这两种网络都同时具有两个基本特征：高平均集聚程度、小的最短路径，而无标度网络的度分布又具有幂律分布特征。因此无标度网络的复杂性程度还高于小世界网络的复杂性程度。另外，复杂网络的基本测度性概念也反映了网络内某些个体对其他个体的影响，以及其他个体对这些个体的影响，这种双向的影响是网络分析的重点。如一个顶点的度的概念，一个顶点的度是指与此顶点连接的边的数量。边是什么？边是相互作用的数量反映。那么，一个顶点的度就反映了与

61、这个顶点（个体）相互作用的多寡，关注的重心是相互作用。这次毕业设计对于我来说，既是一次机遇，又是一次挑战。通过这次的毕业设计，我学到了很多东西，通过自己的实践，增强了动手能力。通过对公交网络的市场研究，也使我了解到书本知识和实际应用的差别。在实际应用中遇到很多的问题，这都需要我对问题进行具体的分析，并一步一步地去解决它。致谢在此论文完成之际，我要感谢多年来关心、帮助和支持我的人。首先，我衷心感谢我的导师覃森老师。本论文是在覃老师的精心指导下完成的，论文从选题到撰写，自始自终都得到覃老师的深切关怀和悉心指导。覃老师开阔的视野，渊博的知识，严谨的治学态度，通达的性格以及强烈的事业心，都对我产生了很

62、大的影响，让我受益非浅。在此，我向覃老师表示诚挚的感谢和崇高的敬意！其次，在学习和完成论文的期间，我也得到了杭州电子科技大学理学院各位领导和老师的关怀和帮助，在次表示衷心的感谢！最后，我还要感谢寝室里的同学和我的父母，他们为我营造了良好的氛围，没有他们的支持和鼓励，我可能无法克服各种困难，顺利完成学业。 参考文献1 覃森无标度网络及其应用研究M西安：西北工业大学，2007，1：13-182 戴冠中，王林，覃森复杂系统的Scale-free性及其宏观调控问题J科技导报，2006，(24)5，11-153 郭雷，许晓鸣复杂网络M上海：上海科技教育出版社，20064 汪小帆，李翔，陈关荣，复杂网络理论及其应用M北京：清华大学出版社，2006：12-145 J. Duncan, H. Steven. Collective dynamics of small-world networksJ. Nature, 1998, 33(6684): 440-442.6 A. L. Bar