1.2 复杂网络

一般来说，人们通常将具有自组织、自相似、小世界、无标度等性质的网络称为复杂网络。从代数图论的角度来看，由大量节点和连接节点间的边所构成的复杂的综合体可称为复杂网络。在研究现实网络时，我们可把真实的个体视为网络的节点，用连接节点间的边来体现个体之间的相互关系，如此便可以把真实的网络转化成复杂网络来研究。

1.2.1 复杂网络的发展历程

七桥问题是研究网络图论的起源。该问题来自柯尼斯堡（Königsberg）镇，该镇中有七座桥，镇上的人们有这样一个问题：一个人能否在一次散步中在每座桥都只经过一次的情况下走过所有七座桥，并最后返回原地？该问题困扰了无数人，直到1736年，欧拉才将其数学化并给出了严格的证明。

20世纪60年代，匈牙利数学家Erdos和Renyi发表了名为On the evolution of random graphs的著名论文^[1]，提出了随机图理论，建立了ER模型，被认为是创立随机网络理论系统性研究的开端。用随机图来描述网络拓扑结构，为复杂网络理论的研究奠定了数学基础，是复杂网络研究的一个重要突破。

1998年6月，美国康奈尔大学理论和应用力学系的博士生Watts及其导师、非线性动力学专家Strogatz教授在Nature杂志上发表了题为《“小世界”网络的集体动力学》（Collective dynamics of“small-world”networks）的文章，这是复杂网络研究新纪元开始的标志之一^[2]。在该文中，他们提出了一种融合了随机网络和规则网络优点的“小世界”（small-world）模型，更能反映实际网络系统。

1999年10月，美国圣母大学物理系的Barabási教授及其博士生Albert在Science杂志上发表题为《随机网络中标度的涌现》（Emergence of Scaling in Random Networks）的文章，提出了一个无标度网络模型——BA模型^[3]。他们认为以前的许多网络模型都没有考虑到实际网络的两个重要特性：（1）增长特性，即网络的规模是不断扩大的；（2）优先连接特性，即新的节点更倾向于与那些具有较高连接度的大节点相连接。无标度网络的发现为复杂网络的研究开辟了一条崭新的道路，这是人们首次从变化的角度来研究复杂网络的开放性和复杂性。

研究表明，许多真实世界网络既不是规则网络，也不是随机网络，而是兼具小世界和无标度特性，具有与规则网络和随机图完全不同的统计特性。小世界网络和无标度网络的发现，使复杂网络研究进入了一个新的时代，复杂网络成为一门全新的学科，受到了广泛关注^[4-8]。开展复杂网络的研究可帮助人们更好地了解真实世界的复杂网络，从而为设计具有良好性能的网络提供重要的理论依据。同时，复杂网络研究的理论成果还会被广泛地应用于社会、物理、生物等各个学科领域。例如，通过构建人与人之间的关系网络模型来研究传染病在人群当中的流行、谣言在社会中的扩散，从而寻找出能控制该行为的有效方法等。

1.2.2 复杂网络的结构特征

从实际背景出发，我们可将网络看成由具有一定特征和功能的个体通过个体之间的相互作用组成的集合体，通常把个体视为网络的节点，把个体之间的相互作用视为网络节点之间的连接，也可称为边。根据不同的研究角度，可以将复杂系统抽象成由相互作用的子系统组成的网络，节点代表复杂系统的子系统，边代表子系统之间的相互作用。因此，复杂网络就可以认为是复杂系统的高度抽象化。

复杂网络可用图论的语言和符号加以精确的描述。从图论的观点看，网络是由边相连接的众多节点所构成的具有一定状态和功能的图，即网络就是一个由节点集和边集所构成的图。边集中的每条边都有节点集的一对节点与之对应，其中的节点即表示系统中的基本单元，边可以用来表示节点间相互作用的关系。例如在因特网中，可以用节点来表示路由器，用边来表示连接它们的电缆线。

根据图论可知，一个具体的网络可抽象为由点集V={1，2，…，N}和边集E⊆V×V组成的图G=（V，E，A）。其中，矩阵A=（a_ij）是描述节点和边之间关系的连接矩阵^[9]。任意一个有N个节点的网络可以用一个N×N的连接矩阵A来表示，如果网络中存在一条边从节点i指向节点j，则a_ij≠0，否则a_ij=0。在网络的图表示中，如果网络是连通的，即网络中没有所谓的孤立节点，那么对应的连接矩阵为不可约矩阵。如果网络中所有的节点对是有顺序的，可将网络称为有向网络，否则称为无向网络。对于无向网络来说，A为对称矩阵。对于有向网络来说，A为非对称矩阵。如果无向网络中的两个节点有边相连接，那么a_ij=1，否则a_ij=0。如果人为地给网络中的每条边都赋予不同的权值，那么可称该网络为加权网络，否则称为无权网络。对于加权网络，它的连接矩阵的元素a_ij表示的是节点i和节点j之间权值的大小。

