网络数学建模与交通流

1、 复杂网络数学建模与交通流周 涛 中国科技大学，近代物理系 Chapter I复杂网络演化机制Outline 复杂网络研究现状概述 国内的情况 什么是网络？ 典型网络的主要统计特征与物理意义 更加深入细致的统计特性 重要的模型介绍 复杂网络上的数学模型国内主要研究小组 陈关荣范正平流动访问学者（香港城市大学） 汪小帆李翔方锦清吕金虎（上交，中科院） 何大韧（扬州大学）* 狄增如樊瑛郑志刚李梦辉（北师大）* 李春光张洪斌（电子科大） 朱陈平古志鸣（南航）* 马志明耿显明（中科院，南航） 许伯铭K. P. Chan（香港中文大学）* 朱建阳朱涵（北师大，南大） 史定华（上海大学） 章忠志（大连理工

2、）* 刘宗华（华东师范） 蔡勖（华中师范）(William R. Cheswick)(Stephen G. Eick)网络最基本的几个概念i节点的度节点的度ki5簇系数簇系数(clustering coefficient): 朋友之间相互是朋友的概率朋友之间相互是朋友的概率节点簇系数节点簇系数Ci2/10=0.2j距离？距离？dij=3规则网络大的簇系数大的簇系数大的平均距大的平均距离离单点度分布单点度分布有限维晶格网络，超立方体网络等等有限维晶格网络，超立方体网络等等J.-M. Xu, Topological Structure and Analysis of Interconnection

3、Network, Kluwer Academic, Dordrecht, 2001.随随 机机 网网 络络小小 的的 簇簇 系系 数数小小 的的 平平 均均 距距 离离泊泊 松松 分分 布布Watts-Strogatz网络网络以很小的概率以很小的概率p断键重断键重连连簇系数依然很簇系数依然很大大平均距离变得很平均距离变得很小小指数分布指数分布D. J. Watts and S. H. Strogatz, Nature London 393, 440, 1998.M. E. J. Newman and D. J. Watts, Phys. Lett. A 263, 341,1999.Baraba

4、si-Albert网络网络每个时步增加一个节点每个时步增加一个节点每个节点按线性偏好连接每个节点按线性偏好连接Power-law 度分度分布布P(k) k-短的平均距离短的平均距离小的簇系数小的簇系数(lnN)2/NA.-L. Barabsi and R. Albert, Science 286, 509 1999.各种网络主要拓扑特征一览各种网络主要拓扑特征一览平均距离簇系数度分布规则网络大大Delta函数ER随机网络小小泊松分布WS小世界网络 小大指数分布BA无标度网络小小幂率分布部分部分真实网络小大近似幂率分布Question 1如何构造同时满足如何构造同时满足三个统计特性的简三个统计特

5、性的简单优美的网络模型单优美的网络模型更加深入细致 的统计特性度度- -度相关性度相关性度很大的节点到底是倾向于和度大度很大的节点到底是倾向于和度大的节点相连还是和度小的节点相连？的节点相连还是和度小的节点相连？正相关正相关负相关负相关M. E. J. Newman, Phys. Rev. Lett. 87, 208701(2002)W. -X. Wang, B. Hu, T. Zhou, B. -H. Wang and Y. -B. Xie,arXiv: cond-mat/0504062 (submitted to Phys. Rev. E)Question 2为什么社会网络是正相为什么社会

6、网络是正相关，而技术生物网络是关，而技术生物网络是负相关的？如何构建正负相关的？如何构建正相关的无标度网络？相关的无标度网络？簇簇- -度相关性度相关性好莱坞演员网络好莱坞演员网络英文单词网络英文单词网络在只有拓扑的网络中，簇度往往是负相关的；在只有拓扑的网络中，簇度往往是负相关的；在考虑几何的网络中，簇度往往是不相关的。在考虑几何的网络中，簇度往往是不相关的。E. Ravasz and A.-L Barabasi, Phys. Rev. E 67, 026112(2003)Question 3几何性质与簇度相关性几何性质与簇度相关性之间的关系到底是什么之间的关系到底是什么网络中的群落（网络中

7、的群落（community）M. Girvan and M. E. J. Newman, PNAS 99, 7821(2002)Question 4网络中群落结构的形成网络中群落结构的形成是外生原因还是内生原是外生原因还是内生原因，如果是内生原因，因，如果是内生原因，这个机制到底是什么？这个机制到底是什么？其 他 超家族分类 定点强度（strength）幂率分布 Strength-Degree幂率相关性 后代规模分布 合作规模分布 定点项目度分布与度分布的一致性问题 特征值谱 一些著名的模型 Krapivsky非线性BA模型 Holme-Kim可调簇系数模型 Klemm高集聚网络模型 Doro

