复杂网络及其matlab模拟

1、 毕 业 论 文题 目： 复杂网络及其matlab模拟 学 院： 物理与电子工程学院 专 业： 物理学 毕业年限： 2015 学生姓名： 学 号： 指导教师： 复杂网络及其matlab模拟 班级：物理学2班 姓名： 指导教师： 摘 要 近年来,关于复杂网络的研究正方兴未艾,1998年Watts和Strogatz在Nature杂志上发表文章,引入了小世界(Small一World)网络模型。本文对复杂网络的特性还有无标度与小世界网络进行简单介绍，详细介绍各个模型的生成与算法，并用matlab软件进行了模拟。关键词 复杂网络 无标度 小世界 模拟Abstract In recent years, t

2、he research on complex networks of academia is be just unfolding, in particular, the two pioneering work set off an upsurge in the study of complex networks.In 1998 Watts and Strogatz published an article In this paper, the properties of complex networks are scale-free and small world networks are b

3、riefly introduced,Generation and algorithm details of each model, and use MATLAB software to simulate.Key word Complex network； Scale free； Small World； Simulation引言 在人类生存的整个空间甚至宇宙中都存在着大量复杂系统，这些系统可以通过形形色色的网络加以描述。一个典型的网络是由许多节点与连接两个节点之间的一些边组成的，其中节点用来代表真实系统中不同的个体，而边则用来表示个体间的关系，往往是两个节点之间具有某种特定的关系则连一条边，反

4、之则不连边，有边相连的两个节点在网络中被看作是相邻的。例如，神经系统可以看作大量神经细胞通过神经纤维相互连接形成的网络1；计算机网络可以看作是自主工作的计算机通过通信介质如光缆、双绞线、同轴电缆等相互连接形成的网络2,类似的还有电力网络1、社会关系网络1,4、交通网络等等。数学家和物理学家在研究网络的时候，往往只关心节点之间有没有边相连，至于节点到底在什么位置，边是长还是短，是弯曲还是平直，有没有相交等等都是他们不在意的。在这里，我们把网络不依赖于节点的具体位置和边的具体形态就能表现出来的性质叫做网络的拓扑性质，相应的结构叫做网络的拓扑结构。那么，什么样的拓扑结构比较适合用来描述真实的系统呢？

5、 本文首先介绍了复杂网络的研究进展及其统计特征，然后对小世界网络和无标度网络模型及各模型的matlab模拟作了详细介绍。1 复杂网络的发展及统计特征1.1复杂网络的发展由于现实世界网络的规模大，节点间相互作用复杂，其拓扑结构基本上未知或未曾探索。两百多年来，人们对描述真实系统拓扑结构的研究经历了三个阶段。在最初的一百多年里，科学家们认为真实系统要素之间的关系可以用一些规则的结构表示，例如大数学家欧拉的哥尼斯堡七桥问题8，哥尼斯堡是当时东普鲁士的首都，今俄罗斯加里宁格勒市，普莱格尔河横贯其中，这条河上建有七座桥，将河中间的两个岛和河岸联结起来，。有人在闲暇散步时提出：能不能每座桥都只走一遍，最后

6、又回到原来的位置。大数学家欧拉用一种独特的方法给出了解答。他把两座小岛和河的两岸分别看作四个点，分别用A、B、C和D表示，而把七座桥看作这四个点之间的连线，分别用a、b、c、d、e、f和g表示（如图1）。于是这个问题就简化成：能不能用一笔就把这个图形画出来？经过进一步的分析，欧拉得出结论：不可能每座桥都走一遍，最后回到原来的位置，并且给出了所有能够一笔画出来的图形所应具有的条件。图1 欧拉哥尼斯堡七桥问题英国数学家哈密顿于1859年以游戏的形式提出：把一个正十二面体的二十个节点看成二十个城市，要求找出一条经过每个城市恰好一次而回到出发点的路线，这条路线就称“哈密顿圈”9。1852年，毕业于伦敦

7、大学的格思里来到一家科研单位做地图着色工作时，发现了一个有趣的现象：每幅地图都可以用四种颜色着色，使得有共同边界的国家着上不同的颜色9。1959年，两个匈牙利著名的数学家Erdös和Rényi建立了著名的随机图理论，用相对简单的随机图来描述网络，简称ER随机图理论5。ER随机图理论对图论理论研究的影响长达近40年，以至于在随后的近半个世纪，随机图一直是科学家研究真实网络最有力的武器。直到最近几年，科学家们发现大量的真实网络既不是规则网络，也不是随机网络，而是具有与前两者皆不同的统计特性的网络，其中最有影响的是美国的 Watts和Strogatz于1998年发表了题为“小世界