一般来说，实际的网络系统由于节点数目多，连接结构复杂，常规的方法难以给出理想的理论刻画，运用高性能计算机对网络进行统计分析是当前主要方法。近年来，为了反映不同网络的拓扑结构特征，人们在刻画网络结构的统计特性上主要使用平均路径长度、聚类系数和度分布三个概念。

1.平均路径长度

复杂网络中两个节点i和j之间的距离d_ij定义为连接两个节点的最短路径所含有的边数。任意两个节点之间的距离的最大值称为该网络的直径，记为D，即

网络的平均路径长度L定义为任意两个节点之间的距离的平均值，假设网络的节点数为N，那么计算平均路径长度的常用公式为

网络的平均路径长度可以用来描述网络节点的分离程度。研究表明，尽管许多实际的复杂网络的节点数目非常大，但它们的平均路径长度却非常小。对于不连通的网络，由于存在不连通的节点对，所以它们之间的距离无穷大，D和L也无穷大。为了避免这一问题，通常可以定义L为所有连通的节点对之间的平均最短距离，D为所有组元的直径的最大值。

2.聚类系数

聚类系数主要用来描述网络的聚类特性。假设节点i连接着k_i条边，并通过这些边连接到网络中k_i个其他的节点，这k_i个节点就可以认为是节点i的邻居。很明显，最多可以有k_i（k_i-1）/2条边与节点i相连接。节点i的聚类系数定义为在这k_i个节点中实际与节点i 相连接的边数E_i与总的可能的边数k_i（k_i-1）/2之比，即

假设网络的节点数为N，那么网络的聚类系数C就是网络中所有节点的聚类系数的平均值，即

显然，0＜C＜1。当且仅当网络中所有节点为孤立点时，C=0。对于一个具有N个节点的随机网络，当N很大时，C=O（1/N）。而在许多大规模的实际网络中，C尽管小于1，但通常远大于1/N，这就意味着某些实际的复杂网络并不是完全随机的，它们具有明显的聚类效应。

3.度和度分布

节点的度是网络中单个节点的属性中简单而又重要的概念，它表示的是一个节点连接的其他节点的数目，即与该节点相连接的边的数目。在无向网络中，节点的度定义为与该节点连接的其他节点的数目，但在有向网络中存在入度和出度两种概念。节点的出度为从该节点出发指向其他节点的边的数目，节点的入度为从其他节点指向该节点的边的数目。直观来看，一个节点的度越大往往意味着这个节点越重要。网络中所有节点的度的平均值称为网络的平均度，记为＜k＞。通常用分布函数P（k）来描述网络中节点的度的分布情况，表示一个随机选定的节点的度为k的概率。

深刻理解复杂网络的结构特征，可以帮助我们从不同角度去理解网络的特性，这对于进一步研究复杂网络的模型并利用模型解决实际问题是非常重要的。

1.2.3 复杂网络的基本模型

一般而言，根据复杂网络的不同拓扑结构，复杂网络通常可以分为星形网络、全局耦合网络、最近邻网络等规则网络模型，以及随机网络、小世界网络、无标度网络等不规则网络模型。下面就分别简单介绍这六种典型网络模型及其拓扑特征。

1.星形网络

星形网络是一类比较特殊的网络，该类网络有且只有一个中心节点，其他所有的节点都与这个中心节点相连，而非中心节点之间彼此互不相连。星形网络有一些比较显著的特点，例如当网络节点数N→∞时，它的平均路径长度L=2，聚类系数C=1。需要说明的是，这里假设一个节点如果只有一个邻居节点，那么该节点的聚类系数定义为1。然而，在有些文献中则定义只有一个邻居节点的聚类系数是0。按照这个定义，星形网络的聚类系数则为0。

2.全局耦合网络

