復(fù)雜網(wǎng)絡(luò)數(shù)學(xué)建模與交通流

復(fù)雜網(wǎng)絡(luò)數(shù)學(xué)建模與交通流第1頁(yè)/共71頁(yè)ChapterI復(fù)雜網(wǎng)絡(luò)演化機(jī)制第2頁(yè)/共71頁(yè)復(fù)雜網(wǎng)絡(luò)研究現(xiàn)狀概述國(guó)內(nèi)的情況什么是網(wǎng)絡(luò)？典型網(wǎng)絡(luò)的主要統(tǒng)計(jì)特征與物理意義更加深入細(xì)致的統(tǒng)計(jì)特性重要的模型介紹復(fù)雜網(wǎng)絡(luò)上的數(shù)學(xué)模型Outline第3頁(yè)/共71頁(yè)第4頁(yè)/共71頁(yè)第5頁(yè)/共71頁(yè)第6頁(yè)/共71頁(yè)第7頁(yè)/共71頁(yè)第8頁(yè)/共71頁(yè)陳關(guān)榮＋范正平＋流動(dòng)訪問(wèn)學(xué)者（香港城市大學(xué)）汪小帆＋李翔＋方錦清＋呂金虎（上交，中科院）何大韌（揚(yáng)州大學(xué)）*狄增如＋樊瑛＋鄭志剛＋李夢(mèng)輝（北師大）*李春光＋張洪斌（電子科大）朱陳平＋古志鳴（南航）*馬志明＋耿顯明（中科院，南航）許伯銘＋K.P.Chan（香港中文大學(xué)）*朱建陽(yáng)＋朱涵（北師大，南大）史定華（上海大學(xué)）章忠志（大連理工）*劉宗華（華東師范）蔡勖（華中師范）國(guó)內(nèi)主要研究小組第9頁(yè)/共71頁(yè)什么是網(wǎng)絡(luò)第10頁(yè)/共71頁(yè)ComplexNetworkExample:

Internet

(WilliamR.Cheswick)第11頁(yè)/共71頁(yè)ComplexNetworkExample:WWW

(K.C.Claffy)第12頁(yè)/共71頁(yè)ComplexNetworkExample:TelecommNetworks

(StephenG.Eick)第13頁(yè)/共71頁(yè)

ComplexNetworkExample:RoutesofAirlines

第14頁(yè)/共71頁(yè)ComplexNetworkExample:VLSICircuits,CNN第15頁(yè)/共71頁(yè)ComplexNetworkExample:BiologicalNetworks第16頁(yè)/共71頁(yè)ComplexNetworkExample:Arts

第17頁(yè)/共71頁(yè)第18頁(yè)/共71頁(yè)網(wǎng)絡(luò)最基本的幾個(gè)概念i節(jié)點(diǎn)的度ki＝5簇系數(shù)(clusteringcoefficient):朋友之間相互是朋友的概率節(jié)點(diǎn)簇系數(shù)Ci＝2/10=0.2j距離？dij=3第19頁(yè)/共71頁(yè)規(guī)則網(wǎng)絡(luò)大的簇系數(shù)大的平均距離單點(diǎn)度分布有限維晶格網(wǎng)絡(luò)，超立方體網(wǎng)絡(luò)等等J.-M.Xu,TopologicalStructureandAnalysisofInterconnectionNetwork,KluwerAcademic,Dordrecht,2001.第20頁(yè)/共71頁(yè)隨機(jī)網(wǎng)絡(luò)小的簇系數(shù)小的平均距離泊松分布第21頁(yè)/共71頁(yè)Watts-Strogatz網(wǎng)絡(luò)以很小的概率p斷鍵重連簇系數(shù)依然很大平均距離變得很小指數(shù)分布D.J.WattsandS.H.Strogatz,NatureLondon

