摘 要

从上世纪至今，人们对于复杂网络的相关研究得到了飞速的发展，对于复杂网络中的小世界网络的研究工作具有实际性的意义，其中对于小世界网络中的WS和NW两种网络模型的研究最为重要，本篇介绍了两种小世界网络模型的构造算法，并在Matlab上进行了建模。研究小世界网络的基本特征参数并用图形的方式进行展示。画出了特点参数状态下的NW小世界仿真图，分析它们的静态特征，包括节点的度分布、平均最短路径和聚类系数。在进一步对小世界网络进行重新归一化分析，得出一系列的结论，完成设计要求。

关键词：小世界模型；复杂网络；聚类系数；平均路径长度；度分布

Abstract

From the last century to the present, people's research on complex networks has been developing rapidly, which is of practical significance to the research of small-world networks in complex networks. For the WS and NW networks in small world networks, Research is the most important, this paper introduces two small world network model of the construction algorithm, and in Matlab on the modeling. Study the basic characteristics of the small world network parameters and graphics to show the way. The NW small world simulation maps with characteristic parameters are plotted to analyze their static characteristics, including the degree distribution of nodes, the average shortest path and the clustering coefficients. In the further re-normalization of the small world network, a series of conclusions, to complete the design requirements.

Key Words：small-word model；complex network；clustering coefficient；Average path length；Degree distribution

目 录

第1章 绪论

1.1 复杂网络研究背景及意义

1.2 国内外研究现状

第2章 网络的理论基础

2.1 网络的特征参数

2.1.1 度与度分布

2.1.2 平均路径长度

2.1.3 聚类系数

2.2 规则网络

2.3 随机网络

2.4 小世界网络

2.4.1 WS小世界模型

2.4.2 NW小世界网络

第3章 仿真及实验内容分析

3.1 仿真结果

3.2 小世界网路的性质

3.2.1 聚类系数

3.2.2 平均路径长度

3.2.3 度分布

第4章 总结感悟

参考文献

致 谢

第1章 绪论

1.1 复杂网络研究背景及意义

网络无所不在，我们生活的世界就是一个巨大的网络。因特网，互联网，代谢网络，食物网络，个人之间的熟悉社交网络，组织网络和公司之间的业务关系网络，分配网络等。如果这个网络越发达，那么有效性就会更强，这个世界也会变得更小。我们的生活离不开网络，就像是被无数网络所围起来一样。而生活中关于网络的问题以及现象也是很值得我们去研究和发现的。譬如传染病的网络，病毒怎么在生物中传播，计算机上的病毒又是怎么样来毒害电脑的。一个大型城市的交通网络中为何会频频堵车。当你发现你和某个朋友有共同的认识的人的时候，会不会有“小世界”的感慨。这些都是复杂网络科学所要研究的事情。网络分为规则网络、随机网络和小世界网络。复杂网络就包括了接下来所要研究的小世界网络。

图1.1 某高校的人际关系网络

自上个世纪三十年代以来，社会科学网络得到科学家们的广泛研究。社会学家认识到人们对人类社会运作理解的联系模式的重要性。社会学的典型网络研究涉及问卷调查，要求受访者详细介绍他们与他人的互动。然后可以使用响应来重构网络，其中顶点表示个体，并且边缘之间的交互。典型的社会网络研究解决了中心性问题和连接性。然而近年来，网络研究出现了大量新的运动，重点从单个小图的分析和这些图中的各个顶点或边缘的属性转移到考虑图形的大规模统计特性。这种新方法主要受到计算机和通信网络的可用性的驱动，这些网络允许我们以比以前更大的规模收集和分析数据。在研究用来查看可能数十个或极端情况下数百个顶点的网络的情况下，现在看到具有数百万甚至数十亿个顶点的网络是不常见的。这种规模的变化迫使我们在分析方法上有相应的变化。以前在小型网络研究中提出的许多问题在更大的网络中根本无用。试着想一想：“在如果一个网络中，哪些顶点对连接这个网络尤为重要，如果这些重要的点被删除，会有什么后果。”，但是这个问题在大多数百万个顶点的网络中是没有意义的。另一方面，人们可以合理地提出一个问题，如“在某些给定方式下，需要将几个百分比的顶点移除到基本上一个网络连接”，这种类型的统计问题即使在一个非常大的网络中也是有意义的。对于数十或数百个顶点的网络，使用实际的点和线绘制网络的图片是比较直接的。并通过检查这张图片来回答有关网络结构的具体问题。这是网络分析师从现场开始以来的主要方法之一。人眼是一种具有显着力量的分析工具，网络的眼球照片是了解其结构的好方法。然而，使用一百万或十亿顶点的网络，这种方法是无用的。一个简单的不能画出一百万个顶点的有意义的图片，即使是现代的3D电脑渲染工具，因此通过眼睛直接分析是无望的。最近开发量化大型网络的统计方法在很大程度上是尝试在二十世纪网络分析中找到发挥眼球的一部分。统计方法回答了这个问题：“我怎么看不清楚这个网络呢？”

