杭州公交網(wǎng)絡(luò)的無標(biāo)度性實(shí)證研究畢業(yè)論文_第1頁
杭州公交網(wǎng)絡(luò)的無標(biāo)度性實(shí)證研究畢業(yè)論文_第2頁
杭州公交網(wǎng)絡(luò)的無標(biāo)度性實(shí)證研究畢業(yè)論文_第3頁
杭州公交網(wǎng)絡(luò)的無標(biāo)度性實(shí)證研究畢業(yè)論文_第4頁
杭州公交網(wǎng)絡(luò)的無標(biāo)度性實(shí)證研究畢業(yè)論文_第5頁
已閱讀5頁,還剩20頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)

文檔簡介

1、 本科畢業(yè)論文(2009屆)題 目杭州公交網(wǎng)絡(luò)的無標(biāo)度性實(shí)證研究學(xué) 院理學(xué)院專 業(yè)數(shù)學(xué)與應(yīng)用數(shù)學(xué)班 級學(xué) 號學(xué)生姓名指導(dǎo)教師完成日期摘 要復(fù)雜網(wǎng)絡(luò)的無標(biāo)度性是指網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中邊連接的度分布服從冪律分布,而該分布具有標(biāo)度不變性;其小世界特性是指其網(wǎng)絡(luò)平均最短路長度與網(wǎng)絡(luò)規(guī)模的對數(shù)成比例,且網(wǎng)絡(luò)聚類系數(shù)遠(yuǎn)大于隨機(jī)圖網(wǎng)絡(luò)的聚類系數(shù)。復(fù)雜網(wǎng)絡(luò)的拓?fù)涮匦苑治?,特別是驗(yàn)證網(wǎng)絡(luò)的無標(biāo)度性與小世界特性,對于網(wǎng)絡(luò)的關(guān)鍵節(jié)點(diǎn)發(fā)現(xiàn),網(wǎng)絡(luò)的抗毀性,網(wǎng)絡(luò)上信息傳播、網(wǎng)絡(luò)導(dǎo)航等都具有十分重要的理論與現(xiàn)實(shí)意義。復(fù)雜網(wǎng)絡(luò)是最近幾年新興的一個研究熱點(diǎn),科學(xué)家們發(fā)現(xiàn)越來越多的實(shí)際網(wǎng)絡(luò)具有復(fù)雜網(wǎng)絡(luò)的特性,并對復(fù)雜網(wǎng)絡(luò)的模型、容錯與

2、抗攻擊及其動力學(xué)特性做了很多研究。交通網(wǎng)絡(luò)在實(shí)際的生活中有著重要的作用,交通網(wǎng)絡(luò)的設(shè)計、規(guī)劃與實(shí)現(xiàn)對人們出行有著重要的影響。公交網(wǎng)絡(luò)是交通網(wǎng)絡(luò)中的重要的組成部分。本文首先介紹了復(fù)雜網(wǎng)絡(luò)的概念及其研究進(jìn)展,網(wǎng)絡(luò)演化模型的研究方法,并通過掌握復(fù)雜網(wǎng)絡(luò)獲得度分布的三種方法,即速率、主方程、連續(xù)理論方法等,分析無標(biāo)度性與小世界特性的內(nèi)在形成機(jī)理。然后獲取杭州公交網(wǎng)絡(luò)的實(shí)際數(shù)據(jù),獲得網(wǎng)絡(luò)的度分布,聚類系數(shù),平均最短路長度等拓?fù)渲笜?biāo),驗(yàn)證網(wǎng)絡(luò)的無標(biāo)度性與小世界特性,從而可以根據(jù)現(xiàn)有的研究成果針對該網(wǎng)絡(luò)給出新增公交線路或現(xiàn)有線路改造的合理建議。關(guān)鍵詞:無標(biāo)度網(wǎng)絡(luò);小世界特性;聚集性;復(fù)雜網(wǎng)絡(luò)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復(fù)雜網(wǎng)絡(luò)的介紹22.1復(fù)雜網(wǎng)絡(luò)的發(fā)展22.2復(fù)雜網(wǎng)絡(luò)的特性32.3復(fù)雜網(wǎng)絡(luò)的區(qū)分32.4復(fù)雜網(wǎng)絡(luò)的研究意義43復(fù)雜

10、網(wǎng)絡(luò)的分類63.1規(guī)則網(wǎng)絡(luò)63.2隨機(jī)圖63.3小世界網(wǎng)絡(luò)模型73.4無標(biāo)度網(wǎng)絡(luò)模型74杭州公交網(wǎng)絡(luò)的建立94.1公交網(wǎng)絡(luò)模型94.2杭州公交網(wǎng)絡(luò)數(shù)據(jù)描述105公交網(wǎng)絡(luò)無標(biāo)度性125.1公交網(wǎng)絡(luò)的無標(biāo)度分布125.2公交網(wǎng)絡(luò)的聚集性155.3公交網(wǎng)絡(luò)平均最短路長度與聚類系數(shù)155.4結(jié)果分析176結(jié)論19致謝20參考文獻(xiàn)21附錄251引言復(fù)雜網(wǎng)絡(luò),特別是小世界網(wǎng)絡(luò)和無尺度網(wǎng)絡(luò)剛一提出,就呈現(xiàn)出廣闊的應(yīng)用前景。internet、www以及新陳代謝等的連接度分布函數(shù)具有冪律形式,而且這類網(wǎng)絡(luò)的節(jié)點(diǎn)的連接度沒有明顯的特征長度,故稱為無標(biāo)度網(wǎng)絡(luò)1。barabasi和albert提出的無標(biāo)度網(wǎng)絡(luò)模型被稱

11、為ba模型。ba模型的兩個重要特性是:增長特性和有線連接特性。它表明網(wǎng)絡(luò)的規(guī)模不斷擴(kuò)大,新的鏈接更傾向于那些具有較高連接度的“大”節(jié)點(diǎn)相鏈接,這種現(xiàn)象也叫“馬太效應(yīng)”2。隨著網(wǎng)絡(luò)的不斷發(fā)展,公交網(wǎng)絡(luò)的不斷普及和完善,現(xiàn)實(shí)中無標(biāo)度網(wǎng)絡(luò)的指的是除了小世界效應(yīng)外,大量實(shí)際網(wǎng)絡(luò)還存在著另一個突出的結(jié)構(gòu)特征冪律度分布,稱其為無標(biāo)度網(wǎng)絡(luò)。無標(biāo)度網(wǎng)絡(luò)的特點(diǎn)是分布的自相似結(jié)構(gòu)及其高度彌散性,在不相關(guān)的無標(biāo)度性網(wǎng)絡(luò)必然是小世界的(事實(shí)上,比小世界更小)。盡管如此,無標(biāo)度網(wǎng)絡(luò)相關(guān)度分布可能并非如此。我們描述一個產(chǎn)生具有高對稱性但非小世界的無標(biāo)度性網(wǎng)絡(luò)模型的演化機(jī)理。在公交網(wǎng)絡(luò)中引入了復(fù)雜網(wǎng)絡(luò)中的基本靜態(tài)幾何量,本

