基于复杂网络的交通网络评价

1、LOGO1 1 复杂网络简介复杂网络简介LOGO1.1.1 1.1.1 二十一世纪涌现的新现象二十一世纪涌现的新现象万万 维维 网网 万维网是怎样万维网是怎样“链链”接的？接的？从一个页面到另一个页面从一个页面到另一个页面平均需要点击多少次鼠标？平均需要点击多少次鼠标？1.11.1、为什么研究复杂网络？、为什么研究复杂网络？ LOGO非典发现在广州，为什么却非典发现在广州，为什么却 在北京爆发呢？在北京爆发呢？传染病是怎样扩散和消失的？传染病是怎样扩散和消失的？计算机病毒是怎样传播的？计算机病毒是怎样传播的？为什么为什么“好事不出门，坏事好事不出门，坏事行千里行千里”呢？呢？互联网LOGO1.

2、1.2. 1.1.2. 二十一世纪科学研究的特点二十一世纪科学研究的特点 二十世纪，科学研究的特点是二十世纪，科学研究的特点是分析分析的方法，的方法，还原论还原论的方法：物理学（牛顿力学、量子力学、的方法：物理学（牛顿力学、量子力学、电子论、半导体），化学（量子分子论），生电子论、半导体），化学（量子分子论），生物（双螺旋结构）；建筑工程（应力应变分物（双螺旋结构）；建筑工程（应力应变分析），析），。 二十一世纪（二十世纪末），二十一世纪（二十世纪末），系统系统成为主要成为主要的研究对象，的研究对象，整合整合成为主要方法。普列高津的耗成为主要方法。普列高津的耗散结构理论，混沌和复杂系统理论，系

3、统生物散结构理论，混沌和复杂系统理论，系统生物学学 。LOGO美国美国ScienceScience周刊：周刊：“如果对当前流行的、时髦的关键词进行一如果对当前流行的、时髦的关键词进行一番分析，那么人们会发现，番分析，那么人们会发现，“系统系统”高居在高居在排行榜上。排行榜上。” 当分析为主要的研究方法时，人类关注如何将系当分析为主要的研究方法时，人类关注如何将系统统“分析分析”、“分解分解”，揭开系统的细部，了解是什，揭开系统的细部，了解是什么元素或部件组成了系统，却忽视或破坏了这些元素么元素或部件组成了系统，却忽视或破坏了这些元素是如何组合成系统的。而是如何组合成系统的。而整合整合的方法在于

4、了解细部以的方法在于了解细部以后，研究后，研究“如何组合如何组合”的问题。这种方法导致的问题。这种方法导致复杂网复杂网络结构络结构的研究。的研究。LOGO1.21.2复杂系统与复杂网络复杂系统与复杂网络1.2.1 复杂系统和复杂网络的概念复杂系统和复杂网络的概念（1）什么是系统？）什么是系统？ 系统：系统：集合（具体元素）集合（具体元素）+ 结构结构+功能。功能。 （例：不同角度分析系统，人）（例：不同角度分析系统，人）（2）系统的结构是什么？）系统的结构是什么？u 一切系统的一切系统的基础基础结构都是结构都是网络网络；u 一切系统的一切系统的核心结构核心结构都是都是逻辑网络；逻辑网络；u 复

5、杂系统的结构就是复杂系统的结构就是复杂网络。复杂网络。LOGO 我认为，下个世纪将是复杂性的世纪我认为，下个世纪将是复杂性的世纪(I think the next century will be the century of complexity) 斯蒂芬斯蒂芬.霍金霍金(StephenHaking)（2000）u 英国剑桥大学应用数学及理论物理学系教授，当代最重要的广义相对论和英国剑桥大学应用数学及理论物理学系教授，当代最重要的广义相对论和宇宙论家，是当今享有国际盛誉的伟人之一，被称为在世的最伟大的科学家，宇宙论家，是当今享有国际盛誉的伟人之一，被称为在世的最伟大的科学家，还被称为还被称为“