全局耦合网络是指该网络中的每个节点都与其他所有的节点相连，通常也可以称为完全网络。因此，在具有相同节点数的所有网络中，全局耦合网络具有最小的平均路径长度L=1和最大的聚类系数C=1。虽然全局耦合网络模型反映了许多实际网络具有的聚类和小世界等性质，但该模型作为实际网络模型的局限性也是很明显的：一个具有N个节点的全局耦合网络有N（N-1）/2条边，但大多数大型实际网络都是非常稀疏的，它们的边数一般最多是O（N），而不是O（N²）。该网络所有节点的度都相等，它是一个完全均匀的网络。

3.最近邻网络

在真实的规则网络中，星形网络和全局耦合网络是非常特殊的情况，因此最近邻耦合的规则网络具有更重要的研究价值。对于最近邻网络来说，它的N个节点围成一个环，其中每个节点都与它左右各K/2个邻居节点相连（K是一个偶数），这样就形成了一个最近邻网络。最近邻网络中的各个节点的度都是K，从度分布的角度来说，最近邻网络是一种完全均匀的网络。对于较大的K值，最近邻网络的聚类系数为C=3（K-2）/4（K-1）≈3/4，因此，这类网络可以看成是高度聚类的。当最近邻网络的节点数很大时，网络的平均路径长度也是非常大的，特别是当N→∞时，平均距离也趋于无穷大，所以最近邻网络不具有小世界性质。这可以帮助我们从侧面理解为什么在这样一个局部耦合的网络中很难实现全局的动态过程（如同步化过程）。

4.随机网络

1960年，Erdos和Renyi首次将随机性引入网络研究中，提出了著名的随机网络模型（简称为ER模型）。其基本思想是：考虑N个节点，每对节点之间以概率p相连接，这样就可以得到一个有N个节点、pN （N-1）/2条边的ER随机图。ER随机图的主要特点是：度分布为正态分布且峰值取平均值，每个节点有大致相同的度。到目前为止，ER模型仍被广泛研究，在很多领域中被广泛应用，而且是研究其他网络模型的基础。

5.小世界网络

经过大量的实例，研究者们发现许多现实网络既不能看成随机网络，也不能看成规则网络。1998年，Watts和Strogatz提出了单参数的小世界网络模型（称为WS模型）。对WS模型可以简单描述如下：考虑具有N个节点的最近邻网络，每个节点与它左右各k/2个邻居节点相连接（k为偶数），然后以概率p随机地重新连接网络中的每条边，其中任意两个节点不能连接两次且一个节点并不能与其自身相连接。如果p=0，那么该网络就对应于原来的最近邻网络；如果p=1，那么该网络对应于完全随机网络。我们通过调节p的值就可以控制从完全规则网络到完全随机网络的过渡。从这个角度上来看，小世界网络模型在规则网络模型和随机网络模型之间架起了桥梁。同时，WS模型也可以看成所有节点的度都近似相等的均匀耦合网络。

1999年，Newman和Watts对原始的WS模型进行改进后形成了NW模型。该模型是在原来最近邻网络的基础上，以概率p随机地给一对节点添加一条边，要求任意两个节点不能连接两次且任意一个节点不能与其自身相连接。随着节点数目的增加，NW模型和WS模型展示了从“大世界”（平均路径长度线性增长）到“小世界”（平均路径长度对数增长）的演变。当p 足够小而节点数N 足够大时，NW模型与WS模型是一致或等价的。因为NW模型总是连通的，而WS模型有可能不连通，所以NW模型比WS模型更易于做理论研究分析。

6.无标度网络

近年来，大量的研究成果表明许多大型网络节点的连接度没有明显的特征标度，而节点的连接度分布具有幂律形式。1999年，Barabási和Albert首先将这个特性称为无标度（Scale-free）分布，从而提出了一类无标度网络模型，也称为BA模型^[3]。该网络模型考虑了现实网络的两个显著特征：

（1）大多数实际网络是不断通过增加新节点而增长的开放系统，这是所谓的网络增长性。

（2）在产生新连接时，大多数实际网络呈现出择优连接迹象，这是所谓的倾向性选择，即连接到某个节点的可能性与该节点的度有关。

对无标度网络的具体描述如下：从具有较少节点数的节点n₀开始，经过每个时间间隔就增添一个具有n（n≤n₀ ）条边的新节点，并且连接到n个已经存在于网络中的节点上。在新节点选择连接节点的时候，新节点将会连接到节点i的概率p正比于该节点的度k_i，即。经过时间t 以后，该模型产生一个具有N=n₀+t、nt条边的无标度网络。

深入研究复杂网络模型的特点和性质，可以帮助人们进一步了解现实网络系统，增加对现实网络的理解，以便更好地将网络知识应用于实际生产、生活中。