小世界复杂网络模型研究

《小世界复杂网络模型研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、小世界复杂网络模型研究摘要：复杂网络在工程技术、社会、政治、医药、经济、管理领域都有着潜在、广泛的应用。通过高级计算机网络课程学习，本文介绍了复杂网络研究历史应用，理论描述方法及阐述对几种网络模型的理解。1复杂网络的发展及研究意义1.1复杂网络的发展历程现实世界中的许多系统都可以用复杂网络来描述，如社会网络中的科研合作网、信息网络中的万维网、电力网、航空网，生物网络中的代谢网与蛋白质网络。由于现实世界网络的规模大，节点间相互作用复杂，其拓扑结构基本上未知或未曾探索。两百多年来，人们对描述真实系统拓扑结构的研究经历了三个阶段。在最初的一百多年里，科学家们认为

2、真实系统要素之间的关系可以用一些规则的结构表示，例如二维平面上的欧几里德格网；从20世纪50年代末到90年代末，无明确设计原则的大规模网络主要用简单而易于被多数人接受的随机网络来描述，随机图的思想主宰复杂网络研究达四十年之久；直到最近几年，科学家们发现大量的真实网络既不是规则网络，也不是随机网络，而是具有与前两者皆不同的统计特性的网络，其中最有影响的是小世界网络和无尺度网络。这两种网络的发现，掀起了复杂网络的研究热潮。2复杂网络的基本概念2.1网络的定义自随机图理论提出至今，在复杂网络领域提出了许多概念和术语。网络（Network）在数学上以图（Graph

3、）来表示，图的研究最早起源于18世纪瑞士著名数学家Euler的哥尼斯堡七桥问题。复杂网络可以用图论的语言和符号精确简洁地加以描述。图论不仅为数学家和物理学家提供了描述网络的语言和研究的平台，而且其结论和技巧已经被广泛地移植到复杂网络的研究中。网络的节点和边组成的集合。节点为系统元素，边为元素间的互相作用（关系）。若用图的方式表示网络，则可以将一个具体网络可抽象为一个由点集V和边集E组成的图G=（V,E）。节点数记为N=

4、V

5、，边数记为M=

6、E

7、.E中每条边都有V中一对点与之相对应。如果任意点对（i,j）与（j,i）对应同一条边，则该网络成为无向网络（und

8、irectednetwork），否则称为无权网络（unweightednetwork）。当然，无权网络也看作是每条边的权值都为1的等权网络。1.1复杂网络的基本概念复杂网络结构的有很多概念和方法，其中基本的概念是：平均路径长度(averagepathlength)、集聚系数(clusteringcoefficient)和度分布(degreedistribution)。abdc图1平均路径长度：网络中的任意两点间有一条最短的路径，它等于沿这条路径从一点走到另一点所经过的最少边数，平均路径长度表示网络中所有的节点对之间的最短路径的平均值。如图1所示：•D(ab

9、)=1,D(ac)=1,D(ad)=2•D(bc)=1,D(bd)=2•D(cd)=1•L=(1+1+2+1+2+1)/6=8/6集聚系数：社会上形成了许多派系（Clique）或集团，同一派系里的人两两相互认识。为了描述网络中与同一节点直接相连的节点之间的连接关系，人们引进了集聚系数这一概念：假定某一节点i有Ki个最近邻，那么在这些最近邻的点之间最多可能存在Ki(Ki-1)/2条边，用Ci表示这些可能存在的边中实际上存在的百分比。对网络中所的Ci取平均值，就得到集聚系数C，它描述了网络中点与点集结成团的趋势。如图1所示：•Ca=1(becausebandc

10、connected)•Cb=1(becauseaandbconnected)•Cc=1/3(a-b,notb-d,nota-d)•Cd=0•Averageclustering=(7/3)/4=7/12度分布：节点的度也称为连通度，它指的是与该节点连接的边数。度分布P(k)函数表示节点有k条边连接（即有k个最近邻居）的概率。如图1所示：Ka=2,Kb=2,Kc=3,Kd=11.1复杂网络的分类根据节点度的分布情况，可以将复杂网络分为指数网络和无尺度网络两大类。指数网络中的节点是同质的，它们的度大致相同，绝大部节点的度都位于网络节点平均度附近，网络节点度分布随

11、度数的增加呈指数衰减，使得网络中不存在度数特别大的节点，最经典的两种指数网络是Erdös与Rényi于1960年提出的Erdös-Rényi（ER）随机图模型和Watt与Strogatz在1998年提出的Watt-Strogatz小世界网络模型（WS模型）。随机图与小世界网络的主要区别是：前者的簇系数小，而后者的簇系数大。目前，把具有较小平均路径长度和较大簇系数的网络统称为小世界网络，这一说法已得到学术界的公认。无尺度网络中的节点是异质的，其节点度服从幂律分布。最著名的无尺度网络模型是1999年Barabási和Albert建立的Barabási-Albe

12、rt无尺度网络模型（BA模型或BA网络）。在无尺度网络中，大部分节