复杂网络及其matlab模拟

毕业论文题目：复杂网络及其matlab模拟学院：物理与电子工程学院专业：物理学毕业年限：2015学生姓名：学号：指导教师：1复杂网络及其matlab模拟班级：物理学2班姓名：指导教师：摘要近年来,关于复杂网络的研究正方兴未艾,1998年Watts和Strogatz在Nature杂志上发表文章,引入了小世界(Small一World)网络模型。本文对复杂网络的特性还有无标度与小世界网络进行简单介绍，详细介绍各个模型的生成与算法，并用matlab软件进行了模拟。关键词复杂网络无标度小世界模拟AbstractInrecentyears,theresearchoncomplexnetworksofacademiaisbejustunfolding,inparticular,thetwopioneeringworksetoffanupsurgeinthestudyofcomplexnetworks.In1998WattsandStrogatzpublishedanarticleInthispaper,thepropertiesofcomplexnetworksarescale-freeandsmallworldnetworksarebrieflyintroduced,Generationandalgorithmdetailsofeachmodel,anduseMATLABsoftwaretosimulate.KeywordComplexnetwork；Scalefree；SmallWorld；Simulation引言在人类生存的整个空间甚至宇宙中都存在着大量复杂系统，这些系统可以通过形形色色的网络加以描述。一个典型的网络是由许多节点与连接两个节点之间的一些边组成的，其中节点用来代表真实系统中不同的个体，而边则用来表示个体间的关系，往往是两个节点之间具有某种特定的关系则连一条边，反之则不连边，有边相连的两个节点在网络中被看作是相邻的。例如，神经系统可以看作大量神经细胞通过神经纤维相互连接形成的网络[1]；计算机网络可以看作是自主工作的计算机通过通信介质如光缆、双绞线、同轴电缆等相互连接形成的网络[2],类似的还有电力网络[1]、社会关系网络[1,4]、交通网络等等。数学家和物理学家在研究网络的时候，往往只关心节点之间有没有边相连，至于节点到底在什么位置，边是长还是短，是弯曲还是平直，有没有相交等等都是他们不在意的。在这里，2我们把网络不依赖于节点的具体位置和边的具体形态就能表现出来的性质叫做网络的拓扑性质，相应的结构叫做网络的拓扑结构。那么，什么样的拓扑结构比较适合用来描述真实的系统呢？本文首先介绍了复杂网络的研究进展及其统计特征，然后对小世界网络和无标度网络模型及各模型的matlab模拟作了详细介绍。1复杂网络的发展及统计特征1.1．复杂网络的发展由于现实世界网络的规模大，节点间相互作用复杂，其拓扑结构基本上未知或未曾探索。两百多年来，人们对描述真实系统拓扑结构的研究经历了三个阶段。在最初的一百多年里，科学家们认为真实系统要素之间的关系可以用一些规则的结构表示，例如大数学家欧拉的哥尼斯堡七桥问题[8]，哥尼斯堡是当时东普鲁士的首都，今俄罗斯加里宁格勒市，普莱格尔河横贯其中，这条河上建有七座桥，将河中间的两个岛和河岸联结起来，。有人在闲暇散步时提出：能不能每座桥都只走一遍，最后又回到原来的位置。大数学家欧拉用一种独特的方法给出了解答。他把两座小岛和河的两岸分别看作四个点，分别用A、B、C和D表示，而把七座桥看作这四个点之间的连线，分别用a、b、c、d、e、f和g表示（如图1）。于是这个问题就简化成：能不能用一笔就把这个图形画出来？经过进一步的分析，欧拉得出结论：不可能每座桥都走一遍，最后回到原来的位置，并且给出了所有能够一笔画出来的图形所应具有的条件。图1欧拉哥尼斯堡七桥问题英国数学家哈密顿于1859年以游戏的形式提出：把一个正十二面体的二十个节点看成二十个城市，要求找出一条经过每个城市恰好一次而回到出发点的路线，这条路线就称“哈密顿圈”[9]。1852年，毕业于伦敦大学的格思里来到一家科研单位做地图着色工作时，3发现了一个有趣的现象：每幅地图都可以用四种颜色着色，使得有共同边界的国家着上不同的颜色[9]。1959年，两个匈牙利著名的数学家Erdös和Rényi建立了著名的随机图理论，用相对简单的随机图来描述网络，简称ER随机图理论[5]。ER随机图理论对图论理论研究的影响长达近40年，以至于在随后的近半个世纪，随机图一直是科学家研究真实网络最有力的武器。直到最近几年，科学家们发现大量的真实网络既不是规则网络，也不是随机网络，而是具有与前两者皆不同的统计特性的网络，其中最有影响的是美国的Watts和Strogatz于1998年发表了题为《“小世界”网络的群体动力行为》的论文[1]，推广了“六度分离”的科学假设[8]，提出了小世界网络模型。“六度分离”最早来自于20世纪60年代美国哈佛大学心理学家Milgram对社会调查的推断，是指在大多数人中，任意两个素不相识的人通过朋友的朋友，平均最多通过6个人就能够彼此认识。随后Barabasi等人于1999年发表了题为《随机网络中标度的涌现》的论文[6]，提出了一个无标度网络模型，指出在复杂网络中节点的度分布具有幂指数函数的规（节点的度是指与该节点连接的边数，而度分布是指网络中所有节点的度的分布情况），其度分布可以用幂律形式进行描述。近10年来，复杂网络的研究正渗透到众多不同的学科。推进复杂性科学的交叉研究，深入探索和科学理解复杂网络的定性特征与定量规律，使它获得广泛的应用，对全球科学和社会的发展具有十分重大的长远意义。1.2．复杂网络的统计特征平均路径长度：网络中两个节点i到j之间的距离定义为连接这两个节点的最短路径上的边数。网络中任意两个节点之间的距离的最大值称为网络的直径，记为D。即：D=max(dij)。网络的平均路径长度L定义为任意两节点之间距离的平均值，即：jiijd)1(211NNL（1）其中，N为网络的总节点数，网络的平均路径长度也称为网络的特征路径长度。集聚系数：集聚系数又称作簇系数，它衡量的是网络的集团化程度，是网络的另一个重要参数。簇系数的概念有其深刻的社会根源。对社会网络而言，集团4化形态是其一个重要特征，集团表示网络中的朋友圈或熟人圈，集团中的成员往往相互熟悉，为衡量这种群集现象，科学家们提出了簇系数的概念。节点i的簇系数iC描述的是网络中与该节点直接相连的节点之间的连接关系，即与该节点直接相邻的节点间实际存在的边数目占最大可能存在的边数的比例，iC的表达式为：）（1kk/e2iiiiC（2）式中ik表示节点i的度，ie表示节点i的邻接点之间实际存在的边数。网络的簇系数C为所有节点簇系数的算术平均值，即：NCNC1-ii1（3）其中N为网络的阶。不尽尽是社会网络，在其它类型的网络中，也普遍存在集聚现象。计算下面简单网络的直径、平均距离和各节点的集聚系数。图2网络统计特征计算示意图解：首先计算出所有节点对的距离：d12＝1；d13＝1；d14＝2；d15＝1；d16＝2；d23＝1；d24＝1；d25＝2；d26＝2；d34＝2；d35＝2；d36＝1；d45＝3；d46＝1；d56＝3。由此可得直径和平均距离和集聚系数分别为：直径3dddmax5645ijj1i1，D，平均距离67.1)56/()252(16621jijdL）（，集聚系数616/c1iiNC。5度分布：度分布是网络的一个重要统计特征。这里的度（Degree）也称为连通度（Connectivity），节点的度指的是与该节点连接的边数。对网络中所有节点的度求平均，可得到网络的平均度＜k＞。度分布则表示节点度的概率分布函数()Pk，它指的是节点有k条边连接的概率。2．小世界网络模型及其模拟1929年，匈牙利作家F.Karinthy最早提出了“小世界现象”的论断。他认为，在地球上的任何两个人都可以平均通过一条由六位联系人组成的链条而联系起来。而后，在1967年，美国哈佛大学社会心理学教授Milgram通过设计一个连锁信件实验，提出了著名的“六度分离”假说，即“小世界现象”[1]。这体现了一个似乎很普遍的规律：在如今的信息化时代，人们之间的关系已经完全社会化，任何两位素不相识的人都可能通过“六度空间”产生必然联系或关联。这一现象表明，在看似庞大的网络中各要素之间的间隔实际上是非常“近”的，大家在世界上通过一步一步的社会相识寻找到目标的这个短链子理论普遍存在于各种社会、经济网络中，科学家们把这种现象称为小世界效应[1]（Small-worldeffect）。为了用网络图来解释“六度分离”的小世界效应，，Watts和Strogatz在对规则网络和随机网络理论研究的基础上，于1998年提出了著名的WS小世界网络[1]。WS模型提出后，很多学者在此基础作了近一步改进，其中应用最多的是Newman和Watts提出的所谓NW小世界模型。事实上，当p很小N很大的时候，这两个模型理论分析的结果是相同的，现在我们统称它们为小世界模型。前面我们已经简单的介绍了一下小世界网络的WS和NW模型，下面将着重介绍小世界网络的ws模型的特点。2.1．WS模型构造算法1998年,Watts和Strogatz提出了小世界网络这一概念,并建立了WS模型[1]。实证结果表明,大多数的真实网络都具有小世界特性(较小的最短路径)和聚类特性(较大的聚类系数)。传统的规则最近邻耦合网络具有高聚类的特性,但并不具有小世界特性;而ER随机网络具有小世界特性但却没有高聚类特性。因此这两种传统的网络模型都不能很好的来表示实际的真实网络。Watts和Strogatz建立的WS小世界网络模型就介于这两种网络之间,同时具有小世界特6性和聚类特性,可以很好的来表示真实网络[1]。WS网络模型同时具有平均路径长度短集群系数高的特点，但是，它的度分布仍是一个轻尾的Poisson分布，而且WS网络中不存在具有大量连接边的中枢点，因此，它仍然是一个平衡网络。近年来，研究人员对小世界网络得结构性质和动力学行为进行了深入的探索，取得了丰富成果。研究表明小世界网络能够增强信号的传播速度、提高计、提高计算能力和网络同步能力[8]。特别地，传染性疾病在小世界网络中传播要比在规则网络中容易得多。WS模型的生成算法为：给定一个具有N个结点的环形网络规则，每一个结点对称地与它最近的m(mN)个邻点相连。而后对每个结点的每一条顺时针边以概率P重连，对每个结点重复上述过程，得到的网络称为小世界网络[10]。2.2．小世界网络模型设计及实现1、从规则图开始：考虑一个含有N个点的最近邻耦合网络，它们围成一个环，其中每个节点都与它左右相邻的各K/2节点相连，K是偶数。2、随机化重连：以概率p随机地重新连接网络中的每个边，即将边的一个端点保持不变，而另一个端点取为网络中随机选择的一个节点。其中规定，任意两个不同的节点之间至多只能有一条边，并且每一个节点都不能有边与自身相连。在上述模型中，p=0对应于完全规则网络，p=1则对应于完全随机网络，通过调节p的值就可以控制从完全规则网络到完全随机网络的过渡。网络图像如下：图3不同概率下网络示意图网络图中各节点度的概率分布如下：7图4不同概率下各节点度的概率分布图上面P=0.2时网络图显示，大部分连边保持不变，出现了少量捷径，正是由于这少量捷径造成了网络的小世界效应。3.无标度网络模型及其模拟1999年，Alber和Barabds发现分布，而是重尾特征的幂律分布，而且基本上是由少数具有大量超链接的网页串连起来的，绝大部分网页的链接很少，他们把网络的这个特性称为无标度性[3](Scale-freenature，SF)。研究人员对大量的实际网络进行了实证分析，发现许多网络的度分布都是幂律的，要描述这些网络的结构和演化过程，随机图模型和小世界网络模型显然无能