复杂网络调研.docx

《复杂网络调研.docx》由会员分享，可在线阅读，更多相关《复杂网络调研.docx（8页珍藏版）》请在优知文库上搜索。

1、关于复杂网络的调研-陈维唐玲玲一.复杂网络理论概述复杂网络的研究背景：近年来，学界关于复杂网络的研究正方兴未艾。特别是,国际上有两项开创性工作掀起了一股不小的研究复杂网络的热潮。一是1998年WattS和StrogaIZ在NaIUre杂志上发表文章，引入了小世界(Small-WOrld)网络模型，以描述从完全规那么网络到完全随机网络的转变。小世界网络既具有与规那么网络类似的聚类特性,又具有与随机网络类似的较小的平均路径长度IJ(Watts&StrogaIZ,p.440-442)。二是1999年Barabasi和Albert在Science上发表文章指出，许多实际的复杂网络的连接度分布具有幕律形

2、式。由于幕律分布没有明显的特征长度,该类网络又被称为无标度(SCaIe-Free)网络。(BarabasiSAlbert,p.509-512)而后科学家们又研究了各种复杂网络的各种特性。(Strogatz,p.268-276)国内学界也己经注意到了这种趋势，并且也开始展开研究。(吴金闪、狄增如,第18-46页)参加复杂网络研究的学者主要来自图论、统计物理学、计算机网络研究、生态学、社会学以及经济学等领域，研究所涉及的网络主要有：生命科学领域的各种网络(如细胞网络、蛋白质一蛋白质作用网络、蛋白质折叠网络、神经网络、生态网络)、Internet/WWW网络、社会网络，包括流行性疾病的传播网络、科学

3、家合作网络、人类性关系网络、语言学网络，等等：所使用的主要方法是数学上的图论、物理学中的统计物理学方法和社会网络分析方法。概念：钱学森给出了复杂网络的一个较严格的定义：具有自组织、自相似、吸引子、小世界、无标度中局部或全部性质的网络称为复杂网络。表现：复杂网络简而言之即呈现高度复杂性的网络。其复杂性主要表现在以下几个方面：1)结构复杂，表现在节点数目巨大，网络结构呈现多种不同特征。2)网络进化：表现在节点或连接的产生与消失。例如WOrkI-WidenetWOrk,网页或链接随时可能出现或断开，导致网络结构不断发生变化。3)连接多样性：节点之间的连接权重存在惊讶，且有可能存在方向性。4)动力学复

4、杂性：节点集可能属于非线性动力学系统，例如节点状态随时间发生复杂变化。5)节点多样性：复杂网络中的节点可以代表任何事物，例如，人际关系构成的复杂网络节点代表单独个体，万维网组成的复杂网络节点可以表示不同网页。6)多重.复杂性融合：即以上多重复杂性相互影响，导致更为难以预料的结果。例如，设计一个电力供给网络需要考虑此网络的进化过程，其进化过程决定网络的拓扑结构。当两个节点之间频繁进行能量传输时，他们之间的连接权重会随之增加，通过不断的学习与记忆逐步改善网络性能内容：目前，复杂网络研究的内容主要包括：网络的儿何性质，网络的形成机制，网络演化的统计规律，网络上的模型性质，以及网络的结构稳定性，网络的

5、演化动力学机制等问题。其中在自然科学领域，网络研究的根本测度包括：度（degree）及其分布特征，度的相关性，集聚程度及其分布特征，最短距离及其分布特征，介数（betweenness）及其分布特征，连通集团的规模分布。复杂网络理论的开展：复杂网络研究是在复杂性科学开展到一定程度后才出现的，是复杂性科学研究中一种新的研究方法。复杂网络理论借助网络理论、统计物理学、不确定性理论等方法，对于复杂系统的网络特性、演化机制与规律、动力学特性等方面进行研究。为能从整体上研究复杂系统的结构、开展与功能提供了十分有利的研究工具。鉴于复杂网络在复杂系统研究中表现出越来越多的优势，复杂网络的研究正处于蓬勃开展的阶

