复杂网络研究

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

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

中图分类号：TP393文献标识码：A文章编号：1009-3044(2008)30-0561-03

Research of Complex Networks

WANG Lu1,2,SONG Hao-jie1

(1.Anyang Institute of Technology,Computer Engineering Department,Anyang 455000,China;2.Tianjin University of Technology,Management School,Tianjin 300191)

Abstract: Basic on the main characters of complex networks―Average Path Length, Cluster Coefficient andDegree Distribution ,the paper analyses three main model of complex networks―ER model, small-world networks (WS model) and scale-free networks(BA model). At last ,the paper point out some research directions of complex networks.

Key words: complex networks;ER model;small-world networks (WS model);scale-free networks (BA model)

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模型为代表的小世界网络模型很好地展示了小世界的特性，但现实系统中的小世界网络异常丰富，理论上，有多少种现实网络就有多少种生成机制。因此，研究小世界网络形成的新机制，揭示产生小世界特性的多样性和新途径，是十分有意义的。

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

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

参考文献：

[1] 方锦清,汪小帆,刘曾荣.略论复杂性问题和非线性复杂网络系统的研究[J].科技导报,2004,2(2):9-12.

[2] Latora V,Marehiori M.Effieient behavior of small-world networks[J].Physics Review Letters,87(19):198701,2001.

[3] Barrat A,Weigt M. On the properties of small world networks.European Physical Journal B,13(3):547-560,2000.

[4] Watts D J,Strogatz S H.Collective dynamics of 'small-world' networks[J].Nature,1998,393:440-442.

[5] Barabási.Albert-Laszlo,Bonabeau,Eric.Scale free Networks[M].Scientific American,May 2003.

[6] Barabási A L,Albert R.Emergence of scaling in random networks[J].Science,1999,286:509-512.

[7] Barabási A L,Albert R,Jeong H.Mean-field theory for scale-free random networks[J].Physica A,1999,272:173-187.

注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文