复杂网络环境下交通流.ppt

复杂网络环境交通流,ChapterI,复杂网络演化机制,Outline,复杂网络研究现状概述国内的情况什么是网络？典型网络的主要统计特征与物理意义更加深入细致的统计特性重要的模型介绍复杂网络上的数学模型,国内主要研究小组,陈关荣范正平流动访问学者（香港城市大学）汪小帆李翔方锦清吕金虎（上交，中科院）何大韧（扬州大学）*狄增如樊瑛郑志刚李梦辉（北师大）*李春光张洪斌（电子科大）朱陈平古志鸣（南航）*马志明耿显明（中科院，南航）许伯铭K.P.Chan（香港中文大学）*朱建阳朱涵（北师大，南大）史定华（上海大学）章忠志（大连理工）*刘宗华（华东师范）蔡勖（华中师范）,什么是网络,ComplexNetworkExample:Internet(WilliamR.Cheswick),ComplexNetworkExample:WWW(K.C.Claffy),ComplexNetworkExample:TelecommNetworks(StephenG.Eick),ComplexNetworkExample:RoutesofAirlines,ComplexNetworkExample:VLSICircuits,CNN,ComplexNetworkExample:BiologicalNetworks,ComplexNetworkExample:Arts,网络最基本的几个概念,i,节点的度ki5,簇系数(clusteringcoefficient):朋友之间相互是朋友的概率,节点簇系数Ci2/10=0.2,j,距离？,dij=3,规则网络,大的簇系数,大的平均距离,单点度分布,有限维晶格网络，超立方体网络等等,J.-M.Xu,TopologicalStructureandAnalysisofInterconnectionNetwork,KluwerAcademic,Dordrecht,2001.,随机网络,小的簇系数,小的平均距离,泊松分布,Watts-Strogatz网络,以很小的概率p断键重连,簇系数依然很大,平均距离变得很小,指数分布,D.J.WattsandS.H.Strogatz,NatureLondon393,440,1998.M.E.J.NewmanandD.J.Watts,Phys.Lett.A263,341,1999.,Barabasi-Albert网络,每个时步增加一个节点,每个节点按线性偏好连接,Power-law度分布,P(k)k-,短的平均距离,小的簇系数(lnN)2/N,A.-L.BarabsiandR.Albert,Science286,5091999.,各种网络主要拓扑特征一览,Question1,如何构造同时满足三个统计特性的简单优美的网络模型,更加深入细致的统计特性,度-度相关性,度很大的节点到底是倾向于和度大的节点相连还是和度小的节点相连？,正相关,负相关,M.E.J.Newman,Phys.Rev.Lett.87,208701(2002),W.-X.Wang,B.Hu,T.Zhou,B.-H.WangandY.-B.Xie,arXiv:cond-mat/0504062(submittedtoPhys.Rev.E),Question2,为什么社会网络是正相关，而技术生物网络是负相关的？如何构建正相关的无标度网络？,簇-度相关性,好莱坞演员网络,英文单词网络,在只有拓扑的网络中，簇度往往是负相关的；在考虑几何的网络中，簇度往往是不相关的。,E.RavaszandA.-LBarabasi,Phys.Rev.E67,026112(2003),Question3,几何性质与簇度相关性之间的关系到底是什么,网络中的群落（community）,M.GirvanandM.E.J.Newman,PNAS99,7821(2002),Question4,网络中群落结构的形成是外生原因还是内生原因，如果是内生原因，这个机制到底是什么？,其他,超家族分类定点强度（strength）幂率分布Strength-Degree幂率相关性后代规模分布合作规模分布定点项目度分布与度分布的一致性问题特征值谱,一些著名的模型,Krapivsky非线性BA模型Holme-Kim可调簇系数模型Klemm高集聚网络模型Dorogovtsev-Mendes老化网络模型Sen距离偏好模型BBV含权网络模型等等等等等等等等等等等等,Holme-Kim可调簇系数模型,在优先连接的同时以一定的概率连接被选中节点的邻居,节点度分布依然是幂指数为-3的幂率分布,簇系数变得很大（解析结果PRE67,056102）,平均距离依然很小,P.HolmeandB.J.Kim,Phys.Rev.E65,0661092002.,Dorogovtsev-Mendes老化网络模型,老化：真实网络中不可避免的现象,KlemmKandEguiluzVM2002Phys.Rev.E65036123,老化模型的基本框架连接概率不仅与节点的度k有关，还与节点的年龄有关,不考虑年龄则退化为BA模型。不同的模型有不同的老化函数其中最有名的是DM,DorogovtsevSNandMendesJFF2000Phys.Rev.E621842,主要的有关老化网络的文献,AmaralLAN,ScalaA,BarthelemyMandStanleyHE2000Proc.Natl.Acad.Sci.U.S.A.9711149KlemmKandEguiluzVM2002Phys.Rev.E65036123ZhuH,WangXRandZhuJY2003Phys.Rev.E68056121DorogovtsevSNandMendesJFF2000Phys.Rev.E621842JiangPQ,WangBH,ZhouTetal,2005Chin.Phys.Lett.221285,Sen距离偏好模型,在很多实际网络中，距离因素是必须考虑的，例如Internet和电力网等,BA模型,Sen模型,S.S.MannaandP.Sen,Phys.Rev.E66,066114(2002)S.S.Manna,G.MukherjeeandP.Sen,Phys.Rev.E69,017102(2004),主要结论：存在一个阈值，当大于该值时度分布是幂率的，反之度分布是指数的。,我自己的一些工作,整数网络T.Zhouetal,arXiv:cond-mat/0405258合作网络模型T.Zhou,Y.-D.Jinetal,arXiv:cond-mat/0502253随机阿波罗网络与单纯形网络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握手模型含权合作网络自组织无标度网络高聚簇无标度的多样性网络,整数网络模型,规则：1到N之间的合数，如果有整除关系就连一条边，只考虑最大连通分支,N30的情况，最大连通分支有15个节点和19条边,主要结论,簇系数比BA网络大，且随着N的变化是稳定的，大约在0.34左右度分布是由指数为2的幂率分布（出度）和乱七八糟单的分布（入度）组合而成，数值上可以看作近似与指数2.4的幂率直径有一个常数上界！簇度相关性C(k)1/k,有意思的地方,很简单，没有超过高中的数学毕达哥拉斯的理念既是模型又是实证直径的常数上界一个新的网络类环与理想，各种各样的数学对象,随机阿波罗网络,ChapterII,复杂网络上的交通问题,动力学问题,传播动力学（SIR,SIS,SI）网络同步与控制自旋相互作用（Iring,XY临界模型）级联动力学交通流与信息流网络导航网络上的博弈问题（囚徒博弈、争当少数者博弈，退出者博弈）,复杂网络上的交通流,交通流理论，已经在自然科学与经济社会的许多领域，特别是公路网上的车辆流问题和计算机互联网上的信息流问题上，有着广泛而深入的应用。近年来关于复杂网络方面的研究表明，计算机互联网具有无标度特性，不能用简单的规则网络模型或ER随机网络模型模拟。因此，讨论网络拓扑结构对其上交通动力学行为的影响是非常有意义的。,什么是交通流,交通是指人,物以及思想,信息的地点间移动.因此交通流的研究对象是广泛的!交通流研究可以属于广义传播范畴,它包括信息流,粒子流,车辆流,颗粒流等等.物理学家感兴趣的部分包括:交通系统的动力学行为:相变与自组织临界性.灾难救援与疏散策略.交通系统性能优化等等.,模型,每时步产生R个粒子每个粒子有一个起点和终点（随机），粒子到终点后被删除路由表固定每个节点的单位时间的传输能力是有限的（考虑节点全同性网络，即所有节点的相等，这里不妨设为1）,Rc网络吞吐量,提高网络吞吐量的办法,提高节点的处理能力（周涛）重新分配节点的处理能力（周涛）有效路由（严钢）G.Yan,T.Zhou,etal,arXiv:cond-mat/0505366分布式动态寻路（王文旭）,