6、段，越来越多的学者将其研究的重点转移到这一复杂性科学的新方向。复杂网络将大多数的复杂系统抽象为复杂网络，将复杂系统中的个体视为网络中的顶点，将个体之间的联系或是相互作用关系视为网络中的顶点之间的边，建立起一个可抽象表征复杂系统的复杂网络，在此根底上，从复杂系统的网络结构出发，对复杂系统进行研究。如今，复杂网络的分析方法己经应用于各个领域，被用来描述系统中个体之间的关系以及系统的集体行为。复杂网络中的一些重要研究成果如下特性：第一，小世界。它以简单的措辞描述了大多数网络尽管规模很大但是任意两个节（顶）点间却有一条相当短的路径的事实。以日常语言看，它反映的是相互关系的数目可以很小但却能够连接世界的

7、事实，例如，在社会网络中，人与人相互认识的关系很少，但是却可以找到很远的无关系的其他人。正如麦克卢汉所说，地球变得越来越小，变成一个地球村，也就是说，变成一个小世界。第二，集群即集聚程度（ClUSIeringCoeffiCient）的概念。例如，社会网络中总是存在熟人圈或朋友圈，其中每个成员都认识其他成员集聚程度的意义是网络集团化的程度：这是一种网络的内聚倾向。连通集团概念反映的是一个大网络中各集聚的小网络分布和相互联系的状况例如，它可以反映这个朋友圈与另一个朋友圈的相互关系。第三，幕律（powerlaw）的度分布概念。度指的是网络中顶（节）点（相当于一个个体）与顶点关系（用网络中的边表达）的

8、数量：度的相关性指顶点之间关系的联系紧密性：介数是一个重要的全局几何量。顶点U的介数含义为网络中所有的最短路径之中，经过U的数量.它反映了顶点U(即网络中有关联的个体)的影响力。无标度网络(Scaledreenetwork)的特征主要集中反映了集聚的集中性。复杂网络理论根底：复杂网路的根本模型现实世界中各种领域的许多复杂系统都已用复杂网络来进行描述，虽然建模的方式各不相同，但其最根本的方法却相同：即将网络中个体与个体之间联系的建立为一个复杂网络。任何复杂网络都能够用这一构造方法建模，且许多复杂网络的根本特征指标就是在这种最简单网络图的根底上提出的。这种复杂网络的建模方法的具体过程为：将复杂网络

9、中根本元素定义为节点，根据建模的目的考察两节点之间的关系，假设两节点之间存在直接的关联那么认为两节点之间存在一条边相连，假设没有直接关联，那么认为不存在将两节点直接相连的边。例如：在社会关系网的建模中，每一个人是网络的根本元素，因此将其定义为节点，而将人与人之间是否相识，定义为判断两节点之间是否存在边的依据，通过这个建模方式得到的就是根本的复杂网络模型。在数学上，网络是用图(GraPh)来表示的，即采用图论的语言和符号来对网络进行精简的描述，因此不同复杂网络的建模最终是根据具体构造算法的不同得到不同的描述网络的图。虽然复杂网络构造得到的图存在着多样性，但是从根本上来说，无论用何种构造算法，其得

10、到的复杂网络的图可以分为两类：即关系图和空间图。这两类图都能够描述介于有序与无序两个极端之间的复杂网络，但关系图往往描述的正是复杂网络的最根本结构。根据复杂网络的最根本的建模方法得到的是一个由节点的集合V和边的集合E组成的关系图，图中节点数为N=IVI,边数为M=IEI,其中E中每条边都与V中的一对节点相对应对于建模得到的关系图，根据不同复杂网络的特性，还可以将网络分为有向网络(Directednetwork)和无向网络(Undirectednetwork)或是无权网络(Unweightednetwork)和加权网络(Weightednetwork).无向网络指的是：图中任一对节点的边(i,j

11、)与边(j,i)指的都是同一条边，否那么称为有向网络例如，在学术文献引用网中，一篇文献可能被另一篇文献引用，被引用的文献不能反过来引用这一篇文献，两者之间的关系只能是从一个节点指向另一个节点的，指向相反的边并不存在。而如果给每条边都赋予与联系程度相关的权值，那么该网络就称为加权网络，否那么就称为无权网络，无权网络也可以看作权值为1的有权网络。通过网络的加权，可以更详细的描述；两节点之间的关系在本文中所称的网络均为无权网络。复杂网络拓扑构造模型：复杂网络模型的提出经历了一个从简单到复杂的过程，随着人们对复杂网络研究的不断深入，最开始提出的规那么网络模型和随机网络模型被发现越来越不适用于描述现实网