12、文結(jié)合杭州市公交網(wǎng)絡(luò)的實(shí)際數(shù)據(jù),驗(yàn)證了杭州市公交網(wǎng)絡(luò)的小世界特性和無標(biāo)度特征,并在此基礎(chǔ)上分析研究了公交網(wǎng)絡(luò)的有效性和脆弱性3-4。 首先,根據(jù)公交網(wǎng)絡(luò)的特性,結(jié)合杭州市實(shí)際公交網(wǎng)絡(luò)數(shù)據(jù)建立了杭州市公交網(wǎng)絡(luò)模型和杭州市公交換乘網(wǎng)絡(luò)模型。目前,國際上已經(jīng)形成研究復(fù)雜性問題和復(fù)雜網(wǎng)絡(luò)的研究熱潮。而復(fù)雜網(wǎng)絡(luò)是研究復(fù)雜性問題的有力工具。自然界中存在著大量的復(fù)雜系統(tǒng),如internet網(wǎng)、計算機(jī)網(wǎng)絡(luò)、神經(jīng)系統(tǒng)、社會關(guān)系網(wǎng)絡(luò)等等,都可以通過復(fù)雜網(wǎng)絡(luò)進(jìn)行描述。通過研究這些復(fù)雜網(wǎng)絡(luò)的內(nèi)在機(jī)制和演化規(guī)律,從而找到網(wǎng)絡(luò)上的復(fù)雜行為與網(wǎng)絡(luò)結(jié)構(gòu)的關(guān)系,增加對復(fù)雜網(wǎng)絡(luò)系統(tǒng)的自然規(guī)律的認(rèn)識。 度分布是復(fù)雜網(wǎng)絡(luò)問題中研究較

13、多的一個方向,本文主要研究了復(fù)雜網(wǎng)絡(luò)中勻速增長的非線性擇優(yōu)連接的ba模型度的分布。2復(fù)雜網(wǎng)絡(luò)的介紹2.1復(fù)雜網(wǎng)絡(luò)的發(fā)展萬維網(wǎng)上從一個頁面到另一個頁面平均需要點(diǎn)擊多少次鼠標(biāo)?層出不窮的計算機(jī)病毒是如何在互聯(lián)網(wǎng)上傳播的?各種傳染病是如何在人類和動物中流行的?全球或地區(qū)性的金融危機(jī)是如何發(fā)生的?大城市的交通阻塞問題是如何引起的?為什么大腦能夠具有思維的功能?這些問題看上去各不相同,但每個問題都涉及很復(fù)雜的網(wǎng)絡(luò),包括www、internet、社會關(guān)系網(wǎng)、經(jīng)濟(jì)網(wǎng)絡(luò)、電力網(wǎng)絡(luò)、交通網(wǎng)絡(luò)、經(jīng)濟(jì)網(wǎng)絡(luò)等等。由于現(xiàn)實(shí)世界網(wǎng)絡(luò)的規(guī)模大,節(jié)點(diǎn)間相互作用復(fù)雜,其拓?fù)浣Y(jié)構(gòu)基本上未知或未曾探索。兩百多年來,人們對描述真實(shí)系

14、統(tǒng)拓?fù)浣Y(jié)構(gòu)的研究經(jīng)歷了三個階段。在最初的一百多年里,科學(xué)家們認(rèn)為真實(shí)系統(tǒng)要素之間的關(guān)系可以用一些規(guī)則的結(jié)構(gòu)表示,例如二維平面上的歐幾里德格網(wǎng)從20世紀(jì)50年代末到90年代末,無明確設(shè)計原則的大規(guī)模網(wǎng)絡(luò)主要用簡單而易于被多數(shù)人接受的隨機(jī)網(wǎng)絡(luò)來描述,隨機(jī)圖的思想主宰復(fù)雜網(wǎng)絡(luò)研究達(dá)四十年之久直到最近幾年,科學(xué)家們發(fā)現(xiàn)大量的真實(shí)網(wǎng)絡(luò)既不是規(guī)則網(wǎng)絡(luò),也不是隨機(jī)網(wǎng)絡(luò),而是具有與前兩者皆不同的統(tǒng)計特性的網(wǎng)絡(luò),其中最有影響的是小世界網(wǎng)絡(luò)和無尺度網(wǎng)絡(luò)。這兩種網(wǎng)絡(luò)的發(fā)現(xiàn),掀起了復(fù)雜網(wǎng)絡(luò)的研究熱潮。1959-1960年,匈牙利數(shù)學(xué)家艾爾德(p.erdos)和萊利(a.renyi)建立了隨機(jī)圖(er模型),被公認(rèn)為是

15、數(shù)學(xué)上開創(chuàng)了復(fù)雜網(wǎng)絡(luò)理論的系統(tǒng)性研究。20世紀(jì)60年代美國哈弗大學(xué)的社會心理學(xué)家stanley milgram通過一些社會調(diào)查后給出的推斷是:地球上任意兩個人之間的平均距離是6。也就是說,平均中間只要通過5個人,你就能與地球上的任何一個角落的任何一個人發(fā)生聯(lián)系。1998年,康奈爾大學(xué)的社會學(xué)家watts和strogatz 提出了小世界網(wǎng)絡(luò)(ws模型)5。1999年,圣母大學(xué)的物理學(xué)家barabsi和albert提出了無尺度網(wǎng)絡(luò)(ba模型)6。復(fù)雜網(wǎng)絡(luò)研究的快速發(fā)展的主要原因包括:1、越來越強(qiáng)大的計算設(shè)備和迅猛發(fā)展的internet,使得人們開始能夠收集和處理規(guī)模巨大且種類不同的實(shí)際網(wǎng)絡(luò)數(shù)據(jù)。2

16、、學(xué)科之間的相互交叉使得研究人員可以廣泛比較各種不同類型的網(wǎng)絡(luò)數(shù)據(jù),從而揭示復(fù)雜網(wǎng)絡(luò)的共性。3、以還原論和整體論相結(jié)合為重要特色的復(fù)雜性科學(xué)的興起,也促使人們開始從整體上研究網(wǎng)絡(luò)的結(jié)構(gòu)和性能之間的關(guān)系。著名的物理學(xué)家霍金認(rèn)為二十一世紀(jì)是復(fù)雜性的世紀(jì)。復(fù)雜網(wǎng)絡(luò)的研究是復(fù)雜性理論研究的一部分,作為研究復(fù)雜性科學(xué)和復(fù)雜系統(tǒng)的有力工具,復(fù)雜網(wǎng)絡(luò)為研究復(fù)雜性提供了全新的視角。復(fù)雜網(wǎng)絡(luò)借助于圖論和統(tǒng)計物理的一些方法7-13,可以用來捕捉并描述系統(tǒng)的演化機(jī)制、演化規(guī)律結(jié)構(gòu)和整體行為功能。2.2復(fù)雜網(wǎng)絡(luò)的特性2.2.1 結(jié)構(gòu)復(fù)雜性網(wǎng)絡(luò)連接結(jié)構(gòu)看上去錯綜復(fù)雜、極其混亂,而且網(wǎng)絡(luò)鏈接結(jié)構(gòu)可能是隨時間變化的,例如,

17、www上每天都不停地有頁面和鏈接的產(chǎn)生和刪除。此外,節(jié)點(diǎn)之間的連接可能具有不同的權(quán)重或方向。例如,神經(jīng)系統(tǒng)中的突觸有強(qiáng)有弱,可以是抑制的也可以是興奮的。2.2.2 節(jié)點(diǎn)復(fù)雜性 網(wǎng)絡(luò)中的節(jié)點(diǎn)可能是具有分岔和混沌等復(fù)雜非線性行為的動力系統(tǒng)。例如,基因網(wǎng)絡(luò)和josephson結(jié)陣列中每個節(jié)點(diǎn)都具有復(fù)雜的時間演化行為。而且,一個網(wǎng)絡(luò)中可能存在多種不同類型的節(jié)點(diǎn)。例如,控制哺乳動物中細(xì)胞分裂的生化網(wǎng)絡(luò)就包含各種各樣的基質(zhì)和酶。2.2.3 各種復(fù)雜性因素的相互影響 實(shí)際的復(fù)雜網(wǎng)絡(luò)會受到各種各樣因素的影響和作用。例如,耦合神經(jīng)元重復(fù)地被同時激活,那么它們之間的連接就會加強(qiáng),這被認(rèn)為是記憶和學(xué)習(xí)的基礎(chǔ)。此外,