自上个世纪末来，关于复杂网络的相关研究正处在一个蓬勃发展的阶段，复杂网络的研究工作越来越受到关注。特别是在工程建设领域，越来越多的科学家们开始着手研究与试验，在此之间，人们提到复杂网络，往往都是觉得与应用数学类似方面相关。换句话说，这个概念曾经在现实中还是很局限的。而现如今，已经发展为网络领域的新型科学。在生物和物理学家中，这是一个很狂热的话题，研究者们着手考虑更为繁琐，具有更大量的节点以及构成结构的网络^[1,2]。而作为复杂网络中最重要的一块---小世界网络模型的研究是进行的相对较早且较多的，小世界网络是一个很广的概念，它包括WS小世界网络^[1]、NW小世界网络^[3]、莫纳逊小世界网络^[4]以及很多在以上基础上进行变换的网络模型，譬如BW小世界网络模型之类的^[5]。其中由斯托加茨与瓦茨二人首次引出了小世界网络的概念，即当时的WS小世界网络模型；随机纽曼和瓦茨在这个基础上完成了改进，即本文要重点研究的---NW小世界网络，他们改进了之前研究中存在的一个大问题，用随机化加边代替了此前的随机化重连，这一改进措施，巧妙得避免网络产生孤立节点的可能性。在上述这些网络模型中，目前以WS小世界网络以及Barabasi与Alert的无标度网络模型^[6]相关研究工作的成果最为显著与丰富。自上世纪末以来，外国科学家建立了大量现实网络及拓扑构造的模型，一系列结论显示，生活中大部分的网络并不单一的具有单个性质，往往除了小世界性，无标度性，仍包括一些其他性质，譬如群集 ^[7-10]。还有对于特定的行为，网络结构起着怎样的作用，这些都是迄今为止研究者思考过的难题。小世界网络从某种方面反映了真实系统的两个重要特征，即全局平均距离以及局部集聚系数。而无标度网络则从另一个方面反映真实系统的另一个特征，即节点的度分布符合幂律分布。

WS和NW这两种小世界模型是迄今最经典的小世界网络模型，也是最常用到的小世界模型，所以对WS和NW小世界网络模型进行研究是很有意义的。

1.2 国内外研究现状

上个世纪六十年代中叶，年仅30岁的美国哈佛大学心理学家斯坦利在尝试进行了小世界的试验后受到了启发，他想要描绘一个人际关系网，这个网络能够包含和连结人与社区之间的关系，随即发现了“六度分离”的现象。即：“两个陌生人之间所隔至多为六，换句话说，至多只需要通过6人，你就可以认识这个世界上的任何1个人。”

具体的实验内容是这样的：斯坦利给奥马哈随机的一百六十个人每人一封信函，让这些人把信函送到麻省的某个股票经纪人手中，并说明可以直接去送，也可以将其转交给可能帮的上忙的认识的人，让他们去转交，当然了，这些被委托转交的人也可以采用同样的方式，每阶都是如此，直到信函被成功送到。每传递一个人，这个人也要反馈给斯坦利。尽管最后只有50个人参与了这项实验，并且只有百分之五的人成功将信函送达，但后来他发现，很多微小的因素，都可能对试验结果造成一定影响，比如接受着的人种和经济状况，通过改良，他成功将最终送达率提高到了百分之九十七。

在这项试验中，有很多有趣的发现，譬如：信函成功送达的平均经由的中间人为五人；每个随机的联系人与其提供的外界信息量并非均等，相反，这些信息量高度的集中某在几个人上。整个关系链中，有百分之四十八最终是由三个人送达的；不同种族不同文化对于信函的传递有着不同的引导作用。在所有的志愿者中，有百分之八十九的人寄给了自己的朋友或者熟人，只有百分之十一的人寄给了亲戚。对于这个看似奇怪的现象，斯坦利给出了比较合理的解释：美国是一个亲属关系并不紧密的国家，而如果实验在亚洲的一些国家进行，例如中国这样的大家庭文化国家，信函寄给亲戚的比例会明显增高，甚至超过送给朋友和熟人的几率。