小世界复杂网络模型研究.doc

苏州大学本科生毕业设计（论文） 目录摘要1第1章 引言2第2章 复杂网络理论基础3第2.1节 复杂网络的发展、应用及研究意义3第2.2节 复杂网络的基本概念7第2.3节 复杂网络现有演化模型11第3章 小世界网络的模拟及研究15第3.1节 实现算法15第3.2节 模拟过程15第四章 结论19参考文献21致谢2222摘要复杂网络已成为学术界研究的一个热点，它在工程技术、社会、政治、医药、经济、管理领域都有着潜在、广泛的应用。 本文介绍了复杂网络研究历史应用，理论描述方法及现有的几种模型，重点在VB环境下设计实现了WS小世界模型并用所建立的这个模型研究了它的平均路径长度和聚类系数。关键词：复杂网络 小世界 平均路径长度 聚类系数AbstractComplex networks are of great interests in many research fields. It has many potential applications in a variety of fields including engineering technology, society, politics, communications, medicine, neural networks, economics and management. In the present paper, we give a general review about complex networks. We focus on how to design a way tocarry out WS small world network by use of VB program and uses it to study its properties, such as the average path length and clustering coefficient.Keyword: complex networks, small-world,average path length, clustering coefficient第1章 引 言自然界中存在的大量复杂系统都可以通过形形色色的网络加以描述。一个典型的网络是由许多节点与连接两个节点之间的一些边组成的，其中节点用来代表真实系统中不同的个体，而边则用来表示个体间的关系，往往是两个节点之间具有某种特定的关系则连一条边，反之则不连边，有边相连的两个节点在网络中被看作是相邻的。例如，神经系统可以看作大量神经细胞通过神经纤维相互连接形成的网络；计算机网络可以看作是自主工作的计算机通过通信介质如光缆、双绞线、同轴电缆等相互连接形成的网络。类似的还有电力网络、社会关系网络、交通网络等等。数学家和物理学家在考虑网络的时候，往往只关心节点之间有没有边相连，至于节点到底在什么位置，边是长还是短，是弯曲还是平直，有没有相交等等都是他们不在意的。在这里，我们把网络不依赖于节点的具体位置和边的具体形态就能表现出来的性质叫做网络的拓扑性质，相应的结构叫做网络的拓扑结构。那么，什么样的拓扑结构比较适合用来描述真实的系统呢？两百多年来，对这个问题的研究经历了三个阶段。在最初的一百多年里，科学家们认为真实系统各因素之间的关系可以用一些规则的结构表示，例如二维平面上的欧几里德格网，它看起来像是格子体恤衫上的花纹；又或者最近邻环网，它总是会让你想到一群手牵着手围着篝火跳圆圈舞的姑娘。到了二十世纪五十年代末，数学家们想出了一种新的构造网络的方法，在这种方法下，两个节点之间连边与否不再是确定的事情，而是根据一个概率决定。数学家把这样生成的网络叫做随机网络，它在接下来的四十年里一直被很多科学家认为是描述真实系统最适宜的网络。直到最近几年，由于计算机数据处理和运算能力的飞速发展，科学家们发现大量的真实网络既不是规则网络，也不是随机网络，而是具有与前两者皆不同的统计特征的网络。这样的一些网络被科学家们叫做复杂网络（complex networks），对于它们的研究标志着第三阶段的到来。遗憾的是，就目前而言，科学家们还没有给出复杂网络精确严格的定义，从这几年的研究来看，之所以称其为复杂网络，大致上包含以下几层意思：首先，它是大量真实复杂系统的拓扑抽象；其次，它至少在感觉上比规则网络和随机网络复杂，因为我们可以很容易地生成规则和随机网络，但就目前而言，还没有一种简单方法能够生成完全符合真实统计特征的网络；最后，由于复杂网络是大量复杂系统得以存在的拓扑基础，因此对它的研究被认为有助于理解“复杂系统之所以复杂”这一至关重要的问题。第2章 复杂网络理论基础第2.1节 复杂网络的发展、应用及研究意义复杂网络研究的兴起时间还不长，但人们对复杂网络的研究方兴未艾，同时，复杂网络理论已经从许多方面展现出广泛、潜在的应用价值。复杂网络的发展历程现实世界中的许多系统都可以用复杂网络来描述，如社会网络中的科研合作网、性关系网、公司董事网，信息网络中的万维网、科研引用网、语言网，技术网络中的因特网、电力网、航空网，生物网络中的代谢网与蛋白质网络。网络节点为系统元素，边为元素间的互相作用，例如，在生命系统的巨型遗传网络中，节点和边分别表示蛋白质和蛋白质间的化学作用，在社会网络中，节点表示个人、组织机构或国家，边表示他（它）们之间的社会联系。现实网络系统的复杂性主要体现在三个方面：首先，网络的结构非常复杂，对网络节点间的连接，至今仍没有很清晰的概念；其次，网络是不断演化的，网络节点不断地增加，节点之间的连接在不断地增长，而且连接之间存在着多样性；第三，网络的动力学具有复杂性，每个节点本身可以是非线性系统，具有分岔和混沌等非线性动力学行为而且在不停地变化。由于现实世界网络的规模大，节点间相互作用复杂，其拓扑结构基本上未知或未曾探索。两百多年来，人们对描述真实系统拓扑结构的研究经历了三个阶段。在最初的一百多年里，科学家们认为真实系统要素之间的关系可以用一些规则的结构表示，例如二维平面上的欧几里德格网；从20世纪50年代末到90年代末，无明确设计原则的大规模网络主要用简单而易于被多数人接受的随机网络来描述，随机图的思想主宰复杂网络研究达四十年之久；直到最近几年，科学家们发现大量的真实网络既不是规则网络，也不是随机网络，而是具有与前两者皆不同的统计特性的网络，其中最有影响的是小世界网络和无尺度网络。这两种网络的发现，掀起了复杂网络的研究热潮。复杂网络的应用及研究意义复杂网络（特别是小世界网络和无尺度网络）刚一提出，就呈现出广阔的应用前景，其应用领域涉及工程技术、社会、政治、医药、经济、管理等不同方面。在过去几年里，不同领域的研究者发现，包括万维网、细胞代谢系统、好莱坞的演员网络在内的许多现实网络，都是无尺度网络，它们由少数几个具有众多连结的节点所支配，这些重要节点通常称为集散节点。无尺度网络对意外故障具有惊人的承受力，但面对协同式攻击时则很脆弱。这些新发现极大地改变了人们对复杂外部世界的认识，让人们认识到了以前的理论尚未涉及的问题：各种复杂系统具有相同的严格结构，都受制于某些基本的法则，这些法则似乎可同等地适用于细胞、计算机、语言和社会。认识这些法则，可以将其应用到不同领域，帮助人们解决一系列重要问题。首先，复杂网络理论可以用于保护许多现实系统的正常运行。因特网、电力网、航空网、万维网、电子邮件网、食物链网等网络与我们的生活息息相关，人们对这些网络的依赖程度日益增强，凸现了一个广受关注的问题：这些网络到底有多可靠呢？2000年，爱虫病毒侵犯了英国议会的电子邮件系统，导致该系统瘫痪；同年，一场暴风雨袭击芝加哥，致使OHare机场关闭，由此而影响了全美航班；2003年美加电网的大崩溃事故让纽约人感到惶恐不安；当前，人类赖以生存的生态系统不断遭到破坏已经危及到人类的生存环境，等等。从这些现象可以自然地提出下面的问题：计算机病毒如何在万维网上传播而导致流行？病毒如何通过电子邮件传播？人们如何控制病毒传播？面对黑客的攻击，应该采取何种对策？怎样设计出承受意外故障较强的网络（如电力网、航空网）？怎样保持当前不断恶化的生态系统的平衡？这些问题的解决都与复杂网络的研究有关，开展好复杂网络稳定性的研究，对于互联网、电力网、航空网等技术网络的设计保护及基础设施网络的保护具有重要的意义，也可以有效地防止黑客侵入互联网、阻止病毒在万维网上传播蔓延。复杂网络在社会领域也有广阔的应用。传染病（如艾滋病、非典、禽流感等）对人类的威胁很大：艾滋病让人们不寒而栗；2003年的非典对于宏观经济和人类的生命安全都产生了巨大的负面影响；目前，禽流感也已成为世界关注的一个焦点。那么在特定的社会网络中，传染病如何通过接触关系传播而导致流行呢？决策者如何控制这些疾病，将损失降到最低限度呢？这些问题或许可以从复杂网络那里寻找答案。最近几年，科学家们考虑了不同现实系统的主要特征，提出了许多有针对性的疾病免疫方法，为疾病的预测、预防和免疫提供了科学的方案。譬如，用复杂网络理论可以很好地预测非典爆发的多样性、了解疾病传播的动态性，为决策者控制流行病蔓延、改善公共卫生提供有效的手段。在当今社会，稳定是经济发展的基础，流言飞语往往会影响社会的安定。复杂网络理论可以用于模拟社会上谣言传播过程，对控制传言的扩散、降低其负面影响具有一定的借鉴意义。除了社会领域外，复杂网络在政治方面也开始显示出实际的应用价值。在当今世界上，恐怖主义已被列为21世纪的十大危害之一，发生在美国的911事件让全美至今仍有后怕。对于恐怖主义、犯罪组织这些需要破坏的网络，人们可以利用复杂网络理论，通过捉拿逮捕其主要人物，就可摧毁网络，使其功能失常，以维护人类社会政治的稳定。网络理论还可用于揭示政府议员的组织、层次关系，甚至可以成功模拟政治选举，分析一些因素对选举结果的影响。在医药领域，复杂网络同样有其重要的应用价值。许多传染病的疫苗价格昂贵，而且数量有限，不可能对每个人都接种疫苗。如何充分利用数量有限的疫苗呢？对非典、天花等严重疾病，如果能采取措施直接或间接地针对集散节点（即那些与很多人具有连结关系的人）接种疫苗，可以达到很好的效果，复杂网络理论为这一做法提供了科学的依据 。在分配艾滋病、天花等成本很高的疫苗时，对于那些无力照顾到全民的国家和地区而言，这种做法可能是最实用的。在制药业方面，细胞对集散节点的依赖，给药物研究者提供了新的方法：有可能找到这样的药物，能针对性地攻击细胞或者细菌的集散节点，以便杀死它们而又不会影响健康的组织。例如，癌症是让人类头疼的一种疾病，在复杂的基因网络中，如果知道故障节点相互作用引发癌症的病理，就可能研制出针对癌症集散节点的药物，对癌症的治疗也许有很好的效果。此外，弄清人体细胞内的网络结构，有助于研究者发现和控制药物的副作用。复杂网络也为人们认识语言文字、获取知识提供了新的有力工具，是人们研究知识管理的新途径。语言是人类区别动物的主要标志之一，可是我们今天使用的语言是如何演化的呢？为什么只有人类才具有复杂语言呢？人脑为什么接触到某一事物后，可以很快的联想到其它事物呢？现实复杂网络中的语言网作为语言演化研究的新方法与新尝试，其在认知科学中意义很大，如语言网的小世界特性可以部分地解释人脑具有很快的联想功能等。目前正处在信息（知识）时代，信息时代需要时代信息，可是，在信息网络（如万维网）中信息如何传播呢？人们如何尽快获取所需要的信息呢？复杂网络不但对于专家领域知识的发现及表示方法有一定的意义，而且在知识学习与获取方面，复杂网络也可一显身手。另外，根据万维网特殊的复杂结构，人们可以提出相应的搜索算法，为获取所需信息提供方便。复杂网络在经济、管理领域也有着重要的实际意义。利用复杂网络理论了解公司、产业与经济之间的连结方式，有助于监控和预防大规模的经济衰退。在管理领域，决策对经济的发展起着关键性的作用，同一个人可以在多个组织内兼任董事。建立公司董事网，使得分析决策的动态性成为可能。另外，研究流行病在复杂网络中的传播现象，为市场人员传播新产品和新时尚提供了新方法、新理论。许多市场营销专家都在大力研究扩散理论，出于各种商业目的，他们需要引发流行而不是遏制流行，于是他们提出了所谓的病毒式行销，这一方法实用可行，但一直没有公认的理论基础，新近的复杂网络研究，为更严谨地探讨这些现象，提供了一个科学的框架和数学工具。利用网络理论，还可以分析公司等组织内部及组织之间的信息传播、信息交换、组织间的战略同盟 、组织的综合评价及排名。在复杂的市场环境下，复杂网络还可用于对金融产品进行定价等。除了以上应用外，复杂网络的研究，对于其他许多领域也是有价值的。例如，将小世界的思想用于BP网络，可以减少BP网络的学习时间和学习误差，使得BP网可以更好地用于数据挖掘、语音识别、图像处理及模式识别等多个领域；另外，将复杂网络用于Hopfield网络，可以改变神经网络的联想记忆功能。特别地，复杂网络对于系统科学有着极其重要的理论意义和工程应用价值，中国系统工程学会将复杂网络对系统工程与系统科学的贡献作了深远的展望。众所周知，结构是客观事物的基本属性，也是各学科领域研究的一个重要问题。虽然每门学科在其研究对象的结构方面，都有非常丰富的具体成果，但从系统学的高度，横跨物质系统、生物系统和社会经济系统的具体研究成果，也就是系统学层面的成果还不多，其系统层面的内涵迄今还没有完备的阐述。复杂网络是综合以往的自组织理论、非线性理论与复杂性理论研究的成果而形成的崭新的理论。复杂网络的兴起，为系统科学的研究开拓了视野，提供了全新的视角。复杂网络作为复杂系统的一般抽象和描述方式，作为复杂系统的结构形态，它突出强调了系统结构的拓扑特征。可以说，任何复杂系统都可以当作复杂网络来研究。以复杂网络形式研究复杂系统，可以加深人们对系统结构的深入了解，随着复杂网络研究的深入以及用网络理论研究系统演化工作的深入开展，复杂系统演化的研究必将出现新的突破性结果；反过来，复杂网络的研究成果对探索复杂性具有一定的启发和借鉴意义；当然也可以从系统科学的角度来研究网络，这也是网络研究的新视角。可见，利用网络理论对系统进行研究，是系统科学一种新的研究手段。本文拟以复杂网络的演化模型研究作为切入点，深入开展复杂系统结构的研究。因此，本文的研究十分有意义。广泛的应用前景使得复杂网络的研究倍受国内外的密切关注，引起了不同学科的高度重视。在2004年召开的国际统计物理大会（每三年召开一次）上，第一个报告就是关于复杂网络方面的研究。在国内，包括中国科学技术大学、上海交通大学、武汉大学等在内的许多院校，都专门成立了复杂网络研究中心和研究小组。近些年，国家自然科学基金委员会每年都设置关于复杂网络的基金项目或重点基金项目。目前，对复杂网络的研究已成为极其重要而且富有挑战性的前沿科研课题。这些进一步说明，选择复杂网络作为博士学位研究课题具有一定的实际背景，有重要的理论意义和应用价值。图1 生物系统中的复杂网络：细胞网络，蛋白质-蛋白质作用网络，生态网络，蛋白质折叠网络，神经系统图2 人类社会的复杂网络：湖北省电子政务“小世界”网络 图3 微电子技术中的复杂网络：VLSI Circuits第2.2节 复杂网络的基本概念网络的定义及表示方式自随机图理论提出至今，在复杂网络领域提出了许多概念和术语。网络（Network）在数学上以图（Graph）来表示，图的研究最早起源于18世纪瑞士著名数学家Euler的哥尼斯堡七桥问题。复杂网络可以用图论的语言和符号精确简洁地加以描述。图论不仅为数学家和物理学家提供了描述网络的语言和研究的平台，而且其结论和技巧已经被广泛地移植到复杂网络的研究中。为了能够方便准确地表达复杂网络的统计性质，有必要先介绍一些网络和图论的基本知识。网络（图）是指二元组，其中为节点集，为边集，中元素称为节点或顶点（Vertex或Node），中元素称为边（Edge或Link），且中的每条边有的一对节点与之对应，如果中任意的节点对和对应同一条边，则该网络称为无向网络，否则为有向网络；如果中所有边的长度均为1，即，则称网络为无权网络，否则为加权网络。中元素个数和中元素个数分别称为网络的阶（Order）和边数（Size）。阶和边数都有限的图为有限图（Finite Graph）。边所连接的节点称为端点（End-vertices），两端点相同的边称为环（Loop）。有公共起点并且有公共终点的两条边称为平行边（Parallel Edges）或重边（Multi-edge）。无环且无平行边的图称为简单图（Simple Graph）。任何不同的两节点之间都有边相连的简单无向图称为完全图（Complete Graph）。本文提到的图，若没有特别的说明，均指没有重边的无向简单图2。复杂网络的特征度量随着对复杂网络研究的深入，人们提出了许多概念和度量方法，用于表示复杂网络的结构特性。度分布（Degree Distribution）。度分布是网络的一个重要统计特征。这里的度（Degree）也称为连通度（Connectivity），节点的度指的是与该节点连接的边数。度在不同的网络中所代表的含义也不同，在社会网络中，度可以表示个体的影响力和重要程度，度越大的个体，其影响力就越大，在整个组织中的作用也就越大，反之亦然。度分布则表示节点度的概率分布函数，它指的是节点有条边连接的概率。在目前的研究中，两种度分布较为常见：一是指数度分布，即随着的增大以指数形式衰减；另一种分布是幂律分布，即，其中称为度指数，不同的网络，其动力学性质也不同。另外，度分布还有其它形式，如星型网络的度分布是两点分布，规则网络的度分布为单点分布。簇系数（Clustering Coefficient）。簇系数又称作集聚系数，它衡量的是网络的集团化程度，是网络的另一个重要参数。簇系数的概念有其深刻的社会根源。对社会网络而言，集团化形态是其一个重要特征，集团表示网络中的朋友圈或熟人圈，集团中的成员往往相互熟悉，为衡量这种群集现象，科学家们提出了簇系数的概念。节点i的簇系数描述的是网络中与该节点直接相连的节点之间的连接关系，即与该节点直接相邻的节点间实际存在的边数目占最大可能存在的边数的比例，的表达式为，式中表示节点i的度，表示节点i的邻接点之间实际存在的边数。网络的簇系数为所有节点簇系数的算术平均值，即，其中为网络的阶。不尽尽是社会网络，在其它类型的网络中，也普遍存在集聚现象。平均路径长度（Average Path Length, APL）。平均路径长度是网络中另一个重要的特征度量，它指网络中所有节点对之间的平均最短距离。这里节点间的距离（Distance）指的是从一节点到另一节点所要经历的边的最小数目，其中所有节点对之间的最大距离称为网络的直径(Diameter)。平均路径长度和直径衡量的是网络的传输性能与效率。平均路径长度的计算公式为，式中为节点和之间的最短距离。度分布、簇系数和平均路径长度是网络的三个最基本的结构特性。如果一个网络同时具有较小的平均路径长度和较大的簇系数，则称该网络具有“小世界效应”（Small-world Effect），这里较小的平均路径长度指的是网络的平均路径长度按照网络阶的对数形式增长，或者以更慢的速度增长。除了上面三个最重要的参数，网络还有其它特征度量，如介数及其分布、最大连通分支的规模分布、混合模式、度相关性、簇度相关性、模块性等。为了保持本文的相对完备性，下面对这些性质作简单介绍，具体详细的内容可以参考相关文献。介数（Betweenness）。介数分为顶点介数和边介数两种，它是一个全局变量，反映了节点或边的作用和影响力。如果一对节点间共有条不同的最短路径，其中有条经过节点，那么节点对这对节点的介数的贡献为。把节点对所有节点对的贡献累加起来再除以节点对总数，就可得到节点的介数。类似的，边的介数定义为所有节点对的最短路径中经过该边的数量比例。研究表明，节点的介数与度之间有很强的相关性，不同类型的网络，其介数分布也大不一样。最大连通分支（Giant Component）。网络一般由分支组成，一个分支指的是一个连通的最大子网络，所谓最大意味着原网络中任何其它节点或边加入分支时都将破坏分支的连通性，人们把分支中阶数最大的一个称为最大连通分支，当网络演化成无限网络时，最大连通分支的阶数与整个网络的阶数之比对不同的网络会呈现不同的结果，这一比值是衡量网络稳定性的一个重要参数。混合模式（Mixing Patterns）。很多网络中通常包含不只一种类型的节点，节点间有边相连的概率常常依赖于节点的类型。例如在食物链网络中，节点可以分为三种类型：植物、食草动物和食肉动物。Newman提出了一种用关联系数来定量描述混合模式的量化方法，对于完全随机图与完全同类图（只有同类节点之间才连边）这两类极端的网络，其关联系数分别等于0和1。度相关性（Degree Correlations）。度相关性描述的是网络中不同节点之间的连接关系。如果度大的节点倾向于连接度大的节点，则称网络是正相关的；反之，如果度大的节点倾向于和度小的节点连接，则称网络是负相关的。西班牙的Pastor-Satorras等人给出了度相关性一个简洁直观的刻画，即计算度为的节点的邻居的平均度，其值为k的函数。对于正、负相关的网络，函数图形分别是的递增、递减曲线；对于不相关的网络，函数值为常数。随后，Newman进一步简化了度相关性的计算方法，指出只需计算顶点度的Pearson相关系数就可以描述网络的度相关性，的定义为： (1.1)其中，分别表示连接第条边的两个顶点j，k的度，表示网络的总边数。的取值范围为，当时，网络是正相关的；当时，网络是负相关的；当时，网络是不相关的。簇度相关性（Clustering-degree Correlations）。如果用表示度为k的节点的平均簇系数，则与k之间的关系称为簇度相关性。实证研究表明，在许多现实网络中，与k之间存在如下的倒数关系：，人们把这种倒数关系的簇度相关性称为层次性，把具有层次性的网络称作层次网络。模块性（Modularity）。现实世界中的许多网络(如代谢网络)是由模块结构组成的。模块有两个显著特征：模块内部的节点间高度连接，有着直接的相互作用；模块与模块之间只有少数甚至没有连接，模块与模块或模块与非模块之间有着清晰的边界。在复杂网络研究领域，模块也称作社区（Community） 。如在电影演员合作网中，不同的模块代表不同的流派；在引文网络中，模块代表特定的研究领域；在万维网中，模块反映网络的主题分类。在社会学文献中往往采用聚类分析的方法来检测网络的社区结构。目前许多学者提出了寻找社区结构的新方法。2002年，Girvan和Newman给出了一种识别社区结构的新算法（GN算法），该算法的基本思想是每次选择一条介数最大的边，将其从网络中删除。不断地重复该过程，就可以凸现网络的社区结构。2004年，他们又定义了一个量，定量地衡量网络的模块化程度（模块性）。该模块性定义为： (1.2)其中，指连接社区i中的顶点的边数的比例，指两个端点都在社区i中的边的比例。值越大，网络的社区结构越明显。一般认为值在0.3与0.7之间的网络具有较强的社区结构。2004年，Newman利用贪婪算法通过最大化的值来寻找社区结构，该算法的复杂度有了很好的改进，处理问题的规模比过去大大增加。王林和戴冠中对社区发现的方法进行了综述。用上述参数可以很方便地衡量现实网络的特性。根据Newman的观点，现实网络大致分为四种：社会网络，信息网络，技术网络和生物网络。这四种网络，虽然各自具有不同的物理形式，彼此描述的系统各异，其节点和边的定义差别也很大，但它们却具有一些相同的特征：网络节点间的作用很复杂，而且高度不规则；节点之间在度、簇系数、集中性等网络特征度量方面表现出不对称性，不同节点差异很大；尽管这些网络大而复杂，节点间的平均距离却很小，呈现出小世界特性。大量的实证研究表明：现实世界中的许多网络具有下面三个共同特性：节点度服从度指数介于的幂律分布；集聚程度高；节点间平均距离小。关于现实网络的统计性质，请参阅有关的文献，限于篇幅，此处不再赘述。现实网络除了上述三大特性之外，不同的网络还具有各自的其它性质，如社会网络往往是正相关的，而技术和生物网络往往是负相关的。另外，诸如代谢网、电影演员网、万维网、AS层的因特网等许多网络还呈现出层次性和模块性。综上，网络的统计特性多而复杂。本文将重点围绕度分布、簇系数和平均路径长度（或直径）等目前公认的网络基本特征，从演化模型着手，研究网络演化过程中的微观事件对网络拓扑结构的影响，发现网络演化的规律，最终达到更好地了解认识现实网络系统的目的。复杂网络的分类到目前为止，人们还没有给复杂网络下一个明确的定义，只是从不类角度对复杂网络大致进行了分类3。根据节点度的分布情况，可以将复杂网络分为指数网络和无尺度网络两大类。指数网络中的节点是同质的，它们的度大致相同，绝大部节点的度都位于网络节点平均度附近，网络节点度分布随度数的增加呈指数衰减，使得网络中不存在度数特别大的节点，最经典的两种指数网络是Erds与Rnyi于1960年提出的Erds-Rnyi（ER）随机图模型和Watt与Strogatz在1998年提出的Watt-Strogatz小世界网络模型（WS模型）。随机图与小世界网络的主要区别是：前者的簇系数小，而后者的簇系数大。目前，把具有较小平均路径长度和较大簇系数的网络统称为小世界网络，这一说法已得到学术界的公认。无尺度网络中的节点是异质的，其节点度服从幂律分布。最著名的无尺度网络模型是1999年Barabsi和Albert建立的Barabsi-Albert无尺度网络模型（BA模型或BA网络）。在无尺度网络中，大部分节点只与少数几个其它节点连接，但网络中存在为数不多的度数特别大的节点，称为集散节点（或hub节点），它对无尺度网络的特性起着主导和支配作用。从生成方式上可将复杂网络分成随机性网络和确定性网络。顾名思义，随机网络的生成是随机的，尽管生成规则相同，每次在电脑上模拟生成的网络却存在差异性；确定性网络的生成规则是确定的，其结构特性可以精确求解。从边的方向性上可将网络分为无向网络和有向网络，无向网络的边不存在方向性，有向网络的边却有方向。从边有无权值可将网络分为加权网络和0-1网络。第2.3节 复杂网络现有演化模型目前，对复杂网络的研究主要集中在三个领域：一是网络生成机制及演化模型，即通过生成机制建立模型，模仿真实网络行为；二是复杂网络的稳定性，研究限制条件对网络几何特性的影响，如复杂网络承受意外故障和恶意攻击的能力等；三是复杂网络上的动力学，这是人们研究复杂网络的最终目标，也就是超越网络拓扑结构，掌握建立在这些网络上的系统的工作方式和机理，认识复杂系统内部深奥得难以理解的动力学：如复杂网络上的同步，疾病、信息、知识、舆论如何在复杂网络上的传播等。目前的研究重点主要集中在第一个领域，即研究复杂网络的演化机制及模型，再现现实系统的主要拓扑特性。如上所述，学术界十分关心网络结构的复杂性研究，主要原因之一是网络的结构在很大程度上决定了它的功能。众多研究发现，复杂网络结构对发生在其上的动力学特性至关重要。复杂网络上的博弈（如囚徒悖论、雪堆模型）、合作、同步、搜索、随机游走、疾病传播等动力学行为，都在很大程度上受到拓扑结构的影响，不同结构的网络，其动力学行为表现出明显的、本质上的差异。近年来，对复杂网络的研究方兴未艾，研究从不同角度同时展开，相对而言，关于网络演化机制及演化模型的研究最为活跃，取得了十分骄人的成绩。复杂网络的生成机制指的是网络的形成方式与形成过程，根据生成机制建立的模型称为复杂网络的演化模型。目前，在复杂网络模型方面的研究已经取得了许多可喜的成就，在正式引入本文的工作之前，先对已有的相关工作进行简要的介绍与评述。规则网络在很长一段里，人们认为真实系统各因素之间的关系可以用一些规则网络表示，如一维链、二维平面上的欧几里德格网等。用得最多的规则网络是由个节点组成的环状网络，网络中每个节点只与它最近的个节点连接。在规则网络中，每个节点具有相同的度和簇系数。节点的度分布为函数，即；节点簇系数为（d为网络维数），集聚程度较高。一维规则网络的平均路径长度L较大，与节点数成线性比例关系，即。随机图模型随机网络理论由匈牙利数学家Erds和Rnyi提出，他们提出的模型称为经典的Erds-Rnyi（ER）模型。ER模型的定义为：在由个顶点、条边构成的图中，随机连接条边形成一随机网络，记为，由这样的个节点、条边组成的网络共有种，构成一个概率空间，每一个网络出现的概率是相等的。另一种与ER模型等价的随机网络模型是二项式模型，其定义如下：给定的节点数目固定不变，假定任意节点对之间有条边连接的概率为，形成的网络记为。这样，整个网络中边的数目是一个随机变量，其期望值为。设是由节点为，且有条边连接组成的一个随机网络，则按上述构造过程，得到的概率为。如果令，则两个模型和互相等价，由任一模型得出的结果可以非常容易地推广到另一模型。人们往往根据方便，将两种形式替换使用。ER随机图的节点度服从泊松分布，它具有较小的平均路径长度和较小的簇系数。ER模型提出后，从20世纪50年代末到90年代末的近四十年里，无明确设计原则的大规模网络主要用这种简单而易于被多数人接受的随机图的拓扑结构来描述，即认为大规模网络的形成过程中，节点间的连接是完全随机的。期间，一些数学家对随机图进行了非常好的研究，通过严格的数学证明，得到了许多近似和精确的结果。ER模型的思想支配人们研究复杂网络长达四十年之久，直到最近几年，由于计算机数据处理和运算能力的飞速发展，科学家们发现大量的现实网络不是完全随机的网络，而是具有其他统计特征的网络。小世界网络实证研究表明，许多现实网络特别是社会网络都表现出集群现象，由此引发人们对小世界网络的研究。最早的小世界网络模型是Watts和Strogatz在1998年提出的网络模型（WS模型），该模型由一个具有个节点的环开始，环上每一个节点与两侧各有条边相连，然后对每条边以概率随机进行重连（自我连接和重边除外），这些重连的边叫“长程连接”，长程连接大大地减小了网络的平均路径长度，而对网络的簇系数影响较小。WS模型的建立和生成有其深刻的社会根源，因为在社会系统中，大多数人直接和邻居、同事相识，但个别人也有远方甚至国外的朋友。Watts和Strogatz开创性论文的发表掀起了小世界网络和WS模型的研究高潮。在WS模型提出不久，Newman和Watts对WS模型作了改进，提出了WS模型的一个变体模型，通过在随机选择的节点对之间增加边作为长程连接，而原始格上的边保持不动。这一模型比WS模型容易分析，因为它在形成过程中不会出现孤立的簇，但在WS模型中却可能发生这种情况。1999年，Kasturirangan提出了WS模型的一个替代模型，该模型同样始于环状格，然后，在格中间增加节点并与格上的节点随机进行连接，这些随机连接的边充当了WS模型中“长程连接”的角色。其实只要在网格中间增加一个新节点并连接到网格边缘足够多的节点上，网络就呈现出小世界特性，Dorogovtsev和Mendes对这一情况进行了精确的求解。为进一步研究小世界特性，在二维方格的基础上Kleinberg提出了WS网络的一般化模型，Kleinberg模型的平均路径长度是可调的。虽然许多现实网络都表现出小世界特性，但它们的形成机制不尽相同。为进一步研究小世界网络的产生机理，杨波、陈忠、段文奇提出了基于个体选择的小世界网络的结构演化；Ozik等提出了地理位置择优连接机制，说明小世界的形成是系统增长和局部作用的共同结果；刘强、方锦清等通过交叉边的方式探索了一种产生小世界特性的新方法。图4 下面分别是规则网络、小世界网络、随机网络即其转化过程无尺度网络模型ER模型和WS模型的度分布与许多现实网络都不相符，用它们来描述这些现实网络，具有很大的局限性，因此科学家们只好寻求另一种模型，来更好地描述这些现实网络。1999年，Barabsi和Albert通过追踪万维网的动态演化过程，发现了许多复杂网络具有大规模的高度自组织特性，即多数复杂网络的节点度服从幂律分布，并把具有幂律度分布的网络称为无尺度网络。Barabsi认为，增长和择优连接是无尺度网络形成的两种必不可少的机制，这一观点已被学术界普遍接受。最原始的无尺度网络模型称为Barabsi-Albert（BA）模型（或称为BA网络），它是第一个随机的无尺度网络模型。在BA模型生成的初始时刻，假定系统中已有少量节点，在以后的每一个时间间隔中，新增一个节点，并与网络中已经存在一定数目的不同节点进行连接。当在网络中选择节点与新增节点连接时，假设被选择的节点与新节点连接的概率和被选节点的度成正比，人们将这种连接称为择优连接。BA网络最终演化成标度不变状态，即节点度服从度指数等于3的幂律分布。BA模型的平均路径长度很小，簇系数也很小，但比同规模随机图的簇系数要大，不过当网络趋于无穷大时，这两种网络的簇系数均近似为零。图5：无标度网络的拓扑结构示意图 第3章 小世界网络的模拟及研究第3.1节 实现算法根据参考文献1 Watts J S, Strogatz S H关于小世界模型的描述，欲构造一个小世界模型，我们可以假设一个圆环状网络有n个顶点，每个顶点与最近的k个顶点相连（例如本例中的n = 20 ,k = 4但一般比这些大得多），不改变边和顶点的数目。我们选出一个点，按顺时针方向把连接它和它最近的那个点的边以p的概率重新连接到整个环上的其它点，然后同样按顺时针方向把连接它与第二近的那个点的边以p的概率重新连接到整个环上的其它点，重复此过程直到此点的所有边都按p的概率重新连了一下；然后是下一个顶点也这么换边一下直到n个顶点都连完（参考图4）。第3.2节 模拟过程1 建立规则图 n = Val(Text1.Text): k = Val(Text2.Text) 确定规则边 Randomize ReDim edge(n, k), edge2(n, n), edge22(n, n) For i = 1 To n For j = 1 To k / 2 If i + j n Then edge(i, j) = i + j - n Else edge(i, j) = i + j End If Next j For j = k / 2 + 1 To k If i - j + k / 2 = 0 Then edge(i, j) = i - j + k / 2 + n Else edge(i, j) = i - j + k / 2 End If Next j Next I 确定规则边 For i = 1 To n 确定规则矩阵 For j = 1 To k edge2(i, edge(i, j) = 1 NextNext 确定规则矩阵节点图6 此时生成了如下的规则网络（以n= 20 ,k= 4 为例）2 生成小世界网络Private Sub pp(edge3() As Integer, pp As Single, nn As Long, ka As Integer)确定随机矩阵 Dim i As Long, j As Long, r As Single, r1 As Single, a As Long, a1() As Long, ii As Long, jj As Long Randomize For j = 1 To ka / 2 For i = 1 To nn r = Rnd If r nn Then jj = i + j - nn Else jj = i + j edge3(i, jj) = 0: edge3(jj, i) = 0 随机消边 随机连边 a = 0: ReDim a1(nn) For ii = 1 To nn If edge3(i, ii) = 0 Then If i ii Then a = a + 1 a1(a) = ii End If End If Next r1 = Int(Rnd * a) + 1 edge3(i, a1(r1) = 1: edge3(a1(r1), i) = 1 随机连边 End If Next Next确定随机矩阵End Sub图7 此时生成了如下的小世界网络（以n= 20 ,k= 4，p = 0.1 为例）由图可看出其中一些边已经换过了，不过因为换边的概率不大，所以很多边没变，这使得每个节点的与其周围邻居的关系相较规则网络而言没多大变化（聚类系数保持在一个较大的数值），但因为生成了一些长程边加强了远距离节点间的联系，从而使得特征路径长度并不再像从前那样大了。3 计算平均路径长度Private Function lount(si As Long, nn As Long, edgee() As Integer) As Single Dim a As Integer, c As Integer, d As Integer, dd As Integer, b() As Integer, link() As Integer, linkk() As Integer, e() As Integer Dim i As Integer, j As Integer, s As Integer ReDim b(nn) As Integer, link(nn) As Integer, linkk(nn) As Integer, e(nn) As Integer a = nn - 1: dd = 1 linkk(1) = si e(si) = 10 Do While a 0 c = c + 1 For i = 1 To dd For j = 1 To nn If edgee(linkk(i), j) = 1 Then If e(j) 10 Then d = d + 1 link(d) = j b(c) = b(c) + 1 e(j) = 10 a = a - 1 End If End If Next Next dd = d: d = 0 If dd = 0 Then MsgBox (有节点未连) Exit Function End If For i = 1 To dd linkk(i) = link(i): link(i) = 0 Next Loop For i = 1 To c lount = lount + i * b(i