18、各種網(wǎng)絡(luò)之間也存在密切的聯(lián)系,這使得對復(fù)雜網(wǎng)絡(luò)的分析變得更加困難。例如,電力網(wǎng)絡(luò)的故障可能會導(dǎo)致internet流量變慢、金融機(jī)構(gòu)關(guān)閉、運(yùn)輸系統(tǒng)失去控制等一系列不同網(wǎng)絡(luò)之間的連鎖反應(yīng)。2.3復(fù)雜網(wǎng)絡(luò)的區(qū)分根據(jù)節(jié)點(diǎn)度的分布情況,可以將復(fù)雜網(wǎng)絡(luò)分為指數(shù)網(wǎng)絡(luò)和無尺度網(wǎng)絡(luò)兩大類。指數(shù)網(wǎng)絡(luò)中的節(jié)點(diǎn)是同質(zhì)的,它們的度大致相同,絕大部節(jié)點(diǎn)的度都位于網(wǎng)絡(luò)節(jié)點(diǎn)平均度附近,網(wǎng)絡(luò)節(jié)點(diǎn)度分布隨度數(shù)的增加呈指數(shù)衰減,使得網(wǎng)絡(luò)中不存在度數(shù)特別大的節(jié)點(diǎn),最經(jīng)典的兩種指數(shù)網(wǎng)絡(luò)是er隨機(jī)圖模型和小世界網(wǎng)絡(luò)模型。隨機(jī)圖與小世界網(wǎng)絡(luò)的主要區(qū)別是前者的簇系數(shù)小,而后者的簇系數(shù)大。目前,把具有較小平均路徑長度和較大簇系數(shù)的網(wǎng)絡(luò)統(tǒng)稱為小

19、世界網(wǎng)絡(luò),這一說法己得到學(xué)術(shù)界的公認(rèn)。無尺度網(wǎng)絡(luò)中的節(jié)點(diǎn)是異質(zhì)的,其節(jié)點(diǎn)度服從冪律分布。最著名的無尺度網(wǎng)絡(luò)模型是1999年barabasi和albert建立的無尺度網(wǎng)絡(luò)模型模型3。在無尺度網(wǎng)絡(luò)中,大部分節(jié)點(diǎn)只與少數(shù)幾個其它節(jié)點(diǎn)連接,但網(wǎng)絡(luò)中存在為數(shù)不多的度數(shù)特別大的節(jié)點(diǎn),稱為集散節(jié)點(diǎn)或節(jié)點(diǎn),它對無尺度網(wǎng)絡(luò)的特性起著主導(dǎo)和支配作用。從生成方式上可將復(fù)雜網(wǎng)絡(luò)分成隨機(jī)性網(wǎng)絡(luò)和確定性網(wǎng)絡(luò)。顧名思義,隨機(jī)網(wǎng)絡(luò)的生成是隨機(jī)的,盡管生成規(guī)則相同,每次在電腦上模擬生成的網(wǎng)絡(luò)卻存在差異性確定性網(wǎng)絡(luò)的生成規(guī)則是確定的,其結(jié)構(gòu)特性可以精確求解。從邊的方向性上可將網(wǎng)絡(luò)分為無向網(wǎng)絡(luò)和有向網(wǎng)絡(luò),無向網(wǎng)絡(luò)的邊不存在方向性,

20、有向網(wǎng)絡(luò)的邊卻有方向。從邊有無權(quán)值可將網(wǎng)絡(luò)分為加權(quán)網(wǎng)絡(luò)和0-1網(wǎng)絡(luò)。2.4復(fù)雜網(wǎng)絡(luò)的研究意義復(fù)雜網(wǎng)絡(luò),特別是小世界網(wǎng)絡(luò)和無尺度網(wǎng)絡(luò)剛一提出,就呈現(xiàn)出廣闊的應(yīng)用前景,其應(yīng)用領(lǐng)域涉及工程技術(shù)、社會、政治、醫(yī)藥、經(jīng)濟(jì)、管理等不同方面4。在過去幾年里,不同領(lǐng)域的研究者發(fā)現(xiàn),包括萬維網(wǎng)、細(xì)胞代謝系統(tǒng)、好萊塢的演員網(wǎng)絡(luò)在內(nèi)的許多現(xiàn)實(shí)網(wǎng)絡(luò),都是無尺度網(wǎng)絡(luò),它們由少數(shù)幾個具有眾多連結(jié)的節(jié)點(diǎn)所支配,這些重要節(jié)點(diǎn)通常稱為集散節(jié)點(diǎn)。無尺度網(wǎng)絡(luò)對意外故障具有驚人的承受力,但面對協(xié)同式攻擊時則很脆弱。這些新發(fā)現(xiàn)極大地改變了人們對復(fù)雜外部世界的認(rèn)識,讓人們認(rèn)識到了以前的理論尚未涉及的問題各種復(fù)雜系統(tǒng)具有相同的嚴(yán)格結(jié)構(gòu),都

21、受制于某些基本的法則,這些法則似乎可同等地適用于細(xì)胞、計算機(jī)、語言和社會。認(rèn)識這些法則,可以將其應(yīng)用到不同領(lǐng)域,幫助人們解決一系列重要問題。首先,復(fù)雜網(wǎng)絡(luò)理論可以用于保護(hù)許多現(xiàn)實(shí)系統(tǒng)的正常運(yùn)行。因特網(wǎng)、電力網(wǎng)、航空網(wǎng)、萬維網(wǎng)、電子郵件網(wǎng)、食物鏈網(wǎng)等網(wǎng)絡(luò)與我們的生活息息相關(guān),人們對這些網(wǎng)絡(luò)的依賴程度日益增強(qiáng),凸現(xiàn)了一個廣受關(guān)注的問題,這些網(wǎng)絡(luò)到底有多可靠呢?2000年,愛蟲病毒侵犯了英國議會的電子郵件系統(tǒng),導(dǎo)致該系統(tǒng)癱瘓;2003年,美加電網(wǎng)的大崩潰事故讓紐約人感到惶恐不安當(dāng)前,人類賴以生存的生態(tài)系統(tǒng)不斷遭到破壞己經(jīng)危及到人類的生存環(huán)境,等等。從這些現(xiàn)象可以自然地提出下面的問題計算機(jī)病毒如何在萬

22、維網(wǎng)上傳播而導(dǎo)致流行病毒如何通過電子郵件傳播,人們?nèi)绾慰刂撇《緜鞑ィ棵鎸诳偷墓?,?yīng)該采取何種對策?怎樣設(shè)計出承受意外故障較強(qiáng)的網(wǎng)絡(luò)如電力網(wǎng)、航空網(wǎng)?怎樣保持當(dāng)前不斷惡化的生態(tài)系統(tǒng)的平衡?這些問題的解決都與復(fù)雜網(wǎng)絡(luò)的研究有關(guān),開展好復(fù)雜網(wǎng)絡(luò)穩(wěn)定性的研究,對于互聯(lián)網(wǎng)、電力網(wǎng)、航空網(wǎng)等技術(shù)網(wǎng)絡(luò)的設(shè)計保護(hù)及基礎(chǔ)設(shè)施網(wǎng)絡(luò)的保護(hù)具有重要的意義,也可以有效地防止黑客侵入互聯(lián)網(wǎng)、阻止病毒在萬維網(wǎng)上傳播蔓延。 復(fù)雜網(wǎng)絡(luò)在社會領(lǐng)域也有廣闊的應(yīng)用。傳染病如艾滋病、非典、禽流感等對人類的威脅很大艾滋病讓人們不寒而栗年的非典對于宏觀經(jīng)濟(jì)和人類的生命安全都產(chǎn)生了巨大的負(fù)面影響目前,禽流感也己成為世界關(guān)注的一個焦點(diǎn)。那

