《杭电毕业论文模板》由会员分享，可在线阅读，更多相关《杭电毕业论文模板（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、越来越强大的计算设备和迅猛发展的Internet，使得人们开始能够收集和处理规模巨大且种类不同的实际网络数据。2、学科之间的相互交叉使得研究人员可以广泛比较各种不同类型的网络数据，从而揭示复杂网络的共性。3、以还原论和整体论相结合为重要特色的复杂性科学的兴起，也促使人们开始从整体上研究网络的结构和性能之间的关系。著名的物理学家霍金认为二十一世纪是复杂性的世纪。复杂网络的研究是复杂性理论研究的一部分，作为研究复杂性科学和复杂系统的有力工具，复杂网络为研究复杂性提供了全新的视角。复杂网络借助于图论和