8、govtsev-Mendes老化网络模型 Sen距离偏好模型 BBV含权网络模型 等等等等等等等等等等等等Holme-Kim可调簇系数模型在优先连接的同时在优先连接的同时以一定的概率连接以一定的概率连接被选中节点的邻居被选中节点的邻居节点度分布依然是幂指数为节点度分布依然是幂指数为-3的幂率分的幂率分布布簇系数变得很大（解析结果簇系数变得很大（解析结果PRE 67, 056102）平均距离依然很小平均距离依然很小P. Holme and B. J. Kim, Phys. Rev. E 65, 066109 2002.Dorogovtsev-Mendes老化网络模型老化：真实网络中不可避免的现象

9、老化：真实网络中不可避免的现象Klemm K and Eguiluz V M 2002 Phys. Rev. E 65 036123老化模型的基本框架老化模型的基本框架连接概率不仅连接概率不仅与节点的度与节点的度k有关，还与节点的年龄有关有关，还与节点的年龄有关不考虑年龄则退化为不考虑年龄则退化为BA模型。不同的模型模型。不同的模型有不同的老化函数有不同的老化函数 其中最有名的是其中最有名的是DMDorogovtsev S N and Mendes J F F 2000 Phys. Rev. E 62 1842参数 取值范围幂指数 0 2 3 0 1 3 1指数分布，链状结构主要的有关老化网络

10、的文献 Amaral L A N, Scala A, Barthelemy M and Stanley H E 2000 Proc. Natl. Acad. Sci. U.S.A. 97 11149 Klemm K and Eguiluz V M 2002 Phys. Rev. E 65 036123 Zhu H, Wang X R and Zhu J Y 2003 Phys. Rev. E 68 056121 Dorogovtsev S N and Mendes J F F 2000 Phys. Rev. E 62 1842 Jiang P Q, Wang B H, Zhou T et al

11、, 2005 Chin. Phys. Lett. 22 1285Sen距离偏好模型在很多实际网络中，距离因素是必在很多实际网络中，距离因素是必须考虑的，例如须考虑的，例如Internet和电力网等和电力网等BA模型模型Sen模型模型S. S. Manna and P. Sen, Phys. Rev. E 66, 066114(2002)S. S. Manna, G. Mukherjee and P. Sen, Phys. Rev. E69, 017102(2004)主要结论：存在一个阈值，当主要结论：存在一个阈值，当 大于该值时大于该值时度分布是幂率的，反之度分布是指数的。度分布是幂率的，反之

12、度分布是指数的。我自己的一些工作整数网络T. Zhou et al, arXiv: cond-mat/0405258 合作网络模型T. Zhou, Y. -D. Jin et al, arXiv: cond-mat/0502253随机阿波罗网络与单纯形网络T. Zhou, et al, Phys. Rev. E 71, 046141T. Zhou, G. Yan, et al, arXiv:cond-mat/0409414Z. -M. Gu, T. Zhou, et al, arXiv: cond-mat/0505175生长老化模型P. -Q. Jiang, B. -H. Wang, T. Z

13、hou, et al, Chin. Phys. Lett. 22 1285握手模型含权合作网络自组织无标度网络高聚簇无标度的多样性网络整数网络模型整数网络模型规则：规则：1到到N之间的合数，如果有整除之间的合数，如果有整除关系就连一条边，只考虑最大连通分支关系就连一条边，只考虑最大连通分支N30的情的情况，最大连况，最大连通分支有通分支有15个节点和个节点和19条边条边主要结论 簇系数比BA网络大，且随着N的变化是稳定的，大约在0.34左右 度分布是由指数为2的幂率分布（出度）和乱七八糟单的分布（入度）组合而成，数值上可以看作近似与指数2.4的幂率 直径有一个常数上界！ 簇度相关性C(k)1/

14、k有意思的地方 很简单，没有超过高中的数学 毕达哥拉斯的理念 既是模型又是实证 直径的常数上界一个新的网络类 环与理想，各种各样的数学对象随机阿波罗网络随机阿波罗网络Chapter II复杂网络上的交通问题动力学问题 传播动力学（SIR,SIS,SI） 网络同步与控制 自旋相互作用（Iring, XY临界模型） 级联动力学 交通流与信息流 网络导航 网络上的博弈问题（囚徒博弈、争当少数者博弈，退出者博弈） 复杂网络上的交通流交通流理论，已经在自然科学与经济社会的许多领域，特别是公路网上的车辆流问题和计算机互联网上的信息流问题上，有着广泛而深入的应用。近年来关于复杂网络方面的研究表明，计算机互联网具有无标度特性，不能用简单的规则网络模型或ER随机网络模型模拟。因此，讨论网络拓扑结构对其上交通动力学行为的影响是非常有意义的。 什么是交通流交通是指人,物以及思想,信息的地点间移动.因此交通流的研究对象是广泛的!交通流研究可以属于广义传播范畴,它包括信息流,粒子流,车辆流,颗粒流等等. 物理学家感兴趣的部分包括:交通系统的动力学行为:相变与自组织临界性.灾难救