1.2 复杂网络的结构特征及其拓扑模型

从数学描述的角度看，网络可以用图这个概念进行描述：节点可看作系统的基本个体，边可以描述节点间的相互作用。其实，早在18世纪人们就尝试用网络来描述真实系统，并在随后的两百多年里认为规则图和随机图是描述真实网络的恰当表示。直到20世纪末，计算机数据采集处理和运算能力得到飞速发展，科学家们发现大量的现实网络具有与规则图和随机图皆不相同的统计特征，并将其称为复杂网络。Watts和Strogatz在1995年提出的小世界网络与Barabási和Azbert在1999年提出的无标度网络揭示了不同真实网络具有普遍的、非平凡的特性，被公认为复杂网络研究的两项开创性工作。这两项工作彻底颠覆了人们对真实世界网络的传统认识，掀起了复杂网络研究的热潮。众多复杂系统诸如互联网、万维网、人际关系网络、科研合作网络、电力网、交通网络、新陈代谢网络、基因调控网络、疾病传播网络等都采用复杂网络进行研究并取得了可喜的阶段性成果，复杂网络也成为一种描述和理解复杂系统的重要方法。

1.2.1 复杂网络的特征度量

现实中的复杂系统往往因其个体差异和系统结构等不同而成为独一无二的，由此抽象的网络也被理所当然地认为互不相同。然而，一个令人惊讶的结果是大部分真实网络尽管具体的拓扑结构不尽相同，但不约而同地表现出共通的统计性质，最具典型意义的是小世界效应（small-world effect）和无标度特性（scale-free feature）。这两个特征的定义均采用了不同于传统的特征度量进行描述，下面介绍几种主要的复杂网络的特征度量。

（1）网络的图表示

网络的图（graph）表示，就是用抽象的点表示网络中的节点，用点之间的连线表示网络中节点之间的相互关系。从图论的观点来看，一个具体网络可抽象为由一个点集V和边集E组成的图G=（V, E），其中节点数记为N=|V|，边数记为M=|E|。若点对（i, j）与（j, i）对应同一条边，则为无向网络（undi-rected network），否则为有向网络（directed network）；若按照不同的性质，如速度、类别等，节点i与节点j之间对应着两条及两条以上的边，则为多重边网络（multi-link network），否则称为单重边网络（single link network）；若每条边都有各自相应的权值即为加权网络（weighted network），否则为无权网络（unweighted network）。当然，无权网络也可以看作是每条边的权值都为1的等权网络。此外，一个网络中还可能包含不同类型的节点，如在社会关系网络中可以用权表示两个人的熟悉程度，而不同类型的节点可以代表具有不同国籍、地区、年龄、性别和收入的人。本书重点介绍的是有向、加权、多重边复杂网络的同步分析与控制。

（2）平均路径长度

网络中两个节点i和j之间的距离dij，定义为连接这两个节点的最短路径上的边数。特别地，网络中任意两个节点之间距离的最大值称为网络的直径，记为D，即：

网络的平均路径长度L定义为两个节点之间的距离的平均值，即：

其中N是网络的节点数。网络的平均路径长度描述了网络中节点的分离程度。对真实网络平均路径长度的计算，揭示了网络的“小世界（small-world）特性”，比如说具有十几亿个节点的万维网，其平均路径长度不到20。

（3）聚类系数

社会网络的一个共同特征是聚类特性，比如在朋友关系网络中，一个人的两个朋友很可能彼此也是朋友。网络的这一特性可以用聚类系数来定量描述，假设网络的一个节点i有ki条边将它和其他节点相连，所连接的ki个节点被称为节点i的邻居。这ki个节点间实际存在的边数Ei和可能的总边数之比为节点i的聚类系数Ci，即：

整个网络的聚类系数C就是网络中所有节点的聚类系数的平均值，即：

显然，0≤C≤1。C=0当且仅当网络中所有节点均为孤立节点，即没有任何连接边；C=1时，网络是全局耦合的，即网络中任意两个节点都直接相连。对于一个含有N个节点的完全随机网络，当N很大时，C=O（N-1）。而许多大规模的实际网络都具有明显的聚类效应，它们的聚类系数尽管远小于1但却比O（N-1）要大得多。事实上，在许多类型的网络（如社会关系网络）中，你朋友的朋友同时也是你的朋友的概率会随着网络规模的增加而趋向于某个非零常数，即当N→∞时，C=O（1）。这意味着这些实际的复杂网络并不是完全随机的，而是在某种程度上具有类似于社会关系网络中“物以类聚，人以群分”的特性。

（4）度与度分布

