PPT—复杂网络.ppt

复杂网络概述不同领域的真实网络社会网：演员合作网，友谊网，姻亲关系网，科研合作网，Email网生物网：食物链网，神经网，新陈代谢网，蛋白质网，基因网络信息网络：，专利使用，论文引用，计算机共享技术网络：电力网，Internet，电话线路网交通运输网：航线网，铁路网，公路网，自然河流网社会网络人物关系网生物网食物链网神经网络信息网络网技术网络电话网交通运输网公路网航空网河流网复杂网络简而言之即呈现高度复杂性的网络。1）结构复杂：表现在节点数目巨大，网络结构呈现多种不同特征。2）网络进化：表现在节点或连接的产生与消失。例如world-widenetwork，网页或链接随时可能出现或断开，导致网络结构不断发生变化。3）连接多样性：节点之间的连接权重存在诧异，且有可能存在方向性。4）动力学复杂性：节点集可能属于非线性动力学系统，例如节点状态随时间发生复杂变化。5）节点多样性：复杂网络中的节点可以代表任何事物，例如，人际关系构成的复杂网络节点代表单独个体，万维网组成的复杂网络节点可以表示不同网页。6）多重复杂性融合：即以上多重复杂性相互影响，导致更为难以预料的结果。例如，设计一个电力供应网络需要考虑此网络的进化过程，其进化过程决定网络的拓扑结构。当两个节点之间频繁进行能量传输时，他们之间的连接权重会随之增加，通过不断的学习与记忆逐步改善网络性能电力系统复杂网络受到随意攻击网络图的基本概念图的基本元素：节点、边关联，邻接有限图，无限图规则图，随机图有向图，无向图(V,E)G度、平均度节点的度分布最短路径与平均路径长度集聚系数aedcb有向图、无向图、不连通图度(degree)：节点i的度ki定义为与该节点连接的其他节点的数目。★直观上看，一个节点的度越大就意味着这个节点在某种意义上越“重要”（“能力大”）。网络的平均度：网络中所有节点的度和的平均值，记作k。度分布函数p(k):随机选定节点的度恰好为k的概率节点的聚类系数（簇系数）：在简单图中，设节点v的邻集为N(v),|N(v)|=ki，则节点v的聚类系数定义为这ki个节点之间存在边数Ei与总的可能边数ki(ki-1)/2之比，即：Ci=2Ei/ki(ki-1)★节点v的邻点间关系的密切程度pvdGVvpnk复杂网络的统计特征网络的聚类系数C：所有节点i的聚类系数Ci的平均值。（0C1）C=0网络中所有节点都是孤立点C=1网络中任意节点间都有边相连★网络节点间联系的密切程度,体现网络的凝聚力★许多大规模的实际网络都具有明显的聚类效应。事实上，在很多类型的网络(如社会关系网络)中，你的朋友同时也是朋友的概率会随着网络规模的增加而趋向于某个非零常数，即当N→∞时，C=O(1)。这意味着这些实际的复杂网络并不是完全随机的，而是在某种程度上具有类似于社会关系网络中“物以类聚，人以群分”的特性。复杂网络的统计特征18最短路径（Shortestpath）:两个节点之间边数最少的路径，最短路径的长度称为两点间的距离.平均路径长度（特征路径长度）L：所有节点对之间的距离的平均值.★研究发现：尽管许多实际复杂网络的节点数巨大，网络的平均路径长度却小的惊人。（小世界效应）复杂网络的统计特征19介数（Betweenness）★点介数：网络中通过该节点的最短路径的条数★边介数：网络中通过该边的最短路径的条数★反映了节点或边的作用和影响力。如果一对节点间共有B条不同的最短路径，其中有b条经过节点i，那么节点i对这对节点的介数的贡献为b/B。把节点i对所有节点对的贡献累加起来再除以节点对总数，就可得到节点i的介数。类似的，边的介数定义为所有节点对的最短路径中经过该边的数量比例。★介数越大，说明经过该节点（边）的最短路径越多。在信息传播过程中，通过该节点（边）的信息量就越大，于是就越容易发生拥塞。★研究表明，节点介数与度之间有很强的相关性，不同类型的网络，其介数分布也大不一样。复杂网络的统计特征20网络介数★网络点介数，网络边介数：所有节点（边）的平均介数★网络介数说明了网络的什么性质？核数★一个图的k-核：反复去掉图中度小于k的节点后，所剩余的子图★若一个节点存在于k-核，而在(k+1)-核中被去掉，则此节点核数为k★节点核数中的最大值称为网络图的核数★节点核数可以表明节点在核中的深度；即便一个节点的度数很高，它的核数也可能很小。例如：包含N个节点的星型网络的中心节点的度数为N-1，但它的核数为1复杂网络的统计特征三、社区结构整个网络是由若干个“社区或“组’’构成的。每个社区内部的结点间的连接相对非常紧密，但是各个社区之间的连接相对来说却比较稀疏（网络中的顶点可以分成组,组内连接稠密而组间连接稀疏）。我们将复杂网络的这种结构特征称之为复杂网络的社团结构或社区结构。社区结构是复杂网络的一个重要的特性，社区也被称为簇，大量研究表明网络是由各种不同类型的节点构成的，一般情况下，在不同类型的节点间存在较少的边，而在相同类型的节点间会有较多的边。位于一个子图内的节点和边组成一个社团。复杂网络社区结构还有一个很重要的特性,即是它的层次特性现实中的网络是由一个个较小的社团组成,而这些社团又可以包括更小的社团。发现网络中的社团结构,对于了解网络结构，分析网络特性都具有很重要的意义。22复杂网络研究内容1）复杂网络模型典型的复杂网络：随机网、小世界网、无标度网等；实际网络及其分类。2）网络的统计量及与网络结构的相关性度分布的定义和意义，聚集性、连通性的统计量及其实际意义等。3）复杂网络性质与结构的关系同步性、鲁棒性和稳定性与网络结构的关系。4）复杂网络的动力学信息传播动力学、网络演化动力学、网络混沌动力学。5）复杂网络的复杂结构社团结构、层次结构、节点分类结构等。6）网络控制关键节点控制、主参数控制和控制的稳定性和有效性。237）复杂网络建模机理建模、数据建模和实际系统的复杂网络正向与逆向建模。8）复杂逻辑网络逻辑与高阶逻辑定义、分类、判定算法，高阶逻辑的实际意义等等。F1:A→B;F2:(A,B)→C;F3:(A,B,C)→DA,B,C,D取布尔值。节点1到7之间的最短路13，平均路径长度5.47，平均度为3.4，集聚系数为0.48。早期网络模型规则图和随机图规则图系统中节点及其与边的关系是固定的，每个节点都有相同的度数。随机图平均说来系统中节点及其与边的关系不确定。规则图的特征平均度为3。随机图的特征节点确定，但边以概率任意连接。节点不确定，点边关系也不确定。p随机图——节点19，边43平均度为2.42，集聚系数为0.13。随机图——节点42，边118平均度为5.62，集聚系数为0.133。ER模型Erdös和Rényi（ER）最早提出随机网络模型并进行了深入研究，他们是用概率统计方法研究随机图统计特性的创始人。给定N个节点，没有边，以概率p用边连接任意一对节点，用这样的方法产生一随机网络。ER模型节点的度分布：平均值为的泊松分布k!λeP(k)kλPoissondistribution三、复杂网络模型小世界（small-world)网络模型无标度（scale-free)网络模型小世界实验20世纪60年代美国哈佛大学的社会心理学家StanleyMilgram通过一些社会调查后给出的推断是：地球上任意两个人之间的平均距离是6。这就是著名的“六度分离”（sixdegreesofseparation）推断。小世界实验—六度分离我们或许有过这样的经历：偶尔碰到一个陌生人，同他聊了一会后发现你认识的某个人居然他也认识，然后一起发出”这个世界真小”的感叹。那么对于世界上任意两个人来说，借助第三者、第四者这样的间接关系来建立起他们两人的联系平均来说最少要通过多少人呢？美国社会心理学家斯坦利•米尔格伦(StanleyMilgram)在1967年通过一些实验后得出结论：中间的联系人平均只需要5个。他把这个结论称为“六度分离”。六度分离:平均只要通过5个人，你就能与世界任何一个角落的任何一个人发生联系。这个结论定量地说明了我们世界的”大小”，或者说人与人关系的紧密程度。30多年来，六度分离理论一直被作为社会心理学的经典范例之一。尽管如此，实际上这个理论并没有得到严格的证实。美国心理学教授朱迪斯•克兰菲尔德(JudithKleinfeld)对米尔格伦最初的实验提出不同意见，因为她发现实验的完成率极低。小世界实验---六度分离米尔格伦的实验过程是：他计划通过人传人的送信方式来统计人与人之间的联系。首先把信交给志愿者A，告诉他信最终要送给收信人S。如果他不认识S，那么就送信到某个他认识的人B手里，理由是A认为在他的交集圈里B是最可能认识S的。但是如果B也不认识S，那么B同样把信送到他的一个朋友C手中，……，就这样一步步最后信终于到达S那里。这样就从A到B到C到……最后到S连成了一个链。斯坦利•米尔格伦就是通过对这个链做了统计后做出了六度分离的结论。小世界模型为了描述从一个局部有序系统到一个随机网络的转移过程，Watts和Strogatz（WS）提出了一个新模型，通常称为小世界网络模型。WS模型始于一具有N个节点的一维网络，网络的节点与其最近的邻接点和次邻接点相连接，然后每条边以概率p重新连接。约束条件为节点间无重边，无自环。（一）很小的最短路径长度平均值（二）很大的群聚系数的小世界网络C(p):聚类系数L(p):平均路径长度P(k)=0.1p(k)=0.3当p等于0时，对应于规则图。两个节点间的平均距离L线性地随N增长而增长，集聚系数大。当p等于1时，系统变为随机图。L对数地随N增长而增长，且集聚系数随N减少而减少。在p等于（0，1）区间任意值时，L约等于随机图的值，网络具有高度集聚性---小世界效应。无标度(Scale-free)网络现实世界的网络大部分都不是随机网络，少数的节点往往拥有大量的连接，而大部分节点却很少。——无标度网络。这里的无标度是指网络缺乏一个特征度值（或平均度值），即节点度值的波动范围相当大。无标度网络（Scale-freenetwork）按生长方式定义：如果网络的每个节点的连接数与此节点产生新连接的概率成增函数关系，这个网络就叫无尺度网络。按分布定义：如果网络中有一定数量的连接的节点数与此连接数量成减函数，这个网络就叫无尺度网络。Scale-free网络的发现信息交换网（万维网、国际互联网、电话网、电力网）社会网络（电影演员合作网、科研合作图、引文网、人类性接触网、语言学网）生物网络（细胞网络、生态网络、蛋白质折叠）Scale-free网络的特性度分布呈幂率分布中枢节点出现鲁棒性脆弱性无标度（Scale-free）网络无标度模型由Albert-LászlóBarabási和RékaAlbert在1999年首先提出，现实网络的无标度特性源于众多网络所共有的两种生成机制：（ⅰ）网络通过增添新节点而连续扩张；（ⅱ）新节点择优连接到具有大量连接的节点上。BA模型增长和择优连接这两种要素激励了Barabási－Albert模型的提出，该模型首次导出度分布按幂函数规律变化的网络。模型的算法如下：（1）增长：开始于较少的节点数量（m0），在每个时间间隔增添一个具有m（≤m0）条边的新节点，连接这个新节点到m个不同的已经存在于系统中的节点上。（2）择优连接：在选择新节点的连接点时，假设新节点连接到节点i的概率π取决于节点i的度数即经过t时间间隔后，该算法程序产生一具有N=t+m0个节点，mt条边的网络。数量模拟表明具有k条边的节点的概率服从指数为r=3的幂指数分布。jjiikkk)(模型的度分布是与时间无关的渐进分布且与系统规模无关。幂律度分布的系数与成正比。无标度模型的动态特性可以用各种分析方法给出：平均场理论主方程法变化率方程法2mBaralási-Albert模型的限制条件保持了网络的增长特性，不考虑择优连接，网络度分布呈指数衰