复杂网络论文15篇.docx

1、复杂网络论文15篇复杂网络论文摘要：复杂网络是指具有无标度、小世界、吸引子、自相似、自组织中部分或者所有性质的网络。在现实世界中，许多复杂的系统基本上都能以网络来进行描述，而现实中的那些复杂的系统则可以以“复杂网络”来称之，比如社会网、交通网、电力网、万维网、因特网等等都可以称之为复杂网络。本文主要通过对复杂网络理论的介绍，从而对计算机Internet网进行分析，对Internet网这一复杂系统进行探究，揭示Internet拓扑现象关键词 复杂网络 网络论文 网络 基于复杂网络理论的计算机网络拓扑分析摘要：复杂网络是指具有无标度、小世界、吸引子、自相似、自组织中部分或者所有性质的网络。在现实世

2、界中，许多复杂的系统基本上都能以网络来进行描述，而现实中的那些复杂的系统则可以以“复杂网络”来称之，比如社会网、交通网、电力网、万维网、因特网等等都可以称之为复杂网络。本文主要通过对复杂网络理论的介绍，从而对计算机Internet网进行分析，对Internet网这一复杂系统进行探究，揭示Internet拓扑现象的特性、规律及动因。关键词：复杂网络；计算机网络；网络拓扑在现实世界中，许多复杂的系统基本上都能以网络来进行描述，而现实中的那些复杂的系统则可以以“复杂网络”来称之，比如社会网、交通网、电力网、万维网、因特网等等都可以称之为复杂网络。在这些复杂系统中，那些现实中的实体往往通过复杂网络的节

3、点来表示，实体跟节点相对应，节点之间的连线（即边）则对应于实体与实体之间的关系。而Internet网络自从诞生开始，其一直沿着更优、更高级、更复杂的路径演化和发展着，现在Internet网络已经成为一个开放的、无中心控制的、异构的、分布式的极其复杂的网络系统。其复杂性主要表现在：第一，Internet网络结构日益复杂。Internet网络的规模在不断的扩大，网络中的节点不断加入和退出，各个节点以及它们之间的链路时常发生失效，链路也经常出现方向和权重的变化。第二，网络中节点日益复杂化。各节点越来越具有复杂非线性行为的动力学系统。第三，复杂因素之间的彼此影响。各个节点之间或者数据包流和节点之间出现

4、了非线性的作用及其各个用户之间的竞争和合作等等都是彼此的影响因素。一、复杂网络理论简介复杂网络是指具有无标度、小世界、吸引子、自相似、自组织中部分或者所有性质的网络。复杂网络理论的主要内容有：网络的演化特征、演化规律、演化动力学机制、演化的统计规律以及网络的模型特质、形成机制、几何性质、结构稳定性等。在自然科学中，复杂网络研究的最为基本的内容包括：度、相关性、集聚程度、最短距离、介数以及它们的分布特征。复杂网络系统一般有着下面几个特征：（1）小世界。复杂网络通过简单的描述对许多复杂的现实网络进行了解释，认为不管规模多大的网络，其任意两个节点都是由一条路径连接的事实。它阐释无论什么世界都是通过相

5、互关系非常小的无数个节点所连接起来的。比如，在现实的社会网中，每个人的生活圈很小，人跟人认识的数目非常少，但是这个社会却是由无数个关系所组成的，通过一条关系，可以找到跟你相距很远的无关系的陌生人。就好像麦克卢汉所讲的，地球将越来越小，是一个小的地球村，即一个小世界。（2）集群性。复杂网络会越来越具有集群性。比如，在现实的社会网络中，每个人都有自己的朋友圈、熟人圈，在这个圈子里，每位成员都可能跟其他成员认识。集群性就是指网络具有一种内聚的倾向，即在一个大网络中，会分布着许多个彼此联系的积聚小网络。比如一个朋友圈往往会通过某种关系跟另一个朋友圈联系着。（3）幂律的度分布。度是指网络中的节点及其节点

6、关系的数量；度的相关性是指各个节点之间的联系紧密程度；介数是指网络中所有最短路径经过某一节点的数量，即有一节点A，在网络中，所有经过A的数量，它反映的是节点A的影响力。无标度网络的特征主要集中反映了集聚的集中性。总之，复杂网络的主要特征有：无标度性、小世界效应、节点度的幂律分布。二、Internet网络的拓扑分析（一）Internet拓扑的特点近些年来对于Internet拓扑的研究，最重要的成果是对于Internet拓扑节点度的幂律分布。这种分布在规模不同的网络拓扑中表现出一定的稳定性，也就是指，在规模不同的Internet拓扑中，它们的节点度表现出一种幂律分布，即：P（k）=k-其中，一般在

