网络数学建模与交通流

复杂网络数学建模与交通流周涛中国科技大学，近代物理系ChapterI复杂网络演化机制Outline•复杂网络研究现状概述•国内的情况•什么是网络？•典型网络的主要统计特征与物理意义•更加深入细致的统计特性•重要的模型介绍•复杂网络上的数学模型国内主要研究小组•陈关荣＋范正平＋流动访问学者（香港城市大学）•汪小帆＋李翔＋方锦清＋吕金虎（上交，中科院）•何大韧（扬州大学）*•狄增如＋樊瑛＋郑志刚＋李梦辉（北师大）*•李春光＋张洪斌（电子科大）•朱陈平＋古志鸣（南航）*•马志明＋耿显明（中科院，南航）•许伯铭＋K.P.Chan（香港中文大学）*•朱建阳＋朱涵（北师大，南大）•史定华（上海大学）•章忠志（大连理工）*•刘宗华（华东师范）•蔡勖（华中师范）什么是网络ComplexNetworkExample:Internet(WilliamR.Cheswick)ComplexNetworkExample:(K.C.Claffy)ComplexNetworkExample:TelecommNetworks(StephenG.Eick)ComplexNetworkExample:RoutesofAirlinesComplexNetworkExample:VLSICircuits,CNNComplexNetworkExample:BiologicalNetworksComplexNetworkExample:Arts网络最基本的几个概念i节点的度ki＝5簇系数(clusteringcoefficient):朋友之间相互是朋友的概率节点簇系数Ci＝2/10=0.2j距离？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/NA.-L.BarabásiandR.Albert,Science286,5091999.各种网络主要拓扑特征一览平均距离簇系数度分布规则网络大大Delta函数ER随机网络小小泊松分布WS小世界网络小大指数分布BA无标度网络小小幂率分布部分真实网络小大近似幂率分布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模型。不同的模型有不同的老化函数其中最有名的是DMDorogovtsevSNandMendesJFF2000Phys.Rev.E621842参数取值范围幂指数0230131指数分布，链状结构主要的有关老化网络的文献•AmaralLAN,ScalaA,BarthelemyMandStanleyHE2000Proc.Natl.Acad.Sci.U.S.A.9711149•KlemmKandEguiluzVM2002Phys.Rev.E65036123•ZhuH,WangXRandZhuJY2003Phys.Rev.E68056121•DorogovtsevSNandMendesJFF2000Phys.Rev.E621842•JiangPQ,WangBH,ZhouTetal,2005Chin.Phys.Lett.221285Sen距离偏好模型在很多实际网络中，距离因素是必须考虑的，例如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之间的合数，如果有整除关系就连一条边，只考虑最大连通分支N＝30的情况，最大连通分支有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•分布式动态寻路（王文旭）谢谢