复杂系统理论基础

主讲人：蒋朝哲副教授复杂系统理论基础第一章引言1.1关于复杂系统1.2复杂系统与复杂网络1.3什么是复杂网络1.4复杂网络研究简史1.5复杂网络基本概念1.6实际复杂网络网络1.1复杂系统的特征复杂系统可表述为具有某些特性的系统，这些系统某一方面的特性超出了各组成部分的叠加1）系统个单元联系紧密，构成了一个网络。每个单元变化都会彼此影响。2）系统具有多层次，多功能的结构。3）系统是开放的，与环境有密切的联系，并能向适应环境的方向变化。4）系统是动态的，处于不断的发展变化中，具有某种程度的智能和自组织能力1.2复杂系统与复杂网络复杂系统不能够用分析的方法去研究，必须考虑个体之间的关联和作用；理解复杂系统的行为应该从理解系统相互作用网络的拓扑结构开始；网络拓扑结构的信息是构建系统模型、研究系统性质和功能的基础；复杂网络是构成复杂系统的基本框架（backbone），每一个复杂系统都可以看作是单元或个体之间的相互作用网络。1.2复杂系统与复杂网络复杂网络是研究复杂系统的一种角度和方法，它关注系统中个体相互关联的作用的拓扑结构，是理解复杂系统性质和功能的基础。1.3什么是复杂网络复杂网络简而言之即呈现高度复杂性的网络。其复杂性主要表现在以下几个方面：1）结构复杂性网络连接结构错综复杂，网络连接结构随时变化2）节点复杂性网络中的节点可能具有分叉和混沌等复杂非线性行为的动力系统，且网络中可能存在多种不同类型节点。3）各种复杂性因素的相互作用实际的复杂网络会受到各种各样因素的影响和作用。1.4复杂网络研究简史1.1736年，Euler：哥尼斯堡七桥问题（图论的开创）关于复杂网络的研究与七桥问题的研究一脉相承：网络结构与网络性质密切相关Canonewalkacrossthesevenbridgesandneveracrossthesameonetwice?---No!(ProvedbyEulerin1736)1.4复杂网络研究简史2.1959，Erdős和Rényi,随机图理论（ER随机图）任一两个节点间连边的概率为p，对于给定的概率p，要么几乎每个图都具有某个性质，要么几乎都没有：ER随机图的许多重要性质都是突然涌现的。1.4复杂网络研究简史3.小世界实验（1）1967年Milgram小世界实验：每个参与者被要求通过自己所认识的人，用自己认为尽可能少的传递次数，设法把一封信最终转交到一个给定的目标对象手中。实验结果：从一个志愿者到其他目标对象的平均距离为6实验成果从某种程度上反映了人际关系的“小世界”特征1.4复杂网络研究简史例：如何仅用3步就从堪萨斯州的一位农场主首重转交到马萨诸塞州的神学院的妻子手中1.4复杂网络研究简史（2）1998年Granovetter,弱连接的强度：Granovetter发现，在寻找工作时，那些关系密切的朋友（强连接）反倒没有那些关系一般的甚至偶尔见面的朋友（弱连接）更能够发挥作用。1.4复杂网络研究简史（3）1998年，Watts和Strogatz，小世界模型：通过以某个很小的概率p切断规则网络中原始的边,并随机选择新的端点重新连接,构造出了一种介于规则网络和随机网络之间的网络(WS网络),它同时具有大的簇系数和小的平均距离,具有这种效应的网络就是小世界网络(smallworldnetworks)。1.4复杂网络研究简史（4）1999年,Barabasi和Albert，无标度网络许多实际的复杂网络的链接度分布具有幂律形式,即,其中k为点的度（Degree），λ为幂指数一般分布在2~3之间。由于幂律分布没有明显的特征长度，所以被称为无标度（scale-free）网络。kkP~)(1.4复杂网络研究简史目前，复杂网络理论研究的主要内容：①发现：揭示刻画网络系统结构的统计性质，以及度量这些性质的合适方法②建模：建立合适的网络模型以帮助理解统计性质的意义与产生机理③分析：基于单个节点的特性和整个网络的结构性之分析与预测网络的行为④控制：提出改善已有网络性能和设计新的网络的有效方法，特别是稳定性、同步和数据流通等方面1.5基本概念描述复杂网络结构的统计特性有三个基本概念：平均路径长度（averagelength）聚类系数（clusteringcoefficient)度分布（degreedistribution）1.5基本概念（1）网络的图表示一个具体网络可抽象为一个由点集V和边集E组成的图G=(V,E)。（a）单一类型节点和边的无向网络（b）不同类型节点的无向网络（c）节点和边权重变化的无向网络（c）有向网络1.5基本概念（2）平均路径长度概念：任意两个节点之间的距离平均值公式：网络的直径：11(1)2ijijLdNN其中：L——平均路径长度N——网络中的节点数dij——网络中两个节点i和j之间的距离，即为连接这两点的最短路径上的变数其中：D——网络的直径,maxijijDd例：21543D=d45=3L=1.61.5基本概念（3）聚类系数节点i的聚类系数Ci：即：其中：ki——与节点i连接的其他节点的数目Ei——ki个节点实际存在的边数网络聚类系数C：所有节点i的聚类系数Ci的平均值，0≤C≤1。C=0，当且仅当所有的节点均为孤立节点，即没有任何连接边C=1，当且仅当网络是全局耦合的，即网络中任意两个节点都是直接相连的。iiCi与点相连的三角形的数量与点相连的三元组的数量(1)2iiiCkkiE1.5基本概念（4）度与度分布度ki:与节点i连接的其他节点的数目。有向网络分成出度与入度。直观上看，一个节点的度越大就意味着这个节点在某种意义上越“重要”节点的度分布情况可用分布函数P(k)来描述：P(k)表示的是一个随机选定的节点的度恰好为k的概率。1.5基本概念（4）度与度分布Poisson分布：完全随机网络Poisson分布的形状在远离峰值k处呈指数下降，意味着当k»k时，度为k的节点实际上是不存在的，这类网络成为均匀网络。1.5基本概念（4）度与度分布幂律分布：许多实际网络更接近于幂律分布，用幂律形式能更好的描述，幂律分布曲线比Poisson指数分布曲线下降要缓慢得多。幂律分布也称无标度分布，具有幂律分布的网络也称为无标度网络。类似于幂律分布所表现的性质，这类网络非均匀的，也称非均匀网络（inhomogeneousnetwork），具有度相对很高的节点：网络的“集线器”（hub）。美国的航空网络可看成是一个无标度网络Pk1.5基本概念（4）度与度分布另一种表示度数据的方法是绘制累积度分布函数（cumulativedegreedistributionfunction),表示度小于k的节点的概率分布：''()kkkppk1.6实际复杂网络国际互联网万维网WorldWideWeb（）美国航空网生物网络现实中不同领域的复杂网络社会网：演员合作网，友谊网，姻亲关系网，科研合作网，Email网生物网：食物链网，神经网，新陈代谢网，蛋白质网，基因网络信息网络：，专利使用，论文引用，计算机共享技术网络：电力网，Internet，电话线路网交通运输网：航线网，铁路网，公路网，自然河流网