第一章复杂动态网络基本概念课件

复杂动态网络及其控制任课教师：樊春霞南京邮电大学自动化学院课程介绍学时：32内容：复杂动态网络基本概念、小世界模型、无尺度模型、复杂动态网络状态耦合同步方法、复杂动态网络输出耦合同步方法、时滞网络同步、复杂动态网络拓扑辨识、复杂动态网络故障诊断参考书1．汪小帆、李翔、陈关荣编著，复杂网络：理论及其应用，清华大学出版社，2006年.2.汪小帆、李翔、陈关荣编著，网络科学导论，高等教育出版社，2012年.3.针对研究方向，网络资料，海量相关资料：许晓鸣,郭雷.复杂网络.上海科技教育出版社,2006年11月.S.H.Strogatz.Nature,410,(2001)268.R.Albert,A.-L.Barabasi.Rev.Mod.Phys.,51(2002)1079.M.E.J.Newman.SIAMRev.,45(2003),167.S.N.Dorogovtesev,J.Mendes.EvolvingofNetworks,OxfordUn.Press,2003.E.Ben-Naim,etal.ComplexNetworks,Springer,2004.S.Boccaletti,etal.ComplexNetworks:Structureanddynamics,Phys.Rep.424(2006)175-308.Newman,Barabasi,Watts.TheStructureandDynamicsofNetworks.PrincetonUniversityPress,2006.4复杂动态网络基本概念1.什么是复杂网络？2．为什么研究复杂网络?3.复杂动态网络的基本概念61.二十一世纪涌现的新现象万维网万维网是怎样“链”接的？从一个页面到另一个页面平均需要点击多少次鼠标？一、为什么研究复杂网络？

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

二十世纪，科学研究的特点是分析的方法，还原论的方法：物理学（牛顿力学、量子力学、电子论、半导体），化学（量子分子论），生物（双螺旋结构）；建筑工程（应力应变分析），……。

二十一世纪（二十世纪末），系统成为主要的研究对象，整合成为主要方法。普列高津的耗散结构理论，哈肯的协同学，混沌和复杂系统理论，系统生物学……。10美国《Science》周刊：“如果对当前流行的、时髦的关键词进行一番分析，那么人们会发现，“系统”高居在排行榜上。”

当分析为主要的研究方法时，人类关注如何将系统“分析”、“分解”，揭开系统的细部，了解是什么元素或部件组成了系统，却忽视或破坏了这些元素是如何组合成系统的。而整合的方法在于了解细部以后，研究“如何组合”的问题。这种方法导致复杂网络结构的研究。二、复杂系统与复杂网络111.1.复杂系统与复杂网络的概念

（1）什么是系统？系统：集合（具体元素）+结构+功能。（例：不同角度分析系统，人）（2）系统的结构是什么？一切系统的基础结构都是网络；一切系统的核心结构都是逻辑网络；复杂系统的结构就是复杂网络。12复杂网络是构成复杂系统的基本结构，每个复杂系统都可以看作是单元或个体之间的相互作用网络；复杂网络在刻画复杂性方面的重要性是由于结构决定功能的。复杂网络是研究复杂系统的一种角度和方法，它关注系统中因子相互关联作用的拓扑结构，是理解复杂系统性质和功能的基础。

我认为，下个世纪将是复杂性的世纪(Ithinkthenextcenturywillbethecenturyofcomplexity)——斯蒂芬.霍金(StephenHaking)（2000）英国剑桥大学应用数学及理论物理学系教授，当代最重要的广义相对论和宇宙论家，是当今享有国际盛誉的伟人之一，被称为在世的最伟大的科学家，还被称为“宇宙之王”。网络与复杂网络成为二十一世纪的新科学领域！1)开放性。即与环境和其它系统进行相互作用，交换物质、能量、信息，保持和发展系统内部的有序性与结构稳定性。在这种交换中，系统经历着从低级向高级、从简单到复杂、从无序向有序的不断优化的动态发展过程。虽然开放性是所有真实系统的基本属性，但这里的开放非指一般意义上的相互作用与交流，而开放的度量、性质、强度对复杂系统的性态、演化具有决定性的意义。例子，人，城市网络簇。２)涌现性。即内部元素通过非线性相互作用，在宏观层次上产生出新的、元素不具有的整体属性，表现为整体斑图、模式等。虽然涌现同样是所有系统都具有的，但这里涌现意味着新的整体属性的产生。例子，

“整体大于部分之和”，大脑的神经网络系统142.复杂系统与复杂网络的主要特性：15３）演化性（不可逆性）。即通过与所在环境中的其它系统的相互作用和内部的自组织，使系统发展到新的阶段，表现出阶段性、临界性，完成系统演化的生命周期。例:社会网络中的人，生物群体的自组织系统（鸟群）４）复杂性。包括系统的结构、行为、功能等多个方面同时具有的复杂性。结构复杂性表现为多元性，非对称性，非均匀性，非线性（分岔(Bifurcation),混沌(Chaos),分形Fractal）；行为复杂性表现为学习，自适应性，混沌同步，混沌边沿，随机性等等；认识复杂性又称为主观复杂性，它表现为不确定性，描述复杂性与计算复杂性等等。例:神经网络中的突触有强有弱，可抑制也可兴奋