8、”网络的群体动力行为的论文1，推广了“六度分离”的科学假设8，提出了小世界网络模型。“六度分离”最早来自于20世纪60年代美国哈佛大学心理学家Milgram对社会调查的推断，是指在大多数人中，任意两个素不相识的人通过朋友的朋友，平均最多通过6个人就能够彼此认识。随后Barabasi等人于1999年发表了题为随机网络中标度的涌现的论文6，提出了一个无标度网络模型，指出在复杂网络中节点的度分布具有幂指数函数的规（节点的度是指与该节点连接的边数，而度分布是指网络中所有节点的度的分布情况），其度分布可以用幂律形式进行描述。 近10年来，复杂网络的研究正渗透到众多不同的学科。推进复杂性科学的交叉研究，深

9、入探索和科学理解复杂网络的定性特征与定量规律，使它获得广泛的应用，对全球科学和社会的发展具有十分重大的长远意义。1.2复杂网络的统计特征平均路径长度：网络中两个节点i到j之间的距离定义为连接这两个节点的最短路径上的边数。网络中任意两个节点之间的距离的最大值称为网络的直径，记为D。即：D=max(d)。网络的平均路径长度L定义为任意两节点之间距离的平均值，即： （1）其中，N为网络的总节点数，网络的平均路径长度也称为网络的特征路径长度。集聚系数：集聚系数又称作簇系数，它衡量的是网络的集团化程度，是网络的另一个重要参数。簇系数的概念有其深刻的社会根源。对社会网络而言，集团化形态是其一个重要特征，集

10、团表示网络中的朋友圈或熟人圈，集团中的成员往往相互熟悉，为衡量这种群集现象，科学家们提出了簇系数的概念。节点i的簇系数描述的是网络中与该节点直接相连的节点之间的连接关系，即与该节点直接相邻的节点间实际存在的边数目占最大可能存在的边数的比例，的表达式为： （2）式中表示节点i的度，表示节点i的邻接点之间实际存在的边数。网络的簇系数为所有节点簇系数的算术平均值，即： （3）其中为网络的阶。不尽尽是社会网络，在其它类型的网络中，也普遍存在集聚现象。计算下面简单网络的直径、平均距离和各节点的集聚系数。图2网络统计特征计算示意图解：首先计算出所有节点对的距离：d121；d131；d142；d151；d1

11、62；d231；d241；d252；d262；d342；d352；d361；d453；d461；d563。由此可得直径和平均距离和集聚系数分别为：直径，平均距离，集聚系数。度分布：度分布是网络的一个重要统计特征。这里的度（Degree）也称为连通度（Connectivity），节点的度指的是与该节点连接的边数。对网络中所有节点的度求平均，可得到网络的平均度k。度分布则表示节点度的概率分布函数，它指的是节点有条边连接的概率。2小世界网络模型及其模拟 1929 年，匈牙利作家 F.Karinthy 最早提出了“小世界现象”的论断。他认为，在地球上的任何两个人都可以平均通过一条由六位联系人组成的链条

12、而联系起来。而后，在1967 年，美国哈佛大学社会心理学教授Milgram 通过设计一个连锁信件实验，提出了著名的“六度分离”假说，即“小世界现象”1。这体现了一个似乎很普遍的规律：在如今的信息化时代，人们之间的关系已经完全社会化，任何两位素不相识的人都可能通过“六度空间”产生必然联系或关联。这一现象表明，在看似庞大的网络中各要素之间的间隔实际上是非常“近”的，大家在世界上通过一步一步的社会相识寻找到目标的这个短链子理论普遍存在于各种社会、经济网络中，科学家们把这种现象称为小世界效应1（Small-world effect）。为了用网络图来解释“六度分离”的小世界效应，Watts 和 Stro

13、gatz在对规则网络和随机网络理论研究的基础上，于 1998 年提出了著名的 WS 小世界网络1。WS模型提出后，很多学者在此基础作了近一步改进，其中应用最多的是Newman和Watts提出的所谓NW小世界模型。事实上，当p很小N很大的时候，这两个模型理论分析的结果是相同的，现在我们统称它们为小世界模型。前面我们已经简单的介绍了一下小世界网络的WS和NW模型，下面将着重介绍小世界网络的ws模型的特点。2.1WS 模型构造算法1998年, Watts和Strogatz 提出了小世界网络这一概念,并建立了WS模型1。 实证结果表明,大多数的真实网络都具有小世界特性(较小的最短路径) 和聚类特性(较

14、大的聚类系数) 。 传统的规则最近邻耦合网络具有高聚类的特性,但并不具有小世界特性;而ER 随机网络具有小世界特性但却没有高聚类特性。 因此这两种传统的网络模型都不能很好的来表示实际的真实网络。 Watts和Strogatz建立的WS小世界网络模型就介于这两种网络之间,同时具有小世界特性和聚类特性,可以很好的来表示真实网络1。WS 网络模型同时具有平均路径长度短集群系数高的特点，但是，它的度分布仍是一个轻尾的Poisson 分布，而且WS 网络中不存在具有大量连接边的中枢点，因此，它仍然是一个平衡网络。近年来，研究人员对小世界网络得结构性质和动力学行为进行了深入的探索，取得了丰富成果。研究表明