23、么在特定的社會網(wǎng)絡(luò)中,傳染病如何通過接觸關(guān)系傳播而導(dǎo)致流行呢?決策者如何控制這些疾病,將損失降到最低限度呢這些問題或許可以從復(fù)雜網(wǎng)絡(luò)那里尋找答案。最近幾年,科學(xué)家們考慮了不同現(xiàn)實(shí)系統(tǒng)的主要特征,提出了許多有針對性的疾病免疫方法晰一,為疾病的預(yù)測、預(yù)防和免疫提供了科學(xué)的方案。譬如,用復(fù)雜網(wǎng)絡(luò)理論可以很好地預(yù)測非典爆發(fā)的多樣性、了解疾病傳播的動態(tài)性,為決策者控制流行病蔓延、改善公共衛(wèi)生提供有效的手段。復(fù)雜網(wǎng)絡(luò)在經(jīng)濟(jì)、管理領(lǐng)域也有著重要的實(shí)際意義5。利用復(fù)雜網(wǎng)絡(luò)理論了解公司、產(chǎn)業(yè)與經(jīng)濟(jì)之間的連結(jié)方式,有助于監(jiān)控和預(yù)防大規(guī)模的經(jīng)濟(jì)衰退。在管理領(lǐng)域,決策對經(jīng)濟(jì)的發(fā)展起著關(guān)鍵性的作用,同一個人可以在多個組

24、織內(nèi)兼任董事。建立公司董事網(wǎng),使得分析決策的動態(tài)性成為可能。經(jīng)濟(jì)網(wǎng)絡(luò)恰好刻畫了經(jīng)濟(jì)系統(tǒng)中微觀個體之間存在相互作用的關(guān)系結(jié)構(gòu),這種關(guān)系可以是經(jīng)濟(jì)個體之間的信息交流、商品或股票交易、投資關(guān)系、信用關(guān)系或者隸屬控制關(guān)系等等。1999年,barabsi與albert作出了對復(fù)雜網(wǎng)絡(luò)里程碑式的研究,他們揭示了許多現(xiàn)實(shí)網(wǎng)絡(luò)的連接具有無標(biāo)度性的這個引人注目的結(jié)果。受這一研究結(jié)果的激勵,人們開始關(guān)注經(jīng)濟(jì)與經(jīng)濟(jì)網(wǎng)絡(luò)的結(jié)構(gòu),開展了許多關(guān)于經(jīng)濟(jì)與金融系統(tǒng)網(wǎng)絡(luò)結(jié)構(gòu)的實(shí)證研究。結(jié)果顯示:在經(jīng)濟(jì)的多個方面人們觀測到了經(jīng)濟(jì)網(wǎng)絡(luò)具有無標(biāo)度性和小世界等性質(zhì)。3復(fù)雜網(wǎng)絡(luò)的分類3.1規(guī)則網(wǎng)絡(luò) 在很長一段里,人們認(rèn)為真實(shí)系統(tǒng)各因素之

25、間的關(guān)系可以用一些規(guī)則網(wǎng)絡(luò)表示,如一維鏈、二維平面上的歐幾里德格網(wǎng)等。用得最多的規(guī)則網(wǎng)絡(luò)是由n個節(jié)點(diǎn)組成的環(huán)狀網(wǎng)絡(luò),網(wǎng)絡(luò)中每個節(jié)點(diǎn)只與它最近的k個節(jié)點(diǎn)連接。在規(guī)則網(wǎng)絡(luò)中,每個節(jié)點(diǎn)具有相同的度和簇系數(shù)。節(jié)點(diǎn)的度分布為函數(shù),即。節(jié)點(diǎn)簇系數(shù)為(d為網(wǎng)絡(luò)維數(shù)),集聚程度較高6。在一個全局耦合網(wǎng)絡(luò)中,任意兩個點(diǎn)之間都有邊直接相連(圖3.1)。在具有相同節(jié)點(diǎn)數(shù)的所有網(wǎng)絡(luò)中,全局耦合網(wǎng)絡(luò)具有最小的平均路徑長度l=1和最大的聚類系數(shù)c=1。圖3.1 規(guī)則網(wǎng)絡(luò)3.2隨機(jī)圖 與完全規(guī)則網(wǎng)絡(luò)相反的是完全隨機(jī)網(wǎng)絡(luò),其中一個典型的模型是er隨機(jī)圖模型。er隨即圖的性質(zhì)與概率之間的關(guān)系,采用以下定義:如果當(dāng)時產(chǎn)生一個具有

26、性質(zhì)q和er隨機(jī)圖的概率為1,那么就稱幾乎每一個er隨機(jī)圖都具有性質(zhì)er隨機(jī)圖的節(jié)點(diǎn)度服從泊松分布,它具有較小的平均路徑長度和較小的簇系數(shù)。er模型提出后,從20世紀(jì)50年代末到90年代末的近四十年里,無明確設(shè)計原則的大規(guī)模網(wǎng)絡(luò)主要用這種簡單而易于被多數(shù)人接受的隨機(jī)圖的拓?fù)浣Y(jié)構(gòu)來描述,即認(rèn)為大規(guī)模網(wǎng)絡(luò)的形成過程中,節(jié)點(diǎn)間的連接是完全隨機(jī)的。期間,一些數(shù)學(xué)家對隨機(jī)圖進(jìn)行了非常好的研究,通過嚴(yán)格的數(shù)學(xué)證明,得到了許多近似和精確的結(jié)果。er模型的思想支配人們研究復(fù)雜網(wǎng)絡(luò)長達(dá)四十年之久,直到最近幾年,由于計算機(jī)數(shù)據(jù)處理和運(yùn)算能力的飛速發(fā)展,科學(xué)家們發(fā)現(xiàn)大量的現(xiàn)實(shí)網(wǎng)絡(luò)不是完全隨機(jī)的網(wǎng)絡(luò),而是具有其他統(tǒng)計

27、特征的網(wǎng)絡(luò)7。3.3小世界網(wǎng)絡(luò)模型 實(shí)證研究表明,許多現(xiàn)實(shí)網(wǎng)絡(luò)特別是社會網(wǎng)絡(luò)都表現(xiàn)出集群現(xiàn)象,由此引發(fā)人們對小世界網(wǎng)絡(luò)的研究。最早的小世界網(wǎng)絡(luò)模型是watts和strogatz在1998年提出的網(wǎng)絡(luò)模型(ws模型),該模型由一個具有n個節(jié)點(diǎn)的環(huán)開始,環(huán)上每一個節(jié)點(diǎn)與兩側(cè)各有條邊相連,然后對每條邊以概率p隨機(jī)進(jìn)行重連自我連接和重邊除外,這些重連的邊叫“長程連接”,長程連接大大地減小了網(wǎng)絡(luò)的平均路徑長度,而對網(wǎng)絡(luò)的簇系數(shù)影響較小。ws模型的建立和生成有其深刻的社會根源,因?yàn)樵谏鐣到y(tǒng)中,大多數(shù)人直接和鄰居、同事相識,但個別人也有遠(yuǎn)方甚至國外的朋友。作為從完全規(guī)則網(wǎng)絡(luò)向完全隨機(jī)圖的過渡,watts和

