复杂动态网络基本概念课件.pptx

1、复杂动态网络及其控制 任课教师：樊春霞南京邮电大学自动化学院课程介绍 学时：32 内容：复杂动态网络基本概念、小世界模型、无尺度模型、复杂动态网络状态耦合同步方法、复杂动态网络输出耦合同步方法、时滞网络同步、复杂动态网络拓扑辨识、复杂动态网络故障诊断参考书 1汪小帆、李翔、陈关荣编著，复杂网络：理论及其应用，清华大学出版社，2006年. 2. 汪小帆、李翔、陈关荣编著，网络科学导论，高等教育出版社，2012年. 3.针对研究方向，网络资料，海量相关资料：u许晓鸣, 郭雷.复杂网络.上海科技教育出版社, 2006年11月.uS.H.Strogatz. Nature, 410, (2001) 26

2、8.uR.Albert, A. -L. Barabasi. Rev. Mod. Phys. , 51 (2002)1079.uM. E. J. Newman. SIAM Rev., 45(2003) , 167.uS. N. Dorogovtesev, J.Mendes. Evolving of Networks, Oxford Un. Press, 2003.uE. Ben-Naim, et al. Complex Networks, Springer, 2004.uS.Boccaletti, et al. Complex Networks: Structure and dynamics,

3、Phys. Rep. 424 (2006) 175-308.uNewman, Barabasi, Watts. The Structure and Dynamics of Networks. Princeton University Press, 2006.4 4复杂动态网络基本概念 1.什么是复杂网络？ 2为什么研究复杂网络? 3. 复杂动态网络的基本概念6 61. 1. 二十一世纪涌现的新现象二十一世纪涌现的新现象万万 维维 网网 万维网是怎样万维网是怎样“链链”接的？接的？从一个页面到另从一个页面到另一个页面一个页面平均需要点击多平均需要点击多少次鼠标？少次鼠标？一、为什么研究复杂网络？

4、一、为什么研究复杂网络？ 7 7美国航空网美国航空网城市公共交通网城市公共交通网为什么两者结构差异如此之大？为什么两者结构差异如此之大？这种差异是必然还是偶然的？这种差异是必然还是偶然的？城市交通涌堵的原因是什么？城市交通涌堵的原因是什么？8 8非典发现在广州，为什么却非典发现在广州，为什么却 在北京爆发呢？在北京爆发呢？传染病是怎样扩散和消失的？传染病是怎样扩散和消失的？计算机病毒是怎样传播的？计算机病毒是怎样传播的？为什么为什么“好事不出门，坏事好事不出门，坏事行千里行千里”呢？呢？互联网9 92. 2. 二十一世纪科学研究的特点二十一世纪科学研究的特点 二十世纪，科学研究的特点是二十世纪

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

6、ceScience周刊：周刊：“如果对当前流行的、时髦的关键词进行一如果对当前流行的、时髦的关键词进行一番分析，那么人们会发现，番分析，那么人们会发现，“系统系统”高居在高居在排行榜上。排行榜上。” 当分析为主要的研究方法时，人类关注如何将系当分析为主要的研究方法时，人类关注如何将系统统“分析分析”、“分解分解”，揭开系统的细部，了解是什，揭开系统的细部，了解是什么元素或部件组成了系统，却忽视或破坏了这些元素么元素或部件组成了系统，却忽视或破坏了这些元素是如何组合成系统的。而是如何组合成系统的。而整合整合的方法在于了解细部以的方法在于了解细部以后，研究后，研究“如何组合如何组合”的问题。这种方

7、法导致的问题。这种方法导致复杂网复杂网络结构络结构的研究。的研究。二、复杂系统与复杂网络11111. 1. 复杂系统与复杂网络的概念复杂系统与复杂网络的概念 （1）什么是系统？）什么是系统？ 系统：系统：集合（具体元素）集合（具体元素）+ 结构结构+功能。功能。 （例：不同角度分析系统，人）（例：不同角度分析系统，人）（2）系统的结构是什么？）系统的结构是什么？u 一切系统的一切系统的基础基础结构都是结构都是网络网络；u 一切系统的一切系统的核心结构核心结构都是都是逻辑网络；逻辑网络；u 复杂系统的结构就是复杂系统的结构就是复杂网络。复杂网络。1212u复杂网络是构成复杂系统的基本结构，每个复

