基于复杂网络的供应链建模与性能分析研究.docx

基于复杂网络的供应链建模与性能分析J I A N G S U U N I V E R S I T Y基于复杂网络的供应链建模与性能分析研究班级：运输1101姓名：杨阳阳学号：3110405012日期：2014.6.24基于复杂网络的供应链建模与性能分析研究（杨阳阳）（汽车学院，运输1101, 3110405012）摘要：供应链是社会经济系统中的一个整体功能网链结构，目前的供应链系统结构的复杂性与不确定性越来越严重。而基于复杂的网络理论的供应链分析与建模，为应对供应链系统结构的复杂性与不确定性提供了一个全新的理论与方法。是实现经济型，环保型社会结构的重要途径之一，本文主要针对网络的鲁棒性行为，分析了不同类型拓扑结构的网络模型对于网络的鲁棒性行为影响和性能差别，为提高供应链网络应对鲁棒性行为能力提供一些可参考建议。关键词：供应链网络；复杂网络；鲁棒性； Supply Chain Modeling and Performance Analysis Based on Complex Networks(YangYangyang)(Auto college，Traffic and Transportation 1101,3110405012)Abstract：Supply chain is a social economic system of a whole function nets chain structure，for now，The complexity and uncertainty of the supply chain system structure becomes more and more serious .And based on the analysis and modeling of the complex network theory of the supply chain, it provides a new theory and method to cope with the complexity and uncertainty of the supply chain system structure .it is one of the important ways to realize the economic and environmental friendly society structure This article mainly aims at the robustness of the network behavior, analyzes the influence that the different types of topological structure of the supply chain network model for network behavior on the performance and robustness, in order to give some advice on improving the ability of supply chain network to cope with robustness behavior Keywords：Supply Chain Network ; Complex Network; Robustness目录基于复杂网络的供应链建模与性能分析研究11.引言32.选题背景与研究意义33.供应链系统33.1供应链概述33.2供应链建模研究分析与现状53.3现行系统存在问题64.复杂网络74.1复杂网络概述74.1.1网络的定义及表示方式74.1.2复杂网络的特征度量84.2复杂网络的分类114.3复杂网络理论经典模型114.3.1小世界网络模型114.3.2随机图模型144.3.3无尺度网络模型154.3.4局域世界演化模型165.基于复杂网络的供应链建模175.1.供应链的基础模型介5175.1.1.网状结构的供应链模型175.1.2.链状结构的供应链模型175.1.3.核心企业网状供应链185.2.供应链模型的建立195.2.1.基础模型的选择195.2.2.供应链构建的原理及方法206.供应链的鲁棒性能分析226.1.鲁棒性定义与度量8226.2.复杂网络模型上的鲁棒性分析236.2.1.无标度网络的鲁棒性与脆弱性246.2.2.传统复杂网络鲁棒性分析246.2.3.复杂网络中重要节点的挖掘6256.2.4.供应链复杂网络鲁棒性分析257.总结27参考文献28基于复杂网络的供应链建模与性能分析研究1. 引言通过对大量文献的阅读，本文先阐述了论文的写作背景，总结了部分对基于复杂网络的供应链建模的相关理论、研究意义和国内外现状进行叙述，进而提出一些可参考建议。随着社会的发展，社会经济结构的变化也越来越剧烈，越来越复杂，由于市场变化的不确定性和供应链的整体性，导致供应链网络中任何一个环节由于抵抗干扰能力的不足都会对整个供应链造成严重的影响和冲击。2008年由美国华尔街为始点爆发的全球经济危机，使全球的供应链网络系统都遭受了不同程度破坏。在竞争日趋激烈的社会环境下，企业抵抗干扰的能力和强化供应链管理的鲁棒性就显得尤为重要。2. 选题背景与研究意义随着经济全球化和知识经济时代的来临,市场竞争日益激烈,用户需求的不确定性日益增加,产品周期缩短而产品结构越来越复杂。如何准确把握市场机遇快速、有效地满足消费者个性化需求,提高满意度水平,这些都己成为传统企业管理模式面对的重要挑战。20世纪80年代初应运而生的供应链以其敏捷度高、生产成本低、生产周期短等特点,近年来得到全球生产企业的广泛重视和运用,供应链管理已经成为关乎企业生存和发展的重要因素。进入21世纪,全球经济一体化的步伐在加快,政治、经济、社会环境发生巨大变化,顾客的消费水平不断提高,使得企业间的竞争日益加剧。如何构建最有效的供需网络,提高企业生产效率及商品流通的效率成为迫切需要解决的问题。因此,供应链系统成为当前的一个研究热点。3. 供应链系统3.1 供应链概述供应链是围绕核心企业，通过对信息流，物流，资金流的控制，从采购原材料开始，制成中间产品以及最终产品，最后由销售网络把产品送到消费者手中的将供应商，制造商，分销商，零售商，直到最终用户连成一个整体功能网链结构。市场竞争的加剧使得企业正面对着一个迅速变化且难以预测的外部环境。传统的“纵向一体化”管理模式(核心企业通过投资自建、投资控股或兼并等方式实现对原材料获取、产品制造、分销和销售全过程的控制),由于对外部环境的响应迟缓和被动,难以满足日益增长的客户需求。为了摆脱这种困境,快速、敏捷地响应外部环境变化,“横向一体化”管理模式逐渐得到了重视。“横向一体化”模式强调充分利用企业的外部资源来快速响应市场需求。其基本思想是企业关注于提高自身的核心竞争力业务,而将非核心的业务委托或外包给合作伙伴企业。“横向一体化”导致形成了一条从供应商到制造商再到分销商、零售商的贯穿所有企业的“链”。供应链,作为企业间一种有效的组织形式,正是随着“横向一体化”管理模式的发展而逐渐形成的。自上世纪80年代,供应链的概念提出后,其受到了学术界和企业管理实践者的广泛关注。虽然经历了近四十多年的发展,然而对供应链的定义却一直缺乏一个统一的共识。表3.1列举了部分学者关于供应链的定义1。这些定义侧重的角度各有不同,但从中不难看出,供应链是一个涉及供应商、物流提供商、制造商、分销商和零售商等众多实体的网络。这些实体通过其上下游成员之间的相互联系,实现原材料的获取、将原材料转化成半成品和成品,并最终将产品销售给最终用户。表3. 1供应链定义Kolchak供应链是由供应商、物流服务提供商、制造商、分销商以Kolchak及零售商组成的实体集合,这些实体通过相互作用实现原材料、产品以及信息的流动。Christopher供应链是网络化组织,包含了为最终用户以产品或服务方式产生价值的不同过程和活动。Ellram供应链是由公司组成的网络,它通过公司间的相互作用实现将产品和服务交付给最终用户,并通过相互联系完成从原材料供应到最终产品送达活动。马士华等供应链是围绕核心企业,通过对信息流、物流、资金流的控制,从采购原材料开始,制成中间产品以及最终产品,最后由销售网络把产品送到消费者手中的由供应商、制造商、分销商、零售商直到最终用户构成的网链结构组织。供应链管理委员会供应链是为了生产和交付最终的产品而涉及的从供应商的供应商到客户的客户所有实体集合。Sarimvies等供应链是由供应商、制造商、分销商以及零售商组成的网络,它的功能是实现原材料获取、将原材料转换成半成品和成品,并将成品销售给用户。中华人民共和国国家标准物流术语供应链是生产及流通过程中,为了将产品或服务交付给最终用户,由上游和下游企业共同建立的网链状组织。Lambert等供应链集成了从初始的供应商到最终用户的商业过程,它通过提供产品、服务以及信息为用户增加价值。3.2 供应链建模研究分析与现状供应链系统是由众多自治的实体组成的,实体间存在复杂的相互关系。为了准确地刻画供应链,进而对其性能进行分析与预测,建立有效的供应链模型是十分必要的。供应链建模分析也一直是该领域学术界研究的难点和热点。本节主要从供应链模型分类和常用建模分析方法两方面对供应链建模分析研究现状进行简要的回顾。供应链研究主要涉及三个层次,即战略层、战术层和运作层。相应地,供应链建模也在这三个层次上展开。根据建模所涉及问题的层次,供应链模型可分为战略层模型、战术层模型和运作层模型三类。1、战略层模型关注于在供应链的长期规划中所涉及的决策问题。这类模型研究的范围包括选址、需求计划,分销渠道规划、新产品研发、外购、供应商的选择、信息技术的选择、价格和网络的重构等。2、战术层模型主要是针对资源分配决策。它涉及的问题包括库存控制,生产与分销协调、订单及货运的统一、原材料的处理、设备的选择和布局的设计等。3、运作层模型包括了那些影响企业短期经营行为的决策,它包括车辆的调度,员工的调度、记录的保存等。建立供应链模型是为了支持供应链管理中的各项分析和决策活动。当前常用的建模方法基本上可以分为网络设计方法、近似方法和基于仿真的方法三种。A）网络设计方法:一般使用整数规划(PI)或混合整数规划(MIP)来描述和求解问题模型;其不足之处在于:所建立的模型规模较大,当考虑范围扩展时,模型求解困难;另一方面对随机因素问题考虑不足。B）近似方法:其主要用于经营性决策,大都集中在多级库存问题的研究,其缺陷是:只注重供应链中的库存,对模型的约束条件太多;而忽视了相关的业务流程、随机因素的影响以及协调问题。C)仿真方法:可用于分析全面的供应链模型,同时考虑策略性和经营性因素,由于不存在数学求解上的间题,因此建立的仿真模型可以考虑各种复杂因素,包括结构上的和参数上的随机性,比较适于评价现有策略.根据建模方法的不同,Beamon将供应链模型分为如下四类2:1、确定模型:在这类模型中,所有变量都是已知或事前指定的。该类模型又可进一步细分为单目标和多目标模型。2、随机模型:供应链中存在着大量的随机因素,如客户需求,交付时间,生产波动等。随机模型考虑了这些不确定和随机因素。在该类模型中至少有一个变量是未知的,且假定遵循特定的概率分布。根据采用的方法不同,又分为基于最优化控制模型和动态规划模型。3、经济学模型:该类模型主要是利用经济学的方法对供应链进行建模和分析,其中最为常见的是采用博弈理论作为工具对供应链中成员间的关系进行建模。4、仿真模型:仿真模型是利用仿真技术对供应链进行建模。相对于分析模型,仿真模型能够更好的刻画供应链的动态特性。Min等人在总结前人研究的基础上,并结合信息技术在供应链中的应用,将供应链模型分为如下四类:确定模型(非概率模型),随机模型(概率模型),混合模型以及IT驱动模型。其中,混合模型是指该类模型中既包含确定元素也包含随机元素,例如一些仿真模型能同时处理确定和随机变量。IT驱动模型主要指利用信息技术,通过应用软件集成,提高供应链可视化程度的信息模型。这些IT 技术包括联合计划预测补偿 CPFR ( Collaborative Planning and Forecasting Replenishment),物流需求计划 MRP(Material Requirement Planning )和地理信息系统 GIS(Geographic Information Systems)等。Chan等人将供应链模型归纳为两类,即分析模型(数学模型)和仿真模型传统的分析模型主要处理参数确定的场景。虽然有些分析模型包含了一定的动态性,但由于实际中,系统的不确定因素很难预测,分析模型,如整数规划模型或混合整数规划模型,只能应用于涉及少量变量且基于有限假设的事先定义好的供应链场景。当涉及到更复杂的场景,如需求动态变化以及供应不确定等问题,分析模型难以取得良好的效果。随着计算技术的发展,仿真方法成为分析复杂问题的重要工具。由于仿真方法能够有效分析复杂问题,更好的模拟实际供应链的场景,仿真模型近年来受到持续的关注。与传统的分析模型不同,仿真模型从不同的视角来分析供应链的动态特性,如利用多代理系统MAS方法(Multi-Agent-System )来分析成员之间的协作问题应用复杂自适应系统理论CAS( Complex Adaptive System )解释供应链系统结构的动态演化等。3.3 现行系统存在问题随着供应链求解范围的扩大,模型求解也变得相当困难,而且其数学模型的约束条件过多也无法满足供应链管理的实际需要;此外,这些模型只能考虑确定和静态的问题模型,忽略了非平衡随机因素的影响;对供应链决策过程中的自治性、供应链组成成员之间相互作用的动态行为缺乏深入的研究。可归纳为:a)一般将整个供应链纳入一个模型,采用集中方式进行管理与决策,忽视了相关组成成员之间具有地理上的分散性、职权的自主性和充分的自治性,且合作与竞争、自主与联合并存。b)在研究供应链的管理决策中,过分强调伙伴关系的稳定性,大多采用串行、递阶的计划与控制模式,较难适应快速变化的市场环境。c)对供应链中的随机性考虑不足,例如未能充分考虑与全球性供应链效益密切相关的金融因素、包括汇率稳定性、利率差别等。d)供应链的数学模型,一般基于很多的限定性假设和简化,包括各节点无能力限制、结构参数定常、费用线性等,这些大大限制了结论的适用性。4. 复杂网络4.1 复杂网络概述4.1.1 网络的定义及表示方式自随机图理论提出至今，在复杂网络领域提出了许多概念和术语。网络（Network）在数学上以图（Graph）来表示，图的研究最早起源于18世纪瑞士著名数学家Euler的哥尼斯堡七桥问题。复杂网络可以用图论的语言和符号精确简洁地加以描述。图论不仅为数学家和物理学家提供了描述网络的语言和研究的平台，而且其结论和技巧已经被广泛地移植到复杂网络的研究中。为了能够方便准确地表达复杂网络的统计性质，有必要先介绍一些网络和图论的基本知识。网络（图）是指二元组，其中为节点集，为边集，中元素称为节点或顶点（Vertex或Node），中元素称为边（Edge或Link），且中的每条边有的一对节点与之对应，如果中任意的节点对和对应同一条边，则该网络称为无向网络，否则为有向网络；如果中所有边的长度均为1，即，则称网络为无权网络，否则为加权网络。中元素个数和中元素个数分别称为网络的阶（Order）和边数（Size）。阶和边数都有限的图为有限图（Finite Graph）。边所连接的节点称为端点（End-vertices），两端点相同的边称为环（Loop）。有公共起点并且有公共终点的两条边称为平行边（Parallel Edges）或重边（Multi-edge）。无环且无平行边的图称为简单图（Simple Graph）。任何不同的两节点之间都有边相连的简单无向图称为完全图（Complete Graph）。本文提到的图，若没有特别的说明，均指没有重边的无向简单图。4.1.2 复杂网络的特征度量随着对复杂网络研究的深入，人们提出了许多概念和度量方法，用于表示复杂网络的结构特性。度分布（Degree Distribution）。度分布是网络的一个重要统计特征。这里的度（Degree）也称为连通度（Connectivity），节点的度指的是与该节点连接的边数。度在不同的网络中所代表的含义也不同，在社会网络中，度可以表示个体的影响力和重要程度，度越大的个体，其影响力就越大，在整个组织中的作用也就越大，反之亦然。度分布则表示节点度的概率分布函数，它指的是节点有条边连接的概率。在目前的研究中，两种度分布较为常见：一是指数度分布，即随着的增大以指数形式衰减；另一种分布是幂律分布，即pki=k，其中称为度指数，不同的网络，其动力学性质也不同。另外，度分布还有其它形式，如星型网络的度分布是两点分布，规则网络的度分布为单点分布。簇系数（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相关系数就可以描述网络的度相关性，的定义为： （4.1）其中，分别表示连接第条边的两个顶点j，k的度，表示网络的总边数。的取值范围为，当时，网络是正相关的；当时，网络是负相关的；当时，网络是不相关的。簇度相关性（Clustering-degree Correlations）。如果用表示度为k的节点的平均簇系数，则与k之间的关系称为簇度相关性。实证研究表明，在许多现实网络中，与k之间存在如下的倒数关系：，人们把这种倒数关系的簇度相关性称为层次性，把具有层次性的网络称作层次网络。模块性（Modularity）。现实世界中的许多网络(如代谢网络)是由模块结构组成的。模块有两个显著特征：模块内部的节点间高度连接，有着直接的相互作用；模块与模块之间只有少数甚至没有连接，模块与模块或模块与非模块之间有着清晰的边界。在复杂网络研究领域，模块也称作社区（Community） 。如在电影演员合作网中，不同的模块代表不同的流派；在引文网络中，模块代表特定的研究领域；在万维网中，模块反映网络的主题分类。在社会学文献中往往采用聚类分析的方法来检测网络的社区结构。目前许多学者提出了寻找社区结构的新方法。2002年，Girvan和Newman给出了一种识别社区结构的新算法（GN算法），该算法的基本思想是每次选择一条介数最大的边，将其从网络中删除。不断地重复该过程，就可以凸现网络的社区结构。2004年，他们又定义了一个量，定量地衡量网络的模块化程度（模块性）。该模块性定义为： (4.2)其中，指连接社区i中的顶点的边数的比例，指两个端点都在社区i中的边的比例。值越大，网络的社区结构越明显。一般认为值在0.3与0.7之间的网络具有较强的社区结构。2004年，Newman利用贪婪算法通过最大化的值来寻找社区结构2，该算法的复杂度有了很好的改进，处理问题的规模比过去大大增加。王林和戴冠中对社区发现的方法进行了综述。用上述参数可以很方便地衡量现实网络的特性。根据Newman的观点，现实网络大致分为四种：社会网络，信息网络，技术网络和生物网络。这四种网络，虽然各自具有不同的物理形式，彼此描述的系统各异，其节点和边的定义差别也很大，但它们却具有一些相同的特征：网络节点间的作用很复杂，而且高度不规则；节点之间在度、簇系数、集中性等网络特征度量方面表现出不对称性，不同节点差异很大；尽管这些网络大而复杂，节点间的平均距离却很小，呈现出小世界特性。大量的实证研究表明：现实世界中的许多网络具有下面三个共同特性：节点度服从度指数介于的幂律分布；集聚程度高；节点间平均距离小。关于现实网络的统计性质，请参阅有关的文献，限于篇幅，此处不再赘述。现实网络除了上述三大特性之外，不同的网络还具有各自的其它性质，如社会网络往往是正相关的，而技术和生物网络往往是负相关的。另外，诸如代谢网、电影演员网、万维网、AS层的因特网等许多网络还呈现出层次性和模块性。综上，网络的统计特性多而复杂。本文将重点围绕度分布、簇系数和平均路径长度（或直径）等目前公认的网络基本特征，从演化模型着手，研究网络演化过程中的微观事件对网络拓扑结构的影响，发现网络演化的规律，最终达到更好地了解认识现实网络系统的目的。4.2 复杂网络的分类到目前为止，人们还没有给复杂网络下一个明确的定义，只是从不类角度对复杂网络大致进行了分类。根据节点度的分布情况，可以将复杂网络分为指数网络和无尺度网络两大类。指数网络中的节点是同质的，它们的度大致相同，绝大部节点的度都位于网络节点平均度附近，网络节点度分布随度数的增加呈指数衰减，使得网络中不存在度数特别大的节点，最经典的两种指数网络是Erds与Rnyi于1960年提出的Erds-Rnyi（ER）随机图模型和Watt与Strogatz在1998年提出的Watt-Strogatz小世界网络模型（WS模型）2。随机图与小世界网络的主要区别是：前者的簇系数小，而后者的簇系数大。目前，把具有较小平均路径长度和较大簇系数的网络统称为小世界网络，这一说法已得到学术界的公认。无尺度网络中的节点是异质的，其节点度服从幂律分布。最著名的无尺度网络模型是1999年Barabsi和Albert建立的Barabsi-Albert无尺度网络模型（BA模型或BA网络）。在无尺度网络中，大部分节点只与少数几个其它节点连接，但网络中存在为数不多的度数特别大的节点，称为集散节点（或hub节点），它对无尺度网络的特性起着主导和支配作用。从生成方式上可将复杂网络分成随机性网络和确定性网络。顾名思义，随机网络的生成是随机的，尽管生成规则相同，每次在电脑上模拟生成的网络却存在差异性；确定性网络的生成规则是确定的，其结构特性可以精确求解。从边的方向性上可将网络分为无向网络和有向网络，无向网络的边不存在方向性，有向网络的边却有方向。从边有无权值可将网络分为加权网络和0-1网络。4.3 复杂网络理论经典模型4.3.1 小世界网络模型实证研究表明，许多现实网络特别是社会网络都表现出集群现象，由此引发人们对小世界网络研究。最早的小世界网络模型是Watts和Strogatz在1998年提出网络模型（WS模型）3，该模型由一个具有个节点的环开始，环上每一个节点与两侧各有条边相连，然后对每条边以概率随机进行重连（自我连接和重边除外），这些重连的边叫“长程连接”，长程连接大大地减小了网络的平均路径长度，而对网络的簇系数影响较小。WS模型的建立和生成有其深刻的社会根源，因为在社会系统中，大多数人直接和邻居、同事相识，但个别人也有远方甚至国外的朋友。Watts和Strogatz开创性论文的发表掀起了小世界网络和WS模型的研究高潮。在WS模型提出不久，Newman和Watts对WS模型作了改进，提出了WS模型的一个变体模型，通过在随机选择的节点对之间增加边作为长程连接，而原始格上的边保持不动。这一模型比WS模型容易分析，因为它在形成过程中不会出现孤立的簇，但在WS模型中却可能发生这种情况。1999年，Kasturirangan提出了WS模型的一个替代模型，该模型同样始于环状格，然后，在格中间增加节点并与格上的节点随机进行连接，这些随机连接的边充当了WS模型中“长程连接”的角色。其实只要在网格中间增加一个新节点并连接到网格边缘足够多的节点上，网络就呈现出小世界特性，Dorogovtsev和Mendes对这一情况进行了精确的求解。为进一步研究小世界特性，在二维方格的基础上Kleinberg提出了WS网络的一般化模型，Kleinberg模型的平均路径长度是可调的。虽然许多现实网络都表现出小世界特性，但它们的形成机制不尽相同。为进一步研究小世界网络的产生机理，杨波、陈忠、段文奇提出了基于个体选择的小世界网络的结构演化；Ozik等提出了地理位置择优连接机制，说明小世界的形成是系统增长和局部作用的共同结果；刘强、方锦清等通过交叉边的方式探索了一种产生小世界特性的新方法。图4. 1规则网络、小世界网络、随机网络即其转化过程在现实生活中，人们通常认识他们的邻居和同事，但是也有可能有少量远在异国他乡的朋友。而 WWW 上的网页也绝不是像 ER 随机图那样完全随机地连接在一起的。 作为从完全规则网络向完全随机图的过渡，Watts 和 Strogtz 于 1998 年引入了一个有趣的小世界模型，称为 WS 小世界模型。WS 小世界模型的构造算法如下： 从随机图开始：考虑一个含有 N 个点的最近邻耦合网络，它们围城一个环，其中每个节点都与它左右相邻的各 K/2 节点相连，K 是偶数。 随机化重连：以概率 p 随机地重新连接网络中的每个边，即将边的一个端点保持不变，而另一个端点取为网络中随机选择的一个节点，其中规定，任意两个不同的节点之间至多只能有一条边，并且每一个节点都不能有边与自身相连。 在这个模型中，p=0 相应于完全规则网络，p=1 则对应于完全随机网络，通过调节 p 的值就可以控制从完全规则网络到完全随机网络的过渡。 WS 小世界模型构造算法中的随机化过程有可能破坏网络的连通性。另一个研究较多的小世界模型由 Newman 和 Watts 稍后提出的，称为 NW 小世界模型。该模型是通过“随机化加边”取代 WS 小世界模型构造的“随机化重连”而得到的。具体的构造算法如下： 从规则图开始：考虑一个含有 N 个点的最近邻耦合网络，它们围城一个环，其中每个节点都与它左右相邻的各 K/2 节点相连，K 是偶数。 随机化加边：以概率 p 在随机选取的一对节点之间加上一条边。其中，任意两个不同的节点之间至多只能有一条边，并且每一个节点都不能有边与自身相连。在 NW 小世界模型中，p=0 对应于原来的最近邻耦合网络，p=1 则对应于全局耦合网络。在理论分析上，NW 小世界模型要比 WS 小世界模型简单一些。当 p 足够小和 N 足够大时，NW 小世界模型本质上等同于 WS 小世界模型。 图4. 2（a)WS小世界模型（随机化重连）（b）NW小世界（随机化加边）4.3.2 随机图模型随机网络理论由匈牙利数学家Erds和Rnyi提出，他们提出的模型称为经典的Erds-Rnyi（ER）模型。ER模型的定义为：在由个顶点、条边构成的图中，随机连接条边形成一随机网络，记为，由这样的个节点、条边组成的网络共有种，构成一个概率空间，每一个网络出现的概率是相等的。另一种与ER模型等价的随机网络模型是二项式模型，其定义如下：给定的节点数目固定不变，假定任意节点对之间有条边连接的概率为，形成的网络记为4。这样，整个网络中边的数目是一个随机变量，其期望值为。设