基于复杂网络理论的计算机网络拓扑分析

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

关键词：复杂网络；计算机网络；网络拓扑

在现实世界中，许多复杂的系统基本上都能以网络来进行描述，而现实中的那些复杂的系统则可以以“复杂网络”来称之，比如社会网、交通网、电力网、万维网、因特网等等都可以称之为复杂网络。在这些复杂系统中，那些现实中的实体往往通过复杂网络的节点来表示，实体跟节点相对应，节点之间的连线（即边）则对应于实体与实体之间的关系。而Internet网络自从诞生开始，其一直沿着更优、更高级、更复杂的路径演化和发展着，现在Internet网络已经成为一个开放的、无中心控制的、异构的、分布式的极其复杂的网络系统。其复杂性主要表现在：第一，Internet网络结构日益复杂。Internet网络的规模在不断的扩大，网络中的节点不断加入和退出，各个节点以及它们之间的链路时常发生失效，链路也经常出现方向和权重的变化。第二，网络中节点日益复杂化。各节点越来越具有复杂非线性行为的动力学系统。第三，复杂因素之间的彼此影响。各个节点之间或者数据包流和节点之间出现了非线性的作用及其各个用户之间的竞争和合作等等都是彼此的影响因素。

一、复杂网络理论简介

复杂网络是指具有无标度、小世界、吸引子、自相似、自组织中部分或者所有性质的网络。复杂网络理论的主要内容有：网络的演化特征、演化规律、演化动力学机制、演化的统计规律以及网络的模型特质、形成机制、几何性质、结构稳定性等。在自然科学中，复杂网络研究的最为基本的内容包括：度、相关性、集聚程度、最短距离、介数以及它们的分布特征。

复杂网络系统一般有着下面几个特征：

（1）小世界。复杂网络通过简单的描述对许多复杂的现实网络进行了解释，认为不管规模多大的网络，其任意两个节点都是由一条路径连接的事实。它阐释无论什么世界都是通过相互关系非常小的无数个节点所连接起来的。比如，在现实的社会网中，每个人的生活圈很小，人跟人认识的数目非常少，但是这个社会却是由无数个关系所组成的，通过一条关系，可以找到跟你相距很远的无关系的陌生人。就好像麦克卢汉所讲的，地球将越来越小，是一个小的地球村，即一个小世界。

（2）集群性。复杂网络会越来越具有集群性。比如，在现实的社会网络中，每个人都有自己的朋友圈、熟人圈，在这个圈子里，每位成员都可能跟其他成员认识。集群性就是指网络具有一种内聚的倾向，即在一个大网络中，会分布着许多个彼此联系的积聚小网络。比如一个朋友圈往往会通过某种关系跟另一个朋友圈联系着。

（3）幂律的度分布。度是指网络中的节点及其节点关系的数量；度的相关性是指各个节点之间的联系紧密程度；介数是指网络中所有最短路径经过某一节点的数量，即有一节点A，在网络中，所有经过A的数量，它反映的是节点A的影响力。无标度网络的特征主要集中反映了集聚的集中性。总之，复杂网络的主要特征有：无标度性、小世界效应、节点度的幂律分布。

二、Internet网络的拓扑分析

（一）Internet拓扑的特点

近些年来对于Internet拓扑的研究，最重要的成果是对于Internet拓扑节点度的幂律分布。这种分布在规模不同的网络拓扑中表现出一定的稳定性，也就是指，在规模不同的Internet拓扑中，它们的节点度表现出一种幂律分布，即：

P（k）=k-β

其中，β一般在2―3这个小范围内进行波动，k是指节点度，P（k）表示度为k的节点出现的概率，即分布率。

Interne作为一个复杂网络，从其通信网络的优化目的来说，其实现节点间平均距离最小化、网络边数最小化是其拓扑优化的主要目标。即未来通信网络的趋势就是小世界网络。可是Internet网络所覆盖的范围非常巨大，具有全球性，其拓扑结构的发展还面临着许多技术上的问题。所以，对于Internet网络拓扑结构的优化目标的实现有点不大可能。但是话又说回来，尽管Internet的发展并不能实现拓扑设计的整体优化，它的小世界、较少边、高聚集等特性足以表明其还是具有小范围优化的特点，这些特点的产生可表现出其一些规律，即Internet网络具有优先连接和生长的规律。生长表示的是Internet具有动态增长的特性，所以Internet的拓扑结构也是一个动态的过程。优先连接规律表示新节点进入Internet网络的规则，即在新节点加入网络时会选择拥有较大连接数的节点进行连接。

（二）基于复杂网络理论的Internet网络拓扑模型的构建

在世人发现Internet网络节点度具有幂律分布的规律之后，Internet网络拓扑模型的构建产生巨大的转变。大家更多的选择从优先连接和生长等这一网络拓扑规律入手进行Internet网络的拓扑建模，其主要是为了让符合现实Internet拓扑性质的模型通过一些简单规则的演化让其自动地产生出来。可利用优先连接来对新节点加入网络的过程进行描述还比较粗糙，首先是因为新节点在加入之前，对网络全局的信息进行了解和把握具有很大的难度，其次一个原因是单一的优先连接不能够描述复杂的加入决策过程，而且在全网中容易形成少量的集散节点。所以要建立更加符合现实Internet拓扑特征的网络模型则需要考虑更完善的加入规则。

现在对于构建Internet模型主要是依据自治域级和路由器级，但由于Internet网络拓扑特性在不同层次和不同规模中表现出某种本质上的相似性，所以，本拓扑模型的构建都适应于这两个级。此模型主要的规则是前面提到的通过生长和局部优先连接，来形成Internet拓扑模型，这种形成机制就好像一个层次化比较强的选举过程，如下图所示：

此模型首先假设在一个平面中分布着n个节点，并存在着一个离散的均匀走动的时钟，这些节点都清楚自己是何时进入网络的，这些节点进入网络的时刻分布是从零时刻开始至具体某一特定时刻内的随机分布。每个节点进入网络前后的动作就是接收和发送消息及依据所接收的消息产生响应。发送和接收的消息中包括了自己的优先度以及消息传达的范围等内容。并且这些节点优先度将对其消息传送的范围即辐射半径产生直接的影响。在节点接收消息之后往往是按照消息源的优先度来确定其是否跟发送消息的节点建立连接，若所接收到的许多消息源节点存在相近的优先度，其将会随机地选择一个消息源节点进行连接。通过这种规则进行不断的演化和发展，将会得出上图的结果。其中a图表示Internet网络形成的初始阶段，那时仅仅只有一小部分节点进行活动，每个节点度都比较小，其发送和接收消息的范围还比较小，所以这些节点往往只跟自己相邻的节点进行连接。而随着时间的不断推进，节点度的不断增加，各个节点的消息所能到达的距离越来越远，即所形成的连接会越来越大、越来越多。在局部区域胜出的节点代表整个区域参与更大范围的竞争，以致形成更大区域的代表。这个过程将持续下去，直到网络中形成几个较大的聚集中心。如图（b）、（c）所示，这种自组织的层次网络并不具有预先设置的层次数。这就是Internet网络拓扑结构的形成模型，是一种消息自组织和传递接收的模型。

三、结束语

综上所述，复杂网络理论最主要的特性是无标度性、小世界效应、节点度的幂律分布。Internet网络延续着这些性质，在其拓扑结构构建和形成中表现出来，具体所形成的拓扑规则是：Internet网络中节点的生长性和优先连接。通过其不断的生长以及生长出的节点的优先连接，从而促使网络拓扑是一种消息自组织和传递的过程。

复杂网络论文:计算机网络行为的复杂性理论研究

摘要：在信息时代的大背景下，计算机网络行为越来越复杂，传统的研究计算机网络行为的方法已难适应大规模的计算机网络。为更好地管理和控制复杂的计算机网络，提高网络服务的质量，将复杂性理论应用于计算机网络行为的研究，探索出一种复杂网络行为研究新方法。分析计算机网络行为研究的传统方法之不足，阐明复杂性理论应用于计算机网络行为研究的有效性，并概述其发展现状，以及指明其广泛的应用前景。

关键词：计算机网络；网络行为；复杂性理论

一、引言

当今的计算机网络异常复杂，运行时的动态变化规律成超分布、超并行、超复杂性质。计算机网络行为研究的对象正是这种动态变化规律，具体研究对象有：拓扑结构的动态变化、传输性能动态演化、网络安全、故障诊断、以及动态网络流量等。建立或优化出具有更高性能的计算机网络，在巨量用户的情况下，依然能保证高质量服务。故，研究计算机网络行为具有重要的意义。

传统的计算机网络行为分析方法的基础理论大多为“还原论”思想，一定程度不适合当今复杂计算机网络行为研究的发展需求。基于传统计算机网络行为研究方法的缺陷，将复杂性理论应用于计算机网络行为研究之中，为探索复杂网络行为研究方法提供新思路。复杂性理论是一种基于非线性、动态、复杂系统的理论，其是解决系统整体性的新方法。故在研究计算机网络宏观行为特性时，复杂性理论有其巨大优势。

二、传统计算机网络行为研究

传统的计算机网络行为分析方法的基础理论大多为“还原论”思想，一定程度不能较全面地当今复杂计算机网络行为研究的发展需求，其局限主要表现在以下几个方面：

1.传统的计算机网络中的采样和测量理论已不适用于现在复杂背景下的计算机网络。

2.复杂计算机网络中的宏观可靠性的研究甚少。

3.复杂计算机网络中的安全行和宏观安全监控理论缺乏。

4.传统的阵列新能评估理论不能处理长程相关条件下的性能评估。

5.复杂计算机网络拓扑图状态分析理论甚少。

6.复杂计算机网络中时常发生异常大流量，对这种显现的研究和处理理论甚少，而传统的Poisson和Markov理论不能准确刻画，故，需要新的数学理论对其进行研究。

7.研究复杂计算机网络中的流量实时测量和监控理论较少。

然而，现今的计算机网络发展迅猛，已经深入人们生活的各个领域，故，探索新的方法，来研究复杂计算机网络行的方法，以提高网络服务质量，因此其具有重要的理论意义和实用价值。

三、复杂性理论

复杂性理论被誉为“二十一世纪的科学”，作为一种介于相对论和量子力学之间的新科学研究工具。

将复杂性理论应用于现今的复杂计算机网络行为研究之中，可从计算机网络系统的宏观上研究和分析其网络行为特性，该领域的研究能突破传统算法的一些局限，更好地建设出和优化现今的计算机网络结构，保证服务质量。

复杂性理论主要包括：混沌学、分形学、自组织学、以及复杂网络学等，是一种新型的交叉科学：

1.混沌是非线性系统中，貌似随机运动的复杂现象，各个科学领域，包括计算机网络中，存在大量的混沌现象，其主要特征包括有界性、遍历性、不可预测性、分为性、普适性等。

2.分形所描述的一个粗糙或零碎的几何形状，可以分成多个部分，且每一部分都是体缩小尺寸的形状，即自相似性。由于其由非线性、非平衡过程所产生，故其具有非周期、无规则的自相似特征。

