复杂网络数学建模与交通流

复杂网络数学建模与交通流第1页/共71页ChapterI复杂网络演化机制第2页/共71页复杂网络研究现状概述国内的情况什么是网络？典型网络的主要统计特征与物理意义更加深入细致的统计特性重要的模型介绍复杂网络上的数学模型Outline第3页/共71页第4页/共71页第5页/共71页第6页/共71页第7页/共71页第8页/共71页陈关荣＋范正平＋流动访问学者（香港城市大学）汪小帆＋李翔＋方锦清＋吕金虎（上交，中科院）何大韧（扬州大学）*狄增如＋樊瑛＋郑志刚＋李梦辉（北师大）*李春光＋张洪斌（电子科大）朱陈平＋古志鸣（南航）*马志明＋耿显明（中科院，南航）许伯铭＋K.P.Chan（香港中文大学）*朱建阳＋朱涵（北师大，南大）史定华（上海大学）章忠志（大连理工）*刘宗华（华东师范）蔡勖（华中师范）国内主要研究小组第9页/共71页什么是网络第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页网络最基本的几个概念i节点的度ki＝5簇系数(clusteringcoefficient):朋友之间相互是朋友的概率节点簇系数Ci＝2/10=0.2j距离？dij=3第19页/共71页规则网络大的簇系数大的平均距离单点度分布有限维晶格网络，超立方体网络等等J.-M.Xu,TopologicalStructureandAnalysisofInterconnectionNetwork,KluwerAcademic,Dordrecht,2001.第20页/共71页随机网络小的簇系数小的平均距离泊松分布第21页/共71页Watts-Strogatz网络以很小的概率p断键重连簇系数依然很大平均距离变得很小指数分布D.J.WattsandS.H.Strogatz,NatureLondon

393,440,1998.M.E.J.NewmanandD.J.Watts,Phys.Lett.A263,341,1999.第22页/共71页Barabasi-Albert网络每个时步增加一个节点每个节点按线性偏好连接Power-law度分布P(k)

~

k^{-γ}短的平均距离小的簇系数(lnN)^2/NA.-L.BarabásiandR.Albert,Science286,5091999.第23页/共71页各种网络主要拓扑特征一览平均距离簇系数度分布规则网络大大Delta函数ER随机网络小小泊松分布WS小世界网络小大指数分布BA无标度网络小小幂率分布部分真实网络小大近似幂率分布第24页/共71页Question1如何构造同时满足三个统计特性的简单优美的网络模型第25页/共71页更加深入细致的统计特性第26页/共71页度-度相关性度很大的节点到底是倾向于和度大的节点相连还是和度小的节点相连？正相关负相关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为什么社会网络是正相关，而技术生物网络是负相关的？如何构建正相关的无标度网络？第30页/共71页簇-度相关性好莱坞演员网络英文单词网络在只有拓扑的网络中，簇度往往是负相关的；在考虑几何的网络中，簇度往往是不相关的。E.RavaszandA.-LBarabasi,Phys.Rev.E67,026112(2003)第31页/共71页Question3几何性质与簇度相关性之间的关系到底是什么第32页/共71页网络中的群落（community）M.GirvanandM.E.J.Newman,PNAS99,7821(2002)第33页/共71页第34页/共71页Question4网络中群落结构的形成是外生原因还是内生原因，如果是内生原因，这个机制到底是什么？第35页/共71页超家族分类定点强度（strength）幂率分布Strength-Degree幂率相关性后代规模分布合作规模分布定点项目度分布与度分布的一致性问题特征值谱……其他第36页/共71页Krapivsky非线性BA模型Holme-Kim可调簇系数模型Klemm高集聚网络模型Dorogovtsev-Mendes老化网络模型Sen距离偏好模型BBV含权网络模型等等等等等等等等等等等等一些著名的模型第37页/共71页Holme-Kim可调簇系数模型在优先连接的同时以一定的概率连接被选中节点的邻居节点度分布依然是幂指数为-3的幂率分布簇系数变得很大（解析结果PRE67,056102）平均距离依然很小P.HolmeandB.J.Kim,Phys.Rev.E65,0661092002.第38页/共71页第39页/共71页Dorogovtsev-Mendes老化网络模型老化：真实网络中不可避免的现象KlemmKandEguiluzVM2002Phys.Rev.E65036123第40页/共71页老化模型的基本框架——连接概率不仅与节点的度k有关，还与节点的年龄有关不考虑年龄则退化为BA模型。不同的模型有不同的老化函数

其中最有名的是DMDorogovtsevSNandMendesJFF2000Phys.Rev.E621842第41页/共71页参数取值范围幂指数0230131指数分布，链状结构第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主要的有关老化网络的文献第43页/共71页Sen距离偏好模型在很多实际网络中，距离因素是必须考虑的，例如Internet和电力网等BA模型Sen模型S.S.MannaandP.Sen,Phys.Rev.E66,066114(2002)S.S.Manna,G.MukherjeeandP.Sen,Phys.Rev.E69,017102(2004)主要结论：存在一个阈值，当大于该值时度分布是幂率的，反之度分布是指数的。第44页/共71页第45页/共71页整数网络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握手模型含权合作网络自组织无标度网络高聚簇无标度的多样性网络……我自己的一些工作第46页/共71页整数网络模型规则：1到N之间的合数，如果有整除关系就连一条边，只考虑最大连通分支N＝30的情况，最大连通分支有15个节点和19条边第47页/共71页簇系数比BA网络大，且随着N的变化是稳定的，大约在0.34左右度分布是由指数为2的幂率分布（出度）和乱七八糟单的分布（入度）组合而成，数值上可以看作近似与指数2.4的幂率直径有一个常数上界！！！！簇度相关性C(k)～1/k主要结论第48页/共71页第49页/共71页第50页/共71页第51页/共71页很简单，没有超过高中的数学毕达哥拉斯的理念既是模型又是实证直径的常数上界——一个新的网络类环与理想，各种各样的数学对象有意思的地方第52页/共71页随机阿波罗网络第53页/共71页ChapterII复杂网络上的交通问题第54页/共71页传播动力学（SIR,SIS,SI……）网络同步与控制自旋相互作用（Iring,XY临界模型）级联动力学交通流与信息流网络导航网络上的博弈问题（囚徒博弈、争当少数者博弈，退出者博弈……）……动力学问题第55页/共71页复杂网络上的交通流第56页/共71页交通流理论，已经在自然科学与经济社会的许多领域，特别是公路网上的车辆流问题和计算机互联网上的信息流问题上，有着广泛而深入的应用。近年来关于复杂网络方面的研究表明，计算机互联网具有无标度特性，不能用简单的规则网络模型或ER随机网络模型模拟。因此，讨论网络拓扑结构对其上交通动力学行为的影响是非常有意义的。第57页/共71页交通是指人,物以及思想,信息的地点间移动.因此交通流的研究对象是广泛的!交通流研究可以属于广义传播范畴,它包括信息流,粒子流,车辆流,颗粒流等等.物理学家感兴趣的部分包括:交通系统的动力学行为:相变与自组织临界性.灾难救援与疏散策略.交通系统性能优化等等.什么是交通流第58页/共71页每时步产生R个粒子每个粒子有一个起点和终点（随机），粒子到终点后被删除路由表固定每个节点的单位时间的传输能力是有限的（考虑节点全同性网络，即所有节点的相等，这里不妨设为1）模型第59页/共71页第60页/共71页第61页/共71