6、宇宙之王宇宙之王”。网络与复杂网络成为二十一世纪的新科学领域！网络与复杂网络成为二十一世纪的新科学领域！LOGO1) 1) 开放性。开放性。即与环境和其它系统进行相互作用，即与环境和其它系统进行相互作用，交换物质、能交换物质、能量、信息量、信息，保持和发展系统内部的，保持和发展系统内部的有序性与结构稳定性有序性与结构稳定性。在这。在这种交换中，系统经历着从低级向高级、从简单到复杂、从无序种交换中，系统经历着从低级向高级、从简单到复杂、从无序向有序的不断优化的动态发展过程。虽然开放性是所有真实系向有序的不断优化的动态发展过程。虽然开放性是所有真实系统的基本属性，但这里的开放非指一般意义上的相互作

7、用与交统的基本属性，但这里的开放非指一般意义上的相互作用与交流，而开放的度量、性质、强度对复杂系统的性态、演化具有流，而开放的度量、性质、强度对复杂系统的性态、演化具有决定性的意义。决定性的意义。 例子，人，城市网络簇。例子，人，城市网络簇。) )涌现性。涌现性。即内部元素通过非线性相互作用，在宏观层次上产即内部元素通过非线性相互作用，在宏观层次上产生出生出新的、新的、元素不具有的整体属性元素不具有的整体属性，表现为整体斑图、模式等，表现为整体斑图、模式等。虽然。虽然涌现涌现同样是所有系统都具有的，但这里涌现意味着同样是所有系统都具有的，但这里涌现意味着新的新的整体属性的产生整体属性的产生。

8、例子，例子， “整体大于部分之和整体大于部分之和”， 大脑的神经网络系统大脑的神经网络系统1.2.2 复杂系统与复杂网络的主要特性：复杂系统与复杂网络的主要特性：LOGO）演化性（不可逆性）演化性（不可逆性）。即通过与所在环境中的其它。即通过与所在环境中的其它系统的相互作用和内部的自组织，使系统发展到新的阶系统的相互作用和内部的自组织，使系统发展到新的阶段，表现出阶段性、临界性，完成系统演化的生命周期。段，表现出阶段性、临界性，完成系统演化的生命周期。 例例:社会网络中的人，生物群体的自组织系统（鸟群）社会网络中的人，生物群体的自组织系统（鸟群）复杂性。）复杂性。 包括系统的结构、行为、功能等

9、多个方面包括系统的结构、行为、功能等多个方面同时具有的复杂性。同时具有的复杂性。结构复杂性结构复杂性表现为多元性，非对称表现为多元性，非对称性，非均匀性，非线性（分岔性，非均匀性，非线性（分岔 (Bifurcation) , 混沌混沌(Chaos), 分形分形Fractal）；）；行为复杂性行为复杂性表现为学习，自适表现为学习，自适应性，混沌同步，混沌边沿，随机性等等；应性，混沌同步，混沌边沿，随机性等等；认识复杂性认识复杂性又称为主观复杂性，它表现为不确定性，描述复杂性与又称为主观复杂性，它表现为不确定性，描述复杂性与计算复杂性等等。计算复杂性等等。例例: :神经网络中的突触有强有弱，可抑制

10、也可兴奋神经网络中的突触有强有弱，可抑制也可兴奋LOGO ）网络结构。）网络结构。即系统内部和系统之间的相互作用即系统内部和系统之间的相互作用可以看成由节点、边（连接）构成的体系，出现可以看成由节点、边（连接）构成的体系，出现网络复杂性、小世界特征与无标度特征等。网络复杂性、小世界特征与无标度特征等。一切系统都具有网络结构，复杂系统具有复杂的网络结构。一切系统都具有网络结构，复杂系统具有复杂的网络结构。LOGO1.2.3. 网络系统的复杂性网络系统的复杂性（1）结构复杂性）结构复杂性 网络连接网络连接结构错综复杂结构错综复杂、极其混乱，同时又蕴含、极其混乱，同时又蕴含着着丰富的结构丰富的结构：