8、杂复杂网络是构成复杂系统的基本结构，每个复杂系统都可以看作是单元或个体之间的相互作用网络；系统都可以看作是单元或个体之间的相互作用网络；u复杂网络在刻画复杂性方面的重要性是由于复杂网络在刻画复杂性方面的重要性是由于结构结构决定功能决定功能的。的。u复杂网络是研究复杂系统的一种复杂网络是研究复杂系统的一种角度和方法角度和方法，它，它关注系统中因子相互关联作用的关注系统中因子相互关联作用的拓扑结构拓扑结构，是理解复，是理解复杂系统杂系统性质和功能性质和功能的基础。的基础。 我认为，下个世纪将是复杂性的世纪我认为，下个世纪将是复杂性的世纪(I think the next century will

9、be the century of complexity) 斯蒂芬斯蒂芬.霍金霍金(StephenHaking)（2000）u 英国剑桥大学应用数学及理论物理学系教授，当代最重要的广义相对论和英国剑桥大学应用数学及理论物理学系教授，当代最重要的广义相对论和宇宙论家，是当今享有国际盛誉的伟人之一，被称为在世的最伟大的科学家，宇宙论家，是当今享有国际盛誉的伟人之一，被称为在世的最伟大的科学家，还被称为还被称为“宇宙之王宇宙之王”。网络与复杂网络成为二十一世纪的新科学领域！网络与复杂网络成为二十一世纪的新科学领域！1) 开放性。即与环境和其它系统进行相互作用，交换物质、能量、信息，保持和发展系统内部

10、的有序性与结构稳定性。在这种交换中，系统经历着从低级向高级、从简单到复杂、从无序向有序的不断优化的动态发展过程。虽然开放性是所有真实系统的基本属性，但这里的开放非指一般意义上的相互作用与交流，而开放的度量、性质、强度对复杂系统的性态、演化具有决定性的意义。 例子，人，城市网络簇。)涌现性。即内部元素通过非线性相互作用，在宏观层次上产生出新的、元素不具有的整体属性，表现为整体斑图、模式等。虽然涌现同样是所有系统都具有的，但这里涌现意味着新的整体属性的产生。 例子， “整体大于部分之和”， 大脑的神经网络系统14142. 复杂系统与复杂网络的主要特性：复杂系统与复杂网络的主要特性：1515）演化性

11、（不可逆性）演化性（不可逆性）。即通过与所在环境中的其它。即通过与所在环境中的其它系统的相互作用和内部的自组织，使系统发展到新的阶系统的相互作用和内部的自组织，使系统发展到新的阶段，表现出阶段性、临界性，完成系统演化的生命周期。段，表现出阶段性、临界性，完成系统演化的生命周期。 例例:社会网络中的人，生物群体的自组织系统（鸟群）社会网络中的人，生物群体的自组织系统（鸟群）复杂性。）复杂性。 包括系统的结构、行为、功能等多个方面包括系统的结构、行为、功能等多个方面同时具有的复杂性。同时具有的复杂性。结构复杂性结构复杂性表现为多元性，非对称表现为多元性，非对称性，非均匀性，非线性（分岔性，非均匀性

12、，非线性（分岔 (Bifurcation) , 混沌混沌(Chaos), 分形分形Fractal）；）；行为复杂性行为复杂性表现为学习，自适表现为学习，自适应性，混沌同步，混沌边沿，随机性等等；应性，混沌同步，混沌边沿，随机性等等；认识复杂性认识复杂性又称为主观复杂性，它表现为不确定性，描述复杂性与又称为主观复杂性，它表现为不确定性，描述复杂性与计算复杂性等等。计算复杂性等等。例例: :神经网络中的突触有强有弱，可抑制也可兴奋神经网络中的突触有强有弱，可抑制也可兴奋 ）网络结构。即系统内部和系统之间的相互作用可以看成由节点、边（连接）构成的体系，出现网络复杂性、小世界特征与无标度特征等。161