393,440,1998.M.E.J.NewmanandD.J.Watts,Phys.Lett.A263,341,1999.第22頁(yè)/共71頁(yè)Barabasi-Albert網(wǎng)絡(luò)每個(gè)時(shí)步增加一個(gè)節(jié)點(diǎn)每個(gè)節(jié)點(diǎn)按線性偏好連接Power-law度分布P(k)

~

k^{-γ}短的平均距離小的簇系數(shù)(lnN)^2/NA.-L.BarabásiandR.Albert,Science286,5091999.第23頁(yè)/共71頁(yè)各種網(wǎng)絡(luò)主要拓?fù)涮卣饕挥[平均距離簇系數(shù)度分布規(guī)則網(wǎng)絡(luò)大大Delta函數(shù)ER隨機(jī)網(wǎng)絡(luò)小小泊松分布WS小世界網(wǎng)絡(luò)小大指數(shù)分布BA無(wú)標(biāo)度網(wǎng)絡(luò)小小冪率分布部分真實(shí)網(wǎng)絡(luò)小大近似冪率分布第24頁(yè)/共71頁(yè)Question1如何構(gòu)造同時(shí)滿足三個(gè)統(tǒng)計(jì)特性的簡(jiǎn)單優(yōu)美的網(wǎng)絡(luò)模型第25頁(yè)/共71頁(yè)更加深入細(xì)致的統(tǒng)計(jì)特性第26頁(yè)/共71頁(yè)度-度相關(guān)性度很大的節(jié)點(diǎn)到底是傾向于和度大的節(jié)點(diǎn)相連還是和度小的節(jié)點(diǎn)相連？正相關(guān)負(fù)相關(guān)M.E.J.Newman,Phys.Rev.Lett.87,208701(2002)第27頁(yè)/共71頁(yè)第28頁(yè)/共71頁(yè)W.-X.Wang,B.Hu,T.Zhou,B.-H.WangandY.-B.Xie,arXiv:cond-mat/0504062(submittedtoPhys.Rev.E)第29頁(yè)/共71頁(yè)Question2為什么社會(huì)網(wǎng)絡(luò)是正相關(guān)，而技術(shù)生物網(wǎng)絡(luò)是負(fù)相關(guān)的？如何構(gòu)建正相關(guān)的無(wú)標(biāo)度網(wǎng)絡(luò)？第30頁(yè)/共71頁(yè)簇-度相關(guān)性好萊塢演員網(wǎng)絡(luò)英文單詞網(wǎng)絡(luò)在只有拓?fù)涞木W(wǎng)絡(luò)中，簇度往往是負(fù)相關(guān)的；在考慮幾何的網(wǎng)絡(luò)中，簇度往往是不相關(guān)的。E.RavaszandA.-LBarabasi,Phys.Rev.E67,026112(2003)第31頁(yè)/共71頁(yè)Question3幾何性質(zhì)與簇度相關(guān)性之間的關(guān)系到底是什么第32頁(yè)/共71頁(yè)網(wǎng)絡(luò)中的群落（community）M.GirvanandM.E.J.Newman,PNAS99,7821(2002)第33頁(yè)/共71頁(yè)第34頁(yè)/共71頁(yè)Question4網(wǎng)絡(luò)中群落結(jié)構(gòu)的形成是外生原因還是內(nèi)生原因，如果是內(nèi)生原因，這個(gè)機(jī)制到底是什么？第35頁(yè)/共71頁(yè)超家族分類(lèi)定點(diǎn)強(qiáng)度（strength）冪率分布Strength-Degree冪率相關(guān)性后代規(guī)模分布合作規(guī)模分布定點(diǎn)項(xiàng)目度分布與度分布的一致性問(wèn)題特征值譜……其他第36頁(yè)/共71頁(yè)Krapivsky非線性BA模型Holme-Kim可調(diào)簇系數(shù)模型Klemm高集聚網(wǎng)絡(luò)模型Dorogovtsev-Mendes老化網(wǎng)絡(luò)模型Sen距離偏好模型BBV含權(quán)網(wǎng)絡(luò)模型等等等等等等等等等等等等一些著名的模型第37頁(yè)/共71頁(yè)Holme-Kim可調(diào)簇系數(shù)模型在優(yōu)先連接的同時(shí)以一定的概率連接被選中節(jié)點(diǎn)的鄰居節(jié)點(diǎn)度分布依然是冪指數(shù)為-3的冪率分布簇系數(shù)變得很大（解析結(jié)果PRE67,056102）平均距離依然很小P.HolmeandB.J.Kim,Phys.Rev.E65,0661092002.第38頁(yè)/共71頁(yè)第39頁(yè)/共71頁(yè)Dorogovtsev-Mendes老化網(wǎng)絡(luò)模型老化：真實(shí)網(wǎng)絡(luò)中不可避免的現(xiàn)象KlemmKandEguiluzVM2002Phys.Rev.E65036123第40頁(yè)/共71頁(yè)老化模型的基本框架——連接概率不僅與節(jié)點(diǎn)的度k有關(guān)，還與節(jié)點(diǎn)的年齡有關(guān)不考慮年齡則退化為BA模型。不同的模型有不同的老化函數(shù)