５）网络结构。即系统内部和系统之间的相互作用可以看成由节点、边（连接）构成的体系，出现网络复杂性、小世界特征与无标度特征等。16一切系统都具有网络结构，复杂系统具有复杂的网络结构。173.网络系统的复杂性（1）结构复杂性网络连接结构错综复杂、极其混乱，同时又蕴含着丰富的结构：社区、基序、聚集性、生成规律性等等，而且网络连接结构可能是随时间变化的，例如，WWW上每天都不停地有页面和链接的产生和删除。静态结构的复杂性和结构动态演化的复杂性。例：神经系统由神经元互连形成，连接以“突触连接结构”实现，突触有强弱、兴奋与抑制、不同的神经递质；连接不断改变，形成连接结构变化。（重边，加权等）18（2）节点复杂性

A）节点的独立或固有特性网络中的节点可能是具有分岔和混沌等复杂非线性行为的动力系统。例如，基因网络中每个节点都具有复杂的时间演化行为。而且，一个网络中可能存在多种不同类型的节点。例如，控制哺乳动物中细胞分裂的生化网络就包含各种各样的基质和酶。

B)关联引发的节点特性当关联失去时这类特性会在节点处消失或改变。例如，耦合神经元重复地被同时激活，那么它们之间的连接就会加强，这被认为是记忆和学习的基础。19（3）复杂网络之间相互影响的复杂性

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

复杂网络也是研究复杂系统的一种技术和方法，它关注系统中个体相互作用的拓扑结构，是理解复杂系统性质和功能的基本方法。

复杂网络是二十一世纪科学研究的思想和理念，它启发我们用什么观点理解这个世界：整个世界以及组成世界的任何细部都是由网络及其变化形成的。21三、复杂网络研究简史

格尼斯堡七桥问题Euler（1707~1783），瑞士数学家，图论之父一笔画问题

1736年，七桥游戏22随机图理论

20世纪60年代，由两位匈牙利数学家Erdǒs和Rényi建立的随机图理论（randomgraphtheory）被公认为是在数学上开创了复杂网络理论的系统性研究。Erdǒs和Rényi的最重要的发现是：ER随机图的许多重要性质都是突然涌现的。也就是说，对于任一给定的概率p，要么几乎每一个图都具有某个性质Q（比如说，连通性），要么几乎每一个图都不具有该性质。在20世纪的后40年中，随机图理论一直是研究复杂网络的基本理论。23小世界实验20世纪60年代美国哈佛大学的社会心理学家StanleyMilgram通过一些社会调查后给出的推断是：地球上任意两个人之间的平均距离是6。这就是著名的“六度分离”（sixdegreesofseparation）推断。

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

一个有趣的数学家故事：Erdǒs数证明小世界实验。24

有两篇开创性的文章可以看作是复杂网络研究新纪元开始的标志：

一篇是美国康奈尔（Cornell）大学理论和应用力学系的博士生Watts及其导师、非线性动力学专家Strogatz教授于1998年6月在Nature杂志上发表的题为《“小世界”网络的集体动力学》（CollectiveDynamicsof‘Small-World’Networks）的文章；另一篇是美国NotreDame大学物理系的Barabāsi教授及其博士生Albert于1999年10月在Science杂志上发表的题为《随机网络中标度的涌现》（EmergenceofScalinginRandomNetworks）的文章。这两篇文章分别揭示了复杂网络的小世界特征和无标度性质，并建立了相应的模型以阐述这些特性的产生机理。

251998，Watts和Strogatz：WS小世界网络D.J.Watts,andS.H.Strogatz,Nature,393,440-442(1998).26

A.-L.Barabasi

andR.Albert,Science,286,509(1999).1999，Barabasi和Albert

：BA无标度网络27复杂网络研究的简史列表时间（年）人物事件173619591967197319981999EülerErdǒs和RényiMilgramGranovetterWatts和StrogatzBarabási和Albert七桥问题随机图理论小世界实验弱连接的强度小世界模型无标度网络技术网络28WWW电力网因特网复杂网络的事例社会网络29朋友关系网性关系网演员网科学家合著网科学引文网交通运输网络30城市公共交通网道路交通网航空网生物网络神经网络生态网络蛋白质相互作用网络基因网络新陈代谢网络SantaFe研究所的科学家合作网3233经济物理学科学家合作网不同领域的复杂网络