3.自组织是一种系统的自我调节的过程，为整个系统自我生存、寻求适应性、创造性的行为。各种内在因素相互影响，使复杂系统能够自动地变换成“自组织临界状态”，此时，系统的时空动力学行为不再具有特征时间和特征空间尺度，而是时空关联（满足幂定律分布），如果越过该临界状态，系统会产生复杂的相变现象。

复杂计算机网络行为的复杂性是宏观的，包括行为复杂、功能复杂、结构复杂等各个方面。而复杂性理论的自组织性、临界性、自相似性、非线性等鲜明特征正好符合研究复杂计算机网络行为的各种特征。

四、计算机网络行为的复杂性理论发展

由于复杂性理论的特性适用于研究复杂计算机网络行为，故国内外很多学者对将复杂性理论应用于网络行为研究感兴趣，并取得了一些成果。

在计算机网络流量行为研究方面，WE Leland等人于1994年发现实际的计算机网络流量符合自相似特性，而并不符合传统的poisson分步布，这表明传统的poisson、马尔科夫流、自回归等分析手段不在适用，后来进过大量学者深入研究，建立了一系列流量模型，比如报酬模型、无限源Poisson模型、MMPP模型、On/Off模型等。

在网络拓扑行为研究方面，研究成果表明实际的计算机网络并不是一个随机网络系统，而是一种具有小世界特征和无尺度特征的复杂网络，其节点度服从幂律分。欲研究计算机网络的拓扑行为，就必须先着手建立有效的网络拓扑模型，随着学者深入研究，提出了比如WS模型、BA模型、局部演化模型等网络拓扑演化模型，及针对网络的鲁棒和脆弱性，提出的HOT模型等。

在将混沌学引入到计算机网络行为研究中的方面，研究发现计算机网络中普遍存在一种貌似随机的现象，其具有混沌的各种特性。为引导这种混沌现象向好的方面发展，学者陈关荣等人在详细分析了计算机网络流量控制系统中的混沌现象之后，将将混沌控制方法引入到网络流量控制当中，另外，国内外一些学者探索试将混沌最大Lyapunov指数、以及相空间重构技术引入到计算机网络流量行为研究和分析领域，获得了一些成果。

五、展望

将复杂性理论引入计算机网络行为研究，虽然取得了丰硕的成果，但也存在一些尚待解决的问题。现今的计算机网络越来越复杂、有其符合复杂性理论的特性，且复杂性理论的研究比较成熟。

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

六、结论

21世纪的信息化将给人来带来巨大财富，计算机网络行为的研究具有重要的价值，而计算机网络行为研究中的复杂性理论研究将为其提供一种新方法。在此，针对实际计算机网络的复杂性特点，总结了传统网络行为分析方法的缺陷，并综述了计算机网络行为研究中的复杂性理论研究现状，指明其在管理和控制复杂计算机网络方和提高网络服务的质量方面取得的效果，总结了复杂性理论应用于计算机网络行为研究的有效性，并阐述该理论研究的重要意义，以及其广阔的发展前景和应用潜力。

复杂网络论文:复杂网络研究

摘要：从复杂网络的三个主要度量特征量：平均路径长度、聚集系数、度分布的角度分别介绍了复杂网络中最主要的三种网络模型,即随机网络模型、小世界网络模型和无标度网络模型，并提出了进一步研究的一些方向。

关键词：复杂网络；随机网络；小世界网络；无标度网络

1 复杂网络研究概况

近年来，国内外掀起了研究复杂网络的热潮。复杂网络之所以复杂，不仅在于网络规模的巨大，网络结构的复杂，而且网络在时间、空间上都具有动态复杂，网络行为也很复杂。

现实世界中的许多系统都可以用复杂网络来描述，如社会网络中的科研合作网，信息网络中的万维网、科研引用网，技术网络中的因特网、电力网等。网络节点为系统元素，边为元素间的互相作用，例如，在社会网络中，节点表示个人、组织机构或国家，边表示他(它)们之间的社会联系。现实网络系统的复杂性主要体现在三个方面[1]：首先，网络的结构非常复杂，对网络节点间的连接，至今仍没有很清晰的概念;其次，网络是不断演化的，网络节点不断地增加，节点之间的连接在不断地增长，而且连接之间存在着多样性;第三，网络的动力学具有复杂性，每个节点本身可以是非线性系统，具有分岔和混沌等非线性动力学行为而且在不停地变化。

由于现实世界网络的规模大，节点间相互作用复杂，其拓扑结构基本上未知或未曾探索。两百多年来，人们对描述真实系统拓扑结构的研究经历了三个阶段。在最初的一百多年里，科学家们认为真实系统要素之间的关系可以用一些规则的结构表示，例如二维平面上的欧几里德格网;从20世纪50年代末到90年代末，无明确设计原则的大规模网络主要用简单而易于被多数人接受的随机网络来描述，随机图的思想主宰复杂网络研究达四十年之久;直到最近几年，科学家们发现大量的真实网络既不是规则网络，也不是随机网络，而是具有与前两者皆不同的统计特性的网络，其中最有影响的是小世界网络和无标度网络。这两种网络的发现，掀起了复杂网络的研究热潮。

2 复杂网络主要特征度量

2.1 平均路径长度(Average Path Length ,APL)

平均路径长度是网络中一个重要的特征度量，它指网络中所有节点对之间的平均最短距离。这里节点间的距离指的是从一节点到另一节点所要经历的边的最小数目，其中所有节点对之间的最大距离称为网络的直径。平均路径长度和直径衡量的是网络的传输性能与效率。

对于无方向无权重网络，连接点i和点j的连线的数目即称为路径长度。点i和点j之间的最短路径是连接这两点的最短的路长,其长度是点i和点j之间的距离dij。若图带权重，可以使用同样的定义，但是要考虑到权重。计算dij的平均值，称为平均路径长度：。这样的定义存在的问题是如果在网络中存在不连通的节点，则平均最短距离将发散。为此Latora和Marhciorlli[2]提出了一种称为全局效率的相关测量量：。

2.2 聚集系数(簇系数Cluster Coefficient)

集聚系数，它衡量的是网络的集团化程度，是网络的另一个重要参数。簇系数的概念有其深刻的社会根源。对社会网络而言，集团化形态是其一个重要特征，集团表示网络中的朋友圈或熟人圈，集团中的成员往往相互熟悉，为衡量这种群集现象，科学家们提出了聚集系数的概念。

通常用到了两种聚集系数。Barrat和Wegiht[3]提出了对于无向无权重的网络的如下定义：C=3NA/N3 。 其中NA是网络中三角形的数目，N3是三个点连通的数目。因子3是考虑到每个三角形可以看作是三个不同的三连通点。一个三角形是每对点之间都是有连线的三点集，而三连通点则是每个点都是可以从另外的点到达的三点集，这样可以定义给定点i的聚集系数： 。其中NΔ(i)是包含了点i的三角形的数目，N3(i)是点i做为中心点的三连通节点的数目。若ki是节点i的邻居的数目，则N3=ki(ki-1)；同样，NΔ(i)是i点的邻居之间的连线的数目，用li表示邻居之间的连线的数目，则方程可以写为：。

2.3 度分布(Degree Distribution)

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

3 复杂网络模型

3.1 随机网络模型

20世纪50年代末期，匈牙利数学家Paul Erds和Alfred Rény首次将随机性引入网络的研究，提出了著名的随机网络模型，简称ER模型。他们指出可以用两种方法建立随机网络一种方法是给定N个节点，从(N(N-1))/2条可能的边中连接E条边，忽略重边情况;另一种方法是给定N个节点，每一对节点以概率p进行连接，所得到的图是一个随机图。

随机网络的基本特性可以归纳如下:

1) 随机网络的平均度为：

2) 随机网络的聚集系数：由于网络中任何两个节点之间的连接都是等概率的，因此对于某个节点i，其邻接点之间连接的概率也是p，所以随机网络的簇系数

网络的平均最短距离随网络规模的增加呈对数增长。

3) 随机网络的平均最短距离可以进行如下估计：考虑随机网络的平均度(k)，对于任意一个节点，其一阶邻接点的数目为(k)，二阶邻接点的数目为(k)2，依此类推，当l步后达到网络的总节点数目N，有N=N=(k)l，所以lland~lnN/ln((k))可以看出，随机网络的平均最短距离随网络规模的增加呈对数增长。

4) 随机网络的度分布：给定一个连接概率为p的随机图，对于任意节点i，其度ki遵循二项式分布:当网络规模N很大时，网络的度分布接近泊松分布，即 。由于随机网络中节点之间的连接是等概率的，因此大多数节点的度都在均值(k)附近，网络中没有度特别大的节点.随机网络的特征是网络的簇系数较小，平均最短距离也较小。

3.2 小世界网络模型

1998年Watts和Strogatz[4]在ER模型基础上对比真实网络提出了小世界模型(WS), WS模型构造过程如下：

1) 开始于规则图形。初始有数目固定的N个节点，每个节点有k个临近节点，构成一个规则的一维圆环。

2) 随机化。以概率p对圆环中的每一条边重新连接。这个过程中要求不能自身连接和重复连接。例如图1[5]所示，p=0对应于规则图，p=1对应于随机图；当前研究的热点是p在0到1之间的WS网络的性质。

图1 中间为小世界模型(左图为规则图,右图为随机图)

WS网络的主要性质为：

a) 平均路径。图1中被随机选择又重新连结后的线称为捷径，它对整个网络的平均路径有着很大影响。分析表明：当p>=2/(NK)，即在保证系统中至少出现一条捷径的情况下，系统的平均路径开始下降。即使是相当少的捷径也能够显著地减小网络的平均路径长度。这是因为每出现一条捷径，它对整个系统的影响是非线性的，它不仅影响到被这条线直接连着的两点，也影响到了这两点的最近邻、次近邻，以及次次近邻等。

b) WS网络的聚集系数。由初始固定的节点数可计算出P=0时规则网络的集群系数为C(0), C(0)取决于网络结构而与尺寸N无关，因此有相对较大的值。随着边按一定的概率P随机化，集群系数在C(0)的附近变化。

c) 度分布。WS模型是介于规则网络和随机网络之间的模型，P=0时规则网络的度分布是中心点位于K=k的δ函数，P=1时随机网络是Poisson分布，在K=k点达到极大值。P从0变化到1的过程中，原来δ函数形式的度分布逐渐拓宽最终形成 Poisson分布。

3.3 无标度网络模型

上世纪末，Albert 等在对互联网的研究中发现了无标度网络(scale-free network)，开辟了人们对于复杂网络系统认识的新天地。他们发现，互联网实际上是由少数高连接性的页面组织起来的，80%以上页面的连结数不到4 个。然而只占节点总数不到万分之一的极少数节点，却有1000个以上的连结。这种网页的连接分布遵循所谓的“幂次定律”：任何一个节点拥有k 条连接的概率，与1/ k 成正比，这就是无标度网络。其后几年中，各行各业的研究者们在许多不同的领域中，都发现了无标度网络。从生态系统到人际关系，从食物链到代谢系统，处处可以看到无标度网络。

无标度网络最显著特征是度分布属于幂分布。其表现出的特性是：大多数的节点只与一两个少数节点相连接，但有少数节点却被大量的连接。无标度模型一般用来分析网络的动态特性，揭示大型复杂网络的拓扑结构。

