復雜網(wǎng)絡數(shù)學建模與交通流

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

Internet

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

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

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

ComplexNetworkExample:RoutesofAirlines

第14頁/共71頁ComplexNetworkExample:VLSICircuits,CNN第15頁/共71頁ComplexNetworkExample:BiologicalNetworks第16頁/共71頁ComplexNetworkExample:Arts

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

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

~

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

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