7、23这个小范围内进行波动，k是指节点度，P（k）表示度为k的节点出现的概率，即分布率。Interne作为一个复杂网络，从其通信网络的优化目的来说，其实现节点间平均距离最小化、网络边数最小化是其拓扑优化的主要目标。即未来通信网络的趋势就是小世界网络。可是Internet网络所覆盖的范围非常巨大，具有全球性，其拓扑结构的发展还面临着许多技术上的问题。所以，对于Internet网络拓扑结构的优化目标的实现有点不大可能。但是话又说回来，尽管Internet的发展并不能实现拓扑设计的整体优化，它的小世界、较少边、高聚集等特性足以表明其还是具有小范围优化的特点，这些特点的产生可表现出其一些规律，即Inte

8、rnet网络具有优先连接和生长的规律。生长表示的是Internet具有动态增长的特性，所以Internet的拓扑结构也是一个动态的过程。优先连接规律表示新节点进入Internet网络的规则，即在新节点加入网络时会选择拥有较大连接数的节点进行连接。（二）基于复杂网络理论的Internet网络拓扑模型的构建在世人发现Internet网络节点度具有幂律分布的规律之后，Internet网络拓扑模型的构建产生巨大的转变。大家更多的选择从优先连接和生长等这一网络拓扑规律入手进行Internet网络的拓扑建模，其主要是为了让符合现实Internet拓扑性质的模型通过一些简单规则的演化让其自动地产生出来。可利

9、用优先连接来对新节点加入网络的过程进行描述还比较粗糙，首先是因为新节点在加入之前，对网络全局的信息进行了解和把握具有很大的难度，其次一个原因是单一的优先连接不能够描述复杂的加入决策过程，而且在全网中容易形成少量的集散节点。所以要建立更加符合现实Internet拓扑特征的网络模型则需要考虑更完善的加入规则。现在对于构建Internet模型主要是依据自治域级和路由器级，但由于Internet网络拓扑特性在不同层次和不同规模中表现出某种本质上的相似性，所以，本拓扑模型的构建都适应于这两个级。此模型主要的规则是前面提到的通过生长和局部优先连接，来形成Internet拓扑模型，这种形成机制就好像一个层次

10、化比较强的选举过程，如下图所示：此模型首先假设在一个平面中分布着n个节点，并存在着一个离散的均匀走动的时钟，这些节点都清楚自己是何时进入网络的，这些节点进入网络的时刻分布是从零时刻开始至具体某一特定时刻内的随机分布。每个节点进入网络前后的动作就是接收和发送消息及依据所接收的消息产生响应。发送和接收的消息中包括了自己的优先度以及消息传达的范围等内容。并且这些节点优先度将对其消息传送的范围即辐射半径产生直接的影响。在节点接收消息之后往往是按照消息源的优先度来确定其是否跟发送消息的节点建立连接，若所接收到的许多消息源节点存在相近的优先度，其将会随机地选择一个消息源节点进行连接。通过这种规则进行不断的

11、演化和发展，将会得出上图的结果。其中a图表示Internet网络形成的初始阶段，那时仅仅只有一小部分节点进行活动，每个节点度都比较小，其发送和接收消息的范围还比较小，所以这些节点往往只跟自己相邻的节点进行连接。而随着时间的不断推进，节点度的不断增加，各个节点的消息所能到达的距离越来越远，即所形成的连接会越来越大、越来越多。在局部区域胜出的节点代表整个区域参与更大范围的竞争，以致形成更大区域的代表。这个过程将持续下去，直到网络中形成几个较大的聚集中心。如图（b）、（c）所示，这种自组织的层次网络并不具有预先设置的层次数。这就是Internet网络拓扑结构的形成模型，是一种消息自组织和传递接收的模