基于“成长性”和“择优连接”这两种机制，Albert等在深入分析了ER 模型之后，于1999年提出了BA 模型[6-7]，从理论上解释了无标度网络的现象。它比较准确地把握了现实世界中网络最基本的特点，较好地解释了无标度网络的形成机制。

BA模型是第一个增长的网络模型，其算法如下：

1) 增长：在初始时刻，假定系统中已有少量（m0个）节点，在以后的每一个时间间隔中，新增一个度为 的点(m≤m0)，并将这m条边连接到网络中已经存在的m个不同的节点上。

2) 择优连接：当在网络中选择节点与新增节点连接时，假定被选择的节点v与新节点连接的概率?蒹(ki)和节点 的度成正比，即。经过t个时间间隔后，便会形成一个有N=m0+t个节点、 条边的网络。图2显示m=m0=2时的BA模型的演化过程。初始网络有两个节点，每次新增加的一个节点按优先连接机制与网络中已存在的两个节点相连。

图2 BA模型的演化过程

a) 度分布。BA模型生成的网络的度分布是无标度的，因为网络中的每一个节点有k条边的概率p(k)~2m2l-3，如图3所示。

b) 平均路径长度。BA无标度网络的平均路径长度为，这表明该网络也具有小世界特性。

c) 聚类系数。BA无标度网络的聚类系数和网络大小有关，近似成一种幂率分布。

4 小结与展望

综上所述，以前，用规则网络和随机网络理论来描述真实系统的拓扑结构，这只反映了众多系统的两种极端情况，不能很好地描述多数现实系统。近几年来，以小世界网络与无标度网络为核心的复杂网络领域的最新成果反映了大多数复杂系统的基本特性，使得对复杂系统建模的研究取得了实质性的突破。复杂网络的模型研究虽然己取得很大进展，但仍然存在一些问题。

例如，小世界效应新的产生机制有待进一步研究。以WS模型为代表的小世界网络模型很好地展示了小世界的特性，但现实系统中的小世界网络异常丰富，理论上，有多少种现实网络就有多少种生成机制。因此，研究小世界网络形成的新机制，揭示产生小世界特性的多样性和新途径，是十分有意义的。

另外，演化网络拓扑的解析方法仍不完善。目前的多数网络模型是通过数值计算和近似的分析方法来建立的，即先以随机的方式生成网络，然后对度分布给出解析计算，而对其它主要参数仅给出模拟结果。由于模拟的结果带有很大的随机性，所以这种做对于网络拓扑特性方面的严格理解还发展得远远不够。

总之，复杂网络的发展给了我们一种看待世界研究世界的新方法，随着其研究工作的进一步开展，定能给我们带来新的惊喜。

复杂网络论文:利用MEX文件实现复杂网络分形维数计算

摘要:复杂网络是最近几年流行的新兴学科之一。通过复杂网络的研究可以发现人工网络和自然世界中共同存在的一些普遍特征。复杂网络的分形与自相似是复杂网络在演化成小网络时整体和部分、部分与部分之间呈现出来的某种相似性,通过对复杂网络进行分形维数的计算来达到探测网络的微观演化过程非常重要。本文对计算分形维数的盒子覆盖法进行了算法上的改进,同时在具体实现算法时采用了Matlab与C的接口程序C-MEX,有效地提高了运算速度!

关键词:复杂网络;分形维数;C-MEX

随着20世纪末Watts-Strogatz的小世界网络模型和Barabasi-Albert的无尺度网络模型的提出,复杂网络的研究取得快速的发展。经过十几年的蓬勃发展,复杂网络已成为最近几年流行的新兴学科之一,已不同程度的应用于工程技术、经济、医药、生物等领域。

复杂网络是当前重要的一门交叉性学科,通过复杂网络的研究可以发现自然世界和人工网络中存在普遍的特征,如小世界、标度等,从而使人们重新认识自然世界。复杂网络是从网络的视角出发,描述和研究的是系统构件如何相互作用而导致系统的宏观特性与行为。分形与自相似是复杂网络中的一个重要特性,也是其研究的一个热点之一。复杂网络的分形与自相似是复杂网络在演化成小网络时,整个过程将始终保持自己特征状态的相对稳定性,从而使它的整体和部分、部分与部分之间呈现某种相似性。在复杂网络中,定量地描述这种具有自相似的网络的参数就叫做复杂网络的分形维数。计算分形维数最常用方法之一是盒子覆盖法。本文对计算分形维数的盒子覆盖法进行了算法上的改进,同时在具体实现算法时采用了Matlab与C的接口程序C-MEX,有效的提高了计算速度!

1 复杂网络分形维数探讨

复杂网络的分形与自相似性研究是利用复杂网络中节点内部的互动性来探测网络的微观演化过程。一个复杂网络具有分形性是指在对该网络进行重整化的过程中,若覆盖整个网络中的点所需的大小为lB的盒子的最小数量为NB,NB会随着lB的增长呈有限指数的幂律增长,若设幂律指数为dB,则为dB为该网络的分形维数。具体满足关系模型如式(1):

NB≈lB-dB (1)

盒子覆盖法是计算复杂网络分形维数基本的方法,是应用合适的形式于盒子覆盖的方式求出一个复杂网络的分形维数dB。盒子覆盖法描述为:对于一个给定的网络G和盒大小lB,一个盒子是所有任意两个节点i和j之间的距离lij小于lB的节点集合。盒子的最小数(记为NB)要能完全覆盖整个网络。以lB=1为例,那么很明显NB就为网络节点数N。

盒覆盖算法的最终目标就是找到一种行之有效的方式计算在给定盒子大小lB的情况下NB的最小值。

盒子覆盖法也有很多方法可以实现,最常用也是最有效的是贪婪着色法,其他的也有如燃烧算法等。本文采用了最常用的贪婪着色法并对其进行了稍微的改进。改进后的贪婪着色算法可以描述如下:

1) 给网络中的所有节点分配一个唯一的从1到N的数,每个节点并没有着色

2) 对于所有的值lB,分配一个颜色值0给所有1到其他所有节点,如Ci1=0

3) 将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的情况下计算出NB的最小值,接着就可以利用关系模型公式求出该网络的分形维数dB了。

2 利用CMEX文件计算复杂网络分形维数

根据以上的算法描述,我们用matlab具体实现了这个算法。但我们在具体实现的过程中,发现由于复杂网络中的数据量非常大,而且MATLAB又是一种解释性语言,在执行M文件时,需要对矩阵的每个元素循环处理,运算速度非常的缓慢,例如利用MATLAB实现上述算法时仅仅调用一个20万行的数据,就需要执行30几分钟。

对于Matlab直接计算中存在的困难,我们考虑过从更换编程平台,但由于matlab一些优秀的特性,我们还是希望能用matlab软件来实现上述算法。这使我们把目光投向了CMEX混合编程。

MEX文件又称为外部程序调用接口,在进行大规模的数据处理,比如影响 MATLAB执行速度的循环体时,可以编写相应的C或C ++子程序完成相同的功能,并编译成 MEX文件,再由MATLAB调用此MEX文件以提高运行速度。

C-MEX是通过MATLAB的编译器转换为可执行文件,是按照MEX技术要求的格式编写相应的程序,通过编译连接,生成扩展名为.dll的动态链接库文件,可以在MATLAB环境下以函数的形式直接调用。一般来说,C-MEX 文件的执行速度是相同功能的M文件执行速率的20~40倍。

MEX文件主要由两部分组成,它们分工明确,分别用于完成不同的任务。第一部分称为计算功能子程,它包含了所有实际完成计算功能的源代码,用来完成实际的计算工作。第二部分称为入口子程序,它是计算子例行程序同MATLAB环境之间的接口,其作用是在 MATLAB系统与被调用的外部子程序之间建立通信联系。其中入口子程序的名字为mexFunction,其构成形式为:void mexFunction(int nlhs,mxA rray 3 plhs[],int nrhs,constmxA rray 3 p rhs[])。其中:nlhsnrhs为整型,分别表示输出输入变量的个数;plhs[]p rhs[]为mxA rray型指针数组,分别表示输出输入变量的地址。MEX文件执行流程可用图1表示。

针对于盒子覆盖法中的贪婪着色算法,我们也利用MEX文件编程实现了此算法来对复杂网络分形维数进行计算。具体利用C―MEX计算复杂网络分形维数的过程如下:

(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 结论

复杂网络作为一门重要的交叉性学科,通过复杂网络的研究可以发现人工网络和自然世界中存在普遍相似的特征,从而使人们重新认识自然世界的一些特性。通过研究复杂网络的分形维数,除了探究复杂网络中相似网络的维数,还可以探测网络的微观演化。本文对复杂网络的分形维数计算算法进行了探讨,并利用C-MEX混合编程的方式实现了此算法,极大地提高了运算速度。

复杂网络论文:基因表达谱的复杂网络研究

摘要：该文采用复杂网络理论。首先利用分类信息指数对数据进行初步筛选，选出了314个基因。对选出的基因分别做肿瘤样本和正常样本的相关系数矩阵，利用Kruskal算法分别对两个相关系数矩阵做最小生成树，然后通过比较选出阈值，建立起节点间的连边关系，得到致病前后的两个网络。根据复杂网络中的相关理论，分别对肿瘤样本和正常样本进行社区划分，最后通过观察两个样本的网络系统，分析致病前后基因的变化情况，建议了结肠癌的特征基因。

关键词：基因芯片；基因表达谱；社区结构；分类信息指数；最小生成树；阈值；复杂网络

癌症起源于正常组织在物理或化学致癌物的诱导下，基因组发生的突变，即基因在结构上发生碱基对的组成或排列顺序的改变，因而改变了基因原来的正常分布（即所包含基因的种类和各类基因以该基因转录的mRNA的多少来衡量的表达水平）。所以探讨基因分布的改变与癌症发生之间的关系具有深远的意义。

复杂网络理论是近年来发展起来的一个重要的交叉。对于一个复杂的系统，很多时候我们不能够单独通过分析系统内元组来反应系统性质。复杂系统是由微观层次上的海量个体所组成，个体之间存在着作用。把个体抽象为网络节点，而个体之间的相互作用抽象为节点之间的边，则复杂系统就可以用一个复杂网络来描述。

本文的实验数据集包含22 个正常组织样本和40个结肠癌组织样本，每个样本包含 2000个基因的表达数据。首先对样本数据进行归一化，另外，数据的特征维数2000，远远高于样本个数62。因此，有必要对数据进行过滤和降维。我们采用了分类信息指数方法 (information index to classification, ⅡC)[2]，公式为：

其中，μ1(i)，μ2(i)分别表示第i个基因在正常组织样本和结肠癌组织样本中的中表达水平的均值；σ12(i)，σ22(i)分别为该基因表达水平的标准差。

根据上式计算结肠癌基因表达数据中的2000个基因的分类信息指数，大部分基因的分类信息指数在0到0.2之间，仅有少部分基因的大于 0.2（如图1）。保留指数大于 0.2 的314个基因用于下一步的分析，这样就大大缩小了基因选择的特征空间，剔除掉大量“无关基因”，大大缩小需要搜索的致癌基因范围。

另外在撰写本文的准备过程中，我们查阅了大量的有关文献。与已有文献的结果进行比较，发现所选特征基因中包含了一些已被实验证实的与癌症相关的重要基因，这些基因在癌症基因调控网络中起关键作用，一共得到了40个基因（如表1）。我们要探寻的结肠癌的特征基因极有可能包含在这40个基因中，这对我们后续的研究具有重要的参考价值。其中6个基因在我们根据分类信息指数值对数据进行筛选的过程中被剔除了。所以我们选择剩下的34个基因作为我们研究的参考（如表1）。

然后分别计算结肠癌样本(cancer)和正常样本(normal)各个基因间的相似性，得到相似矩阵。分析这些基因点的联系，选择一个相似性的阈值来分别建立复杂网络，用邻接矩阵表示。（如果相似性大于该阈值的则这两个点相连接，在邻阶矩阵中用1表示；反之，如果相似性小于于该阈值的则这两个点不连接，在邻阶矩阵中用0表示）。其中关键的步骤是阈值的选取。本文提出的解决策略是，从关联系数矩阵得到最小生成树作为基因之间关系的骨架，然后再把文献中发现的相关基因之间的关系考虑进来，得到客观的阈值。

我们考查结肠癌基因表达数据中筛选出来的314个变化比较明显的基因，用向量组表示为，

其中T0m,n是第n个基因在第m个样本的基因数据，其中N=314，M是样本个数，正常组织样本个数为22，肿瘤组织样本个数为40。相关系数矩阵为R：

那么基因间的欧几里得距离就可以用以下定义的距离矩阵D定量描述：

最小生成树是图论中的基本概念。我们从距离矩阵中抽取出最小生成树，用N-1条边连接所有基因节点，形成一个无圈图。在形成的最小生成树中，要保证所有基因间的距离之和最小，也即相关系数之和最大，且是无圈图。那么，基因间的其它关系就被过滤掉了。原则上来讲，真正直接相关的基因之间的关联系数最大，因此可以认为最小生成树保留了基因之间的真正关系。因为一个基因可以和多个基因直接相关，所以很多的关系被丢掉。丢掉的关系将在后边的步骤中被找回。我们采用Kruskal算法来生成最小生成树：

我们用筛选后的314个基因数据（我们对这314个基因重新做了编号，其与原数据库中的编号的对应表见附表），对结肠癌样本、正常样本分别用两种方法得到了最小生成树。两个最小生成树的节点也即基因，一定是相同的，且都有314个节点，313条边。图2给出了正常样本中得到的最小生成树。

如前所述，最小生成树给出了基因之间的部分连接，但是很多基因之间的关系被丢掉。另一方面，文献中发现的结肠癌相关基因，为我们提供了重要的参考信息，但是这些信息包含着很大的偶然性，也就是噪声。在此我们将把这两部分信息整合在一起，得到一个客观的构建基因关系网络的阈值。

我们首先抽取出如图2所示的生成树。它给我们提供了高可信度的链接，不足之处是包含的信息不够多，一些重要的关系被忽略了。我们再根据得病前后两类样本信息变化。然而，这里也可能产生噪声边。

从上面得到最小生成树出发。整合相关文献中已知的肿瘤致病基因，我们收集到34个这样的基因。用这34个基因重复上面的过程，得到阈值，肿瘤样本的记为DDIImin，在正常样本的生成树中记为DNIImin建立网络。，它们之间可能直接相连，也可能彼此没有直接相连。计算直接相连的节点间的距离。在这个过程中，我们选取最大的那个作为阈值，在肿瘤样本生成树中记为DDIImin=0.6239，在正常样本的生成树中记为DNIImin=0.6995。

我们选取DDIImin，DNIImin作为阈值，来建立网络。这样在一定程度上减少了一些噪声边的产生，避免了偶然因素可能引起的阈值选取的不稳定性，同时也恢复了我们需要的连接。

肿瘤样本网络以及正常样本网络的阈值选定后，利用我们在数据处理中选定的314个基因建立网络。以肿瘤样本网络为例，先算出肿瘤样本中这314个基因的相关系数矩阵。当任意两个基因的相关系数大于阈值0.6239时，我们就认为这两个基因是有相互作用的，在它们之间画一条边；当任意两个基因的相关系数小于阈值0.6239时，我们就认为这两个基因是没有相互作用的，它们之间就没有直接的边相连。这样我们就得到了肿瘤样本的基因相互作用网络。在相关系数矩阵中，把大于0.6239的值改为1，小于0.6239的改为0，主对角线上元素设为0，这样就由相关系数矩阵得到了邻接矩阵MD。邻接矩阵中的1就表示网络中有连边；邻接矩阵中的0就表示网络中没有连边。

复杂网络的结构是不均匀的，往往存在很多连接致密的集团，在这些集团之间只有很少边形成的松散的连接。这些致密的结构往往与功能有着密切的关系，因此受到普遍的关注。当前普遍采用的划分社区的方法是Newman-Girvan算法。

社区划分反映基因间的功能关系，而在网络模块中，可以发现网络发生了明显的改变。首先我们画出正常样本网络，用Newman-Girvan的划分算法对得到的网络进行分块。当把正常样本网分成14个社区时，得到的聚类系数最大，为Q=0.596（如表2），这样就把网络分成了14个大的功能模块。如图3所示，即为正常样本网络的社区结构（每种颜色代表一个社区）。可以看出，各个社区结构中的节点数目分布并不均匀，并且存在很多孤立节点。社区内节点间的连接比较紧密，而不同社区间的连接比较稀疏。

同样用Newman-Girvan的划分算法，我们画出肿瘤样本的网络，把肿瘤样本网分成了13社区（如图4）。此时得到的聚类系数最大，为Q=0.630（如表3）。可以看出，肿瘤样本网络的各个社区结构中的节点数目分布也是并不均匀，并且同样存在很多孤立节点。社区内节点间的连接比较紧密，而不同社区间的连接比较稀少。

对于两个网络，我们计算出每个节点的度（degree）。我们发现，，，其中DDmax、DNmax分别表示肿瘤样本、正常样本的邻接矩阵中节点的最大度，DDmin、DNmin分别表示肿瘤样本、正常样本的邻接矩阵中节点的最小度。说明网络中的有些点与其他点的相互作用强度发生了明显的变化。反应到网络结构中，可以用平均度加以粗略说明，其中肿瘤样本网络的平均度为9.36，正常样本网络的平均度为5.28。在肿瘤样本网络中每个基因平均与周围9.36个基因有相互作用，在正常样本网中每个基因平均与周围5.28个基因有相互作用。

分析度的变化。通过两个网络的度序列做差，我们就能够找到每个节点度的变化情况。表4即为度变化比较大的前十个节点。

同时我们对每个节点度的变化值做平均，得到度变化的平均值为7.0637。其中大于这个平均变化度的节点有89个，小于这个平均变化度的节点有255个。

我们认为特征基因在这些度变化比较大的节点中的可能性很大。度变化超过平均值的节点与我们查阅的的文献中得出个34个特征基因相比对，其中有15个基因是它们所共同拥有的（如表5），我们认为这15个基因应该是对我们寻找结肠癌特征基因非常重要的基因。

接下来对我们得到了15个重要的基因节点，在网络中分析它们。在上一步过程中，我们比较了文献中得出的，且度变化较大的15个重要节点。这15个基因在肿瘤特征过程中起了很重要的作用。注意到我们选取的这15个基因最大的度变化值是33，但还有7个节点的度变化值超过了33，却并不在我们查阅的文献的结论中，我们认为有必要在网络中进一步对这些点进行分析。这7个基因节点分别是（如表6）：

表6

其中，度变化是同一节点在肿瘤样本网络与正常样本网络中，该节点在两个网络中度的变化值；分类信息指数编号是指该信息指数在所有信息指数中从大到小排列时的次序，我们选取的314个基因是分类信息指数IIC＞0.2的基因，也即分类信息指数编号前314个基因。通过上面的表格我们可以看出，这些基因的分类信息指数都比较大。通常地，样本们会去研究IIC大的点，分类信息指数编号偏后的那些基因极易在分析的过程中被忽略掉。现在我们发现，这些点在两个网络中度的变化值很大，也即癌变前后这些基因在网络中与其它基因的相互作用有了很大的变化。接下来，我们将这7个基因和另外15个基因分别放回正常样本和肿瘤样本的网络中去分析它们的变化。如图5，图6。

图5为我们找到的15个重要基因在正常样本中的相对位置。不同的颜色表示不同的社区。同时把度变化最大的7个节点（156，87，300，139，169，61，34）也放进了网络中。

图6为我们找到的15个重要基因在肿瘤样本中的相对位置。不同的颜色表示不同的社区。同时把度变化最大的7个节点（156，87，300，139，169，61，34）也放进了网络中。

从图5中可以观察出，在正常样本网络中，度变化最大的7个节点分别分布在4个社区中，且仅有一个节点与其它节点相连（节点61―节点68）。这说明7个节点在正常样本网络中没有明显的相互作用。而通过观察图6，我们的发现在肿瘤样本网络中，度变化最大的7个节点同时分布在同一个社区中，且这7个节点与我们找到的15个重要基因节点中的9个节点（分别为68、180、155、270、213、198、207、2、297）也在同一社区中（图6中蓝色表示的社区），并相连。我们有一个大胆的猜想，结肠癌的特征基因就分布在蓝色所表示的社区中。蓝色社区中的这16个节点所代表的基因分别为M22382，T96873，U09564，H08393，J02854，T62947，M59040，H20709，X62048，及M94556，T70062，L28010，M37583，H89087，H64807，T65740，从功能上看，这些基因对结肠癌的癌变过程发挥了重要的作用。在正常样本网络中，这些点分布的比较分散，而在肿瘤样本网络中，这些点集中到了同一社区中，说明癌变后这些基因之间的相互作用加强。所以这16个基因就是我们要寻找的结肠癌的特征基因。另外，除了这些在同一社区的节点之外，还有一些散节点落在各个不同的社区中，其中分为两种情况，一种是该基因位于两个社区的连接点处，如节点58（T60155），它是主动脉平滑肌肌动蛋白，而有研究表明肌动蛋白参与DNA转录，所以T60155是我们所寻找的结肠癌的特征基因。另一种是某社区内部的节点，如节点83（T51571）,130（H43887），219（L41559）,248（M36634），参照这些基因的功能对基因的癌变并没有起到决定性的作用。并且这几个点的度变化值也不是很大，所以，可能是被误选入的，应该被排除掉。综上，本文运用复杂网络的方法，通过社区模块的划分，找出17个结肠癌的特征基因。

本文首先通过分类信息指数这一指标对数据做了初步处理，筛选出314个基因节点，剔除了大量的无关基因，对数据进行过滤和降维。并以此分别构建网络模型。生成网络之后，通过Newman-Girvan方法对我们的网络模型划分社区和评价，无论是肿瘤样本网络还是正常样本网络都是很好的社区结构。我们利用度变化值和参考我们查阅文献中得出的结论，挑选出了22个基因，其中排除掉5个基因后，得出了我们的结论，即结肠癌的特征基因有17个。

本文问题研究还有待于进一步加深完善，比如没有考虑到基因筛选后提出的变化不大的点。另外，我们对于生物医学方面的专业知识比较欠缺，在对模块进行分析的时候，对模块的功能分析不够精确。这需要我们以后的继续努力和学习。

复杂网络论文:复杂金融网络的自相似性研究

摘要：以股票为节点，选取适当阈值量化股票收益率序列间相关关系从而构建复杂金融网络。基于复杂网络的理论，讨论金融网络的度分布、平均最短路径和聚集系数，发现面向金融时间序列的股票网络具有小世界效应，无标度特性和一个很重要的特性―自相似性。该文用两种方法分析了网络的自相似性：一是提出用网络节点的度构造Hurst指数，定量分析金融网络的自相似性；二是金融网络的平均路径长度和聚集系数定性地分析了复杂网络的自相似性。

关键词：金融市场；复杂网络；无标度；自相似

证券市场素有经济晴雨表之称。证券市场由于受企业经济效益，居民收入水平，投资者的心态等诸多因素影响，所以它是一个涵盖大量信息的复杂系统。近年来以复杂网络角度理解和分析证券市场，构建金融网络的方法层出不穷。Boginski [1]等研究了美国证券市场6546支股票，发现股票相关性呈现无标度性。庄新田[2]等基于相关系数构建以上海证券交易所持续交易的股票为节点的复杂网络，讨论上海证券市场的股票价格波动，鲁巍巍[3]等对沪深A股构建复杂网络，计算网络的聚集系数，吸引率，讨论不同行业的聚合强度及其对沪深A股市场股价波动的影响，这些研究都是基于网络的拓扑结构特征：节点度分布、平均路径长度、聚集系数、吸收率等，都从网络节点对网络的影响程度方面考虑，对于复杂金融网络的另一特性――自相似性并无研究。

复杂网络的自相似性是指网络局部和整体在某些特征上相似。对于固定网络自相似性的研究一般是利用节点内部互动性来探测网络的演化过程。自相似系数的测量方法是由 C.M.Song与S.Havlin[4]提出利用重构化测量，以及R.Guimera,L.Danon[5]提出利用邮件系统测量社区结构的相似性，他们也用这些方法描述了一些现实网络的自相似性[4]。

1 复杂金融网络建模

1.1 数据来源

笔者随机抽取从2007年9月28日至2010年2月26日沪深A股的500只股票作为研究对象。根据每只股票月数据的开盘价、收盘价、最高价和最低价平均值计算股票的对数收益率，然后用对数收益率序列建立相关关系，通过相关关系数值化研究复杂金融网络的拓扑特征[6]。

1.2 复杂金融网络建模

以沪深A股为节点，股票相互影响关系为连边构建无权无向网络。设股票i在第t时刻的平均价为xi(t)，xi(t)为股票i在t时刻开盘价，收盘价，最高价和最低价的平均值。

为股票i对数收益率。定义股票i和股票j的相关系数为：

其中E(yi)表示股票i在n期的平均收益率，

由定义知：ρij的值域为[-1，1]。若ρij=1，表示股票i和股票j完全正相关，表现为同向增长或降落；若ρij=－1，表示股票i和股票j完全负相关，表现为反向变化；若ρij=0，股票i和股票j完全不相关。计算n只股票对数收益率的相关系数，得到一个n×n阶对称相关系数矩阵p。选取合适的阈值，将系数矩阵p进行量化，得到一个只有0和1的稀疏矩阵，此矩阵便作为金融网络的邻接矩阵。

1.3 复杂金融网络的拓扑结构特征

1.3.1 节点度分布

节点度是指连接节点的边数，节点度分布是指一个任意选择节点恰好度数为k的概率，也等于网络中节点度数为k的节点数占网络节点总数百分比，用分布函数p(k)来表示。

1.3.2 平均最短路径长度

若一个包含n个节点的无向网络，，其中dij为节点i和节点j的最短距离，也是节点i,j最短路径所经过的边数。考虑到每个节点到期自身的距离为0，无关联节点的距离为无穷大，此时存在问题，所以对进行修改，得到“调和平均”最短路径长度。在股票网络中，平均最短路径长度是任意两只股票相关中介数量的平均值，反映网络的大小和分离程度。

1.3.3 聚集系数

考虑节点i，它通过ki条边和其他ki个网络节点相连接，则它们之间最多有ki(ki－1)/2条边连接，但ki个节点实际有Ei条边，所以节点i的聚集系数ci，，网络的平均聚集系数为。聚集是用来刻画网络的小集团形态，说明邻近集团在相关性意义上的凝聚程度。

2 复杂金融网络的自相似性研究

相识性是现实世界客观存在的一种现象，描述相识性的方法一般分为两种：一种是将对象看作为某k个维特征空间的点，对象的相似由点与点间的距离来确定，另一种衡量相似性方法是比较对象之间的一般特征和一些典型特征。自相似性是一种特殊的相似，是对象本身的一种特性，是对象局部和整体相似。

虽然C.M.Song等用重构化能测量网络的自相似性，但此时网络只能是固定结点的网络，而现实生活中的网络是动态增长的过程，如社会网中每个人认识的朋友数在不断地增加，随着市场经济的完善，上市公司数量越来越多，在证券交易所交易的股票数量也在不断的更新和变化。鉴于这些动态变化的网络，本文分别采用以下两种方法来研究复杂金融网络的自相似性

2.1 基于R/S分析的金融网络自相似性分析

设网络为动态增长的，网络节点不断地增长记为n1,n2,…ni，计算节点在ni时度分布的累积极差R(k)和标准差S(k)。

设x(k)为网络节点是ni时各节点的度数，的均值，也为网络的平均度数。

累积极差R(k)：R(k)=max x(k,ni)-min x((k,ni)

标准差S(k)：，则关系式为，

R/S为重标极差，H为Hurst指数，所以

具体计算：以ln ni为自变量，lnR/S为因变量采用最小二乘进行线性拟合，所得直线的斜率即为H的估计值

复杂网络自相似性与Hurst指数的关系[6]

若0≤H

若H=0.5， 说明复杂网络节点是互相独立的，度分布是随机的。

若0.5

2.2 基于容量维数的自相似性分析

基于分形思想，用半径为r的尺子去测长度为l的尺子，所需尺子个数为

用半径为r的小圆去覆盖面积为S的圆，所需小圆个数为

用半径为r的小球去覆盖体积为V的球，所需小球个数为

以此类推可用半径为r的客体去覆盖被测对象，所需个数N(r)的值与r的取值关系表示为，

定义D为相似容量维数，取对数得相似容量维数[7]

本文计算平均最短路径长度和聚集系数的D来分析复杂金融网络自相似性

3 实证分析

由于本文是分析动态复杂网络的自相似性，所以用不同数量的股票来构造网络。

1） 分别用200，250，300，350，400，450，500不等数量的股票构造金融网络，然后基于R/S分析用各网络节点度分布来求Hurst指数，在matlab编程基础上得到H=0.823，可知复杂金融网络具有自相似性。取阈值为0.85，构建股票网络并计算各网络的平均最短路径长度和聚集系数。

实证研究发现在网络平均度数缓慢增长时，网络平均路径长度和聚集系数呈现相似的变化趋势，这也是网络拓扑特性自相似性表现。

2） 选用200,250,300,350,400,450,500只股票分别构造金融网络，用比较分析法分析金融网络的自相似性。

比较300，400，500只股票时相关系数的概率分布，然后采用修正法[3]求相关系数的概率分布。文献[3]提出采用修正法求相关系数矩阵，来消除时间因素的影响。但笔者认为不能做修正，尽量保持原有信息，这才能反应真实的市场环境。因为首先证券股票市场存在在投机行为，趋利性等很容易造成追杀跌涨的“羊群效应”，其次证券市场受到经济周期和行业因素的影响，而每个行业都要经历幼稚期、成长期、成熟期、衰退期的发展演变过程，这个过程成为行业生命周期，再次证券市场还受到产业政策等影响。笔者用修正法[3]对300,400,500只股票构建的网络进行了修正，得到图3~图4。

显然修正后的相关系数的概率密度是正态分布，符合强势有效市场的假设，但中国证券市场目前状况是弱势有效市场，证券价格只能反映历史信息，还存在内幕信息等，所以本文不对收益序列做任何修改。

在阈值为0.85时各股票网络都表现出很好的无标度特性（如表1所示）：(最小二乘法)。

给出在阈值为0.85时节点为300、400、500的度分布图1。

以500只股票构造的网络为整个复杂网络，300只和400只都为局部小网络，得到容量相似维数。

从表2中可以看出Dl,Dc都比较相近，所以得动态的网络也具有自相似性。

4 结束语

本文基于复杂网络的理论分析了金融市场的网络特性―小世界效应和无标度特性。无标度则表示网络节点分布不均匀，网络中有地位比较重要的“中心点”，可知股票市场存在影响力比较大的股票或是行业。实证研究结果得出，金融网络的幂律指数大概为1，这与庄新田[2]等人得出上海证券市场网络的幂律指数为0.8219和0.7930差异不大。本文还着重介绍了两种方法分析金融网络的自相似性，这说明金融市场变化趋势有一部分依赖于过去，到底依赖程度有多少，就需看整个金融市场自相似程度，这便成了下一步的研究内容。

复杂网络论文:复杂网络下的综合视频会议服务

面对越来越复杂的网络环境及应用,今天的企业用户需要的已经不仅仅是一个传统意义上的产品或者系统,他们需要自己的IT应用发挥更大的价值,实现与客户之间的交互、员工生产力的优化以及企业资源的整合等,并通过这些方面的整合提升企业的运营效率。视频会议作为提高沟通效率的有效方式,满足了人们全方位的交流需求,因而在近年来取得了飞速的发展。

目前,国外从事视频会议系统研制、生产的大公司大多已经进入中国市场,国内也有越来越多的企业积极参与到市场竞争中来,在竞争越来越激烈的情况下,视频会议系统供应商必须充分发挥自身的优势,才能抢占更大的市场份额。北京盛维新世纪网络通信技术有限公司是一家专注于网络多媒体通讯软件开发及服务的高新技术企业。作为全球少数真正全面掌握多媒体通讯核心技术的企业,盛维公司在过去几年中密切关注用户的使用需求,并在其Cenwave多媒体通讯软件平台上开发出网络视频会议系统、网络直播系统、网络实时课堂、多方电话会议等多种视频应用产品。

全面灵活的解决方案

由于我国存在比较复杂的运营商网络环境,企业的出口网络一般较窄,为了确保用户在任何情况下都能够成功召开远程会议,盛维公司为用户准备了一整套远程会议综合解决方案,可以为客户提供基于不同终端、多种实现方式融合的、系统化的视频服务支持。北京盛维新世纪通信技术有限公司总裁魏松祥表示:“我们正在向用户交付一个真正兼容的平台,能够兼容不同网络、不同种类的终端设备,实现语音、视频、数据的全面整合。让用户可以在任何时间、任何地点、和任何人进行多媒体的沟通和交流,实现协同办公。”

相比较市场上其他服务商提供的解决方案,盛维远程会议综合解决方案全面涵盖了软件视频会议系统、硬件视频会议终端、软硬混合视频会议系统、MCU租用、电话会议租用、网络会议租用等各种产品与服务,并能够根据客户的需求提供这一系列产品与服务的组合,真正做到实现客户各种形式、各种应用环境下“成功召开远程会议”的目标。

魏松祥告诉记者,在盛维提供的纯软件高清视频会议解决方案中,用户只需通过普通的PC机、麦克风、摄像头就能够轻松在互联网上召开网络会议。对于关注成本的中小企业用户来说,盛维软件高清视频会议解决方案可以让它们以最小成本实现远程视频会议的召开。而基于硬件的高清视频会议终端主要是为了满足大中型企业客户的应用需求,系统采用了高集成度、嵌入式的设计模式,是一款体积小巧、外形美观、稳定可靠的硬件会议终端。

此外,为了加快网络视频会议在中小型企业市场的普及,盛维以颠覆性的思维推出了网络视频会议租用服务,为企业提供了低风险、低投入、实施简单的视频应用服务。在这种服务模式下,一切网络基础设施、软件平台、硬件平台的建设和维护工作都由盛维公司提供,当用户需要使用网络视频会议时,只需向盛维申请开通网络会议服务,获得登录账号就可以召开远程网络视频会议。这种独创性的租用服务模式,使得企业无需购买任何系统软件、硬件设备,无需租用昂贵的服务器带宽,也无需专业IT人员维护就可以轻松召开远程视频会议,真正做到帮助企业降低运营成本,提高工作效率。

覆盖全球的运营网络

多媒体视讯服务需要坚实可靠的网络来支撑。在全球化的时代,用户的沟通对象可能在全国乃至世界各地。一个网络会议运营网络不但需要能充分覆盖国内,也要能较好覆盖世界各地。盛维在发展过程中,逐步建立起一个覆盖面广、通信质量可靠的面向全球用户的网络会议运营网络,通过这个网络平台可以保证高清视频会议系统的稳定运行。

盛维网络会议运营网络为租用盛维网络会议的客户提供了一个高速的专用网络,确保用户在这个平台上能召开高质量的网络会议。同时盛维还与全球各地的电信运营商建立了紧密合作关系,把电话网成功对接到这个运营网络上。用户能以极低廉的资费召开电话会议,或者实现电话会议与网络视频会议的混合使用。

魏松祥表示,盛维运营网目前已经覆盖了全国所有地区,在主要骨干网上部署了上百台服务器,总带宽达到将近2Gbps。同时,盛维公司在亚太地区、北美与欧洲也部署了众多服务器,其运营网络能全面覆盖亚洲、北美以及欧洲等地。此外,为了确保用户在盛维运营网上的通信安全保密,盛维公司采用了严格的安全策略以及256位数据加密算法,并且有专业运维团队7×24监控服务器与网络。

凭借出色的技术能力,盛维系列产品目前已应用政府、军队、教育、医疗、金融、能源、IT等多个行业。在国内教育行业,更是取得市场占有率60%的业绩。魏松祥告诉记者:“每天全球有数万用户在使用我们的产品及服务,并且已有上百家客户使用我们提供的产品成功召开1000人以上大规模会议或远程培训。”凭借以上出色的表现,在2009年6月,盛维公司一举荣获第十三届中国国际软件博览会“献礼新中国成立60周年•中国软件行业最具成长力企业奖”。

可以说,在工业化与信息化日益融合的大趋势下,盛维公司给企业信息化选型创造了有利的条件,降低了企业视频应用的门槛。某种意义上讲,盛维公司正在改变传统多媒体通讯软件销售的模式,为企业提供了低风险、低投入、实施简单的信息化方案,使企业通过互联网便可以享受到相应的软件和维护服务,切实做到了帮助企业降低运营成本,提高工作效率。

复杂网络论文:基于复杂网络的风险传播模型及有效算法

摘 要：提出一种基于复杂网络的风险传播模型及有效算法，通过结合复杂网络中传播蔓延现象的推广模型，将风险传播模型划分为两种：主动型风险传播模型与被动型风险传播模型。并对已有风险传播算法进行改进，实验表明，该模型及算法能健全风险传播机制，提高传播速度与精确度。

关键词：复杂网络；推广模型；风险传播

1 引 言

随着网络安全问题的日益突出，风险评估越来越受到人们的重视。风险评估一般分为静态评估和动态评估两种，前者评估体系比较完善，评估精确性程度较高，但缺点是评估周期过长，评估模型可能随着时间的推移而不能适用，不能反映网络的实时信息；后者评估能根据网络状况适时的做出风险估计，能及时反映网络风险的动态变化，性能好于静态评估[1，2]。而针对动态风险评估的研究有：基于免疫的网络安全风险检测的模型[3，4]，是一种基于入侵时的检测模型；基于隐马尔可夫模型的网络风险评估方法研究[5，6]；基于贝叶斯模型的网络风险动态评估方法[7，8]， 可以对网络的总体风险和局部要素可能引起风险的程度进行评估。以上文献对网络入侵检测研究较为深入，但侧重于对攻击的动态评估，未能考虑已有风险如何扩散与转移。针对网络风险传播，张永铮等提出了用于评估网络信息系统的风险传播模型[9]和一种求解网络风险传播问题的近似算法[10]，对已有风险在网络中的传播进行研究，但其传播模型与算法存在一些缺点：首先，模型中仅考虑了风险传播模型，未能考虑风险引入模型；其次，一个部件上可能存在多个弱点，则该部件对另一部件的同一方向的可信访问路径可多于一种，则部件不能在有向图中被视为图节点。第三，最小入度的部件感染风险的概率较低，因此其作为风险源的概率不高。第四，若入度最小的部件已经感染风险，其出度不一定是最大的，正如流感爆发在人口密集的地区一样，则其风险不能立即传播出去，存在滞后性，时效性欠佳。

本文在针对网络风险传播问题，结合复杂网络中传播蔓延现象的推广模型 [11，12]，提出了一种网络风险传播模型及相关定义，并改进了风险传播算法。

2 推广模型下的风险传播

网络信息的动态风险不仅仅表现为一般意义的风险，其传播可能会对社会造成不可估量的损失，如病毒的传播造成的跨域风险、有害信息的传播造成的社会风险等。为此我们将借鉴复杂网络的传播机理和分析的方法，研究网络风险传播模型。

按照复杂网络的传播蔓延现象的推广模型[11，12]：假设网络中有N个个体，每个个体是三种状态的中的一种：易染态S，感染态I和移除态R，在时刻t，个体i随机的与个体j相连，若i∈S，j∈I，则个体i以概率p得到一个正剂量di（t′），这里di（t′）都服从分布函数f（d）。每个个体都保留着过去T时期中所接受的总的剂量

在本文中，暂不考虑网络风险移除状态，即仅考虑风险在整个网络中如何转移，而未考虑网络风险传播后所造成情况的如何消除。因此上述推广模型应用于风险传播如下：

计算技术与自动化2016年6月

第35卷第2期吕元海等：基于复杂网络的风险传播模型及有效算法

每一时刻t，风险结点j对其直连结点i每发动一次攻击，就会从被攻击结点i中获取一定的信息剂量di（t），则在过去T时期中风险结点获取被攻击结点的信息总剂量为：

3 风险传播模型

3.1 相关定义

定义1.结点：指网络系统中任意一台网络设备上任意可能被利用的最小单元。其中已经被利用的称为风险结点，而尚未被利用的称为非风险结点。

定义2.有向路径：结点A访问结点B时，形成的从A指向B的单向访问关系。这里所说的单向访问关系是指合法或非法的、由主动发起方指向被访问方的访问，而不代表实际信息传输的路径，因为严格的讲，任何两个相连结点之间的链路都是双向的。有向路径概率即为结点访问概率。

定义3.风险传出：指风险结点对其所访问的任一结点造成的损失或影响。

定义4.风险引入：指非风险结点访问风险结点时，由于存在实际信息的交换而受到该风险结点的影响。

这里举例说明一下定义3、4，某病毒利用空气（相当于网络中的信息交换链路）进行传播，当病体A主动接触易染体B时，A将病毒传播给B，其中A主动接触B即为A访问B，病毒传播方向为A到B；反之当易染体B主动接触病体A，也会被感染，同样病毒传播方向为A至B，但为B访问A。

定义5.风险传出公式：设结点n被成功利用的概率为Pn，被利用后对网络系统的危害程度为Wn，利用至该结点的有向路径概率为Pmn，其中m为主动访问n的风险结点，则对结点n而言，产生的风险为Riskn=Pmn×Pn×Wn。

定义6.风险引入公式：设结点n为非风险结点，该结点成功访问风险结点m的概率为Pm，利用至结点m的有向路径概率为Pnm，由结点n发出至结点m的有用消息权重及概率分别为Unm、pnm，由结点m发出至结点n的有害消息权重及概率分别为Hmn、pmn，则对结点n而言，引入的风险为Riskn=Pnm×Pm×（Unm×pnm+Hmn×pmn）。

定义7.风险网络：借鉴张永铮等对风险网络[4]定义，把一个能够描述各结点风险分布与有向路径的网络称为风险网络。风险分布为网络系统各个设备中结点携带风险的分布情况，为内在风险；有向路径即为各结点之间的访问方向，为外来风险的传出与被引入提供可能。

3.2 风险传播模型

1.主动型风险传播模型：也称为主动型风险传出，即利用风险结点已存在的风险对其直连结点进行主动访问（包括非法攻击或可信访问，下同），产生风险扩散（即风险传出）。如图1（a）所示，结点A为风险源结点，存在至结点B、C、D、E的四条有向路径，设结点A风险结点，至结点B、C、D、E的有向路径概率为PAJ，（J=B，C，D，E），各结点自身被成功访问的概率为PJ，（J=B，C，D，E）[8]，则结点A以概率PAJ×PJ（J=B，C，D，E）引起其出度所连结点发生风险，如图1（b）所示。

在实际网络中，路径传播概率可由两结点的所有可能路径计算得出，而结点被成功攻击的概率则有风险传播推广模型计算得出。

4 最大出度算法

针对最小入度最近邻算法[5]的不足，本文设计了一种能更好反映网络风险动态特征的算法――最大出度算法，又分为针对主动型风险传播模型的最大出度算法和针对被动型风险传播模型的最大出度算法。

4.1 风险源结点最大出度算法

Step1：计算未被处理过的风险结点出度值numofoutdegree。

Step2：优先选择最大出度的结点，利用图1所示算法将其风险值沿其出度传播给相邻结点，风险计算方法见定义5。

Step3：传播风险后将该结点标记为color=red。

Step4：重复Step1、Step2、Step3，直至所有风险结点全部被标记。

4.2 零入度非风险源最大出度算法

严格的讲，零入度的结点是不存在的，因此最小入度最近邻算法关于零入度的概念未指明其时间范畴，在本文中，零入度的结点是指在某时间段内不接受访问的结点。

Step A：将网络结点中所有零入度的非风险源结点标记为color=green。

Step B：计算未被处理过的零入度的非风险源的出度值numofoutdegree。

Step C：优先选择最大出度结点，并判断其出度中有无风险结点，若有则选择其出度所连结点中风险值最大的一个作为引入风险源，以概率引入风险，风险计算方法见定义6，将该结点标记为color=pink，断开与引入风险源的有向链接；若无，则重新选择结点，对该结点不进行任何处理直到再次满足条件。

Step D：引入风险后，该结点已为风险结点，如果满足最大出度的条件，则跳转至最大出度算法的Step2继续风险传播。如果暂不满足最大出度的条件，则跳转至Step A顺序执行。

4.3 一般非风险源风险引入

网络结点的风险在传播最后往往会出现如图3所示的情况：结点A、B、C为非风险源结点，D、E为风险结点且RiskD>RiskE，按照文[5]的理论，则其程序在图3情况下停止运行，为了解决这一问题，引入如下算法：

Step a：计算非风险源结点的出度值numofoutdegree。

Step b：优先选择出度最大的结点，若其出度所连接结点中存在风险结点，则选择风险值最大的一个结点作为风险引入源并断开与该风险引入源的有向链路，该结点被标记为color=pink；若不存在，则重新选择。

Step c：引入风险后，该结点已为风险结点，跳至Step b继续执行，直至又出现图3情况，则跳转至Step a继续执行，直至风险传播完毕。

说明：网络结点被初始化为风险结点（color=pink）和安全可信结点（color=green）后，运行风险源最大出度算法和零入度非风险源最大出度算法时，两者发执行，不存在先后次序，而一般非风险源风险引入只是在出现如图3情况下才使用的算法，是为了防止风险传播中忽略此类风险引入导致风险误差较大的情况。

5 算法性能比较

5.1 风险传播机制比较

最小入度最近邻传播算法[5]虽然能够对网络风险传播给出比较精确的结论，但其在理论上有一定的缺陷，如图4所示，假设结点1、2为风险结点，按照最小入度最近邻传播算法，结点1为入度最小的满足条件的风险结点，则其以概率使结点2、4产生风险，同时将自己标记为已处理，如图5（a）所示，然后结点2又满足传播条件，并以概率使结点3、5、6产生风险，并被标记为已处理，如图5（b）所示，两步共计感染四个结点，但其却是在第二步才将风险传给结点6，因而其时效性欠佳。而按照风险源最大出度算法，则优先选择结点2，使其携带的风险迅速被传播给结点3、5、6，如图6（a）所示，再次结点6满足传播条件，并将风险传播给其出度所连的四个结点，如图6（b）所示，两步共计感染七个结点，多于最小入度最近邻传播算法的新感染结点，并且其时效性优势随着网络结点的复杂化而凸显，更容易满足动态网络风险评估的要求。

此外，零入度的非风险源结点不会传出风险[5]，因此应在风险传播之前对其进行处理：断开此类结点的所有出度，如图7所示，结点9被认为不会对结点2及尤其是结点10造成风险传播，因此可以断开其所有出度。但本论文认为结点9虽不会对结点10造成直接的风险传播，但是它可能会从结点2引入风险，从而使自己变为风险结点，进而对结点10造成风险传播，如图8所示。

5.2 实验结果对比

本实验实验环境为Microsoft Windows XP Professional，Intel（R） Pentium（R） CPU 1.8GHz，512M RAM。仿真工具为NetLogo 4.0.4、Matlab 7.0.0.19920（R14）。

共同参数：总结点为200，平均度为10，风险结点不超过所有结点入度之和，结点危害性参数W=1，风险结点初始风险值为1，路径传播概率服从[0，0.5] 上的均匀分布。

本文参数：结点被成功访问概率P可利用推广模型计算，其中推广模型的参数p=0.5，f（d）=δ（d-1），g（d*）=δ（d*-3），采用最大出度算法进行传播。

文[5]参数：概率权p（x）=0.5，采用最小入度最近邻算法进行传播。

6 结 论

实验表明：本文方法则是风险呈非线性变化，并且开始变化较快，最后变化缓慢，即在一定的精确度容许的范围内，对风险进行任意时刻的抽样，本文的风险值更接近真实风险，因而动态性能更好。另外考虑的非风险源结点的风险引入，使风险值被忽略的部分被重新计算在内，提高了风险精确度。

复杂网络论文:基于复杂网络的车载自组织网络抗毁性分析

摘要：针对车载自组织网络（VANET）的抗毁性问题，分析了其在随意攻击和蓄意攻击下网络的抗毁性特征。首先，提出以最大连通度、连通分支平均规模、临界点移除比例及网络效率为评价指标的VANET拓扑抗毁性参数；然后，基于带有车辆换道功能的智能驾驶员模型，应用VanetMobisim仿真软件建立VANET；最后，通过仿真实验分析了网络节点数、通信半径以及攻击模式对VANET抗毁性的影响。实验结果表明由于车辆节点度分布的不均匀性，VANET对随意攻击具有较强的抗毁性，而在蓄意攻击下显得比较脆弱；基于节点介数的蓄意攻击对网络的破坏更快、更强。这些规律为优化VANET拓扑控制、网络协议开发和网络管理提供新的指导。

关键词：

车载自组织网络；复杂网络；抗毁性；随意攻击；蓄意攻击；仿真

0引言

移动Ad Hoc网络（Mobile Ad Hoc NETwork， MANET）是一种自组织无线网络，由于它不需要基础设施支持，因此网络部署快速，扩展方便，使得它被广泛应用于军事、救灾、商业等各领域。近年来，城市车辆与日俱增，移动网络技术日益突破，车辆自组织网络（Vehicle Ad Hoc NETwork， VANET）[1]作为一种特殊的MANET网络也快速引起高度重视。在VANET中，在一定的区域内使用无线网络通信技术将车辆与车辆以及车辆与固定基础设施连接在一起，从而一个车辆间多跳通信网络在现有道路上被动态、快速地构建，且具有自组织、分布式控制的特点，因此，VANET在交通方面具有良好的应用前景，如信息预警、行车安全、车辆之间通信及车辆Internet访问等。

VANET既具MANET网络的特点，如拓扑结构动态变化、自组织无中心、低带宽等，又有自己的特点，比如快速移动性、拓扑变化频繁、间歇连通性、网络规模大、充足的能量供应等[2]。在VANET中，由于车辆的高速运动，网络拓扑随之变化，对网络性能造成直接影响，因此如果能够掌握VANET拓扑结构的动态特性，可以设计高效的拓扑控制算法，优化网络连通性，使网络能够持续稳定提供可靠的服务。抗毁性是评价网络拓扑特征的主要指标之一，通过抗毁性的研究可以发现网络中的安全隐患和薄弱环节，从而采取一系列有效的措施来提高网络的抗毁性，优化网络拓扑结构，保证网络的稳定的通信能力，这对拓扑动态变化的VANET协议开发和网络管理有着重要的意义。

目前，国内外对Ad Hoc网络的抗毁性研究较多。比如文献[3]研究了网络抗毁性受节点行为的影响，通过建立节点行为模型及分析三维网络连通性得到了三维MANET网络抗毁性的一种定量分析方法；同时仿真检验了它的有效性和合理性。文献[4]引入自然连通度为抗毁性度量指标，建立了能耗的移动Ad Hoc网络拓扑结构抗毁性综合测度模型，并确定了基于网络拓扑抗毁性的最优发射半径。Azni等[5]根据相关节点的行为建立了k相关抗毁性模型，通过仿真分析了Ad Hoc网络的全局抗毁性。文献[6]中有针对性地分别从失效成因、测度、提升策略与故障检测和修复等4个方面对无线传感器网络抗毁性的研究进行归纳和分类，着重探讨了基于网络重构和拓扑演化及路由控制的无线传感器网络抗毁性优化策略。

目前，对VANET拓扑结构的研究主要是基于复杂网络理论分析其网络的度分布、聚类系数、路径长度等。文献[7]以多Agent微观交通仿真器（Multiagent Microscopic Traffic Simulator， MMTS）为仿真工具，研究了瑞士城市苏黎世交通网络的瞬时特性，研究结果表明网络节点数服从参数幂律分布；通信半径越大，最大集团的值越大，集团的数目越少；VANET不存在小世界特性。文献[8]中利用4000多辆出租车收集的实时数据，分析了城市环境下车辆自组网的度分布、聚类系数、特征路径长度等拓扑特性，建立了一种车辆自组网的网络模型，通过仿真验证了所建模型的有效性。文献[9]以城市道路交通仿真软件（Simulation of Urban Mobility，SUMO）为仿真工具研究了德国科隆的交通网络的瞬时拓扑结构，其主要刻画参数包括最大连通分支、度及介数中心性等，分析结果表明车载自组织网不具有小世界特性。文献[10]应用Barabasi和Albert提出的BA（BarabasiAlbert）无标度网络对VANET拓扑进行建模分析，认为VANET具有小世界特性。文献[11]利用车辆全球定位系统（Global Positioning System， GPS）数据分析了VANET拓扑结构的动态演化特征。据研究所知，对VANET拓扑结构抗毁性的研究甚少，仅有文献[12]对VANET的抗毁性作了初步研究，但是该文认为VANET是无标度网络，然后用无标度网络模型产生VANET，事实上，这样生成的VANET就是一个无标度网络，与现实环境的VANET相差太远，几乎没有考虑VANET的任何特征，比如节点移动性、节点移动受到道路限制等，因此该文本质上是研究了无标度网络的抗毁性，并非VANET的抗毁性。

抗毁性是VANET拓扑结构的重要特性之一，它代表网络在某种极端攻击或错误条件下其服务能力下降的程度。由于真实、公开的VANET的trace比较少，而且能够获得的一些真实trace存在一些问题，比如GPS数据不完整、时间粒度、数据精度不够等，使得用真实VANET移动数据研究抗毁性存在一定困难，因此，本文通过VanetMobiSim车辆仿真软件，深入分析VANET的抗毁性特征，为网络拓扑结构的优化提供指导。

1VANET抗毁性研究方法及测度

1.1抗毁性研究方法

目前，抗毁性的主要研究方法是用不同的方式对网络进行攻击，用相应的测度指标对网络的抗毁性进行分析。网络攻击策略是指采取何种方式删除网络中的节点或边，在现有研究中主要应用Albert等[13]Albert提出的文献，与文献13的作者不匹配，请作相应调整，以便保持一致；要注意论文在正文中的依次引用顺序。提出的随意攻击（Random Attacks or Failure）和蓄意攻击（Intentional Attacks）两种方式。随意攻击通常是指随机选择网络的一个节点或边进行攻击，然后再随意攻击其余节点中的一个节点或边，直至将网络中所有节点全部攻击完为止。蓄意攻击又称为选择性攻击，选择重要的节点或边作为攻击对象，一般用度和介数度量节点和边的重要性。具体攻击过程为：首先选取网络中度或介数最大的节点或边作为第一攻击目标，攻击完以后重新计算网络各节点或边的度量等级，依旧对度量等级最高的节点或边进行攻击，重复该过程，直到网络中所有的节点全部被攻击完为止。

1.2节点重要度评估方法

蓄意攻击选择重要节点或边进行攻击，评估网络中节点或边重要性的方法很多，本质都源于图论及基于图论的数据挖掘。本文用度和介数评估车辆节点的重要性。

定义1节点的度。在网络中，节点vi的邻边数目ki称为该节点vi的度。网络的平均度为：

k=1N∑Ni=1ki（1）

直观上看，一个节点的度越大，该节点越重要。

定义2节点的介数。节点vi的介数Bi就是网络中所有最短路径中经过该节点的数量比例之和，即：

Bi=∑j，k∈V， j≠kNjk（i）Njk（2）

其中：Njk表示节点vj和节点vk之间的最短路径条数；Njk（i）表示节点vj和节点vk之间的最短路径路过节点vi的条数。介数是一个全局特征量，反映节点在整个网络中的作用和影响力。在VANET中，若一个节点的介数越大，则表明它在网络中交换的信息流越大，可视为网络中的核心节点，也意味着它更容易拥塞，成为网络的瓶颈。

1.3VANET抗毁性测度

设G=（V，E）为VANET的拓扑图，其中V={v1，v2，…，vN}是网络节点的集合，E={e1，e2，…，ek}是网络边的集合，节点数定义为N=V。定义子图Ci=G（Vi，Ei）为含节点vi连通分支，设m（G）=max1≤i≤nV（Ci）表示图G的所有连通分支中顶点数最多的那个连通分支的节点数，则节点数最多的连通分支为最大连通分支。

定义3最大连通度S。将网络中的最大连通分支中节点数与网络中总的节点数的比值称为最大连通度，即：

S=m（G）/N（3）

那么0

定义4连通分支平均规模s。当VAENT受到攻击后，网络被分割为若干连通分支，连通分支平均规模定义为去掉最大连通分支后其他连通分支的平均节点数，即：

s=（∑ni=1V（Ci）-m（G））/（n-1）（4）

显然0

定义5临界点移除比例fc。当网络中的节点受到攻击后，网络处于崩溃边缘时，网络中被攻击的节点数占总节点数的比例，称为临界点移除比例，记为fc。

网络在某种攻击模式下，百分比f的节点被移除，当f超过一定阈值，即f≥fc当在“=fc”时，属于哪种情形，需明确。时，网络分割成许多小的非连通分支；当f

设网络中任意两个节点vi与vj之间的距离dij为连接这两个节点的最短路径上的边数。VANET由于车辆的高速移动、拓扑变化频繁，使得网络间歇连通，因此存在dij=∞。而且当网络受到攻击时，网络的连通性也将发生改变，网络被破坏到一定程度时，会产生孤立节点，此时会存在dij=∞，因此，文献[13]提出用网络全局效率来描述非全连通网络的连通性。

定义6全局效率E。定义网络全局效率为：

E=1N（N-1）∑i， j∈V，i≠j1dij（5）

显然，网络全局效率越大，网络连通性越好。

2仿真实验

2.1VANET仿真环境

本文采用VanetMobiSim[14]软件建立VANET环境，移动模型采用带有车道变换的智能驾驶员模型（Intelligent Driver Model with Lane Changes， IDMLC）[15]。该模型是一种微观交通流模型，是在IDM的基础上增加了车辆在十字路口的管理及车辆换道功能的智能移动模型，使得其更加符合真实的交通场景。仿真实验中，网络节点即为运动的车辆，可以获取任意时刻任意车辆的位置、速度、加速度、所处车道等瞬时信息。IDMLC移动模型中车辆长度为5m，加速度a和减速度b分别为0.6m/s2和0.9m/s2，礼貌参数p为0.5，其他参数设置如表1所示。

2.2VANET抗毁性分析

下面分析在不同攻击模式下VANET的抗毁性，为了在图中便于区分不同攻击模型，用符号Failure、RD和RB分别表示随意攻击、基于节点度的蓄意攻击和基于节点介数的蓄意攻击。图1为网络中车辆数为200、不同通信半径时，VANET受到Failure、RD和RB等三种攻击时网络最大连通度的变化趋势。由图1可知，当通信半径r=200m， f=0时，S=0.3630，即初始网络连通性较差。在攻击过程中当最大连通度低于0.1000时，视网络基本瘫痪。在随意攻击下，当S为0.0911时，临界点移除比例fc=53.42%；在RD攻击下，当S为0.0616， fc=28.77%；在RB攻击下，当S为0.0890时， fc=20.55%。当r=400m， f=0时，S=0.9521，初始网络近乎全连通（网络全连通时S=1）。在随意攻击下，当S为0.0747时， fc=82.19%；在RD攻击下，当S为0.0822时， fc=57.53%；在RB攻击下，当S为0.0959时， fc=36.99%。这一方面说明了通信半径越大，VANET连通性越好，临界点移除比例fc越大，抗毁性越强；另一方面，当通信半径相同时，随意攻击的临界点移除比例fc的值均大于蓄意攻击模式的，因此VANET有较强的鲁棒性，且在蓄意攻击下，由于将重要节点移除后网络迅速分割为多个连通分支，S先呈现迅速大幅度下降、然后缓慢下降趋势，即VANET又具有脆弱性。这种既鲁棒又脆弱的抗毁特征是VANET中车辆度分布不均匀所致。

图2为网络中车辆数为200、不同通信半径时，VANET受到Failure、RD和RB三种攻击时的网络连通分支平均规模。由图2可知，当通信半径较小（如r=200m）时，初始网络连通性较差，三种攻击策略下连通分支平均规模s均随移除节点比例的增加而逐渐减小。当通信半径较大时，网络初始连通性较好，则s随去除节点比例的变化趋势都是先变大后变小。当通信半径r=400m时，在遭受随意攻击时，s在阈值f=0.8220处开始缓慢变小，在遭受蓄意（RB、RD）攻击时，s分别在阈值f=0.4521和f=0.2055处开始变小。连通分支平均规模s之所以在阈值之前会变大，是由于随着节点被移除，网络总体连通程度变得越来越松散。在阈值之后会变小，是因为网络在大量节点失效时被分割成互不连通的多个较小的分支，当节点被全部移除时，网络则会消失。通过计算，在r=300m时，VANET在Failure、RD和RB三种攻击下连通分支平均规模s的方差分别为2.0306，2.4913和9.0228，即Failure攻击下s的波动最小，RB的波动最大，当通信半径发生变化时，也有类似的结论。这也说明了VANET既鲁棒又脆弱的特征。

图3分别为网络中车辆数为200、不同通信半径时，VANET受到Failure、RD和RB三种攻击时网络全局效率的变化趋势。由图3可知，通信半径越大，VANET效率越高；同时，随意攻击模式下的网络效率均高于蓄意攻击的。

另外，比较图1～3中最大连通度、临界点移除比例、连通分支平均规模和网络效率等抗毁性测度的值，可知对于蓄意攻击的两种策略，RB模式的攻击效能要强于RD模式。

下面研究车辆密度对VANET抗毁性的影响。图4～6为r=400m时不同车辆密度的VANET采取Failure、RD和RB攻击策略时表现出的抗毁性差异。从图4～6中分析得到：在通信半径一定时，车辆密度越大，VANET连通性越好，抗毁性越强，但是当网络达到全连通时，车辆密度对VANET抗毁性影响不大，因此，在VANET拓扑控制时，可以根据实际道路、地形、路边单元（RoadSide Unit， RSU）的配置等情况，对车辆通信半径和车辆密度进行优化设置，使得网络能够保持良好的连通性。

3结语

在VANET中，抗毁性对于分析整个网络性能来说十分重要，尤其是在增强安全性方面的应用。本文基于IDMLC移动模型对车载自组织网络的抗毁性特征作了研究，仿真结果表明，VANETs既有鲁棒性又有脆弱性；通信半径和车辆密度越大，VANETs抗毁性越好，但当网络全连通时，车辆密度对抗毁性影响很小。由于蓄意攻击（RD、RB）对网络破坏性强，因此，如何在拓扑控制时优化网络通信半径、车辆密度及路边基础设施配置等参数，使得网络中各个车辆节点保持相对均衡地位，从而提高VANETs抗毁性，这将是后续的研究工作。另外，本文只研究了VANET的瞬时拓扑结构及其抗毁性，然而，VANET的重要特征之一是网络拓扑结构的实时变化，其动态抗毁性特征也是接下来工作之一。

复杂网络论文:基于复杂网络理论的电网主导节点选择

摘 要：随着电网规模日益增大，对其进行电压控制越发困难。为了更好的对其进行电网优化控制，集中选取电网中的主导节点作为无功补偿点成为关键。为此文章提出基于复杂网络理论的主导节点选择方法，并通过IEEE-39节点系统进行仿真校验。

关键词：电网；电网控制；主导节点，复杂网络理论

前言

自从1999年Baraba和Albert发现了无标度网络特性，揭示出复杂网络结构中包含的结构特征与各种动力学特征之间的关系，突破了单纯的规则网络和随机网络模型的束缚后，复杂网络理论的研究就上了一个新的台阶[1]。而电网可以抽象成一个复杂网络，具有复杂网络的一般特征，可运用复杂网络理论来进行分析。文章引入复杂网络理论中的程度中心性指标与灵敏度矩阵相结合来衡量节点在电网系统中的重要程度。

1 主导节点选择方法

1.1 灵敏度矩阵的介绍

电网中的主导节点不仅要能进行电压调控，同时也应该具有反映其节点电压水平的能力。因此，在已有文献中大部分都是通过构建成考虑可观性与可控性的目标函数来进行主导节点选择[2-3]。该矩阵是关于无功注入变化对电压变化的灵敏度，其性质能反映电网间无功、电压间联系的疏密程度。电网节点i的灵敏度目标函数定义为：

式中，m，j分别为区域内所有负荷节点的编号和无功电源节点的编号；Se为分区内所有负荷节点合集，Sg为分区内所有无功电源节点合集。可观性指标？琢im和可控性指标？茁ij均由潮流计算收敛后的雅克比矩阵求得。

1.2 程度中心性指标介绍

程度中心性指标是社团中节点在其所属群体内的重要程度进行判别依据之一[4]，其定义为：

式中，di（n）为电网第n个节点与电网内其他节点关系权重和，gi为电网内所有节点之间权重和。

按目标函数（1）计算出电网节点具有较大的灵敏度，但在实际电网中求出的节点可能处于电网区域末端位置，那么该节点就不适合作为电网主导节点。因此本文提出基于程度中心性指标改进目标函数，改进的目标函数表达式如下：

为了验证基于复杂网络理论中程度中心性指标的电网主导选择方法的可行性，文章将利用Matlab仿真软件对IEEE-39节点标准测试系统进行仿真分析。

2 算例分析

根据潮流计算收敛后的雅克比矩阵求出了？琢im矩阵和？茁ij矩阵，但这两矩阵数量值不在同一个数量级上，因此需对其进行标准化计算。根据式（3）求出节点的目标函数值，文章只列出最大的3个节点，其值如表1所示。

由表1可以看出，所选主导节点在区域内部大致处于中心位置，有利于对电网区域中末端位置的节点电压水平进行调控，能更好的实现电压无功控制。

3 结束语

文章基于复杂网络理论提出了一种新的主导节点选择方法。并在IEEE-39节点标准测试系统上进行了仿真验证，所得到的主导节点综合考虑了电网的地理结构与灵敏度矩阵，从而提高了主导节点选择的准确度。