11、社区社区、基序、聚集性、生成规律性等、基序、聚集性、生成规律性等等，而且网络连接结构可能是等，而且网络连接结构可能是随时间变化随时间变化的，例如，的，例如，WWW上每天都不停地有页面和链接的产生和删除。上每天都不停地有页面和链接的产生和删除。u 静态结构的复杂性和结构动态演化的复杂性。静态结构的复杂性和结构动态演化的复杂性。 例：神经系统由神经元互连形成，例：神经系统由神经元互连形成，连接以连接以“突触连突触连接结构接结构”实现，突触有强弱、兴奋与抑制、不同的神实现，突触有强弱、兴奋与抑制、不同的神经递质；连接不断改变，形成经递质；连接不断改变，形成连接结构变化连接结构变化。（重边，。（重边，

12、加权等）加权等）LOGO（2）节点复杂性）节点复杂性 A）节点的独立或固有特性）节点的独立或固有特性 网络中的节点可能是具有分岔和混沌等复杂非线网络中的节点可能是具有分岔和混沌等复杂非线 性行为的性行为的动力系统动力系统。例如，基因网络中每个节点都具。例如，基因网络中每个节点都具有复杂的有复杂的时间演化时间演化行为。而且，一个网络中可能存在行为。而且，一个网络中可能存在多种不同类型多种不同类型的节点。的节点。 B) 关联关联引发的节点特性引发的节点特性 当关联失去时这类当关联失去时这类特性特性会在节点处消失或改变。会在节点处消失或改变。例如，耦合神经元重复地被同时激活，那么它们之间例如，耦合神

13、经元重复地被同时激活，那么它们之间的连接就会加强，这被认为是记忆和学习的基础。的连接就会加强，这被认为是记忆和学习的基础。LOGO（3）复杂网络之间相互影响的复杂性）复杂网络之间相互影响的复杂性 实际的复杂网络会受到各种各样因素的影响和作实际的复杂网络会受到各种各样因素的影响和作用。例如，电力网络故障会导致用。例如，电力网络故障会导致Internet网速变慢，网速变慢，运输系统失控等一系列不同网络间的连锁反应。运输系统失控等一系列不同网络间的连锁反应。（4）网络分层结构的复杂性）网络分层结构的复杂性例如，行政管理网络是具有层结构的，多数网络都例如，行政管理网络是具有层结构的，多数网络都有有节点

14、的分层结构节点的分层结构，只是在许多网络中没有意识到，只是在许多网络中没有意识到是一种造成复杂性的重要结构。是一种造成复杂性的重要结构。LOGOu 复杂网络也是研究复杂系统的一种复杂网络也是研究复杂系统的一种技术技术和和方方法法，它关注系统中个体相互作用的拓扑，它关注系统中个体相互作用的拓扑结构结构，是理解复杂系统性质和功能的基本方法。是理解复杂系统性质和功能的基本方法。u 复杂网络是二十一世纪科学研究的复杂网络是二十一世纪科学研究的思想思想和和理理念念，它启发我们用什么观点理解这个世界：，它启发我们用什么观点理解这个世界：整整个世界以及组成世界的任何细部都是由网络及个世界以及组成世界的任何细

15、部都是由网络及其变化形成的其变化形成的。LOGO1.31.3复杂网络研究简史复杂网络研究简史 格尼斯堡七桥问题格尼斯堡七桥问题Euler（17071783），），瑞士数学家瑞士数学家 ，图论，图论之父之父一笔画问题一笔画问题 1736年，七桥游戏LOGO随机图理论随机图理论 20世纪世纪60年代，由两位匈牙利数学家年代，由两位匈牙利数学家Erds和和Rnyi建立建立的随机图理论（的随机图理论（random graph theory）被公认为是在数学）被公认为是在数学上开创了复杂网络理论的系统性研究。上开创了复杂网络理论的系统性研究。 Erds和Rnyi的最重要的发现是：ER随机图的许多重要性质

16、都是突然涌现的。也就是说，对于任一给定的概率p，要么几乎每一个图都具有某个性质Q（比如说，连通性），要么几乎每一个图都不具有该性质。 在20世纪的后40年中，随机图理论一直是研究复杂网络的基本理论。LOGO小世界实验小世界实验u20世纪世纪60年代年代美国哈佛大学美国哈佛大学的社会心理学家的社会心理学家Stanley Milgram通过通过一些社会调查后给出的推断是：地球上任意两个人之间的平均距一些社会调查后给出的推断是：地球上任意两个人之间的平均距离是离是6。这就是著名的。这就是著名的“六度分离六度分离”（six degrees of separation）推断。推断。u 为了检验为了检验“