12、型。三、结束语综上所述，复杂网络理论最主要的特性是无标度性、小世界效应、节点度的幂律分布。Internet网络延续着这些性质，在其拓扑结构构建和形成中表现出来，具体所形成的拓扑规则是：Internet网络中节点的生长性和优先连接。通过其不断的生长以及生长出的节点的优先连接，从而促使网络拓扑是一种消息自组织和传递的过程。复杂网络论文:计算机网络行为的复杂性理论研究摘要：在信息时代的大背景下，计算机网络行为越来越复杂，传统的研究计算机网络行为的方法已难适应大规模的计算机网络。为更好地管理和控制复杂的计算机网络，提高网络服务的质量，将复杂性理论应用于计算机网络行为的研究，探索出一种复杂网络行为研究新

13、方法。分析计算机网络行为研究的传统方法之不足，阐明复杂性理论应用于计算机网络行为研究的有效性，并概述其发展现状，以及指明其广泛的应用前景。关键词：计算机网络；网络行为；复杂性理论一、引言当今的计算机网络异常复杂，运行时的动态变化规律成超分布、超并行、超复杂性质。计算机网络行为研究的对象正是这种动态变化规律，具体研究对象有：拓扑结构的动态变化、传输性能动态演化、网络安全、故障诊断、以及动态网络流量等。建立或优化出具有更高性能的计算机网络，在巨量用户的情况下，依然能保证高质量服务。故，研究计算机网络行为具有重要的意义。传统的计算机网络行为分析方法的基础理论大多为“还原论”思想，一定程度不适合当今复

14、杂计算机网络行为研究的发展需求。基于传统计算机网络行为研究方法的缺陷，将复杂性理论应用于计算机网络行为研究之中，为探索复杂网络行为研究方法提供新思路。复杂性理论是一种基于非线性、动态、复杂系统的理论，其是解决系统整体性的新方法。故在研究计算机网络宏观行为特性时，复杂性理论有其巨大优势。二、传统计算机网络行为研究传统的计算机网络行为分析方法的基础理论大多为“还原论”思想，一定程度不能较全面地当今复杂计算机网络行为研究的发展需求，其局限主要表现在以下几个方面：1.传统的计算机网络中的采样和测量理论已不适用于现在复杂背景下的计算机网络。2.复杂计算机网络中的宏观可靠性的研究甚少。3.复杂计算机网络中

15、的安全行和宏观安全监控理论缺乏。4.传统的阵列新能评估理论不能处理长程相关条件下的性能评估。5.复杂计算机网络拓扑图状态分析理论甚少。6.复杂计算机网络中时常发生异常大流量，对这种显现的研究和处理理论甚少，而传统的Poisson和Markov理论不能准确刻画，故，需要新的数学理论对其进行研究。7.研究复杂计算机网络中的流量实时测量和监控理论较少。然而，现今的计算机网络发展迅猛，已经深入人们生活的各个领域，故，探索新的方法，来研究复杂计算机网络行的方法，以提高网络服务质量，因此其具有重要的理论意义和实用价值。三、复杂性理论复杂性理论被誉为“二十一世纪的科学”，作为一种介于相对论和量子力学之间的新

16、科学研究工具。将复杂性理论应用于现今的复杂计算机网络行为研究之中，可从计算机网络系统的宏观上研究和分析其网络行为特性，该领域的研究能突破传统算法的一些局限，更好地建设出和优化现今的计算机网络结构，保证服务质量。复杂性理论主要包括：混沌学、分形学、自组织学、以及复杂网络学等，是一种新型的交叉科学：1.混沌是非线性系统中，貌似随机运动的复杂现象，各个科学领域，包括计算机网络中，存在大量的混沌现象，其主要特征包括有界性、遍历性、不可预测性、分为性、普适性等。2.分形所描述的一个粗糙或零碎的几何形状，可以分成多个部分，且每一部分都是体缩小尺寸的形状，即自相似性。由于其由非线性、非平衡过程所产生，故其具

17、有非周期、无规则的自相似特征。3.自组织是一种系统的自我调节的过程，为整个系统自我生存、寻求适应性、创造性的行为。各种内在因素相互影响，使复杂系统能够自动地变换成“自组织临界状态”，此时，系统的时空动力学行为不再具有特征时间和特征空间尺度，而是时空关联（满足幂定律分布），如果越过该临界状态，系统会产生复杂的相变现象。复杂计算机网络行为的复杂性是宏观的，包括行为复杂、功能复杂、结构复杂等各个方面。而复杂性理论的自组织性、临界性、自相似性、非线性等鲜明特征正好符合研究复杂计算机网络行为的各种特征。四、计算机网络行为的复杂性理论发展由于复杂性理论的特性适用于研究复杂计算机网络行为，故国内外很多学者对

