复杂网络理论研究状况综述

复杂网络理论研究状况综述

●刘晓庆

陈仕鸿

摘要：文章首先简要介绍了复杂网络理论；然后重点论述了小世界网络模型的研究背景、基础概念及模型的统计特

性；最后对于小世界网络在各个领域的研究进行了简单的概述。关键词：复杂网络；小世界网络；无标度网络

一、复杂网络概述

式，由于幂律分布没有明显的可度量特征，该类网络又被称为无标度网络。

1.复杂网络演化过程。用网络的观点描述客观世界起源于1736年德国数学家欧拉Eular使用图论解决哥尼斯堡

七桥问题。数学家和物理学家在考虑网络的时候，往往只关心节点之间有没有边相连，至于节点到底在什么位置，边是长还是短，是弯曲还是平直，有没有相交等等都是他们不在意的。科学家们认为真实系统各因素之间的关系可以用一些规则的结构表示，例如二维平面上的欧几里德格网，它看起来像是格子体恤衫上的花纹；又如最近邻环网，它总是会让你想到一群手牵着手、围着篝火跳圆圈舞的姑娘。也就是说网络中任意两个节点之间的联系遵循既定的规则。用得最多的规则网络是由N个节点组成的环状网络，网络中每个节点只与它最近的K个节点连接。规则网络的特点就是：每个节点的近邻数目都相同。但是对于大规模网络而言由于其复杂性并不能完全用规则网络来表示。

到了20世纪50年代末，Erdos&Renyi想出了一种新的构造网络的方法，在这种方法下，两个节点之间连边与否不再是确定的事情，而是根据一个概率决定。这是一种完全随机的网络模型，数学家把这样生成的网络叫做随机网络。随机网络ER模型的描述如下：给定网络节点总数N，网络中任意两个节点以概率P连接，生成的网络全体记为G（N，P），构成一个概率空间。由于网络中连线数目是一个随机变量X，取值可以从0到N（N-1）/2。随机网络在接下来的40年里一直被很多科学家认为是描述真实系统最适宜的网络。

规则网络和随机网络是两种极端的情况，随着信息技术的飞速发展，科学家们发现对于大量真实的网络系统而言，他们既不是规则网络，也不是随机网络，而是介于两者之间，具有与前两者皆不同的统计特征的一种复杂网络。

2.复杂网络的统计性质。复杂网络的不同的统计性

质决定了不同的网络内部结构，而结构又决定了系统的功能。所以，我们先了解一下复杂网络的相关统计性质。

（1）度及度分布。在网络中，节点的度是与目标节点相连的边的条数。即与该节点相邻的节点的数目，朋友的个数。而网络的度指网络中所有节点度的平均值。度分布P（k）指网络中一个任意选择的节点，它的度恰好为k的概率。即，不同度数的节点个数占节点总数的比率。

在上面介绍的几种网络中，对于随机网络，当N非常大时，随机网络的节点的度分布近似服从Poisson分布，表达式如下：

P（k）≈e-pN（pN）=e-

k!k!（2）平均路径长度L。在网络中，两点之间的距离为连

k

k

接两点的最短路径上所包含的边的数目。网络的平均路径长度指网络中所有节点对的平均距离，它表明网络中节点间的分离程度，即网络有多小，反映了网络的全局特性。不同的网络结构可赋予L不同的含义。如在疾病传播模型中L可定义为疾病传播时间，交通网络模型中L为站点之间的距离，科学家合作网络中L为交流频率。

随机网络的平均路径长度满足如下表达式：

Lrand≈lnN

ln（3）聚集系数C。在网络中，节点的聚集系数是指与该

节点相邻的所有节点之间连边的数目占这些相邻节点之间最大可能连边数目的比例。而网络的聚集系数则是指网络中所有节点聚集系数的平均值，它表明网络中节点的聚集情况即网络的聚集性，也就是说同一个节点的两个相邻节点仍然是相邻节点的概率有多大，它反映了网络的局部特性。如在疾病传播模型中C可定义为人与人之间的接触密度，交通网络模型中L可定义为站点之间的聚集度，科学家合作网络中L定义为交流集中度等。

随机网络的聚集系数满足如下表达式：

1998年，Watts&Strogatz提出了W-S网络模型，通过以概率p切断规则网络中原始的边并随机选择新的端点重

新连接，构造出一种介于规则网络和随机网络之间的网络———小世界网络（Small-worldNetworks）。显然，当p=0时，相当于各边未动，还是规则网络；当p=1时就成了随机网络。1999年，Barabasi&Albert在Science上发表文章指出，许多实际的复杂网络的连接度分布具有幂律函数形

-99-

■管理创新

■现代管理科学■2010年第9期

Crand=p=

N二、小世界网络概述

1.小世界网络理论。

（1）小世界问题的提出。小世界理论最早提出来源于1967年，哈佛大学社会心理学家斯坦利·米尔格拉姆（StanleyMilgram）作了这样的一个实验，他要求300多人把