12、络，同时，伴随着越来越多新特性的发现，以前网络模型所用到的许多统计特征指标也不再符合实际观察到的复杂网络。在对现存不同领域复杂网络的大量实际结构进行研究后，越来越多的复杂网络模型相继被提出0然而规那么网络模型和随机网络模型并未被研究者们完全放弃，由于它们是两种典型特征完全相反的网络模型，因此仍常被用于进行复杂网络模型特性的比照研究。下文对现有的常用关键复杂网络模型进行介绍，它们包括：规那么网络模型、随机网络模型、小世界网络模型、无标度网络模型、等级网络模型和确定性模型等。1.规那么网络模型规那么网络模型是指节点间连接数量为固定数目的一种网络结构，常用的规那么网络模型有：全局耦合网络模型，其构造

13、方式为任意两个点之间都有边直接相连；最近邻耦合网络模型，其构造方式为每个节点只和周围的邻节点相连具有周期边界条件：星形网络模型，它是一种特殊的耦合网络模型，网络中存在一个中心点，其余的所有节点都只和该中心点相连，互相之间那么不相连。这三种网络的结构示意图如下：2随机网络模型随机网络是在给定一个概率P的情况下，对于网络中的任何两节点间的可能连接，都尝试以概率P的连接。随机网络模型的经典模型是ErdOS和Renyi提出的ER模型，该模型的定义为：在由N个节点和C/=N(N-1)/2条边构成的网络中，随机连接m条边，将形成的随机网络记为GNm,可知这种构成法得到的网络存在CmNND/2种，所有可能存

14、在的网络构成一个概率空间，其中每一个网络出现的概率是相等的。此外，与ER模型等价的二项式模型应用也十分广泛，其定义为：在给定节点N的情况下，假定任意节点对之间存在有条边的连接概率为P，那么将形成的随机网络记为GNX在ER模型中，网络中固定数量的节点彼此完全随机地连接在一起，且每个节点具有相同数量的连接，其结构示意图如下：假设定义网络中有m条边，其中m=pC/,由ER模型得到的随机网络Ggm的种类数为CmNNl2=CPCN2n(N)/2淇中每种网络的出现概率与由二项式模型得到的随机网络Gn，p的概率Pm(I-P)N(N)2m相同，实际两种模型构成法所得到的随机网络完全等价。3小世界网络模型随着大

15、量数据的产生和计算机的应用，人们发现在现实世界里真实的网络与ER模型相差甚远，真实的网络既不是概率为零的绝对规那么连接的网络，也不是概率为1的完全随机连接的网络，而是介于这两者之间的一种网络，这一类网络被称为“小世界网络”.最早的小世界网络模型WS模型是Watts和Strogatz于1998年提出的。WS模型是由一个N节点的环状网开始，网络上的每一个节点都与两侧各有m条边相连，这m条边以概率P随机进行重连，节点的自我连接和白我重复的边连接除外，得到的网络为一小世界网络。连接概率由0变为1时得到的是随机网络:4无标度网络天然的网络结构大多是随机的，而人造的网络结构大多是规那么的。在随机的网络结构

16、中，节点与其他节点的连接的数量呈正态分布；在规那么的网络结构中，节点与其他节点的连结数量是固定的。以上两类网络中，节点与其他节点的连结的数量分布都有规律可循，是有尺度的网络。而无标度网络那么是网络通过增添新节点而连续扩张，同时新节点择优连接到具有大量连接的节点上，且满足网络节点度服从幕律分布。无标度网络中不存在代表性的节点，但受少数集散节点的支配，并具有一些可预期的行为特性，即无标度网络节点度的极度不均衡性导致了无标度网络具有鲁棒性和脆弱性，如:无标度网络遇到随机攻击时有惊人的承受力，而遭到对特定节点的恶意打击时承受力却很脆弱等。下列图是一个无标度网络的结构示意图：最原始的无标度网络模型是BA模型，该模型假设形成初期网络中已有少量的节点，以后每过一段时间新增一个节点，该节点与其他节点连接的概率和被连接节点的节点度成正比.可知BA网络模型最终演化为节点度服从度指数为3的幕律分布的网络，具有大规模的高