18、将复杂性理论应用于网络行为研究感兴趣，并取得了一些成果。在计算机网络流量行为研究方面，WE Leland等人于1994年发现实际的计算机网络流量符合自相似特性，而并不符合传统的poisson分步布，这表明传统的poisson、马尔科夫流、自回归等分析手段不在适用，后来进过大量学者深入研究，建立了一系列流量模型，比如报酬模型、无限源Poisson模型、MMPP模型、On/Off模型等。在网络拓扑行为研究方面，研究成果表明实际的计算机网络并不是一个随机网络系统，而是一种具有小世界特征和无尺度特征的复杂网络，其节点度服从幂律分。欲研究计算机网络的拓扑行为，就必须先着手建立有效的网络拓扑模型，随着学者

19、深入研究，提出了比如WS模型、BA模型、局部演化模型等网络拓扑演化模型，及针对网络的鲁棒和脆弱性，提出的HOT模型等。在将混沌学引入到计算机网络行为研究中的方面，研究发现计算机网络中普遍存在一种貌似随机的现象，其具有混沌的各种特性。为引导这种混沌现象向好的方面发展，学者陈关荣等人在详细分析了计算机网络流量控制系统中的混沌现象之后，将将混沌控制方法引入到网络流量控制当中，另外，国内外一些学者探索试将混沌最大Lyapunov指数、以及相空间重构技术引入到计算机网络流量行为研究和分析领域，获得了一些成果。五、展望将复杂性理论引入计算机网络行为研究，虽然取得了丰硕的成果，但也存在一些尚待解决的问题。现

20、今的计算机网络越来越复杂、有其符合复杂性理论的特性，且复杂性理论的研究比较成熟。在计算机网络拓扑机构研究方面，网络拓扑演化行为具有动力学、非线性、自组织性等，而将复杂性理论的自组织学、混沌学、分形学、拓扑学等领域研究成果引入计算机网络拓扑研究尚不充分，且更具具体的实际计算机网络特点结合复杂性理论进行研究也尚待探索。同样，在计算机网络流量行为研究方面，针对网络流量的混沌、自相似等特性，结合混沌理论、分形理论等，全面阐述网络流量行为的特点动态变化形式，并对计算机网络流量进行有效建模，支持其特征参数，为给出有效的控制方法奠定基础、以及为计算机网络安全防范、稳定运行等方面提供理论前提。六、结论21世纪

21、的信息化将给人来带来巨大财富，计算机网络行为的研究具有重要的价值，而计算机网络行为研究中的复杂性理论研究将为其提供一种新方法。在此，针对实际计算机网络的复杂性特点，总结了传统网络行为分析方法的缺陷，并综述了计算机网络行为研究中的复杂性理论研究现状，指明其在管理和控制复杂计算机网络方和提高网络服务的质量方面取得的效果，总结了复杂性理论应用于计算机网络行为研究的有效性，并阐述该理论研究的重要意义，以及其广阔的发展前景和应用潜力。复杂网络论文:复杂网络研究摘要：从复杂网络的三个主要度量特征量：平均路径长度、聚集系数、度分布的角度分别介绍了复杂网络中最主要的三种网络模型,即随机网络模型、小世界网络模型

22、和无标度网络模型，并提出了进一步研究的一些方向。关键词：复杂网络；随机网络；小世界网络；无标度网络1 复杂网络研究概况近年来，国内外掀起了研究复杂网络的热潮。复杂网络之所以复杂，不仅在于网络规模的巨大，网络结构的复杂，而且网络在时间、空间上都具有动态复杂，网络行为也很复杂。现实世界中的许多系统都可以用复杂网络来描述，如社会网络中的科研合作网，信息网络中的万维网、科研引用网，技术网络中的因特网、电力网等。网络节点为系统元素，边为元素间的互相作用，例如，在社会网络中，节点表示个人、组织机构或国家，边表示他(它)们之间的社会联系。现实网络系统的复杂性主要体现在三个方面1：首先，网络的结构非常复杂，对