他的一封信寄到某市一个“目标”人。于是形成了发信人的链条，链上的每个成员都力图把这封信寄给他们的朋友、家庭成员、商业同事或偶然认识的人，以便尽快到达目标人。实验结果是，一共60个链条最终到达目标人，链条中平均步骤大约为6。人们把这个结果说成“六度分离”并广为传播。现代版本则是，2002年Watts和哥伦比亚大学社会学系合作用E-mail进行了同样实验。而且实验规模也扩展到了全球范围。166个国家6万人，发email给18个目标人。有科学家甚至从这个现象推演出一个可以评估的数学模型。你也许不认识奥巴马，但是在优化的情况下，你只需要通过六个人就可以结识他。“六度分隔”说明了社会中普遍存在一些“弱链接”关系，但是却发挥着非常强大的作用。这个玄妙理论表明“世界真小啊！”，“小世界”由此得名。它引来了数学家、物理学家和电脑科学家纷纷投入研究，结果发现，世界上许多其他的网络也有极相似的结构。比如，人际网络和WWW的架构几乎完全一样，通过超文本链接的网络、经济活动中的商业联系网络、甚至人类脑神经元、以及细胞内的分子交互作用网络，有着完全相同的组织结构。科学家们把这种现象称为小世界效应。（2）小世界原理及网络模型。小世界效应的精确定义还在讨论中，目前有一个较为合理的解释是：若网络中任意两者间的平均距离L随网络节点数N的增加呈对数增长，即L～lnN，当网络中结点数增加很快时，L变化相对缓慢，则称该网络具有小世界效应。

1998年Watts&Strogatz提出了“小世界”网络模型（W-S模型），小世界网络既具有与规则网络类似的分簇特

性，又具有与随机网络类似的较小的平均路径长度，刻画了真实网络所有的大聚簇和短平均路径长度的特性。小世界网络的基本模型是W-S模型，算法描述如下：

（1）给定规则网：假如我们有一个节点总数为N，每个节点与它最近邻的节点K=2k相连线的一维有限规则网，通常要求N>>K>>1。

（2）改写旧连线：以概率p为规则网的每条旧连线重新布线，方法是将该连线的一个端点随机地放到一个新位置上，但需要排除自身到自身的连线和重复连线。

因为不允许重复连线，给定的规则网只有NK2条连

线。重新布线时，依次对每条旧连线选定的某一边的端点随机放置新位置，因此改写的连线数目为pNK2。由于随机

性的缘故，这些改写的连线可能会出现远距离的连线，它们被称为捷径。显然，当p=0时，仍为给定的规则网，当p=

1时，我们将得到一个特殊的随机网。随着p的增加，人们

-100-

可以看到从规则网到随机网的变化。如图1所示。

如图1所示，在规则网络中，p=0，虽然具有很高的集团化系数C，但由于网络结点的增加会破坏原有的网络结构并导致平均特征路径数的明显增加，不符合“L～lnN”的小世界效应条件；在随机网络中，p=1，集团化系数C很小，也不符合小世界网络的定义。因此，规则网络和随机网络都不是小世界网络。

在W-S模型中，p很小，W-S模型中的集团化系数C与规则网络中的值很相近；另一方面，Watts&Strogatz通过数字模拟得出在模型中加入捷径使L下降很快，L与随机网络中的平均距离可比，实现了大世界向小世界的渡越。

W-S模型由于改写连线，有可能出现孤立的集团，而且不便于理论分析。后来Newman和Watts提出了一个改

进的模型。改进模型的算法描述如下：

（1）给定规则网：假如我们有一个节点总数为N，每个节点与它最近邻的节点K=2k相连线的一维有限规则网，通常要求N>>K>>1；

（2）新增随机网：对规则网的N个节点，以概率p在任意两个节点之间连线，但不改动规则网的原有连线，也不允许自身到自身的连线和重复连线。

改进模型实际上是规则网和随机网的叠加，其中增加的捷径总数仍近似为pNK2

。对于足够小的p和很大的N，

改进模型与W-S模型基本等价。

小世界网络因为重新布线，虽然平均度仍然为K，但每个节点的度数不再保持常数。对于Newman&Watts改进的模型，因为每个节点的度数至少为规则网的度数K，而增加的捷径是以概率pKN

连线，因此小世界网络的度分

布形态与随机网的度分布形态相似，都是近似服从对称的泊松分布。表达式如下■N■：

PpKp（c）=

c-K

■N

■c-K

■1-pK

N

■N-c+K

→e-

k

k!其中c≥K。

（3）BA网络模型。W-S模型能够反映现实网络的小世界特征，然而现实世界中的网络还被统计到极少节点拥有大量的连接，而众多的节点仅具有少量连接的特征，这些也无法用随机模型加以合理解释。1999年Barabasi&Albert从动态的、增长的观点研究了复杂网络具有幂律度分布的形成机理，提出了无尺度模型（BA模型）。BA模型的算法描述如下：

（1）初始：开始给定n0个节点；

RegularSmall-worldRandom

P=0P=1图１规则网、小世界网、随机网之间的演化