13、6一切系统都具有网络结构，复杂系统具有复杂的网络结构。一切系统都具有网络结构，复杂系统具有复杂的网络结构。17173. 网络系统的复杂性网络系统的复杂性（1）结构复杂性）结构复杂性 网络连接网络连接结构错综复杂结构错综复杂、极其混乱，同时又蕴含、极其混乱，同时又蕴含着着丰富的结构丰富的结构：社区社区、基序、聚集性、生成规律性等、基序、聚集性、生成规律性等等，而且网络连接结构可能是等，而且网络连接结构可能是随时间变化随时间变化的，例如，的，例如，WWW上每天都不停地有页面和链接的产生和删除。上每天都不停地有页面和链接的产生和删除。u 静态结构的复杂性和结构动态演化的复杂性。静态结构的复杂性和结构

14、动态演化的复杂性。 例：神经系统由神经元互连形成，例：神经系统由神经元互连形成，连接以连接以“突触连突触连接结构接结构”实现，突触有强弱、兴奋与抑制、不同的神实现，突触有强弱、兴奋与抑制、不同的神经递质；连接不断改变，形成经递质；连接不断改变，形成连接结构变化连接结构变化。（重边，。（重边，加权等）加权等）1818（2）节点复杂性）节点复杂性 A）节点的独立或固有特性）节点的独立或固有特性 网络中的节点可能是具有分岔和混沌等复杂非线网络中的节点可能是具有分岔和混沌等复杂非线 性行为的性行为的动力系统动力系统。例如，基因网络中每个节点都具。例如，基因网络中每个节点都具有复杂的有复杂的时间演化时间

15、演化行为。而且，一个网络中可能存在行为。而且，一个网络中可能存在多种不同类型多种不同类型的节点。例如，控制哺乳动物中细胞分的节点。例如，控制哺乳动物中细胞分裂的生化网络就包含各种各样的基质和酶裂的生化网络就包含各种各样的基质和酶。 B) 关联关联引发的节点特性引发的节点特性 当关联失去时这类当关联失去时这类特性特性会在节点处消失或改变。会在节点处消失或改变。例如，耦合神经元重复地被同时激活，那么它们之间例如，耦合神经元重复地被同时激活，那么它们之间的连接就会加强，这被认为是记忆和学习的基础。的连接就会加强，这被认为是记忆和学习的基础。1919（3）复杂网络之间相互影响的复杂性）复杂网络之间相互

16、影响的复杂性 实际的复杂网络会受到各种各样因素的影响和作实际的复杂网络会受到各种各样因素的影响和作用。例如，电力网络故障会导致用。例如，电力网络故障会导致Internet网速变慢，网速变慢，运输系统失控等一系列不同网络间的连锁反应。运输系统失控等一系列不同网络间的连锁反应。（4）网络分层结构的复杂性）网络分层结构的复杂性例如，行政管理网络是具有层结构的，多数网络都例如，行政管理网络是具有层结构的，多数网络都有有节点的分层结构节点的分层结构，只是在许多网络中没有意识到，只是在许多网络中没有意识到是一种造成复杂性的重要结构。是一种造成复杂性的重要结构。2020u 复杂网络也是研究复杂系统的一种复杂

17、网络也是研究复杂系统的一种技术技术和和方方法法，它关注系统中个体相互作用的拓扑，它关注系统中个体相互作用的拓扑结构结构，是理解复杂系统性质和功能的基本方法。是理解复杂系统性质和功能的基本方法。u 复杂网络是二十一世纪科学研究的复杂网络是二十一世纪科学研究的思想思想和和理理念念，它启发我们用什么观点理解这个世界：，它启发我们用什么观点理解这个世界：整整个世界以及组成世界的任何细部都是由网络及个世界以及组成世界的任何细部都是由网络及其变化形成的其变化形成的。2121三、复杂网络研究简史三、复杂网络研究简史 格尼斯堡七桥问题格尼斯堡七桥问题Euler（17071783），），瑞士数学家瑞士数学家 ，