15、小世界网络能够增强信号的传播速度、提高计、提高计算能力和网络同步能力8。特别地，传染性疾病在小世界网络中传播要比在规则网络中容易得多。WS 模型的生成算法为：给定一个具有N 个结点的环形网络规则，每一个结点对称地与它最近的m(m<<N)个邻点相连。而后对每个结点的每一条顺时针边以概率P 重连，对每个结点重复上述过程，得到的网络称为小世界网络10。2.2小世界网络模型设计及实现1、从规则图开始：考虑一个含有N个点的最近邻耦合网络，它们围成一个环，其中每个节点都与它左右相邻的各K/2节点相连，K是偶数。2、随机化重连：以概率p随机地重新连接网络中的每个边，即将边的一个端点保持不变，而另

16、一个端点取为网络中随机选择的一个节点。其中规定，任意两个不同的节点之间至多只能有一条边，并且每一个节点都不能有边与自身相连。在上述模型中，p=0对应于完全规则网络，p=1则对应于完全随机网络，通过调节p的值就可以控制从完全规则网络到完全随机网络的过渡。网络图像如下：图3不同概率下网络示意图网络图中各节点度的概率分布如下：图4不同概率下各节点度的概率分布图上面P=0.2时网络图显示，大部分连边保持不变，出现了少量捷径，正是由于这少量捷径造成了网络的小世界效应。3.无标度网络模型及其模拟1999年，Alber和Barabds发现WWW 网页的度分布不是通常认为的Poisson分布，而是重尾特征的幂

17、律分布，而且WWW 基本上是由少数具有大量超链接的网页串连起来的，绝大部分网页的链接很少，他们把网络的这个特性称为无标度性3(Scale-free nature，SF)。研究人员对大量的实际网络进行了实证分析，发现许多网络的度分布都是幂律的，要描述这些网络的结构和演化过程，随机图模型和小世界网络模型显然无能为力。1999年Barabdsi和Albert考察了实际网络的生成机制，发现增长和择优连接是实际网络演化过程的两个基本要素，他们创造性地构建了能够产生无标度特性的第一个网络模型BA模型6。BA模型的生成算法如下：(1)增长：网络开始于少数几个结点(个)，每个相等时问间隔增加一个新点，新点与m

18、()个不同的已经存在于网络中的旧点相连产生m条新边。(2)择优连接：假设新点与旧点i相连的概率p取决于结点i的度数，即 （4）经过t步时间步后，BA模型演化成一个具有N=t+个结点mt条边的网络。BA网络主要具有以下特性：具有幂律度分布，是一个无标度网络；具有小世界特征。幂律度分布的重尾特征导致无标度网络中有少数具有大量连接边的中枢点，择优连接必然产生“富者愈富”现象。BA 网络同时具有鲁棒性和脆弱性，面对结点的随机失效，网络具有鲁棒性；但面对蓄意攻击时，由于中枢点的存在，网络变得十分脆弱，很容易陷于瘫痪9。3.1. 无标度网络模型构造算法按照BA模型的定义，针对Matlab语言的特点，以初始

19、节点等于3为例，设计如下算法11：第1：生成=3个结点的初始完全网络，设置网络规模为N()，并用Matlab特有的稀疏矩阵处理函数。第2：每隔一个固定时段加入一个新的结点，按照概率p()与原有网络结点产生m条无重复连边，重复上述过程N-次；第3：存储N=100个结点的网络邻接矩阵。下面分别就N=10、N=60、N=100、 做图：图5无标度网络生成的演化图上面三幅图对应的网络图中各节点度的概率分布如下： 图6节点数不同时各节点度的概率分布图上面组图显示，大部分结点的连边较少，少数结点具有大量的连边，这些具有大量连边的结点构成了网络的中枢点。当结点个数无限增加时，网络结点的度分布为幂律分布，可以

20、用幂律形式P（k）k即P（k）=ak网络即为无标度网络。转换为对数函数：lnP（k）=lna-lnk令lnP为y，k为x则y=lna-x，当=2，a=1时函数图如下：图7各节点度的概率分布双对数曲线许多实际大规模无标度网络，其幂指数通常为23，绝大多数节点的度相对很低，也存在少量度值相对很高的节点，把这类网络称为无标度网络。4. 结语现实世界中许许多多的复杂网络都是具有小世界或无尺度特征的复杂网络，从生物体中的大脑结构到各种新陈代谢网络,从Internet到WWW,从大型电力网络到全球交通网络,从科研合作网络到各种政治、经济、社会关系网络等等,数不胜数。因此，对小世界网络和无标度网络及其模型进

21、行更深入的研究是非常必要的。参考文献1 Watts, D.J. and Strogatz, S.H. Collective dynamics of “small world” networks. Nature,393, 440-442,（1998）2 Faloutsos M, Faloutsos P, Faloutsos C. On power-law relationships of the internet topologyC/ACM SIGCOMM Computer Communication Review. ACM, 1999, 29(4): 251-262.3 Albert R, Barabasi A.L.，Statistical mechanics of complex networksJ. Reviews of Modern Physic