社会网：演员合作网，友谊网，姻亲关系网，科研合作网，Email网生物网：食物链网，神经网，新陈代谢网，蛋白质网，基因网络信息网络：WWW，专利使用，论文引用，计算机共享技术网络：电力网，Internet，电话线路网，交通运输网：航线网，铁路网，公路网，自然河流网34中药方剂网虽然中药方剂的数量很大，但目前还没有统计用的数据库。不得不用手工进行统计，因此统计的数据量受到很大限制。选用了1536付药方，681种药物进行了统计。节点（药物），边（在一付方剂中药物的相互作用）。方剂：药物、药物的相互作用构成的固定完全图局域世界，同时也是节点（药物）的合作成果。各个完全图通过共用的节点（药物）架起桥梁，构成网络。网络由完全图连接而成，如下图所示。35中药方剂网示意图点（药材），边（药材之间相互作用），局域世界（方剂）36中国淮扬菜肴网节点——食品边——菜肴中两种食品之间的相互作用每道菜肴——局域世界（完全图）通过公共节点连接构成中国淮扬菜肴网。329道菜肴，242个顶点（食品），1713条边。完全类似于中药方剂网的讨论。3738三、复杂网络研究内容1）复杂网络模型典型的复杂网络：随机网、小世界网、无标度网等；实际网络及其分类。2）网络的统计量及与网络结构的相关性度分布的定义和意义，聚集性、连通性的统计量及其实际意义等。3）复杂网络性质与结构的关系同步性、鲁棒性和稳定性与网络结构的关系。4）复杂网络的动力学信息传播动力学、网络演化动力学、网络混沌动力学。5）复杂网络的复杂结构社团结构、层次结构、节点分类结构等。6）网络控制关键节点控制、主参数控制和控制的稳定性和有效性。397）复杂网络建模机理建模、数据建模和实际系统的复杂网络正向与逆向建模。8）复杂逻辑网络逻辑与高阶逻辑定义、分类、判定算法，高阶逻辑的实际意义等等。F1:A→B;F2:(A,B)→C;F3:(A,B,C)→DA,B,C,D取布尔值。401）突破性进展的主要原因①越来越强大的计算设备和迅猛发展的Internet，使得人们开始能够收集和处理规模巨大且种类不同的实际网络数据。②学科之间的相互交叉使得研究人员可以广泛比较各种不同类型的网络数据，从而揭示复杂网络的共性。③以还原理论和整体论相结合为重要特色的复杂性科学的兴起，也促使人们开始从整体上研究网络的结构与性能之间的关系。四、复杂网络研究—二十一世纪的科学412）主要研究目标发现：揭示刻画网络系统结构的统计性质，以及度量这些性质的合适方法。建模：建立合适的网络模型以及理解网络的统计性质的意义与产生机理。分析：基于单个节点的特性和整个网络的结构性质分析与预测网络的行为。控制：提出改善已有网络性能和设计新的网络的有效方法，特别是稳定性、同步和数据流通等方面。

1.网络的图表示一个具体的网络可以抽象成由点集和边集组成的图五、复杂网络中的基本概念网络是一个由多个节点组成的集合，节点之间有一定的连接例子:国际互联网:节点–路由器连接–光纤科学引用网:节点–文章连接–文章引用社会网络:节点–个体人连接–人际关系

1.网络的图表示五、复杂网络中的基本概念简单图论(a)无向无权节点相同的图(b)无向无权节点不同的图(c)无向加权图(d)有向无权节点相同的图(e)……2.平均路径长度五、复杂网络中的基本概念2.平均路径长度五、复杂网络中的基本概念d12=1d13=1d23=1d14=2d24=1d34=2d15=1d25=2d35=2d45=3Total=16Average:L=16/10=1.63.聚类系数五、复杂网络中的基本概念节点i的邻居：节点i的聚类系数4.度与度分布五、复杂网络中的基本概念节点i的度：节点i的度

ki定义为与该节点连接的其他节点的数目。★直观上看，一个节点的度越大就意味着这个节点在某种意义上越“重要”（“能力大”）。节点i的平均度：网络中所有节点的度和的平均值，记作<k>。事实上，<k>=2q/p？度(degree)：节点i的度

ki

定义为与该节点连接的其他节点的数目。★直观上看，一个节点的度越大就意味着这个节点在某种意义上越“重要”（“能力大”）。

网络的平均度：网络中所有节点的度和的平均值，记作<k>。事实上，<k>=2q/p？度分布函数p(k):随机选定节点的度恰好为k的概率

?节点的聚类系数（簇系数）：在简单图中，设节点v的邻集为N(v),|N(v)|=ki，则节点v的聚类系数定义为这ki个节点之间存在边数Ei与总的可能边数ki(ki-1)/2之比，即：Ci=2Ei/ki(ki-1)★节点v的邻点间关系的密切程度

五、复杂网络中的基本概念网络的聚类系数C：所有节点i的聚类系数Ci的平均值。（0