28、strogtz于1998年引入了一個有趣的小世界網(wǎng)絡(luò)模型,稱為ws小世界模型。在該模型中,對應(yīng)于完全規(guī)則網(wǎng)絡(luò),則對應(yīng)于完全隨機(jī)網(wǎng)絡(luò),通過調(diào)節(jié)的值就可以控制從完全規(guī)則網(wǎng)絡(luò)到完全隨機(jī)網(wǎng)絡(luò)的過渡(圖3.2)8。圖3.2 小世界網(wǎng)絡(luò)3.4無標(biāo)度網(wǎng)絡(luò)模型 er模型和ws模型的度分布與許多現(xiàn)實(shí)網(wǎng)絡(luò)都不相符,用它們來描述這些現(xiàn)實(shí)網(wǎng)絡(luò),具有很大的局限性,因此科學(xué)家們只好尋求另一種模型,來更好地描述這些現(xiàn)實(shí)網(wǎng)絡(luò)。1999年,barabsi和albert通過追蹤萬維網(wǎng)的動態(tài)演化過程,發(fā)現(xiàn)了許多復(fù)雜網(wǎng)絡(luò)具有大規(guī)模的高度自組織特性,即多數(shù)復(fù)雜網(wǎng)絡(luò)的節(jié)點(diǎn)度服從冪律分布,并把具有冪律度分布的網(wǎng)絡(luò)稱為無尺度網(wǎng)絡(luò)9。bara

29、bsi認(rèn)為,增長和擇優(yōu)連接是無尺度網(wǎng)絡(luò)形成的兩種必不可少的機(jī)制,這一觀點(diǎn)已被學(xué)術(shù)界普遍接受。 最原始的無尺度網(wǎng)絡(luò)模型稱為ba模型10,它是第一個隨機(jī)的無尺度網(wǎng)絡(luò)模型。在ba模型生成的初始時刻,假定系統(tǒng)中己有少量節(jié)點(diǎn),在以后的每一個時間間隔中,新增一個節(jié)點(diǎn),并與網(wǎng)絡(luò)中己經(jīng)存在一定數(shù)目的不同節(jié)點(diǎn)進(jìn)行連接。當(dāng)在網(wǎng)絡(luò)中選擇節(jié)點(diǎn)與新增節(jié)點(diǎn)連接時,假設(shè)被選擇的節(jié)點(diǎn)與新節(jié)點(diǎn)連接的概率和被選節(jié)點(diǎn)的度成正比,人們將這種連接稱為擇優(yōu)連接。ba網(wǎng)絡(luò)最終演化成標(biāo)度不變狀態(tài),即節(jié)點(diǎn)度服從度指數(shù)等于3的冪律分布。ba模型的平均路徑長度很小,簇系數(shù)也很小,但比同規(guī)模隨機(jī)圖的簇系數(shù)要大,不過當(dāng)網(wǎng)絡(luò)趨于無窮大時,這兩種網(wǎng)絡(luò)的簇

30、系數(shù)均近似為零。er隨機(jī)圖和ws小世界模型的一個共同特征就是網(wǎng)絡(luò)的連接度分布可近似用poisson分布表示,該分布在度平均值k處有個峰值,然后呈指數(shù)快速衰減。這類網(wǎng)絡(luò)的節(jié)點(diǎn)的連接度沒有明顯的特征長度,具有增長特性和優(yōu)先鏈接特性1112。ba網(wǎng)絡(luò)的度分布函數(shù)可近似描述13(圖3.3)。圖3.3 無標(biāo)度網(wǎng)絡(luò)4杭州公交網(wǎng)絡(luò)的建立4.1公交網(wǎng)絡(luò)模型城市公交系統(tǒng)是城市交通運(yùn)輸系統(tǒng)的重要組成部分。城市公交系統(tǒng)規(guī)劃的好壞直接影響著整個城市交通運(yùn)輸系統(tǒng)的交通狀況,因此,公交網(wǎng)絡(luò)模型是整個公交網(wǎng)絡(luò)設(shè)計的基礎(chǔ),模型的好壞直接影響網(wǎng)絡(luò)設(shè)計的效果。關(guān)于公交客流的分配問題,國外有大量的文獻(xiàn)和研究成果。其中最為典型的理論

31、是80年代提出的出行略理論。出行策略理論不僅抓住了乘客出行的特點(diǎn),而且使得已有的適用于機(jī)動車的平衡分配模型,通過改進(jìn)而適用于公交網(wǎng)絡(luò)?;诔鲂胁呗岳碚摰牡湫头峙淠P褪莝piess 和florian(1984、1989)提出的適用于非擁擠公交網(wǎng)絡(luò)的客流分配模型。針對傳統(tǒng)網(wǎng)絡(luò)表示方法的不足, pallottino 在1988年引入了超級路徑的概念。超級路徑理論的引入再次推動了公交客流分配技術(shù)的發(fā)展?;诔壜窂胶筒呗詢?yōu)化理論的非平衡分配模型的最新研究成果是nguyen提出的基于有效超級路徑的logit分配模型,kikuchi等提出了應(yīng)用模糊邏輯設(shè)計公共交通網(wǎng)絡(luò)。pattnaik等提出了運(yùn)用遺傳算法

32、設(shè)計公交線網(wǎng)。國內(nèi)研究現(xiàn)狀早在80年代初期,張啟人等就在長沙市對公交線網(wǎng)的優(yōu)化問題進(jìn)行了研究,他們提出了以直達(dá)乘客量最大為優(yōu)化目標(biāo),以線路長度、線路重復(fù)系數(shù)等為約束條件的公交線網(wǎng)優(yōu)化模型。該模型在長沙得到了較好的應(yīng)用。張啟人等還提出了運(yùn)用層次分析法(ahp)構(gòu)造公共交通大系統(tǒng)的理論和方法。劉清等提出了基于人工智能理論的廣義a*算法。廣義a*算法,以客流總交通時間、客流直達(dá)率等為目標(biāo),確立估計函數(shù)表達(dá)式,采用啟發(fā)式搜索技術(shù),從每對端點(diǎn)搜索出滿足有關(guān)約束條件的備選線路,然后以此為基礎(chǔ)按二進(jìn)制理論組合成若干優(yōu)化網(wǎng)絡(luò)比較而定。林柏梁等基于組合優(yōu)化的角度,提出了公交網(wǎng)絡(luò)優(yōu)化設(shè)計的非線性0-1規(guī)劃模型,以

33、乘客的出行時間和實(shí)現(xiàn)公交網(wǎng)絡(luò)的資金投入為目標(biāo)函數(shù),在滿足車站容量限制的條件下,最小化目標(biāo)函數(shù),以獲得公交線路的優(yōu)化決策。王志棟提出了以乘客總出行時間最小、客流直達(dá)率最高、線網(wǎng)覆蓋率最高、線路重復(fù)系數(shù)最低、公交經(jīng)濟(jì)效益最高為目標(biāo),以路網(wǎng)、線路長度、線路非直線系數(shù)、線路最大客流量限制、道路流量限制、站點(diǎn)客流量限制和換乘次數(shù)為約束條件的公交網(wǎng)絡(luò)優(yōu)化模型。針對垂直交叉路段與筆直路段,分別提出了城市公共汽車??奎c(diǎn)選址的離散型模型和連續(xù)型模型,并給出了相應(yīng)的算法和軟件。在公交線網(wǎng)站點(diǎn)優(yōu)化技術(shù)領(lǐng)域比較有新意的是唐利民等通過對上海市公交問題的分析,提出的flapt模型,該模型按照一定的標(biāo)準(zhǔn)將上海市劃分成23個

34、層次,運(yùn)用蛙跳式轉(zhuǎn)移和滲透式轉(zhuǎn)移的方法,對選定的梯度中心和區(qū)域進(jìn)行布線,并以客流直達(dá)率為優(yōu)化目標(biāo),進(jìn)行網(wǎng)絡(luò)布局優(yōu)化。計算結(jié)果表明,運(yùn)用flapt模型能明顯縮短乘客出行時間。學(xué)者四兵鋒等在城市道路交通均衡配流模型的基礎(chǔ)上,探討公交網(wǎng)絡(luò)的均衡原則,提出一種較為簡單的城市公共交通網(wǎng)絡(luò)描述方法,并給出公交網(wǎng)絡(luò)配流問題的均衡模型及求解算法。夏志浩等把由路段交通量推算道路網(wǎng)中車輛出行o-d分布的方法移植到公交系統(tǒng),根據(jù)各線路各車站調(diào)查的上下車人數(shù)推算公交客流的o-d分布,成功地應(yīng)用于成都市的公交客流o-d推算。曾小明等對影響公共交通系統(tǒng)服務(wù)質(zhì)量的要素進(jìn)行了研究,應(yīng)用模糊數(shù)學(xué)方法,給出了評價公共交通服務(wù)質(zhì)量

