复杂网络简介课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,复杂网络,Complex Network,计算机学院,复杂网络Complex Network计算机学院,目录,1,引言,本文目录,结构,2,复杂网络的统计特性,3,复杂网络模型,4,总结,目录1 引言本文目录结构2复杂网络的统计特性3 复杂网络模型,引言,引言,1,引言,复杂网络的发展背景,自然界中存在的大量复杂系统都可以通过形,形色色的网络加以描述。一个典型的网络是由许,多节点与连接两个节点之间的一些边组成的,其,中节点用来代表真实系统中不同的个体,而边则,用来表示个体之间的关系,通常是当两个节点之,间具有某种特定的关系时连一条边,反之则不连,边。有边相连的两个节点在网络中被看作是相邻,的。,1引言复杂网络的发展背景自然界中存在的大量复杂系统都可以通过,1,引言,例如,神经系统可以看作是大量神经细胞通过神经纤,维相互连接形成的网络；计算机网络可以看作是自主工作,的计算机通过通信介质如光缆、双绞线、同轴电缆等相互,连接形成的网络。类似的还有电力网络、社会关系网络、,交通网络等等。,神经网络,计算机网络,1引言例如, 神经系统可以看作是大量神经细胞通过神经纤维相互,1,引言,数学家和物理学家在考虑网络的时候,往往只关心节点之,间有没有边相连,至于节点在什么位置,边长还是短,是弯曲,还是平直,有没有相交等等都是他们不在意的。因此,我们把,网络不依赖于节点的具体位置和边的具体形态就能表现出来的,性质叫做,网络的拓扑性质,相应的结构叫做,网络的拓扑结构,.,那么,什么样的拓扑结构比较适用于描述真实的系统呢,?,1引言数学家和物理学家在考虑网络的时候, 往往只关心节点之间,1,引言,两百多年来,对这个问题的研究经历了三个阶段。在最初,的一百多年里,科学家们认为真实系统各因素之间的关系可以,用一些规则的结构表示,例如二维平面上的,欧几里德格网,它,看起来像是格子体恤衫上的花纹,;,又如,最近邻环网,它总是会,让你想到一群手牵着手、围着篝火跳圆圈舞的姑娘,.,到了,20,世纪,50,年代末,数学家们想,出了一种新的构造网络的方法,在这种方,法下,两个节点之间连边与否不再是确定,的事情,而是根据一个概率决定,.,数学家,把这样生成的网络叫做,随机网络,它在接,下来的,40,年里一直被很多科学家认为是描,述真实系统最适宜的网络,.,1引言两百多年来, 对这个问题的研究经历了三个阶段。在最初的,1,引言,直到最近几年，由于计算机数据处理和运算能力的飞速发,展,科学家们发现大量的真实网络既不是规则网络，也不是随,机网络,而是具有与前两者皆不同的统计特征的网络。这样的,一些网络被科学家们叫做,复杂网络（,Complex Network,),，对于,它们的研究标志着第三阶段的到来。,大规模复杂网络,1引言直到最近几年，由于计算机数据处理和运算能力的飞速发展,1,引言,复杂网络的定义,具有自组织、自相似、吸引子、,小世界、无标度中部分或全部性质,的网络称为复杂网络。,钱学森,1引言复杂网络的定义具有自组织、自相似、吸引子、小世界、无标,统计特性,统计特性,2,复杂网络的统计特性,1,度、度分布和度相关性,2,最短路径长度、平均最短路径长度、介数,统计特性,3,聚类系数,4,社区结构,5,层次性,2复杂网络的统计特性1 度、度分布和度相关性2 最短路径长度,2,复杂网络的统计特性,度、度分布和度相关性,无向网络的节点的,度,是指与节点连接的边数；而有向网络的节点的度,分为入度和出度。网络中所有节点度的列表称为度序列，度序列的平均值,称为网络的平均度,记为,。给定了网络的度序列就确定了该网络的度分,布。,度分布,是指从图中随机选择一个节点其度为,k,的概率，记为,P(k),。度分,布是网络的最基本的拓扑特性。根据度分布，可以将网络分为随机图、无,标度网络和指数网络等。度分布一个非常有用的表示,(,生成函数表示法,),为,:,其中,pk,表示度为,k,的节点在网络中的比例,.,2复杂网络的统计特性度、度分布和度相关性无向网络的节点的度是,2,复杂网络的统计特性,度、度分布和度相关性,在随机图模型中,任意两个节点间相连的概率为,p,即任意节点连接到,任意的其它节点的概率都是相同的,.,但在许多现实网络中,存在着一定的混,合模式，即一个节点倾向于连接到某一些节点。研究者也发现，许多网络,边的两节点间的度也存在依赖关系,即,度,-,度相关性,。,如果度高的节点倾向于连接其它度高的节点,称为同配混合；如果度,高的节点倾向于连接其它度低的节点称为异配混合。网络的同配性,(,异配性,),影响网络的结构和行为,.,按照度同配混合的网络比对应的异配网络更利于渗,流；对于节点删除,同配混合的网络要比异配和中性的网络更具有鲁棒性,.,2复杂网络的统计特性度、度分布和度相关性在随机图模型中, 任,2,复杂网络的统计特性,最短路径长度、平均最短路径长度、介数,对于无权网络,网络中任意两点间的,最短路径,是从一个节点到另一个,节点的最少边数；对于有权网络,两点间的最短路径是指权值之和为最小的,路径。网络中任意两个节点之间的最短路径长度的最大值称为网络的直径。,平均最短路径长度,是网络中所有节点对之间的最短路径长度的平均值。,平均路径长度可以做为网络信息传递效率的度量,网络的效率定义为：,这里, n,表示节点数，,dij,为两个节点,i,和,j,之间的最短路径长度。网络的平均最,短路径长度较小的现象称为小世界效应。许多现实网络具有小世界效应，,如电影演员网络,(,平均最短路径为,3.48),，对等网络,(,平均最短路径为,4.28),，,代谢网络,(,平均最短路径是,2.56).,2复杂网络的统计特性最短路径长度、平均最短路径长度、介数对于,2,复杂网络的统计特性,最短路径长度、平均最短路径长度、介数,为了度量节点在网络中的重要性,中心性，引进了节点,介数,概念，,定义如下：,边介数是经过这条边的节点对的最短路径数，它在社区发现中为区分一个,社区的内部边和社区之间的边提供了一种有效的度量标准,.,2复杂网络的统计特性最短路径长度、平均最短路径长度、介数为了,2,复杂网络的统计特性,聚类系数,二元关系,R,如果,aRb, bRc,那么,aRc,则称,R,是传递的。熟人网络中，,也有类似的特性，即拥有一个共同朋友的两个人他们也彼此熟悉，这种性,质称为网络的聚类性，也称为传递性。传递性意味着出现三角形，定义节,点,i,聚类系数如下：,-,整个网络的聚类系数,C,就是所有节点,i,的聚类系数,C i,的平均值,且有,0,C,1,。,对于一些无标度网络,局部聚类系数,Ci,随着节点,i,的度下降而下降。随,机网络的聚类系数为,O(n,1,),，当网络规模极大时趋于零，而多数现实网络,的聚类系数显著大于零，,a,即具有明显的聚类特性。,2复杂网络的统计特性聚类系数二元关系R, 如果aRb, bR,2,复杂网络的统计特性,社区结构,社区结构是许多现实网络具有的一个共同的特征,即网络的节点可以,分成几个组,每个组内部的节点连接稠密,而组之间的节点连接稀疏，下图,是一个包含三个社区的一个简单网络。,社区结构的发现具有重要的意义，例如在,WWW,中的社区对应着一组,关于某个主题的网页；社会网络中的社区对应着有着共同爱好或背景的一,群人；生化网络中的社区则对应着某个复合体或某种功能。因此，社区发,现是当前复杂网络研究的一个热点方向，并且已经提出了各种方法，如基,于介数度量的方法、随机游走方法、电阻网络方法、拉普拉斯特征值方法、,极值优化方法、派系过滤算法等。,2复杂网络的统计特性社区结构社区结构是许多现实网络具有的一个,2,复杂网络的统计特性,社区结构,一个广泛使用的度量网络的社区结构的量是模块度，它定义为：设网,络分为,n,个社区，则定义一个,n * n,的矩阵,e,，每一行和每一列都代表一个社,区，矩阵元素,eij,表示社区,i,和,j,间的边数占网络总边数的比例，,eii,就表示社区,i,内部边所占的比例，,ai =eij,表示第,i,行或第,i,列元素之和,即与第,i,个社区的,节点相连的边的总比例,则模块度定义为,:,即社区内部边的比例减去具有同样社区划分但节点间是随机连接的网络的,这一值的期望。,Q,的值在,-1,与,1,之间，,Q,越接近,1(,这是最大值,),预示着具有,越强的社区结构。,2复杂网络的统计特性社区结构一个广泛使用的度量网络的社区结构,2,复杂网络的统计特性,层次性,按层次组织是许多复杂系统的一个共同特征。在代谢网络中，有许多,小的连接密集的簇，它们会相互结合形成较大较稀疏的簇，而这些簇又可,能进一步形成更大更稀疏的簇。这种自相似地嵌套形成了我们现实网络的,严格而又精细的结构。有趣地是，网络的层次性特性,可以通过简单的量来,捕获，即,C ( k),曲线满足,C(K) k,1,。,Clauset,等人建立了一种层次随机图模型，利用该模型对现实网络进,行拟合，发现网络的层次结构可以解释网络的许多其它特征，如平均度、,聚类系数和最短路径等。发现网络中的连接往往需要在实验室或现场付出,高昂的费用，这就使得许多现实网络是不完备的，,在这种情形下预测网络,中丢失的连接具有重要的意义。,Clauset,进一步利用建立的模型设计了一个,丢失连接的预测器，它与传统的方法相比,能够应用于更广泛类型的网络结,构。,2复杂网络的统计特性层次性按层次组织是许多复杂系统的一个共同,复杂网络模型,复杂网络模型,3,复杂网络模型,小世界网,络,无标度网,络,BA,随机图,复杂网,模型,络模型,3复杂网络模型小世界网络无标度网络BA随机图复杂网模型络模型,3,复杂网络模型,随机图,随机图是图论中最年轻的分支之一，对它的系统研究起源,于,1959,年保罗,埃尔德什和阿尔弗雷德,雷尼的工作，他们发表了,一系列的论文，建立了丰富的随机图理论的基础。现实网络具有,复杂的拓扑结构和未知的组织原理，总是呈献出某种随机性，因,此用随机图作为网络的模型是最直接的一种选择。,一个随机图实际上是将给定的顶点之间随机地连上边。边,的产生可以依赖于不同的随机方式，这样就产生了不同的随机,图模型。一个典型的模型是埃尔德什和雷尼共同研究的,ER,模型。,ER,模型是指在给定,n,个顶点后，规定每两个顶点之间都以,p,的概率连起来（,0 p 1,），而且这些判定之间两两无关。这,样得到的随机图一般记作,或,ERn(p),。,3复杂网络模型随机图随机图是图论中最年轻的分支之一，对它的系,3,复杂网络模型,小世界网络,许多现实网络如技术网络、生物网络和社会网络等，既不,是完全规则的，也不是完全随机的，而是介于两者之间。,Watts,和,Strogatz,基于这些观察,提出了,WS,模型，是指对一个具有,n,个,节点的环格，初始时每个节点有,k,个邻居，将每条边以概率,p,进,行随机重绕的过程。由于该模型生成的网络具有较短的特征路,径，即网络具有小世界效应，故称为小世界网络，,WS,模型也因,此常称为小世界网络,(,模型,),。,3复杂网络模型小世界网络许多现实网络如技术网络、生物网络和社,3,复杂网络模型,小世界网络,上述的构造过程有可能破坏网络的连通，因此,Newman,和,Watts,稍后提出了通过随机化加边的方法构造小世界网络的模型，,即,NW,模型。还有许多改进的模型：加点、加边、去点、去边,以及不同形式的交叉，产生多种形式的小世界模型。,小世界网络具有高的聚类系数，,WS,小世界网络的聚类系,数为：,而,NW,小世界网络的聚类系数为：,小世界网络的典型特征是平均最短路径满足对数标度，但,是到目前为止还没有精确的解析表达式。小世界网络的度分布,与多数现实网络并不能很好匹配，对于,NW,模型和,WS,模型，其,表达式都比较复杂。,3复杂网络模型小世界网络上述的构造过程有可能破坏网络的连通，,3,复杂网络模型,无标度网络,节点度服从幂律分布，是指具有某个特定度的节点数目与,这个特定的度之间的关系可以用一个幂函数近似地表示，幂函,数曲线是一条下降相对缓慢的曲线，这使得度很大的节点可以,在网络中存在。对于随机网络和规则网络，度分布区间非常狭,窄，几乎找不到偏离节点度均值较大的点，故其平均度可以被,看作其节点度的一个特征标度。在这个意义上，我们把节点度,服从幂律分布的网络叫做无标度网络,3复杂网络模型无标度网络节点度服从幂律分布，是指具有某个特定,3,复杂网络模型,BA,模型,2019,年, Albert-L,szl,Barab,si,和,R,ka Alber,受,WWW,形,成的启发,提出了构造无标度网络的演化模型，常称为,BA,模型。,该模型考虑了现实网络的两个重要特性：增长特性和择优连接,特性。该模型的构成过程如下：,初始时刻有,m,0,个孤立的节点,在每一个时间步,t= 1,2,3, ,n-m,0,加上一个新的节点,j,，同时加上从此节点出发的,m,条边,将,新节点,j,连接到网络中已经存在的节点，,i,是按照正比于,i,的度的规,律来选择边的另一端节点：,3复杂网络模型BA模型2019年, Albert-Lszl,3,复杂网络模型,BA,模型,BA,无标度网络的聚类系数为：,可见，,BA,无标度网络不具有高的聚类系数。,BA,无标度网络具有小世界特性，其平均路径长度为：,3复杂网络模型BA模型BA无标度网络的聚类系数为：可见，BA,总结,总结,4,总结,复杂网络作为一门新兴的交叉学科正处于蓬勃发展阶段，为各学,科中的复杂系统提供了一种对其进行认识和处理的统一的框架，同时,为处理包括计算机科学在内的许多学科中的复杂问题提供了新的观点,和方法。,加入复杂网络研究的学者主要来自图论、统计物理学、计算机网,络研究、生态学、社会学以及经济学等领域，研究所涉及的网络主要,有：生命科学领域的各种网络（如细胞网络、蛋白质蛋白质作用网,络、蛋白质折叠网络、神经网络、生态网络）、,Internet/WWW,网络、,社会网络，包括流行性疾病的传播网络、科学家合作网络、人类性关,系网络、语言学网络等等；所使用的主要方法是数学上的图论、物理,学中的统计物理学方法和社会网络分析方法。,4总结复杂网络作为一门新兴的交叉学科正处于蓬勃发展阶段，为各,4,总结,参考文献：,1,刘涛，陈忠，陈晓荣。复杂网络理论及其应用研究概述。上海交通大,学安泰管理学院，上海,200030),2,詹卫华,关佶红,章忠志。复杂网络研究进展：模型与应用。同济大学,计算机科学与技术系,上海,201804,，复旦大学计算机学院,上海,201933,。,3,周涛，柏文洁，汪秉宏，刘之景，严钢。复杂网络研究概述。中国科,学技术大学近代物理系，合肥,230026,。,4总结参考文献：1刘涛，陈忠，陈晓荣。复杂网络理论及其应,复杂网络简介课件,