23、网络节点间的连接，至今仍没有很清晰的概念;其次，网络是不断演化的，网络节点不断地增加，节点之间的连接在不断地增长，而且连接之间存在着多样性;第三，网络的动力学具有复杂性，每个节点本身可以是非线性系统，具有分岔和混沌等非线性动力学行为而且在不停地变化。由于现实世界网络的规模大，节点间相互作用复杂，其拓扑结构基本上未知或未曾探索。两百多年来，人们对描述真实系统拓扑结构的研究经历了三个阶段。在最初的一百多年里，科学家们认为真实系统要素之间的关系可以用一些规则的结构表示，例如二维平面上的欧几里德格网;从20世纪50年代末到90年代末，无明确设计原则的大规模网络主要用简单而易于被多数人接受的随机网络来描

24、述，随机图的思想主宰复杂网络研究达四十年之久;直到最近几年，科学家们发现大量的真实网络既不是规则网络，也不是随机网络，而是具有与前两者皆不同的统计特性的网络，其中最有影响的是小世界网络和无标度网络。这两种网络的发现，掀起了复杂网络的研究热潮。2 复杂网络主要特征度量2.1 平均路径长度(Average Path Length ,APL)平均路径长度是网络中一个重要的特征度量，它指网络中所有节点对之间的平均最短距离。这里节点间的距离指的是从一节点到另一节点所要经历的边的最小数目，其中所有节点对之间的最大距离称为网络的直径。平均路径长度和直径衡量的是网络的传输性能与效率。对于无方向无权重网络，连接

25、点i和点j的连线的数目即称为路径长度。点i和点j之间的最短路径是连接这两点的最短的路长,其长度是点i和点j之间的距离dij。若图带权重，可以使用同样的定义，但是要考虑到权重。计算dij的平均值，称为平均路径长度：。这样的定义存在的问题是如果在网络中存在不连通的节点，则平均最短距离将发散。为此Latora和Marhciorlli2提出了一种称为全局效率的相关测量量：。2.2 聚集系数(簇系数Cluster Coefficient)集聚系数，它衡量的是网络的集团化程度，是网络的另一个重要参数。簇系数的概念有其深刻的社会根源。对社会网络而言，集团化形态是其一个重要特征，集团表示网络中的朋友圈或熟人圈

26、集团中的成员往往相互熟悉，为衡量这种群集现象，科学家们提出了聚集系数的概念。通常用到了两种聚集系数。Barrat和Wegiht3提出了对于无向无权重的网络的如下定义：C=3NA/N3 。 其中NA是网络中三角形的数目，N3是三个点连通的数目。因子3是考虑到每个三角形可以看作是三个不同的三连通点。一个三角形是每对点之间都是有连线的三点集，而三连通点则是每个点都是可以从另外的点到达的三点集，这样可以定义给定点i的聚集系数： 。其中N(i)是包含了点i的三角形的数目，N3(i)是点i做为中心点的三连通节点的数目。若ki是节点i的邻居的数目，则N3=ki(ki-1)；同样，N(i)是i点的邻居之间的

27、连线的数目，用li表示邻居之间的连线的数目，则方程可以写为：。2.3 度分布(Degree Distribution)度分布是网络的一个重要统计特征。这里的度也称为连通度，节点的度指的是与该节点连接的边数。度在不同的网络中所代表的含义也不同，在社会网络中，度可以表示个体的影响力和重要程度，度越大的个体，其影响力就越大，在整个组织中的作用也就越大，反之亦然。度分布则表示节点度的概率分布函数P(k)，它指的是节点有k条边连接的概率。在目前的研究中，两种度分布较为常见：一是指数度分布，即P(k)随着k的增大以指数形式衰减；另一种分布是幂律分布，即P(k)k-，其中称为度指数，不同的网络，其动力学性质

28、也不同。另外，度分布还有其它形式，如星型网络的度分布是两点分布，规则网络的度分布为单点分布。3 复杂网络模型3.1 随机网络模型20世纪50年代末期，匈牙利数学家Paul Erds和Alfred Rny首次将随机性引入网络的研究，提出了著名的随机网络模型，简称ER模型。他们指出可以用两种方法建立随机网络一种方法是给定N个节点，从(N(N-1)/2条可能的边中连接E条边，忽略重边情况;另一种方法是给定N个节点，每一对节点以概率p进行连接，所得到的图是一个随机图。随机网络的基本特性可以归纳如下:1) 随机网络的平均度为：2) 随机网络的聚集系数：由于网络中任何两个节点之间的连接都是等概率的，因此对