18、图论，图论之父之父一笔画问题一笔画问题 1736年，七桥游戏2222 随机图理论随机图理论 20世纪世纪60年代，由两位匈牙利数学家年代，由两位匈牙利数学家Erds和和Rnyi建立建立的随机图理论（的随机图理论（random graph theory）被公认为是在数学）被公认为是在数学上开创了复杂网络理论的系统性研究。上开创了复杂网络理论的系统性研究。 Erds和Rnyi的最重要的发现是：ER随机图的许多重要性质都是突然涌现的。也就是说，对于任一给定的概率p，要么几乎每一个图都具有某个性质Q（比如说，连通性），要么几乎每一个图都不具有该性质。 在20世纪的后40年中，随机图理论一直是研究复杂网

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

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

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

22、rgence of Scaling in Random Networks）的文章。）的文章。 这两篇文章分别揭示了复杂网络的这两篇文章分别揭示了复杂网络的小世界特征小世界特征和和无标度性无标度性质质，并建立了相应的模型以阐述这些特性的产生机理。，并建立了相应的模型以阐述这些特性的产生机理。25251998，Watts和和Strogatz：WS小世界网络小世界网络u D. J. Watts, and S. H. Strogatz, Nature, 393, 440-442 (1998). 2626u A.-L. Barabasi and R. Albert, Science, 286, 509

