下载掌阅APP，畅读海量书库
立即打开
复杂网络的历史与现代图论的发展密不可分。 18 世纪，著名数学家欧拉为解决Konigsberg七桥问题创立了图论。 20 世纪 70年代，著名数学家Erdös和Rényi所提出的随机网络（ ER网络） [124] ，标志着现代图论的进一步发展。 1998 年为解决同步现象中的一个问题，康奈尔大学的Watts博士和Strogatz教授提出了具有小世界特性的随机网络 [125] ，即WS网络。值得注意的是，他们所提出的WS网络成功地解释了“六度分割”定理，进一步推动了图论的发展和复杂网络的兴起。 1999 年，Barabási教授和Albert博士提出了一个网络生成模型（BA网络），解释了大多数真实网络呈现无标度特性的本质原因，即偏好连接 [25] 。 BA网络的提出标志着复杂网络的诞生，引起了海内外学者广泛关注。学者们运用复杂网络这一工具去尝试解决各个领域中的问题，包括计算机网络中的病毒传播和控制、路由策略研究 [3，126-128] ，社会学中革新和行为传播 [12-14，79] ，经济学中的市场营销、股票价格、全球金融危机爆发等系列问题 [16-18] 。在大数据时代，学者们将网络爬虫技术、数据挖掘、现代图论、时间序列分析和统计物理等手段，用于分析真实数据，进一步发现真实网络结构具有多重关系和时空特性 [51，54，56，129，130] ，给复杂网络赋予了新的使命和挑战。
第 2.1.1 节介绍常用描述复杂网络的基本结构参量。第 2.1.2节介绍经典复杂网络生成模型，包括ER网络、WS网络、BA网络和无标度配置网络。
基于图论知识，复杂网络可描述为 G ＝ （ N ， ε ）。其中， N 和 ε 分别表示节点和连边所构成的集合。网络中的节点数量为集合 N 元素的个数，连边数量为集合 ε 元素的个数。运用邻接矩阵 A ，就可描述复杂网络的拓扑特性。其中，元素 A ij 表示节点 i 和 j 之间的连边关系。若存在连边，则 A ij ＝ 1；否则， A ij ＝ 0。
（1）度、度分布和平均度。对于指定节点
i
，它的度大小为
k
i
＝
。节点的度越大，意味着它的邻居数量越多；反之越少。对于整个网络而言，度分布
p
（
k
）表示度为
k
的节点在网络中所占比例。度分布可能是不同的分布形式，如泊松分布、指数分布和幂律分布等。整个网络的平均度
k
max
为节点的最大度。类似地，度分布的
n
阶矩为‹
k
n
›
＝
。利用计算机爬虫技术、数据挖掘和数理统计知识，发现大多数真实网络都是稀疏网络且度分布呈现出胖尾现象，即度分布服从幂率分布、幂率指数截断形式或广延指数分布等
[20，131]
。
（2）边权和权重分布。边权用于表示节点间的强度、负载、流量等
[132，133]
。例如，在科学家合作网络中，边权表示两个作者合作的文章数量
[134，135]
；在通讯网络中，边权代表一对用户在一段时间内的通话时间长度
[136]
；在脑网络中，边权可视为神经元间的记忆加强次数
[137，138]
。权重分布
g
（
w
）是指网络连边的权重分布情况，即随机选择一条边权重为
w
的概率。平均边权为‹
w
›
＝
，
w
max
为最大边权。真实网络的权重分布通常呈现出胖尾形式
[132，133]
。
（3）度关联。度关联是用于刻画连边所连到的两个节点度大小关系，可用Pearson相关系数 [139] 描述为
若 r >0，大度节点更倾向于连向大度节点；若 r <0，大度节点以更大的概率与小度节点相连；若 r ＝ 0，节点随机连接。在真实网络中，学者们统计发现科技网络（如万维网、因特网、交通网络等）呈现出负关联，而社会网络（如Twitter、Facebook、电子邮件等）呈现出正关联 [130，132，139] 。
（4）集群系数。集群系数用于衡量节点的两个邻居存在连边的概率。换句话说，集群系数描述的是朋友的朋友也是朋友的概率。节点 i 的集群系数是指，实际连接三角形个数 t i 与可能存在三角形个数的比值，表达式为
对于整个网络而言，集群系数为
对于真实社会网络，学者们发现集群系数 c 很大 [48] 。因为，社会系统中需要维持社会平衡。
（5）网络直径和平均距离。即节点 i 和节点 j 之间最短路径长度为 d ij 。平均距离是指任意两个节点最短路径长度的平均值。网络直径 D 是指任意两个节点最短路径的最大值。若平均距离很短，意味着网络具有小世界特性。 ER网络、WS网络、BA网络和真实网络都具有小世界特性。
（6）模块度。模块度是用于刻画网络的中尺度社区结构的一个重要指标，其表达式 [140，141] 为
其中， δ 为Kronecker函数， c i 和 c j 分别表示节点 i 和 j 所属的社区。模块度 Q 越大，网络社区结构越明显；相反，社区结构越不明显。
自复杂网络诞生至今，已有众多经典的网络模型用于构建具有某些指定特性的网络 [51，54，56，130] 。本节介绍 4 个经典网络模型：ER网络、WS网络、BA网络和无关联配置网络。
（1）ER网络。 ER网络是由Erdös和Rényi两位著名数学家提出的 [124] 。 ER网络构造极其简单，其过程为：
（i）指定网络规模为 N ；
（ii）每一对节点以概率 p 构建连边。
ER网络的度分布为
。当
N
很大且
p
很小时，E R 网络的度分布为泊松分布，即
。平均度‹
k
› ＝
p
（
N
－1）≈
pN
，集群系数
c
＝
p
。
（2）WS网络。 1998 年，Watts博士和Strogatz教授提出了经典的WS小世界网络模型 [125] 。 WS网络具有两个与真实网络相吻合的重要特性：小世界和高集群系数。 WS网络生成方法如下：
（i）指定网络大小 N ，平均度‹ k ›；
（ii）生成环状网络，即每个节点与它的左右‹ k › /2 个邻居相连；
（iii）断边重连，每条边首先以 p 的概率断开。值得注意的是，每条边的一个端点保持不变，另外一个端点在网络中随机选择一个节点连接。重连时不允许重边和自环的出现。
图2-1（a）—（c）给出了不同重连概率 p 时，WS网络示意图。当 p ＝ 0 时，网络为规则网络[图 2-1（ a）]，集群系数和平均距离都较大；当 p 较大时，网络同时具有小世界和高集群系数特性[图 2-1（b）]；当 p 很大时，网络为随机网络，仅具有小世界特性[图 2-1（c）]。集群系数和平均距离随 p 的变化如图 2-1（d）所示。
图2-1 WS网络演化图及其拓扑特性[ 142 ]
（3）BA网络。 BA网络由Barabási教授和Albert博士提出，它标志着复杂网络的诞生 [25] 。 BA网络是一个偏好增长模型，能重现真实网络的无标度和小世界特性，其构建过程如下：
（i）初始时刻为 m 0 个节点所构成的完全图；
（ii）每个时刻，添加度为
m
<
m
0
的节点，每条边偏好连接到节点
i
的概率为
；
（iii）重复第（ii）步，直到网络中有 N 个节点为止。
BA网络的度分布 p （ k ） ~ k －3 如图 2-2 所示。
图2-2 BA网络度分布[ 130 ]
（4）无关联配置网络。 Catanzaro等提出了无关联配置网络 [143] 。利用无关联配置网络，可以生成指定任意度分布的网络。无关联配置网络生成方法如下：
（i）指定网络大小 N 和度分布形式 p （ k ）；
（ii）根据度分布给每个节点 i 赋予大小为 k i 的度，并给节点 i 赋予与度大小相同的半桩数量；
（iii）随机选择两个半桩来构成一条连边，且不允许重边和自环的出现；
（iv）重复第（iii）步，直到网络中没有剩余半桩为止。
在热力学极限下（即 N →∞ ），基于上述方法生成的网络不存在度关联。当度分布为Dirac-Delta函数时（即所有节点度大小都相同），网络称为随机规则网络；当度分布为幂率形式时，网络称为无标度网络。