29、于某个节点i，其邻接点之间连接的概率也是p，所以随机网络的簇系数网络的平均最短距离随网络规模的增加呈对数增长。3) 随机网络的平均最短距离可以进行如下估计：考虑随机网络的平均度(k)，对于任意一个节点，其一阶邻接点的数目为(k)，二阶邻接点的数目为(k)2，依此类推，当l步后达到网络的总节点数目N，有N=N=(k)l，所以llandlnN/ln(k)可以看出，随机网络的平均最短距离随网络规模的增加呈对数增长。4) 随机网络的度分布：给定一个连接概率为p的随机图，对于任意节点i，其度ki遵循二项式分布:当网络规模N很大时，网络的度分布接近泊松分布，即 。由于随机网络中节点之间的连接是等概率的，因

30、此大多数节点的度都在均值(k)附近，网络中没有度特别大的节点.随机网络的特征是网络的簇系数较小，平均最短距离也较小。3.2 小世界网络模型1998年Watts和Strogatz4在ER模型基础上对比真实网络提出了小世界模型(WS), WS模型构造过程如下：1) 开始于规则图形。初始有数目固定的N个节点，每个节点有k个临近节点，构成一个规则的一维圆环。2) 随机化。以概率p对圆环中的每一条边重新连接。这个过程中要求不能自身连接和重复连接。例如图15所示，p=0对应于规则图，p=1对应于随机图；当前研究的热点是p在0到1之间的WS网络的性质。图1 中间为小世界模型(左图为规则图,右图为随机图)WS

31、网络的主要性质为：a) 平均路径。图1中被随机选择又重新连结后的线称为捷径，它对整个网络的平均路径有着很大影响。分析表明：当p=2/(NK)，即在保证系统中至少出现一条捷径的情况下，系统的平均路径开始下降。即使是相当少的捷径也能够显著地减小网络的平均路径长度。这是因为每出现一条捷径，它对整个系统的影响是非线性的，它不仅影响到被这条线直接连着的两点，也影响到了这两点的最近邻、次近邻，以及次次近邻等。b) WS网络的聚集系数。由初始固定的节点数可计算出P=0时规则网络的集群系数为C(0), C(0)取决于网络结构而与尺寸N无关，因此有相对较大的值。随着边按一定的概率P随机化，集群系数在C(0)的附

32、近变化。c) 度分布。WS模型是介于规则网络和随机网络之间的模型，P=0时规则网络的度分布是中心点位于K=k的函数，P=1时随机网络是Poisson分布，在K=k点达到极大值。P从0变化到1的过程中，原来函数形式的度分布逐渐拓宽最终形成 Poisson分布。3.3 无标度网络模型上世纪末，Albert 等在对互联网的研究中发现了无标度网络(scale-free network)，开辟了人们对于复杂网络系统认识的新天地。他们发现，互联网实际上是由少数高连接性的页面组织起来的，80%以上页面的连结数不到4 个。然而只占节点总数不到万分之一的极少数节点，却有1000个以上的连结。这种网页的连接分布遵

33、循所谓的“幂次定律”：任何一个节点拥有k 条连接的概率，与1/ k 成正比，这就是无标度网络。其后几年中，各行各业的研究者们在许多不同的领域中，都发现了无标度网络。从生态系统到人际关系，从食物链到代谢系统，处处可以看到无标度网络。无标度网络最显著特征是度分布属于幂分布。其表现出的特性是：大多数的节点只与一两个少数节点相连接，但有少数节点却被大量的连接。无标度模型一般用来分析网络的动态特性，揭示大型复杂网络的拓扑结构。基于“成长性”和“择优连接”这两种机制，Albert等在深入分析了ER 模型之后，于1999年提出了BA 模型6-7，从理论上解释了无标度网络的现象。它比较准确地把握了现实世界中网

34、络最基本的特点，较好地解释了无标度网络的形成机制。BA模型是第一个增长的网络模型，其算法如下：1) 增长：在初始时刻，假定系统中已有少量（m0个）节点，在以后的每一个时间间隔中，新增一个度为 的点(mm0)，并将这m条边连接到网络中已经存在的m个不同的节点上。2) 择优连接：当在网络中选择节点与新增节点连接时，假定被选择的节点v与新节点连接的概率?蒹(ki)和节点 的度成正比，即。经过t个时间间隔后，便会形成一个有N=m0+t个节点、 条边的网络。图2显示m=m0=2时的BA模型的演化过程。初始网络有两个节点，每次新增加的一个节点按优先连接机制与网络中已存在的两个节点相连。图2 BA模型的演化