节点i的度（degree）ki为与该节点连接的其他节点的数目。有向网络中节点的度分为入度（in-degree）和出度（out-degree），节点的入度为从其他节点指向该节点的边数，出度为从该节点指向其他节点的边数。直观上看，一个节点的度越大就意味着这个节点在某种意义上越“重要”。网络中所有节点的度的平均值为网络的平均度，记为〈k〉。网络中节点的度的分布情况可以用函数P（k）来描述，表示一个随机选定的节点的度恰好为k的概率。

对于规则的格子网络，所有的节点具有相同的度，度分布为Delta尖峰分布。网络中任何随机性连接的引入都会使这个尖峰变宽，完全随机网络的度的分布近似为Poisson分布，如图1.1（a），分布曲线在远离峰值〈k〉处为指数下降。当k≫〈k〉时，度为k的节点概率极小，实际上是不存在的，这类网络为均匀网络（homogeneous network）。

现实中很多网络的度分布明显不同于Poisson分布而可以用幂律形式P（k）∝k-γ来描述，如图1.1（b），被称为无标度（scale-free）分布。幂律分布曲线比Possion指数分布曲线下降要缓慢得多。在无标度网络中，绝大多数节点的度相对很低，而少量节点的度相对很高，因此这类网络为非均匀网络（inhomoge-neous network），那些度数很高的节点成为网络的“集线器”（hub）。

1.2.2 网络拓扑基本模型

人们早在两百多年前就意识到可以用网络来描述真实系统，并坚定地将这一想法付诸于行动。从18世纪欧拉解决康尼斯堡（Konigsberg）七桥问题创立图论到随机网络的提出，再到20世纪末复杂网络的兴起，所有的这些都是人们为不断地认识和探索世界而做出的努力。本部分将就涉及的四种典型网络模型及近期人们研究的一些推广模型作简要介绍与评述。

（1）规则网络

规则网络（regular network）中节点之间的边是完全按照确定性的连接规则而生成，如全局耦合网络（global coupled network）、最近邻耦合网络（nearest-neighbor coupled network）、星型耦合网络（star coupled network）等（如图1.2所示）都是常见的规则网络模型。此类网络的共同点就是具有有序的网络结构，分析起来比较方便，并且有助于人工网络的实现和控制，不过，大多数现实网络都具有随机连接的边，因此，规则网络并不能很好地描述现实生活中的实际网络。

（2）ER随机图

最典型的随机网络模型（random network model）是由匈牙利数学家P. Erdös和A. Rényi提出的ER模型，如图1.3（a）所示。其定义为：在图中的N个节点间，随机连接n条边形成的随机网络，记为GN,n，由N个节点，n条边组成的网络共有种，构成一个概率空间，每一个网络出现的概率是相等的。后来，人们又提出另一种与ER模型等价的随机网络模型——二项式模型，其定义为：给定的节点数目N固定不变，假定任意节点对之间有边连接的概率为p，形成的网络记为GN,p，其节点数目为N，边数期望值为pN（N-1）/2。

ER随机图的主要特点是：平均度为〈k〉=p（N-1）≈pN，平均路径长度LER～ lnN/ln〈k〉，度分布P（k）服从Poisson分布且峰值取度平均值，每个节点有大致相同数目的度，如图1.3（b）所示。ER随机图中两个节点之间的连接概率均为p，因此其聚类系数为C=p=〈k〉/N，从这可以看出大规模的稀疏ER随机图不具有聚类性质，它的平均路径长度和聚类系数都比较小。到目前为止，ER模型在很多领域中仍然被广泛应用，而且充当了一些其他模型和经验研究的基点。随机图和规则图之间最大的区别在于前者引入了随机的内容，使得图的空间变得更大，其数学性质也发生了根本的变化。ER随机图在理论上已经研究得比较透彻了，不过这种网络只考虑随机因素，并没有蕴含实际网络中普遍存在的确定性，所以与实际网络相比还是有很大的缺陷。接来下介绍的小世界网络，就弥补了这个不足。

（3）小世界网络