23、(1999).1999，Barabasi和和Albert ：BA无标度网络无标度网络 kkP)(2727复杂网络研究的简史列表复杂网络研究的简史列表时间（年）人物事件173619591967197319981999ElerErds和RnyiMilgramGranovetterWatts和StrogatzBarabsi和Albert七桥问题随机图理论小世界实验弱连接的强度小世界模型无标度网络技术网络2828WWW电力网电力网因特网因特网复杂网络的事例复杂网络的事例社会网络2929朋友关系网朋友关系网性关系网性关系网演员网演员网科学家合著网科学家合著网科学引文网科学引文网交通运输网络3030城城市

24、市公公共共交交通通网网道道路路交交通通网网航航空空网网生物网络神经网络神经网络生态网络生态网络蛋白质相互作用网络蛋白质相互作用网络基因网络基因网络新陈代谢网络新陈代谢网络32323333 社会网：演员合作网，友谊网，姻亲关系网，科研合作网，Email网 生物网：食物链网，神经网，新陈代谢网，蛋白质网，基因网络 信息网络：WWW，专利使用，论文引用，计算机共享 技术网络：电力网，Internet，电话线路网， 交通运输网：航线网，铁路网，公路网，自然河流网3434 虽然中药方剂的数量很大，但目前还没有统计用的数据库。不得不用手工进行统计，因此统计的数据量受到很大限制。选用了1536付药方，681

25、种药物进行了统计。 节点（药物），边（在一付方剂中药物的相互作用）。 方剂：药物、药物的相互作用构成的固定完全图局域世界，同时也是节点（药物） 的合作成果。 各个完全图通过共用的节点（药物）架起桥梁，构成网络。网络由完全图连接而成，如下图所示。 3535中药方剂网示意图 点（药材）， 边（药材之间相互作用）， 局域世界（方剂）3636 节点食品 边菜肴中两种食品之间的相互作用 每道菜肴局域世界（完全图） 通过公共节点连接构成中国淮扬菜肴网。 329道菜肴，242个顶点（食品），1713条边。 完全类似于中药方剂网的讨论。 37373838三、复杂网络研究内容三、复杂网络研究内容1 1）复杂网络

26、模型）复杂网络模型 典型的复杂网络：随机网、小世界网、无标度网等；典型的复杂网络：随机网、小世界网、无标度网等； 实际网络及其分类。实际网络及其分类。2 2）网络的统计量及与网络结构的相关性）网络的统计量及与网络结构的相关性 度分布的定义和意义，聚集性、连通性的统计量及其实际度分布的定义和意义，聚集性、连通性的统计量及其实际 意义等。意义等。3 3）复杂网络性质与结构的关系）复杂网络性质与结构的关系 同步性、鲁棒性和稳定性与网络结构的关系。同步性、鲁棒性和稳定性与网络结构的关系。4 4）复杂网络的动力学）复杂网络的动力学 信息传播动力学、网络演化动力学、网络混沌动力学。信息传播动力学、网络演化

27、动力学、网络混沌动力学。5 5）复杂网络的复杂结构）复杂网络的复杂结构 社团结构、层次结构、节点分类结构等。社团结构、层次结构、节点分类结构等。6 6）网络控制）网络控制 关键节点控制、主参数控制和控制的稳定性和有效性。关键节点控制、主参数控制和控制的稳定性和有效性。39397）复杂网络建模）复杂网络建模 机理建模、数据建模和实际系统的复杂网络正向与逆向建机理建模、数据建模和实际系统的复杂网络正向与逆向建模。模。8）复杂逻辑网络）复杂逻辑网络 逻辑与高阶逻辑定义、分类、判定算法，高阶逻辑的实际逻辑与高阶逻辑定义、分类、判定算法，高阶逻辑的实际意义等等。意义等等。 F1: AB; F2:(A,

28、B) C; F3:(A, B, C) DA, B, C, D取布尔值。取布尔值。40401 1）突破性进展的主要原因）突破性进展的主要原因 越来越强大的计算设备和迅猛发展的越来越强大的计算设备和迅猛发展的Internet，使得，使得人们开始能够人们开始能够收集收集和和处理处理规模巨大且种类不同的实际规模巨大且种类不同的实际网络网络数据数据。 学科之间的相互交叉使得研究人员可以广泛比较各学科之间的相互交叉使得研究人员可以广泛比较各种种不同类型的网络数据不同类型的网络数据，从而，从而揭示复杂网络的共性揭示复杂网络的共性。 以以还原理论还原理论和和整体论整体论相结合为重要特色的复杂性科相结合为重要特

29、色的复杂性科学的兴起，也促使人们开始从整体上研究网络的结构学的兴起，也促使人们开始从整体上研究网络的结构与性能之间的关系。与性能之间的关系。四、复杂网络研究四、复杂网络研究二十一世纪的二十一世纪的科学科学41412 2）主要研究目标）主要研究目标 发现：发现：揭示刻画网络系统结构的统计性质，以及揭示刻画网络系统结构的统计性质，以及度量这些性质的合适方法。度量这些性质的合适方法。 建模建模：建立合适的网络模型以及理解网络的统计：建立合适的网络模型以及理解网络的统计性质的意义与产生机理。性质的意义与产生机理。 分析分析：基于单个节点的特性和整个网络的结构性：基于单个节点的特性和整个网络的结构性质分

30、析与预测网络的行为。质分析与预测网络的行为。 控制控制：提出改善已有网络性能和设计新的网络的：提出改善已有网络性能和设计新的网络的有效方法，特别是稳定性、同步和数据流通等方面。有效方法，特别是稳定性、同步和数据流通等方面。 1. 网络的图表示网络的图表示一个具体的网络可以抽象成由点集和边集组成的图一个具体的网络可以抽象成由点集和边集组成的图五、复杂网络中的基本概念五、复杂网络中的基本概念网络是一个由多个节点组成的集合，网络是一个由多个节点组成的集合，节点之间有一定的连接节点之间有一定的连接子子: : 国际互联网国际互联网: : 节点节点 由器连接由器连接 光纤光纤 科学引用网科学引用网: :

31、节点节点 文章连接文章连接 文章引用文章引用 社会网络社会网络: : 节点节点 个体人连接个体人连接 人际关系人际关系 1. 网络的图表示网络的图表示五、复杂网络中的基本概念五、复杂网络中的基本概念简单图论简单图论(a) (a) 无向无权节点相同的图无向无权节点相同的图(b) (b) 无向无权节点不同的图无向无权节点不同的图(c) (c) 无向加权图无向加权图(d) (d) 有向无权节点相同的图有向无权节点相同的图(e)(e)2. 平均路径长度平均路径长度五、复杂网络中的基本概念五、复杂网络中的基本概念2. 平均路径长度平均路径长度五、复杂网络中的基本概念五、复杂网络中的基本概念d12 = 1

32、d13 = 1d 23 = 1 d14 = 2d 24 = 1d 34 = 2d15 = 1d 25 = 2d 35 = 2d 45 = 3Total = 16Average: L = 16 / 10 = 1.63. 聚类系数聚类系数五、复杂网络中的基本概念五、复杂网络中的基本概念节点节点i i的邻居：的邻居：节点i的聚类系数聚类系数4. 度与度分布度与度分布五、复杂网络中的基本概念五、复杂网络中的基本概念节点节点i i的度：节点的度：节点 i i 的度的度 ki ki 定义为与该节点连接的其他节点的数目。定义为与该节点连接的其他节点的数目。 直观上看，一个节点的度越大就意味着这个节点在直观上

33、看，一个节点的度越大就意味着这个节点在 某种意义上越某种意义上越“重要重要”（“能力大能力大”）。）。 节点i的平均度：网络中所有节点的度和的平均值 ，记作。事实上，=2q/p ？ v V Gd vpu 度(degree)：节点 i 的度 ki 定义为与该节点连接的其他节点的数目。 直观上看，一个节点的度越大就意味着这个节点在 某种意义上越“重要”（“能力大”）。 u 网络的平均度：网络中所有节点的度和的平均值 ，记作。事实上，=2q/p ？u 度分布函数p(k):随机选定节点的度恰好为k的概率 ?u 节点的聚类系数（簇系数）：在简单图中，设节点v的邻集为N(v), |N(v)|=ki，则节点

34、v的聚类系数定义为这ki个节点之间存在边数Ei与总的可能边数ki(ki-1)/2之比，即：Ci=2Ei/ki(ki-1) 节点v的邻点间关系的密切程度 v V Gd vpknp五、复杂网络中的基本概念五、复杂网络中的基本概念u 网络的聚类系数C：所有节点i的聚类系数Ci的平均值。（0C1） C=0网络中所有节点都是孤立点 C=1网络中任意节点间都有边相连 网络节点间联系的密切程度, 体现网络的凝聚力 许多大规模的实际网络都具有明显的许多大规模的实际网络都具有明显的聚类效应聚类效应。事实上，。事实上，在很多类型的网络在很多类型的网络(如社会关系网络如社会关系网络)中，你的朋友同时也是朋中，你的朋

35、友同时也是朋友的概率会随着网络规模的增加而趋向于友的概率会随着网络规模的增加而趋向于某个非零常数某个非零常数，即当，即当N时，时，C=O(1)。这意味着这些实际的复杂网络并不是完全。这意味着这些实际的复杂网络并不是完全随机的，而是在某种程度上具有类似于社会关系网络中随机的，而是在某种程度上具有类似于社会关系网络中“物以物以类聚，人以群分类聚，人以群分”的特性。的特性。5050u 最短路径最短路径（Shortest path）:两个节点之间边数最少两个节点之间边数最少的路径，最短路径的长度称为两点间的的路径，最短路径的长度称为两点间的距离，距离，用用d dij iju 平均路径长度平均路径长度（

36、特征路径长度）（特征路径长度）L L： 所有节点对之间的距离的平均值。所有节点对之间的距离的平均值。 研究发现：尽管许多实际复杂网络的节点数巨大，研究发现：尽管许多实际复杂网络的节点数巨大，网络的平均路径长度却小的惊人。（小世界效应）网络的平均路径长度却小的惊人。（小世界效应）5151u 介数（介数（BetweennessBetweenness）点介数点介数：网络中通过该节点的最短路径的条数：网络中通过该节点的最短路径的条数 边介数边介数：网络中通过该边的最短路径的条数：网络中通过该边的最短路径的条数反映了节点或边的作用和影响力。如果一对节点间共有反映了节点或边的作用和影响力。如果一对节点间共

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

38、过该节点（边）的信息量就越大，于是就越容传播过程中，通过该节点（边）的信息量就越大，于是就越容易发生拥塞。易发生拥塞。 研究表明，节点介数与度之间有很强的相关性，不同类型的研究表明，节点介数与度之间有很强的相关性，不同类型的网络，其介数分布也大不一样。网络，其介数分布也大不一样。复杂寓于简单 在不同领域许多系统都呈自相似结构,即局部与总体相似。例如国家、河流、行星系等都是这样。 “分形”是研究自相似结构的。分形的构成常遵循一种法则:复杂的分形外形是由简单的规则重复迭代生成的。 以Koch曲线为例:将一直线三等分,中间的1 /3用一等边三角形取代。直线变为4段等长折线。每段直线再按此规则变化,一直重复下去,即生成Koch曲线