35、过程a) 度分布。BA模型生成的网络的度分布是无标度的，因为网络中的每一个节点有k条边的概率p(k)2m2l-3，如图3所示。b) 平均路径长度。BA无标度网络的平均路径长度为，这表明该网络也具有小世界特性。c) 聚类系数。BA无标度网络的聚类系数和网络大小有关，近似成一种幂率分布。4 小结与展望综上所述，以前，用规则网络和随机网络理论来描述真实系统的拓扑结构，这只反映了众多系统的两种极端情况，不能很好地描述多数现实系统。近几年来，以小世界网络与无标度网络为核心的复杂网络领域的最新成果反映了大多数复杂系统的基本特性，使得对复杂系统建模的研究取得了实质性的突破。复杂网络的模型研究虽然己取得很大进

36、展，但仍然存在一些问题。例如，小世界效应新的产生机制有待进一步研究。以WS模型为代表的小世界网络模型很好地展示了小世界的特性，但现实系统中的小世界网络异常丰富，理论上，有多少种现实网络就有多少种生成机制。因此，研究小世界网络形成的新机制，揭示产生小世界特性的多样性和新途径，是十分有意义的。另外，演化网络拓扑的解析方法仍不完善。目前的多数网络模型是通过数值计算和近似的分析方法来建立的，即先以随机的方式生成网络，然后对度分布给出解析计算，而对其它主要参数仅给出模拟结果。由于模拟的结果带有很大的随机性，所以这种做对于网络拓扑特性方面的严格理解还发展得远远不够。总之，复杂网络的发展给了我们一种看待世界

37、研究世界的新方法，随着其研究工作的进一步开展，定能给我们带来新的惊喜。复杂网络论文:利用MEX文件实现复杂网络分形维数计算摘要:复杂网络是最近几年流行的新兴学科之一。通过复杂网络的研究可以发现人工网络和自然世界中共同存在的一些普遍特征。复杂网络的分形与自相似是复杂网络在演化成小网络时整体和部分、部分与部分之间呈现出来的某种相似性,通过对复杂网络进行分形维数的计算来达到探测网络的微观演化过程非常重要。本文对计算分形维数的盒子覆盖法进行了算法上的改进,同时在具体实现算法时采用了Matlab与C的接口程序C-MEX,有效地提高了运算速度!关键词:复杂网络;分形维数;C-MEX随着20世纪末Watts

38、Strogatz的小世界网络模型和Barabasi-Albert的无尺度网络模型的提出,复杂网络的研究取得快速的发展。经过十几年的蓬勃发展,复杂网络已成为最近几年流行的新兴学科之一,已不同程度的应用于工程技术、经济、医药、生物等领域。复杂网络是当前重要的一门交叉性学科,通过复杂网络的研究可以发现自然世界和人工网络中存在普遍的特征,如小世界、标度等,从而使人们重新认识自然世界。复杂网络是从网络的视角出发,描述和研究的是系统构件如何相互作用而导致系统的宏观特性与行为。分形与自相似是复杂网络中的一个重要特性,也是其研究的一个热点之一。复杂网络的分形与自相似是复杂网络在演化成小网络时,整个过程将始终

39、保持自己特征状态的相对稳定性,从而使它的整体和部分、部分与部分之间呈现某种相似性。在复杂网络中,定量地描述这种具有自相似的网络的参数就叫做复杂网络的分形维数。计算分形维数最常用方法之一是盒子覆盖法。本文对计算分形维数的盒子覆盖法进行了算法上的改进,同时在具体实现算法时采用了Matlab与C的接口程序C-MEX,有效的提高了计算速度!1 复杂网络分形维数探讨复杂网络的分形与自相似性研究是利用复杂网络中节点内部的互动性来探测网络的微观演化过程。一个复杂网络具有分形性是指在对该网络进行重整化的过程中,若覆盖整个网络中的点所需的大小为lB的盒子的最小数量为NB,NB会随着lB的增长呈有限指数的幂律增长