35、的模糊評定法,用它對佛山市城市公共交通服務(wù)質(zhì)量進(jìn)行綜合評價。孫芙靈對公交調(diào)度優(yōu)化中的發(fā)車間隔問題進(jìn)行了研究,通過研究得到控制發(fā)車間隔的四個目標(biāo)是:根據(jù)乘客需求確定一個可供選擇的發(fā)車間隔;當(dāng)車輛供給受到約束時,相應(yīng)地改變發(fā)車間隔;在相鄰的時間段使用平滑法調(diào)節(jié)發(fā)車間隔;在一個發(fā)車時刻表中綜合利用各種間隔設(shè)置法。在實(shí)踐中最常用的公交客流需求預(yù)測模型有三種:即增長率法、概率模型法、重力模型法。(1)增長率法增長率法是在考慮各小區(qū)發(fā)生量、吸引量的增長率的基礎(chǔ)上,用現(xiàn)狀o-d表來直接推算未來的o-d表。該法基于兩點(diǎn)基本假設(shè):在預(yù)測年以內(nèi)城市交通運(yùn)輸系統(tǒng)沒有明顯的變化和區(qū)間的出行與路網(wǎng)的改變相對獨(dú)立。它又分

36、為均勻增長率模型,平均增長率模型等。(2)概率分布模型法概率分布模型是將小區(qū)的發(fā)生量以一定的概率分布到吸引小區(qū)的方法。這是一種以出行個體效用最大為目標(biāo)的非集合優(yōu)化模型,從理論上講是一種更為精確的方法,但在實(shí)際應(yīng)用上,這種模型結(jié)構(gòu)復(fù)雜,需要的樣本容量很大,難于求解和標(biāo)定。(3)重力模型法重力模型引用了牛頓萬有引力定律來描述城市居民的出行行為,是國內(nèi)交通規(guī)劃中使用最廣泛的模型。此法綜合考慮了影響出行分布的出行空間、時間阻礙因素,它的基本假設(shè)為:交通小區(qū)i 到交通小區(qū)j 的出行分布量與小區(qū)i 的出行分布量為標(biāo)準(zhǔn)。4.2杭州公交網(wǎng)絡(luò)數(shù)據(jù)描述4.2.1數(shù)據(jù)描述本文通過對杭州公交網(wǎng)絡(luò)實(shí)地調(diào)查取樣,在杭州1

37、000多條公交線路中進(jìn)行數(shù)據(jù)統(tǒng)計分析,把數(shù)據(jù)整理繪制成表格形式,對統(tǒng)計出來的每條線路的各個站點(diǎn)以不同的四位數(shù)字;在有序的情況下替代各個站點(diǎn),然后把數(shù)據(jù)加工整理,在這樣的基礎(chǔ)上用每特來不進(jìn)行編程,把整理的數(shù)據(jù)進(jìn)行處理,最后繪制出圖形,以用來進(jìn)行研究分析。本文在整理的數(shù)據(jù)中選出十五個車次的部分?jǐn)?shù)據(jù)做為樣本,以供參考,如下表(4.1)。表4.1 15條公交線路數(shù)據(jù)線路名稱一二三四五六1/k110011002100310041005100610/k1010161002100310041005100611/k1110301031103210331034103512/k121049105010511052

38、1053105413/k1310701071107210731074107514/k1410841085108610871088108915/k15109410951096109710981099151/k15111111112111311141115111618/k1811311132113310901134113519/k1911401141114211431144114520/k2011541155115611571158107021/k2110301167116811691163113522/k2211821183118411441145118523/k2311791041104011

39、771194119424/k24119911181183118211751176 4.2.2三地最優(yōu)路線路線根據(jù)實(shí)地考察和收集的信息。結(jié)合杭州市區(qū)的實(shí)際情況,我們?nèi)缦卤硐卤砹谐隽?個城市在space p和space l方法中的平均路徑長度和聚類系數(shù)從表中可以看出在space p中,三地的平均路徑長度,即兩站點(diǎn)之間的平均最短路徑長度都介于2.6-3.1之間。因?yàn)閟pace p定義為:兩個站點(diǎn)之間若有直達(dá)交通線路,那么就有連邊,所以平均通過2次(北京和杭州)或3次(上海)換乘就可以到達(dá)目的地。如下圖所示,s1和s4之間的為3,那么從s1到s4只要換乘2次即可(在s2站點(diǎn)從l1換到l2,再在s3站點(diǎn)

40、換另外,聚類系數(shù)也都在0.7以上,這說明整個交通網(wǎng)絡(luò)的連通性好,集團(tuán)化程度高。綜合考慮和可知,3個城市的公交網(wǎng)絡(luò)都具有明顯的小世界特性。在space l中,三地的介于10-16間,比space p中的大的多,同時c也小得多。這是因?yàn)樵趕pace l中,只有當(dāng)兩個站點(diǎn)在同一條線路上相鄰才有連邊。如某一條線路的始發(fā)站s1和終點(diǎn)站s2,在space p中,它們之間有連邊,l為1;在space l中,它們之間卻沒有連邊,中間要經(jīng)過很多站點(diǎn),而不同線路上的站點(diǎn)之間往往存在更多的站點(diǎn)。根據(jù)上面的數(shù)據(jù)可知,這3個城市的公交網(wǎng)絡(luò)規(guī)模都很大,京滬杭平均每條公交線路分別有27.940, 19.867, 17.49

41、7個站點(diǎn)。所以,在space l中,3個城市的公交網(wǎng)絡(luò)平均距離都很小,為平均最短路長度,如圖4.1所示。 圖4.1 六大城市各參數(shù)數(shù)據(jù)統(tǒng)計 5公交網(wǎng)絡(luò)無標(biāo)度性5.1公交網(wǎng)絡(luò)的無標(biāo)度分布5.1.1閾值的選用相關(guān)系數(shù)。在公交系統(tǒng)眾多的車次之中,有些車次間的聯(lián)系很密集。在公交網(wǎng)絡(luò)中,它們之間就沒有連通的邊。為了簡化網(wǎng)絡(luò)圖,我們將的閾值設(shè)定為0.89。在此范圍類,模擬的結(jié)果很符合現(xiàn)實(shí)的情況。5.1.2公交網(wǎng)絡(luò)站點(diǎn)的度分布通過設(shè)定的閾值,可以得到公交網(wǎng)絡(luò)系統(tǒng)的網(wǎng)絡(luò)圖。由于網(wǎng)絡(luò)中的節(jié)點(diǎn)太多,在圖上顯示不太清楚,所以我們直接用表格將每個車次站點(diǎn)顯示出來。我們采用以下matlab程序來實(shí)現(xiàn)各個站點(diǎn)的計算。%