随着计算机数值运算与存储能力的提高，科学家们发现大量的实际网络既不是规则网络，也不是随机网络，而是具有与前两者皆不相同的拓扑特征的网络——小世界网络（small-world network）。小世界网络并非是一个固定的模型，而是一类具有较高的平均聚类系数和较小的平均路径长度的网络模型的统称。关于小世界现象，最著名的实验是社会学家斯坦利·米尔格拉姆（Stanley Mil-gram）关于“六度分离”（six degrees of separation）现象的研究。这个实验表明，地球上任何一个人平均可通过六个认识的人找到任一想找的人。小世界特征存在于大部分的真实网络模型中，比如人际关系网络、大脑神经网络、疾病的传播网络、电力网、经济网以及我们现在所处的互联网等。此类模型中，最有影响力的就是由Watts和Strogatz提出的WS小世界模型。其构造方法是：首先，生成一个网络规模为N、邻居节点数为κ的近邻耦合网络，其中N≫κ≫log（N）≫1；然后，以概率p重新连接网络中的每条边，并确保无重复连接和自连接情况，这样就构成了WS小世界网络。图1.4显示了调节重连概率p从0变化到1，而网络模型从规则网络到WS小世界网络再到完全随机网络的演化过程：当p=0时，网络是规则的近邻耦合网络；p的增加使得网络中存在一些“捷径（shortcut）”，这些捷径的存在使得网络的平均路径长度显著降低，但由于大部分的边还是连接到近邻节点，所以网络的聚类系数依然保持很大；当p=1时，网络变为完全随机网络。图1.5画出了网络的平均路径长度L（p）和聚类系数C（p）随机重连概率p的变化规律，可以看到p在大约0.001到0.1的范围内变化，网络的平均路径长度很小，但聚类系数依然保持很大，我们称在这个范围内的网络为小世界网络。小世界特性是对众多真实复杂网络统计出来的最重要的共通特性之一，Watts和Strogatz的开创性工作掀起了对小世界特征形成机制的热烈讨论。

此外，还有另一个备受关注的由Newman和Watts提出的NW小世界模型，与WS小世界网络不同的是，在构造这个网络模型时，随机加边策略代替了边的重连机制，即对于已经生成的规则网络，以概率p随机选择两个节点增加一条连边。当p=0时，NW小世界模型退化为平均聚类系数高、平均路径长度大的完全规则网络；当p=1时，其变成平均聚类系数低、平均路径长度小的完全随机网络。在理论分析上，NW小世界模型要比WS小世界模型简单一些。当p足够小和N足够大时，NW小世界模型本质上等同于WS小世界模型。

（4）无标度网络

ER随机图模型和WS小世界网络模型的度分布都可近似用Poission分布来表示，这与现实中许多真实网络并不相符，因此，仅仅考虑用小世界特征来刻画现实网络显然还存在一定的局限性。为了探索万维网的规律，1999年，Barabási和Albert通过追踪一个由325729个节点组成的万维网动态演化过程，发现万维网具有大规模的高度自组织特性，万维网除了具有小世界网络的较短平均路径之外，还具有一个重要的特性：其节点度服从幂律分布，如图1.6（b），由于这类网络的节点的连接度没有明显的特征度量，故称之为无标度网络，如图1.6（a）。随后，无标度特性在众多现实网络中得到证实。Barabási和Albert认为，形成无标度特性的根本原因在于，网络的不断生长和新增加节点的择优连接。基于这两个要素，他们构建了一个无标度网络模型（简称BA网络模型）。该网络的生成过程是：从一全连通的网络出发，每一时刻网络增加m个节点，并与网络中存在的节点进行连接。当选择网络中的节点与新节点连接时，连接概率与被选节点的度成正比，这就是择优连接。BA网络演化的稳定态具有以下性质：节点度服从幂指数为3的幂律分布，平均路径长度和聚类系数都很小，Barabási等人利用平均场论方法分析地证明了这一结论。最近，Hou等人从数学的角度出发，利用马氏链方法证明了BA无标度网络的幂率度分布概率密度p（k）的存在（收敛）性。

事实上，BA无标度网络考虑的增长和择优机制都是线性的，而在现实网络中，肯定存在更加复杂的网络演化机制，如非线性增长和择优、节点和边的消亡等。为此，一系列不同的包含更多现实网络特征的无标度网络相继出现，它们的幂指数大都在1和3之间。

具有这种无标度性质的网络是不均匀的，因为绝大部分节点的度都很小，只有一小部分节点（Hub节点）的度很大，这就导致了无标度网络一个比较普遍的性质——对随机故障的鲁棒性和对恶意攻击的脆弱性。

（5）推广模型

已有网络模型的建立，为人类进一步科学地认识复杂网络的结构和研究其上的动力学打下了基础并构建了框架。为了更加客观、全面地描述复杂网络的结构，在原有模型的基础上，也相继出现了一系列推广的模型。例如，Yook等人在BA无标度网络的基础上，为每条边给予权重，从而得到加权的无标度网络。利用等级结构这一确定性的网络生成方式，实现一种新的无标度网络，它的度分布服从p（k）～。Li和Chen提出了一种新颖的局域世界进化网络模型，它是介于指数网络与幂律网络之间的一种过渡网络模型，而BA无标度网络仅仅是它的一个特例，此网络在保持鲁棒性的同时，提高了网络抵抗攻击的能力。最近，Small等人构造了一种具有同配性且度分布可以事先给定的无标度网络模型，他们发现，不具有度相关（同配性系数为零）的无标度网络是超小世界网络（平均路径长度很小），而具有度相关的无标度网络不一定是小世界网络，因为此时网络的平均路径长度可以很大，甚至可能与网络大小呈现出线性增长关系。