复杂网络及其应用研究新进展.ppt

复杂网络及其应用研究新进展 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望v自组织：如果一个系统靠外部指令而形成组织，就是他组织；如果不存在外部指令，系统按照相互默契的某种规则，各尽其责而又协调地自动地形成有序结构，就是自组织。自相似：一种形状的每一部分在几何上相似于整体，一般对分形而言。吸引子：相空间（可以表示出一个系统所有可能状态的空间）中稳 定的不动点集。小世界：无标度：小世界网络图无标度网络图网络分类网络分类v规则网络规则网络:规则网络具有很强规则性，例如全连接网络，规则网络具有很强规则性，例如全连接网络，环形，链形，星形网络以及格点和分形图等环形，链形，星形网络以及格点和分形图等 v随机网络随机网络:随机网络是指按照某种明确的统计规律生成随机网络是指按照某种明确的统计规律生成的网络，与规则网络相对应，主要是经典的随机图模型的网络，与规则网络相对应，主要是经典的随机图模型及其派生出来的相关模型及其派生出来的相关模型 v小世界网络小世界网络:主要有主要有WS改边小世界网络和改边小世界网络和NW加边小世加边小世界网络界网络v无标度网络无标度网络：BA无标度网络是第一个无标度网络。我无标度网络是第一个无标度网络。我们将主要讨论此类网络上的同步与传播问题们将主要讨论此类网络上的同步与传播问题v可导航网络可导航网络规则网络规则网络系统中节点及其与边的关系是固定的。（a）全局耦合网络；（b）最近邻耦合网络；（c）星形网络全局耦合网络具有最小的平均路径长度Lgc=1和最大的聚类系数Cgc=1；最近邻耦合网络:包含N个围成一个环的点，其中每个节点都与它左右各K/2个邻居点相连（K为偶数），对于较大的K值，最近邻耦合网络的聚类系数为因此，这样的网络是高度聚类的。对于固定的K值，网络平均路径长度为 星形耦合网络：有一个中心点，其余N-1个点都只与这个中心点连接，其平均路径长度为 聚类系数为 随机图随机图v随机图是与规则网络相反的网络，一个典型模型是Erdos和Renyi于40多年前开始研究的随机图模型。假设有大量的纽扣（N1）散落在地上，并以相同的概率p给每对纽扣系上一根线。这样就会得到一个有N个节点，约pN(N-1)/2条边的ER随机图的实例。1998，Watts和Strogatz：WS小世界网络WS小世界模型NW小世界模型C(p):平均聚集系数 L(p):平均最短路径小世界网络小世界网络作为从完全规则网络向完全随机图的过渡，Watts和Strogtz于1998年引入了一个小世界网络模型，称为WS小世界模型。其构造算法如下：从规则图开始：考虑一个含有N个点的最近邻耦合网络，它们围成一个环，其中每个节点都与它左右相邻的各K/2个节点相连，K是偶数。随机化重连：以概率p随机地重连网络中的每个边，即将边的一个端点保持不变，而另一个端点取为网络中随机选择的一个节点。其中规定，任意两个不同节点之-间至多只能有一条边，并且每一个节点都不能有边与自身相连。具有较短的平均路径长度又具有较高的聚类系数的网络就称为小世界网络。Newman和Watts提出了NW小世界模型，用“随机化加边”取代WS小世界模型构造中的“随机化重连”。算法如下：从规则图开始：含有N 个节点的最近邻耦合网络。随机化加边：以概率P在随机选取的一对节点之间加上一条边。NW小世界模型中，p=0对应于原来的最近邻耦合网络，p=1对应于全局耦合网络。无标度网络模型无标度网络模型 研究发现许多复杂网络的连接度分布函数具有幂律形式，由于这类网络的节点的连接度没有明显的特征长度，故称为无标度网络。Barabasi 和Albert 提出了一个无标度网络模型，称为BA模型。该模型考虑到了实际网络的两个重要特性：增长特性；优先连接特性。基于这两个特性，BA无标度网络模型构造算法如下：增长：从一个具有m0个节点的网络开始，每次引入一个新的节点，并且连到m个已存在的节点上，这里 。优先连接：一个新节点与一个已经存在的节点i相连接的概率 与节点i的度ki，节点j的度kj之间满足如下关系：幂律分布函数的无标度性质：考虑一个概率分布函数f(x)，如果对任意给定常数a，存在常数 b 使得函数 f(x)满足如下“无标度条件”:f(ax)=bf(x)那么必有(假定 )也就是说，幂律分布函数是唯一满足“无标度条件”的概率分布函数。http:/http:/www.izuqiu.orghttp:/http:/ yyy复杂网络应用复杂网络应用电力系统复杂网络的应用：电力系统复杂网络受到随意攻击细胞复杂网络的应用：肺部细胞形成一个复杂网络因特网复杂网络的应用：因特网形成的复杂网络交通运输复杂网络的应用：城城市市公公共共交交通通网网道道路路交交通通网网航航空空网网复杂网络的统计特征复杂网络的统计特征u度(degree)：节点 i 的度 ki 定义为与该节点连接的其他节点的数目。直观上看，一个节点的度越大就意味着这个节点在 某种意义上越“重要”（“能力大”）。u网络的平均度：网络中所有节点的度和的平均值 ，记作。事实上，=2q/p u度分布函数p(k):随机选定节点的度恰好为k的概率 u节点的聚类系数（簇系数）：在简单图中，设节点v的邻集为N(v),|N(v)|=ki，则节点v的聚类系数定义为这ki个节点之间存在边数Ei与总的可能边数ki(ki-1)/2之比，即：Ci=2Ei/ki(ki-1)节点v的邻点间关系的密切程度 网络的聚类系数C：所有节点i的聚类系数Ci的平均值。（0C1）C=0网络中所有节点都是孤立点 C=1网络中任意节点间都有边相连 网络节点间联系的密切程度,体现网络的凝聚力 许多大规模的实际网络都具有明显的许多大规模的实际网络都具有明显的聚类效应聚类效应。事实上，。事实上，在很多类型的网络在很多类型的网络(如社会关系网络如社会关系网络)中，你的朋友同时也是朋友中，你的朋友同时也是朋友的概率会随着网络规模的增加而趋向于的概率会随着网络规模的增加而趋向于某个非零常数某个非零常数，即当，即当N时，时，C=O(1)。这意味着这些实际的复杂网络并不是完全随。这意味着这些实际的复杂网络并不是完全随机的，而是在某种程度上具有类似于社会关系网络中机的，而是在某种程度上具有类似于社会关系网络中“物以类物以类聚，人以群分聚，人以群分”的特性。的特性。介数（介数（BetweennessBetweenness）点介数点介数：网络中通过该节点的最短路径的条数 边介数：网络中通过该边的最短路径的条数反映了节点或边的作用和影响力。如果一对节点间共有B条不同的最短路径，其中有b条经过节点i，那么节点i对这对节点的介数的贡献为b/B。把节点i对所有节点对的贡献累加起来再除以节点对总数，就可得到节点i的介数。类似的，边的介数定义为所有节点对的最短路径中经过该边的数量比例。介数越大，说明经过该节点（边）的最短路径越多。在信息传播过程中，通过该节点（边）的信息量就越大，于是就越容易发生拥塞。研究表明，节点介数与度之间有很强的相关性，不同类型的网络，其介数分布也大不一样。网络介数网络介数 网络点介数，网络边介数：所有节点（边）的平均介数 网络介数说明了网络的什么性质 核数核数 一个图的一个图的k-核核：反复去掉图中度小于k 的节点后，所剩余的子图 若一个节点存在于k-核，而在(k+1)-核中被去掉，则此节点核数为k 节点核数中的最大值称为网络图的核数 节点核数可以表明节点在核中的深度；即便一个节点的度数很高，它的核数也可能很小。例如：包含N个节点的星型网络的中心节点的度数为N-1，但它的核数为1 复杂网络的研究内容复杂网络的研究内容1 1）复杂网络模型）复杂网络模型 典型的复杂网络：随机网、小世界网、无标度网等；典型的复杂网络：随机网、小世界网、无标度网等；实际网络及其分类。实际网络及其分类。2 2）网络的统计量及与网络结构的相关性）网络的统计量及与网络结构的相关性 度分布的定义和度分布的定义和意义意义，聚集性、连通性的统计量及其实际，聚集性、连通性的统计量及其实际 意义等。意义等。3 3）复杂网络性质与结构的关系）复杂网络性质与结构的关系 同步性、鲁棒性和稳定性与网络结构的关系。同步性、鲁棒性和稳定性与网络结构的关系。4 4）复杂网络的动力学）复杂网络的动力学 信息传播动力学、网络演化动力学、网络混沌动力学。信息传播动力学、网络演化动力学、网络混沌动力学。5 5）复杂网络的复杂结构）复杂网络的复杂结构 社团结构、层次结构、节点分类结构等。社团结构、层次结构、节点分类结构等。6 6）网络控制）网络控制 关键节点控制、主参数控制和控制的稳定性和有效性。关键节点控制、主参数控制和控制的稳定性和有效性。7）复杂网络建模）复杂网络建模 机理建模、数据建模和实际系统的复杂网络正向与逆向建模。机理建模、数据建模和实际系统的复杂网络正向与逆向建模。8）复杂逻辑网络）复杂逻辑网络 逻辑与高阶逻辑定义、分类、判定算法，高阶逻辑的实际逻辑与高阶逻辑定义、分类、判定算法，高阶逻辑的实际意义等等。意义等等。影响复杂网络拓扑结构性能的因素：影响复杂网络拓扑结构性能的因素：v密度：只要某个社区的密度超过阈值，停止该社区的聚合。v聚合网络的映射函数f：v聚合网络密度的计算公式：v其中，|E|=V(V-1)/2 复杂网络研究新进展复杂网络研究新进展 v复杂网络的应用复杂网络的应用复杂网络与生物体的新陈代谢系统、大脑神经网络相结合；复杂网络与生物体的新陈代谢系统、大脑神经网络相结合；复杂网络与生物传染病相结合、在流行病传播与免疫控制方面的复杂网络与生物传染病相结合、在流行病传播与免疫控制方面的研究；研究；复杂网络上的博弈；复杂网络上的博弈；复杂网络在交通网络与社会经济中的应用；复杂网络在交通网络与社会经济中的应用；复杂网络在通信网络中的应用；复杂网络在通信网络中的应用；复杂网络在计算机网络与互联网中的应用；复杂网络在计算机网络与互联网中的应用；复杂网络在传感器网络中的应用；复杂网络在传感器网络中的应用；复杂网络在语言词汇网络和社会意见传播等方面的应用等。复杂网络在语言词汇网络和社会意见传播等方面的应用等。http:/http:/www.izuqiu.orghttp:/http:/ yyy