17、六度分离六度分离”的正确性，小世界实验的正确性，小世界实验Bacon数。美国数。美国Virginia大学计算机系的科学家建立了一个电影演员的数据库，放在大学计算机系的科学家建立了一个电影演员的数据库，放在网上供人们随意查询。网站的数据库里目前总共存有近网上供人们随意查询。网站的数据库里目前总共存有近60万个世界各万个世界各地的演员的信息以及近地的演员的信息以及近30万部电影信息。通过简单地输入演员名字就万部电影信息。通过简单地输入演员名字就可以知道这个演员的可以知道这个演员的Bacon数。数。u 一个有趣的数学家故事：一个有趣的数学家故事：Erds数证明小世界实验。数证明小世界实验。LOGO小

18、世界实验小世界实验u20世纪世纪60年代年代美国哈佛大学美国哈佛大学的社会心理学家的社会心理学家Stanley Milgram通过通过一些社会调查后给出的推断是：地球上任意两个人之间的平均距一些社会调查后给出的推断是：地球上任意两个人之间的平均距离是离是6。这就是著名的。这就是著名的“六度分离六度分离”（six degrees of separation）推断。推断。u 为了检验为了检验“六度分离六度分离”的正确性，小世界实验的正确性，小世界实验Bacon数。美国数。美国Virginia大学计算机系的科学家建立了一个电影演员的数据库，放在大学计算机系的科学家建立了一个电影演员的数据库，放在网上

19、供人们随意查询。网站的数据库里目前总共存有近网上供人们随意查询。网站的数据库里目前总共存有近60万个世界各万个世界各地的演员的信息以及近地的演员的信息以及近30万部电影信息。通过简单地输入演员名字就万部电影信息。通过简单地输入演员名字就可以知道这个演员的可以知道这个演员的Bacon数。数。u 一个有趣的数学家故事：一个有趣的数学家故事：Erds数证明小世界实验。数证明小世界实验。LOGO 有两篇开创性的文章可以看作是有两篇开创性的文章可以看作是复杂网络研究复杂网络研究新新纪元开始的纪元开始的标志标志： 一篇是美国康奈尔（一篇是美国康奈尔（Cornell）大学理论和应用力学系的博）大学理论和应用

20、力学系的博士生士生Watts及其导师、非线性动力学专家及其导师、非线性动力学专家Strogatz教授于教授于1998年年6月在月在Nature杂志上发表的题为杂志上发表的题为“小世界小世界”网络的集体动力学网络的集体动力学（Collective Dynamics of Small-World Networks）的文章；）的文章； 另一篇是美国另一篇是美国Notre Dame大学物理系的大学物理系的Barabsi教授及其教授及其博士生博士生Albert于于1999年年10月在月在Science杂志上发表的题为杂志上发表的题为随机随机网络中标度的涌现网络中标度的涌现（Emergence of Sc