其中最有名的是DMDorogovtsevSNandMendesJFF2000Phys.Rev.E621842第41頁(yè)/共71頁(yè)參數(shù)取值范圍冪指數(shù)0230131指數(shù)分布，鏈狀結(jié)構(gòu)第42頁(yè)/共71頁(yè)AmaralLAN,ScalaA,BarthelemyMandStanleyHE2000Proc.Natl.Acad.Sci.U.S.A.9711149KlemmKandEguiluzVM2002Phys.Rev.E65036123ZhuH,WangXRandZhuJY2003Phys.Rev.E68056121DorogovtsevSNandMendesJFF2000Phys.Rev.E621842JiangPQ,WangBH,ZhouTetal,2005Chin.Phys.Lett.221285主要的有關(guān)老化網(wǎng)絡(luò)的文獻(xiàn)第43頁(yè)/共71頁(yè)Sen距離偏好模型在很多實(shí)際網(wǎng)絡(luò)中，距離因素是必須考慮的，例如Internet和電力網(wǎng)等BA模型Sen模型S.S.MannaandP.Sen,Phys.Rev.E66,066114(2002)S.S.Manna,G.MukherjeeandP.Sen,Phys.Rev.E69,017102(2004)主要結(jié)論：存在一個(gè)閾值，當(dāng)大于該值時(shí)度分布是冪率的，反之度分布是指數(shù)的。第44頁(yè)/共71頁(yè)第45頁(yè)/共71頁(yè)整數(shù)網(wǎng)絡(luò)T.Zhouetal,arXiv:cond-mat/0405258合作網(wǎng)絡(luò)模型T.Zhou,Y.-D.Jinetal,arXiv:cond-mat/0502253隨機(jī)阿波羅網(wǎng)絡(luò)與單純形網(wǎng)絡(luò)T.Zhou,etal,Phys.Rev.E71,046141T.Zhou,G.Yan,etal,arXiv:cond-mat/0409414Z.-M.Gu,T.Zhou,etal,arXiv:cond-mat/0505175生長(zhǎng)老化模型P.-Q.Jiang,B.-H.Wang,T.Zhou,etal,Chin.Phys.Lett.221285握手模型含權(quán)合作網(wǎng)絡(luò)自組織無(wú)標(biāo)度網(wǎng)絡(luò)高聚簇?zé)o標(biāo)度的多樣性網(wǎng)絡(luò)……我自己的一些工作第46頁(yè)/共71頁(yè)整數(shù)網(wǎng)絡(luò)模型規(guī)則：1到N之間的合數(shù)，如果有整除關(guān)系就連一條邊，只考慮最大連通分支N＝30的情況，最大連通分支有15個(gè)節(jié)點(diǎn)和19條邊第47頁(yè)/共71頁(yè)簇系數(shù)比BA網(wǎng)絡(luò)大，且隨著N的變化是穩(wěn)定的，大約在0.34左右度分布是由指數(shù)為2的冪率分布（出度）和亂七八糟單的分布（入度）組合而成，數(shù)值上可以看作近似與指數(shù)2.4的冪率直徑有一個(gè)常數(shù)上界?。。?！簇度相關(guān)性C(k)～1/k主要結(jié)論第48頁(yè)/共71頁(yè)第49頁(yè)/共71頁(yè)第50頁(yè)/共71頁(yè)第51頁(yè)/共71頁(yè)很簡(jiǎn)單，沒(méi)有超過(guò)高中的數(shù)學(xué)畢達(dá)哥拉斯的理念既是模型又是實(shí)證直徑的常數(shù)上界——一個(gè)新的網(wǎng)絡(luò)類(lèi)環(huán)與理想，各種各樣的數(shù)學(xué)對(duì)象有意思的地方第52頁(yè)/共71頁(yè)隨機(jī)阿波羅網(wǎng)絡(luò)第53頁(yè)/共71頁(yè)ChapterII復(fù)雜網(wǎng)絡(luò)上的交通問(wèn)題第54頁(yè)/共71頁(yè)傳播動(dòng)力學(xué)（SIR,SIS,SI……）網(wǎng)絡(luò)同步與控制自旋相互作用（Iring,XY臨界模型）級(jí)聯(lián)動(dòng)力學(xué)交通流與信息流網(wǎng)絡(luò)導(dǎo)航網(wǎng)絡(luò)上的博弈問(wèn)題（囚徒博弈、爭(zhēng)當(dāng)少數(shù)者博弈，退出者博弈……）……動(dòng)力學(xué)問(wèn)題第55頁(yè)/共71頁(yè)復(fù)雜網(wǎng)絡(luò)上的交通流第56頁(yè)/共71頁(yè)交通流理論，已經(jīng)在自然科學(xué)與經(jīng)濟(jì)社會(huì)的許多領(lǐng)域，特別是公路網(wǎng)上的車(chē)輛流問(wèn)題和計(jì)算機(jī)互聯(lián)網(wǎng)上的信息流問(wèn)題上，有著廣泛而深入的應(yīng)用。近年來(lái)關(guān)于復(fù)雜網(wǎng)絡(luò)方面的研究表明，計(jì)算機(jī)互聯(lián)網(wǎng)具有無(wú)標(biāo)度特性，不能用簡(jiǎn)單的規(guī)則網(wǎng)絡(luò)模型或ER隨機(jī)網(wǎng)絡(luò)模型模擬。因此，討論網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)對(duì)其上交通動(dòng)力學(xué)行為的影響是非常有意義的。第57頁(yè)/共71頁(yè)交通是指人,物以及思想,信息的地點(diǎn)間移動(dòng).因此交通流的研究對(duì)象是廣泛的!交通流研究可以屬于廣義傳播范疇,它包括信息流,粒子流,車(chē)輛流,顆粒流等等.物理學(xué)家感興趣的部分包括:交通系統(tǒng)的動(dòng)力學(xué)行為:相變與自組織臨界性.災(zāi)難救援與疏散策略.交通系統(tǒng)性能優(yōu)化等等.什么是交通流第58頁(yè)/共71頁(yè)每時(shí)步產(chǎn)生R個(gè)粒子每個(gè)粒子有一個(gè)起點(diǎn)和終點(diǎn)（隨機(jī)），粒子到終點(diǎn)后被刪除路由表固定每個(gè)節(jié)點(diǎn)的單位時(shí)間的傳輸能力是有限的（考慮節(jié)點(diǎn)全同性網(wǎng)絡(luò)，即所有節(jié)點(diǎn)的相等，這里不妨設(shè)為1）模型第59頁(yè)/共71頁(yè)第60頁(yè)/共71頁(yè)第61頁(yè)/共71