42、采用的相關(guān)系數(shù)的閾值此時為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);% 采用的相關(guān)系數(shù)的閾值此時為0.89%下面求度分布for i=1:length(a) degree_line(i)=sum(d(i,:)-1;enddegree_min=min(degree_line);%最少的度數(shù)degree_max=max(degree_line);%最多的度數(shù)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程序來實(shí)現(xiàn)各個站點(diǎn)的計算有向網(wǎng)絡(luò)中一個節(jié)點(diǎn)的度分為出度和入度。直觀上看,一個節(jié)點(diǎn)的度越大就意味著這個節(jié)點(diǎn)在一定意義上越重要。完全隨機(jī)網(wǎng)絡(luò)的度分布近似為

44、poisson分布,其圖形在遠(yuǎn)離峰值處呈指數(shù)下降。這意味這當(dāng)k時,度為的節(jié)點(diǎn)實(shí)際上是不存在的。因此,這類網(wǎng)絡(luò)也稱為均勻網(wǎng)絡(luò)。研究表明,許多實(shí)際網(wǎng)絡(luò)的度分布明顯地不同于poisson分布。冪律分布曲線比poisson指數(shù)分布曲線下降要緩慢得多。冪律分布也稱為無標(biāo)度分布,具有冪律度分布的網(wǎng)絡(luò)也稱為無標(biāo)度網(wǎng)絡(luò)。我們研究的公交市場的復(fù)雜網(wǎng)絡(luò)的度分布也不同于poisson分布。 通過運(yùn)算,我們可以看出站點(diǎn)間度數(shù)最少的為0,即該站點(diǎn)時間變動不影響其它車次的,現(xiàn)實(shí)中這車次是很少存在的。結(jié)合杭州市實(shí)際公交網(wǎng)絡(luò)數(shù)據(jù)建立了公交??空军c(diǎn)網(wǎng)絡(luò)模型和公交換乘網(wǎng)絡(luò)模型。這兩個模型反映了公交網(wǎng)絡(luò)的自然拓?fù)涮卣饕约肮痪W(wǎng)絡(luò)的

45、可達(dá)性。 其次,本文在兩個公交網(wǎng)絡(luò)模型上進(jìn)行了復(fù)雜網(wǎng)絡(luò)的特性分析,針對公交??空军c(diǎn)網(wǎng)絡(luò),通過其上的復(fù)雜網(wǎng)絡(luò)基本幾何特征量,驗(yàn)證了其上的小世界特性及無標(biāo)度特征。這兩個特性可能給出促進(jìn)交通科學(xué)與技術(shù)發(fā)展的新的方案與模式,該分布大致符合無標(biāo)度網(wǎng)絡(luò)的度分布。目前,國際上已經(jīng)形成研究復(fù)雜性問題和復(fù)雜網(wǎng)絡(luò)的研究熱潮。而復(fù)雜網(wǎng)絡(luò)是研究復(fù)雜性問題的有力工具。自然界中存在著大量的復(fù)雜系統(tǒng),如internet網(wǎng)、計算機(jī)網(wǎng)絡(luò)、神經(jīng)系統(tǒng)、社會關(guān)系網(wǎng)絡(luò)等等,都可以通過復(fù)雜網(wǎng)絡(luò)進(jìn)行描述。通過研究這些復(fù)雜網(wǎng)絡(luò)的內(nèi)在機(jī)制和演化規(guī)律,從而找到網(wǎng)絡(luò)上的復(fù)雜行為與網(wǎng)絡(luò)結(jié)構(gòu)的關(guān)系,增加對復(fù)雜網(wǎng)絡(luò)系統(tǒng)的自然規(guī)律的認(rèn)識。 度分布是復(fù)雜網(wǎng)

46、絡(luò)問題中研究較多的一個方向。而且在網(wǎng)絡(luò)非常重要。5.1.3 ba網(wǎng)絡(luò)模擬 ba模型的兩個重要特性:1、增長特性:即網(wǎng)絡(luò)的規(guī)模是不斷擴(kuò)大的。例如每個月都會有大量的新的科研文章發(fā)表。2、有線連接特性:即新的節(jié)點(diǎn)更傾向于那些具有較高連接度的大節(jié)點(diǎn)相連接。這種現(xiàn)象也稱為“馬太效應(yīng)”。例如新發(fā)表的文章更傾向于引用一些已被廣泛引用的重要文獻(xiàn)。ba無標(biāo)度模型構(gòu)造算法:1、增長:從一個具有個節(jié)點(diǎn)的網(wǎng)絡(luò)開始,每次引入一個新的節(jié)點(diǎn),并且連到個已存在的節(jié)點(diǎn)上,這里。2、優(yōu)先連接:一個新節(jié)點(diǎn)與一個已經(jīng)存在的節(jié)點(diǎn)相連接的概率與節(jié)點(diǎn)的度、節(jié)點(diǎn)的度之間滿足如下關(guān)系: (5.2) 在經(jīng)過步后,這種算法產(chǎn)生一個有個節(jié)點(diǎn)、條邊的

47、網(wǎng)絡(luò)。圖5.2顯示了當(dāng)時的ba網(wǎng)絡(luò)的演化過程。初始網(wǎng)絡(luò)有兩個節(jié)點(diǎn),每次新增加的一個節(jié)點(diǎn)優(yōu)先連接機(jī)制與網(wǎng)絡(luò)中已存在的兩個節(jié)點(diǎn)相連。圖5.2 ba網(wǎng)絡(luò)演化過程圖%下面得到度分布與雙對數(shù)坐標(biāo)下的度分布。 并計算其度指數(shù)。a0size=length(degree_distribution);deg=1:1:a0size;num=degree_distribution;numsum=sum(num);num=num/numsum;figure;loglog(deg,num,+);xlabel(連接數(shù)(個));ylabel(結(jié)點(diǎn)數(shù)(個));title(雙對數(shù)坐標(biāo)系度分布曲線);hold on;% plot