40、若设幂律指数为dB,则为dB为该网络的分形维数。具体满足关系模型如式(1):NBlB-dB (1)盒子覆盖法是计算复杂网络分形维数基本的方法,是应用合适的形式于盒子覆盖的方式求出一个复杂网络的分形维数dB。盒子覆盖法描述为:对于一个给定的网络G和盒大小lB,一个盒子是所有任意两个节点i和j之间的距离lij小于lB的节点集合。盒子的最小数(记为NB)要能完全覆盖整个网络。以lB=1为例,那么很明显NB就为网络节点数N。盒覆盖算法的最终目标就是找到一种行之有效的方式计算在给定盒子大小lB的情况下NB的最小值。盒子覆盖法也有很多方法可以实现,最常用也是最有效的是贪婪着色法,其他的也有如燃烧算法等。

41、本文采用了最常用的贪婪着色法并对其进行了稍微的改进。改进后的贪婪着色算法可以描述如下:1) 给网络中的所有节点分配一个唯一的从1到N的数,每个节点并没有着色2) 对于所有的值lB,分配一个颜色值0给所有1到其他所有节点,如Ci1=03) 将i设为2,重复下面的5个步骤直到i=N(1) 计算从i到j的所有节点的小于i的距离lij(2) 将lB设为1(3) 对于所有的lij=lB选择一种没有使用的颜色Cjlij,就可以得到对于i的给定的lB的颜色值CilB(4) 设lB=lB+1,直到lB=lBmax(5) i=i+1通过以上的算法只要在复杂网络中的所有节点游走一遍,就可以在给定盒子大小lB的情况

42、下计算出NB的最小值,接着就可以利用关系模型公式求出该网络的分形维数dB了。2 利用CMEX文件计算复杂网络分形维数根据以上的算法描述,我们用matlab具体实现了这个算法。但我们在具体实现的过程中,发现由于复杂网络中的数据量非常大,而且MATLAB又是一种解释性语言,在执行M文件时,需要对矩阵的每个元素循环处理,运算速度非常的缓慢,例如利用MATLAB实现上述算法时仅仅调用一个20万行的数据,就需要执行30几分钟。对于Matlab直接计算中存在的困难,我们考虑过从更换编程平台,但由于matlab一些优秀的特性,我们还是希望能用matlab软件来实现上述算法。这使我们把目光投向了CMEX混合编

43、程。MEX文件又称为外部程序调用接口,在进行大规模的数据处理,比如影响 MATLAB执行速度的循环体时,可以编写相应的C或C +子程序完成相同的功能,并编译成 MEX文件,再由MATLAB调用此MEX文件以提高运行速度。C-MEX是通过MATLAB的编译器转换为可执行文件,是按照MEX技术要求的格式编写相应的程序,通过编译连接,生成扩展名为.dll的动态链接库文件,可以在MATLAB环境下以函数的形式直接调用。一般来说,C-MEX 文件的执行速度是相同功能的M文件执行速率的2040倍。MEX文件主要由两部分组成,它们分工明确,分别用于完成不同的任务。第一部分称为计算功能子程,它包含了所有实际完

44、成计算功能的源代码,用来完成实际的计算工作。第二部分称为入口子程序,它是计算子例行程序同MATLAB环境之间的接口,其作用是在 MATLAB系统与被调用的外部子程序之间建立通信联系。其中入口子程序的名字为mexFunction,其构成形式为:void mexFunction(int nlhs,mxA rray 3 plhs,int nrhs,constmxA rray 3 p rhs)。其中:nlhsnrhs为整型,分别表示输出输入变量的个数;plhsp rhs为mxA rray型指针数组,分别表示输出输入变量的地址。MEX文件执行流程可用图1表示。针对于盒子覆盖法中的贪婪着色算法,我们也利用

45、MEX文件编程实现了此算法来对复杂网络分形维数进行计算。具体利用CMEX计算复杂网络分形维数的过程如下:(1) 我们先根据贪婪着色算法描述,用matlab的M文件实现(2) 找出M文件中循环次数较多的代码段(3) 将这些循环次数较多的代码段转化成相应的C-MEX程序,并编译成相应的.dll文件(4) 将M文件中循环次数较多的代码段用相应的.dll代替(5) 最后对修改后的程序编译执行最后我们在CPU为AMD Athlon(tm) 64 X2 Dual Core Processor 4000+,内存为1G的机器上,分别对利用M文件和C-MEX文件两种方式调用了三组数据量不同的数据,得出的实验结果如表1所示。从表1的结果,我们可以看到使用C-MEX混合编程后,实现复杂网络分形维数计算算法的执行时间得到了很大程度的提高。这也证明了我们所采用的方法是行之有效的。3 结论复杂网络作为一门重要的交叉性学科,通过复杂网络的研究