21、aling in Random Networks）的文章。）的文章。 这两篇文章分别揭示了复杂网络的这两篇文章分别揭示了复杂网络的小世界特征小世界特征和和无标度性无标度性质质，并建立了相应的模型以阐述这些特性的产生机理。，并建立了相应的模型以阐述这些特性的产生机理。LOGO1998，Watts和和Strogatz：WS小世界网络小世界网络u D. J. Watts, and S. H. Strogatz, Nature, 393, 440-442 (1998). LOGO1999，Barabasi和和Albert ：BA无标度网络无标度网络kkP)(现实世界的网络大部分都不是随机网络，少数的节

22、点往往拥有大量的连接，而大部分节点却很少。将度分布符合幂律分布的复杂网络称为无标度网络。无标度网络具有严重的异质性，其各节点之间的连接状况（度数）具有严重的不均匀分布性：网络中少数称之为Hub点的节点拥有极其多的连接，而大多数节点只有很少量的连接。少数Hub点对无标度网络的运行起着主导的作用。从广义上说，无标度网络的无标度性是描述大量复杂系统整体上严重不均匀分布的一种内在性质。鲁棒且脆弱性特性是大规模 Internet 网络的基本特性之一,也是体现随机图网络和无标度网络之间存在显著差异的重要拓扑特性.与早期随机图网络不同,无标度网络中幂律分布特性的存在极大地提高了高度数节点存在的可能性,因此,

23、无标度网络同时显现出针对随机故障的鲁棒性和针对蓄意攻击的脆弱性. 这种鲁棒且脆弱性对网络容错和抗攻击能力有很大影响.研究表明,无标度网络具有很强的容错性,但是对基于节点度值的选择性攻击而言,其抗攻击能力相当差,高度数节点的存在极大地削弱了网络的鲁棒性,一个恶意攻击者只需选择攻击网络很少的一部分高度数节点,就能使网络迅速瘫痪.另外,已有研究指出, Internet 网络路由器级拓扑表现出与自治域级拓扑所不同的鲁棒且脆弱性,并且其生成机理不能同样用无标度模型来加以刻画LOGO复杂网络研究的简史列表复杂网络研究的简史列表时间（年时间（年）人物人物事件事件17361959196719731998199

24、9ElerErds和和RnyiMilgramGranovetterWatts和和StrogatzBarabsi和和Albert七桥问题七桥问题随机图理论随机图理论小世界实验小世界实验弱连接的强度弱连接的强度小世界模型小世界模型无标度网络无标度网络LOGO技术网络技术网络WWW电力网电力网因特网因特网复杂网络的事例复杂网络的事例LOGO社会网络社会网络朋友关系网朋友关系网性关系网性关系网演员网演员网科学家合著网科学家合著网科学引文网科学引文网LOGO交通运输网交通运输网络络城城市市公公共共交交通通网网道道路路交交通通网网航航空空网网LOGO生物网络生物网络神经网络神经网络生态网络生态网络蛋白质相

25、互作用网络蛋白质相互作用网络基因网络基因网络新陈代谢网络新陈代谢网络LOGOSanta Fe 研究所的科学家研究所的科学家合作网合作网LOGOLOGO不同领域的复杂网络不同领域的复杂网络v 社会网：演员合作网，友谊网，姻亲关系网，科社会网：演员合作网，友谊网，姻亲关系网，科研合作网，研合作网，Email网网v生物网：食物链网，神经网，新陈代谢网，蛋白质生物网：食物链网，神经网，新陈代谢网，蛋白质网，基因网络网，基因网络v信息网络：信息网络：WWW，专利使用，论文引用，计算，专利使用，论文引用，计算机共享机共享v技术网络：电力网，技术网络：电力网，Internet，电话线路网，电话线路网，v交通

26、运输网：航线网，铁路网，公路网，自然河流交通运输网：航线网，铁路网，公路网，自然河流网网LOGO.复杂网络研究内容复杂网络研究内容1 1）复杂网络模型）复杂网络模型 典型的复杂网络：随机网、小世界网、无标度网等；典型的复杂网络：随机网、小世界网、无标度网等； 实际网络及其分类。实际网络及其分类。2 2）网络的统计量及与网络结构的相关性）网络的统计量及与网络结构的相关性 度分布的定义和意义，聚集性、连通性的统计量及其实际度分布的定义和意义，聚集性、连通性的统计量及其实际 意义等。意义等。3 3）复杂网络性质与结构的关系）复杂网络性质与结构的关系 同步性、鲁棒性和稳定性与网络结构的关

27、系。同步性、鲁棒性和稳定性与网络结构的关系。4 4）复杂网络的动力学）复杂网络的动力学 信息传播动力学、网络演化动力学、网络混沌动力学。信息传播动力学、网络演化动力学、网络混沌动力学。5 5）复杂网络的复杂结构）复杂网络的复杂结构 社团结构、层次结构、节点分类结构等。社团结构、层次结构、节点分类结构等。6 6）网络控制）网络控制 关键节点控制、主参数控制和控制的稳定性和有效性。关键节点控制、主参数控制和控制的稳定性和有效性。LOGO1 1）突破性进展的主要原因）突破性进展的主要原因 越来越强大的计算设备和迅猛发展的越来越强大的计算设备和迅猛发展的Internet，使得，使得人们开始能够人们开始

28、能够收集收集和和处理处理规模巨大且种类不同的实际规模巨大且种类不同的实际网络网络数据数据。 学科之间的相互交叉使得研究人员可以广泛比较各学科之间的相互交叉使得研究人员可以广泛比较各种种不同类型的网络数据不同类型的网络数据，从而，从而揭示复杂网络的共性揭示复杂网络的共性。 以以还原理论还原理论和和整体论整体论相结合为重要特色的复杂性科相结合为重要特色的复杂性科学的兴起，也促使人们开始从整体上研究网络的结构学的兴起，也促使人们开始从整体上研究网络的结构与性能之间的关系。与性能之间的关系。1.5 1.5 复杂网络研究复杂网络研究二十一世纪的二十一世纪的科学科学LOGO2 2）主要研究目标）主要研究目

29、标发现：发现：揭示刻画网络系统结构的统计性质，以及揭示刻画网络系统结构的统计性质，以及度量这些性质的合适方法。度量这些性质的合适方法。建模建模：建立合适的网络模型以及理解网络的统计：建立合适的网络模型以及理解网络的统计性质的意义与产生机理。性质的意义与产生机理。分析分析：基于单个节点的特性和整个网络的结构性：基于单个节点的特性和整个网络的结构性质分析与预测网络的行为。质分析与预测网络的行为。控制控制：提出改善已有网络性能和设计新的网络的：提出改善已有网络性能和设计新的网络的有效方法，特别是稳定性、同步和数据流通等方面。有效方法，特别是稳定性、同步和数据流通等方面。kkkpkp1iikkjiij

30、d12L）（1-kk2Ciiii1iiC1CLOGO 网络节点间联系的密切程度网络节点间联系的密切程度, 体现网络的体现网络的凝聚力凝聚力 许多大规模的实际网络都具有明显的许多大规模的实际网络都具有明显的聚类效应聚类效应。事实上，。事实上，在很多类型的网络在很多类型的网络(如社会关系网络如社会关系网络)中，你的朋友同时也是朋中，你的朋友同时也是朋友的概率会随着网络规模的增加而趋向于友的概率会随着网络规模的增加而趋向于某个非零常数某个非零常数，即当，即当N时，时，C=O(1)。这意味着这些实际的复杂网络并不是完全。这意味着这些实际的复杂网络并不是完全随机的，而是在某种程度上具有类似于社会关系网络

31、中随机的，而是在某种程度上具有类似于社会关系网络中“物以物以类聚，人以群分类聚，人以群分”的特性。的特性。 1nkpCiiXn1i iX*Xn1iiX*XXpCpCmaxpCpCC*XpCn1iiX*XpCpCmax2n3npCpCC2n1iiD*DD2n5n4npCpCC23n1iiB*BB3)-n22n3npCpCC2n1iiC*CCLOGO45u 介数（介数（BetweennessBetweenness）点介数点介数：网络中通过该节点的最短路径的条数：网络中通过该节点的最短路径的条数 边介数边介数：网络中通过该边的最短路径的条数：网络中通过该边的最短路径的条数反映了节点或边的作用和影响力

32、。如果一对节点间共有反映了节点或边的作用和影响力。如果一对节点间共有B条条不同的最短路径，其中有不同的最短路径，其中有b条经过节点条经过节点i，那么节点，那么节点i对这对节点对这对节点的介数的贡献为的介数的贡献为b/B。把节点。把节点i对所有节点对的贡献累加起来再对所有节点对的贡献累加起来再除以节点对总数，就可得到节点除以节点对总数，就可得到节点i的介数。类似的，边的介数定的介数。类似的，边的介数定义为所有节点对的最短路径中经过该边的数量比例（义为所有节点对的最短路径中经过该边的数量比例（关键点边！关键点边！连通性影响连通性影响？）。？）。 介数越大，说明经过该节点（边）的最短路径越多。在信息介数越大，说明经过该节点（边）的最短路径越多。在信息传播