48、_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 1 1250);gtext(lambda=,num2str(pdegree(1);l

49、egend(度分布曲線,擬和結(jié)果);圖5.3 ba模型度指數(shù)計算大量的實(shí)證研究表明,真實(shí)網(wǎng)絡(luò)幾乎都具有小世界效應(yīng),同時科學(xué)家還發(fā)現(xiàn)大量真實(shí)網(wǎng)絡(luò)的節(jié)點(diǎn)度服從冪率分布,這里某節(jié)點(diǎn)的度是指該節(jié)點(diǎn)擁有相鄰節(jié)點(diǎn)的數(shù)目,或者說與該節(jié)點(diǎn)關(guān)聯(lián)的邊的數(shù)目。節(jié)點(diǎn)度服從冪律分布就是說具有某個特定度的節(jié)點(diǎn)數(shù)目與這個特定的度之間的關(guān)系可以用一個冪函數(shù)近似地表示。冪函數(shù)曲線是一條下降相對緩慢的曲線,這使得度很大的節(jié)點(diǎn)可以在網(wǎng)絡(luò)中存在。對于隨機(jī)網(wǎng)絡(luò)和規(guī)則網(wǎng)絡(luò),故其平均度可以被看作其節(jié)點(diǎn)度的一個特征標(biāo)度。我們把節(jié)點(diǎn)度服從冪律分布的網(wǎng)絡(luò)叫做無標(biāo)度網(wǎng)絡(luò)(scale-free networks),并稱這種節(jié)點(diǎn)度的冪律分布為網(wǎng)絡(luò)的無

50、標(biāo)度特性。1999年,barabasi 和albert給出了構(gòu)造無標(biāo)度網(wǎng)絡(luò)的演化模型,他們所用的方法與price的方法是類似的。barabasi 和albert把真實(shí)系統(tǒng)通過自組織生成無標(biāo)度的網(wǎng)絡(luò)歸功于兩個主要因素:生長和優(yōu)先連接,而他們的網(wǎng)絡(luò)模型(ba網(wǎng)絡(luò))正是模擬這兩個關(guān)鍵機(jī)制設(shè)計的。5.2公交網(wǎng)絡(luò)的聚集性集群即集聚程度(clustering coefficient)的概念,就好比在社會網(wǎng)絡(luò)中總是存在熟人圈或朋友圈,其中每個成員都認(rèn)識其他成員。集聚程度的意義是網(wǎng)絡(luò)集團(tuán)化的程度;這是一種網(wǎng)絡(luò)的內(nèi)聚傾向。連通集團(tuán)概念反映的是一個大網(wǎng)絡(luò)中各集聚的小網(wǎng)絡(luò)分布和相互聯(lián)系的狀況。例如,它可以反映這個朋

51、友圈與另一個朋友圈的相互關(guān)系。復(fù)雜網(wǎng)絡(luò)的聚集性反映了當(dāng)代公交網(wǎng)絡(luò)在發(fā)展過程中的一些問題,以至與通過對其研究更好的來服務(wù)于公交網(wǎng)絡(luò)。 復(fù)雜網(wǎng)絡(luò)的研究,為我們提供了一種復(fù)雜性研究的新視角、新方法,并且提供了一種比較的視野??梢栽趶?fù)雜網(wǎng)絡(luò)研究的旗幟下,對各種復(fù)雜網(wǎng)絡(luò)進(jìn)行比較、研究和綜合概括。現(xiàn)實(shí)中的公交網(wǎng)絡(luò)也是復(fù)雜網(wǎng)絡(luò)的一種演變形式, 類的演化就是在給自己增加著的各種網(wǎng)絡(luò)的演化。人的存在方式就是技術(shù)的存在。人的“此在”就是“已在”的疊加、取代和更新,就是復(fù)雜網(wǎng)絡(luò)未來存在到演化的展開。5.3公交網(wǎng)絡(luò)平均最短路長度與聚類系數(shù)5.3.1 公交系統(tǒng)數(shù)據(jù)的采集 城市公共交通是城市整體發(fā)展中不可缺少的物質(zhì)條件和

52、基礎(chǔ)產(chǎn)業(yè),是解決城市交通擁堵問題和居民出行問題的有效手段。我國公交部門和交通學(xué)科研究人員也在公共交通領(lǐng)域內(nèi)進(jìn)行了很多研究,如公交線路網(wǎng)優(yōu)化、客流分配技術(shù)、站點(diǎn)規(guī)劃方法等,并取得了一定成果。為次,我們以杭州公交系統(tǒng)為基礎(chǔ)、根據(jù)公交網(wǎng)絡(luò)系統(tǒng)通過調(diào)查,取樣。采集了一部分杭州公交線路的數(shù)據(jù),以用來做為參考。5.3.2 快速公交網(wǎng)路和最短換成線路算法的定義快速公交系統(tǒng)(bus rapid transit)簡稱brt,是一種介于快速軌道交通(rapid rail transit,簡稱rrt)與常規(guī)公交(normal bus transit,簡稱nbt)之間的新型公共客運(yùn)系統(tǒng),是一種大運(yùn)量交通方式,通常也被

53、人稱作“地面上的地鐵系統(tǒng)”。它是利用現(xiàn)代化公交技術(shù)配合智能交通和運(yùn)營管理,開辟公交專用道路和建造新式公交車站,實(shí)現(xiàn)軌道交通運(yùn)營服務(wù),達(dá)到輕軌服務(wù)水準(zhǔn)的一種獨(dú)特的城市客運(yùn)系統(tǒng)。一個城市進(jìn)行基礎(chǔ)設(shè)施建設(shè)的核心思想,應(yīng)該是提高居民生活質(zhì)量和保護(hù)環(huán)境并重。發(fā)展建設(shè)公共交通系統(tǒng),可以順應(yīng)以上兩點(diǎn)需要。一個高效、可靠的公共交通系統(tǒng),通過減少小汽車的使用率、減緩交通擁堵,減少車輛污染物排放,降低能耗,以及大容量地集散乘客, 可以保護(hù)環(huán)境,節(jié)省自然資源,節(jié)約居民出行時間,保護(hù)公眾健康,刺激經(jīng)濟(jì)發(fā)展,降低對原油的依賴,促進(jìn)社會平等,維護(hù)城市和諧,加強(qiáng)社區(qū)凝聚力。最短線路換乘算法說白了就是在任何一個城市里,在到達(dá)

54、相同公交站點(diǎn),希望自己所乘線路為最短路徑,所需時間為最少的一種理想乘車途徑,它的具體算法如下車最短路經(jīng)算法:系統(tǒng)首先需要獲取各個站點(diǎn)的信息,也就是連接信息了,保存到文件系統(tǒng)中,站點(diǎn)就是圖的頂點(diǎn)了,連接信息就是邊了一般來說,這里面的圖我們應(yīng)該認(rèn)為是有向圖,因?yàn)楹芏嗲闆r下,一個公交線路是:a-b-c-d -e-f-a,這種情況只能采用有向圖。具體的算法:實(shí)際上乘客不一定要找最短,里面還涉及到換乘次數(shù)最少,費(fèi)用最少等問題,因此,邊向量的權(quán)值要分多種情況考慮,所以如果真的要開發(fā)實(shí)用的系統(tǒng)應(yīng)該給出多種最佳選擇,我們以通常意義上的最短路徑為例;可以采用教科書上的算法,但是需要注意的是,應(yīng)該保留經(jīng)過的邊,畢

55、竟結(jié)果需要顯示出來的。5.3.3 公交網(wǎng)絡(luò)的相關(guān)系數(shù) 通過研究公交網(wǎng)絡(luò)中各種不同線路之間的交叉關(guān)聯(lián),以真實(shí)的公交線路的各個站點(diǎn)數(shù)據(jù)時間序列計算不同站點(diǎn)之間的交叉關(guān)聯(lián)矩陣。并以站點(diǎn)交叉矩陣的矩陣元作為相應(yīng)站點(diǎn)之間的相互作用快慢,構(gòu)造站點(diǎn)之間的加權(quán)網(wǎng)絡(luò)。我們將研究這一公交公司加權(quán)網(wǎng)絡(luò)的連接度分布特征,從而揭示對于實(shí)際的公交網(wǎng)絡(luò)系統(tǒng)價格的波動,不同車次究竟起多大的影響程度,以及他們彼此之間又是如何地相互影響。我們利用前面介紹的公交線路模型對杭州車次幾天數(shù)據(jù)進(jìn)行處理。我們定義每個車次作為一個點(diǎn)。然后求出更多車次每天的各個站點(diǎn)數(shù)據(jù)。如下圖(5.4)圖5.4相關(guān)系數(shù)分布圖5.4結(jié)果分析5.4.1外界因素對

56、公交網(wǎng)絡(luò)的影響 對于公交市場,外部經(jīng)濟(jì)環(huán)境對公交系統(tǒng)也起著很大的影響??紤]到金融危機(jī),通貨膨脹指數(shù),油價和時間等外界因素,為提取公交價格變化中關(guān)聯(lián)的內(nèi)在性質(zhì),必須考慮第公司在時刻線路價格相對于所考慮公交系統(tǒng)所有車次價格在時刻平均值的相對漲落。 對公交系統(tǒng)數(shù)據(jù)的處理重新計算后,公交網(wǎng)絡(luò)的度分布數(shù)最小,度分布數(shù)最大都可以得出。其峰值為7.5左右,比模型修正前的峰值更為符合現(xiàn)實(shí)情況。市現(xiàn)實(shí)中比較冪律分布表現(xiàn)為一條斜率為冪指數(shù)的負(fù)數(shù)的直線,這一線性關(guān)系是判斷給定的實(shí)例中隨機(jī)變量是否滿足冪律的依據(jù)。實(shí)際上,冪律分布廣泛存在于物理學(xué),地球與行星科學(xué),計算機(jī)科學(xué),生物學(xué),生態(tài)學(xué)。如下圖(5.5)圖5.5 度分布圖5.4.2閾值的調(diào)節(jié) 在不同的閾值下,計算公交網(wǎng)絡(luò)站點(diǎn)的度分布情況,其度分布圖(圖5.6)圖5.6 度分布圖國際上已經(jīng)形成研究復(fù)雜性問題和

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論