■2010年第9期■现代管理科学■管理创新

100

10-2

）-4

k10（p10-6

10-8

100

101k

102103图２ＢＡ模型度分布的模拟结果图

（2）增长：在每个时间步重复增加一个新节点和m（m<=n0）条新连线；

（3）择优：新节点按照择优概率

蒹（ki）=ki

Σk

j

j

选择旧节点i与之连线，其中ki是旧节点i的度数。他们在网络的构造中引入了两个重要的网络演化机理：增长性和择优连接性。这是从WWW网实际形成过程中抽象出来的，WWW网时刻都有新网页增加，并且新网页总是喜欢与有名的网页相链接。为了论证这两条网络演化机理不可或缺，他们构造了两个模型：模型A将择优改为随机，则产生增长的随机网络；模型B取消增长，由于网络中节点数保持不变而连线不断增加，最终网络中节点全都相互连线，即演化为完全图。可见两条机理缺任一条都不能生成无标度网络。

由于BA网络本质上属于小世界网络，所以它具有小世界网络的短平均路径长度以及高集聚系数的特性。在

1999年，Barabasi&Albert用数量模拟表明具有k条边的节点的概率服从指数为r=3的幂律分布，表达式为：p（k）∝k-y如图2所示。

2.小世界网络应用研究概述。最早运用小世界理论，

以及目前运用小世界理论最多、最具成效的研究就是疾病传播问题。Watts&Strogatz证明疾病全球传播所需的时间和特征路径长度非常相似，只要在传播网络中加入一些捷径就可以使传播速度明显加快。运用病毒在小世界网络中的传播性质可推出信息在一个平均路径长度为6的网络中传播要比在平均路径长度为一百或一百万的网络中快得多。艾滋病、非典、禽流感等各种传染病等对人类造成巨大的威胁，2003年的“非典”对于宏观经济和人类的生命安全都产生了巨大的负面影响；目前，禽流感也已成为世界关注的一个焦点。于是问题是：在特定的社会网络中传染病如何通过接触关系传播而导致流行呢？决策者如何控制这些疾病将损失降到最低限度呢？从复杂网络的规律有望

寻找到这些问题的合理的答案和解决途径。

研究者运用小世界网络的基本特征分析研究了

Internet上信息传播的特点，发现Internet中的网络平均距离L是随网络大小N对数增长的，它明显具有小世界效应。从结构上看，Internet的实际结构介乎于规则网络和随

机网络，表明其具有小世界效应。同时校园网以及超链接的存在和特性，也表明Internet具有集团化、聚类的特征。其中超链接是“断键重连”也是捷径。于是，人们利用小世界的特性有效地改善了网络信息交流的效率。表现为，利用小世界网络原理减少特征路径长度提高可靠性；重视关键结点的建设来保证网络的鲁棒性和脆弱性并存；利用小世界统计特性控制网络计算机病毒的传播。

小世界网络理论为经济管理领域带来了全新的思路，

人们试图用小世界理论去分析、解释日益繁杂的市场经济问题。该理论为经管问题提供了一种有效的技术工具，大大丰富了企业网络理论的内容和方法。具体表现在，人们用小世界理论研究了NPD（新产品开发）团队交流网络、企业创新网络、产学研合作创新、产业集群内的知识转移等问题。这些研究的共同点在于：使用平均路径长度模拟分析各节点之间的交流频率；使用集团化系数模拟分析各节点之间集聚程度。从而极大的提高各集团的功能，实现资源共享和技术互补。

另外，小世界网络在生物学、物理学及交通管理等方面都有很好的应用，学者们取得了一定的研究成果，利用这些成果可以去更好的规划分析我们的实际生活。

三、总结

网络化是今后若干年许多研究领域发展的一个主流方向，因此对复杂网络的研究具有重大的科学意义和应用价值。复杂网络理论为应用提供坚实的理论与技术基础。2003年8月18日令人震惊的是，北美突然大停电，就是复杂电力网络的一系列级联反应，导致整个电力系统土崩瓦解，美国和加拿大北部部分地区一夜间陷入一片黑暗之中，经济损失和社会影响十分严重。这类网络灾变迫使人们深入研究这种灾变与网络的结构、功能及动力学性质的内在关系。这也是今后我们研究复杂网络的重点所在。

在网络技术的迅猛发展以及各种智能化工具和方法纷纷涌现的今天，相信复杂网络理论会得到更充分的运用和更广泛的发展。

参考文献：

１．郭雷，许晓鸣．复杂网络．上海：上海科技教育出版社，２００６．

２．黄萍，张许杰，刘刚．小世界网络的研究现状与展望．情报杂志，２００７，（４）：６５－６８．

３．周涛，柏文洁，汪秉宏．复杂网络研究概述．物理，２００５，３４（１）：３１－３６．

作者简介：刘晓庆，暨南大学管理学院博士生，广东金融学院计算机科学与技术系讲师；陈仕鸿，广东外语外贸大学思科信息学院讲师。

收稿日期：２００９－１１－１５。

-101-