下载掌阅APP，畅读海量书库
立即打开
图是一种用点与线来描述事物某种联系方式的数学模型。假设存在这样一个无向图 G =（ N , M ），其中 N 是包含 n 个节点非空顶点集， M 是顶点间的连接线段集合。如果集合 N 、 M 中的元素为无向的，故称为无向图，其中图中的边表示各个节点之间的连接关系。把无向图的各边定向之后，就构成了有向图，而有向图中倘若把图中存在的边给予固定数值，这样的网络称为有权网络，反之为无权网络。此外，一个图有可能包含不同种类的节点，用不一样的方式表示出来方便区分。如图2.4所示，罗列了4种网络模型。
图2.4 几种不同的网络类型
最早对复杂网络的研究主要是针对规则网络，图2.5为几种常见的规则网络图（Krause、Frank等，2003）。
图2.5 几种常见的规则网络
由图2.5可知，规则网络包括全连通网络、星形网络、最近邻耦合型网络。其中最特殊的是全连通网络，该网络中每个节点都与另外其他节点相连接，网络存在明显的对称性，而且规则网络的平均路径长度为1，聚类系数为1；星形网络有且只有一个节点与各个节点相连，而其余各个节点彼此之间不存在连接关系，该网络中节点度最大的点为中心节点，其他节点度都要比中心节点小很多，它的平均路径长度为 L =2-2 N ，当 N 趋近于无穷时，此时的平均路径长度 L 趋近于2；最近邻耦合型网络的节点只与它相邻的节点连接，图2.5中是一种特殊的最近邻耦合网络—树形网，这种网络与我们数学中常见到的树状图类似，每到一个节点都会分出2个或者多个节点作为下一次分支的节点，此外对于树形网络，如果分支节点分出的节点个数不固定，它就不是规则网络。
随着人们对网络的深入了解，发现现实存在的网络并不是理想的、规则的网络，而组成网络的节点和边具有随机性。学者们就把这种表现随机性的网络结构称为随机网络，这也是最早人们研究的一种网络模型。也是现实中随处可见的网络。ER模型构造方式是对于 N 个网络节点，每个节点对以概率 p 相连接，得到一个具有 N 个节点、约 pN （ N -1） / 2条边的随机网络。分别以概率 p =0, p =0.1, p =0.2构造随机网络图，如图2.6所示（Granovetter, 1973）。
图2.6 随机网络演化示意图
由节点间连接概率 p 可以看出：
（1）当 p =0时，网络中的每个节点不存在连接关系，所有节点都是相互独立的。
（2）当 p =1时，边的数量为 n （ n -1） / 2，网络是全连通的，网络中每个节点对之间的距离全部为1。
（3）当 p ∈（0, 1）时，网络边的个数介于0到 n （ n -1） / 2范围之间，网络中节点度的平均值为 k = p （ n -1）。
根据上面构建方法可知其节点的度分布可以表示为：
当网络中的节点数目 n 非常大时，每个节点之间的连接边存在或者不存在都是独立的，此时ER随机网络的度分布近似于Poisson分布：
式中，
为网络的平均度。
由图2.6可知，当网络中的节点数 n 接近于无穷大时，式（2.3）和式（2.4）是等价的。所以，ER随机图也称为Poisson随机图。图2.7为节点的度分布。
图2.7 节点的度分布
20世纪中期，专家学者以上述两种模型为研究重点。随着人们对复杂网络的研究发现，虽然随机网络普遍存在，但也不是所有的网络都是完全随机的。有一些实际网络的拓扑结构既不具有规则网络的高聚类特性，也不拥有随机网络的小的平均距离和不大的聚类系数，而是具有较大的聚类系数和较小的平均距离，如表2.2所示（刘霞霞，2008）。
表2.2 实际网络的小世界现象
表中，＜ k ＞表示网络的平均度； L 表示网络的平均路径长度； L rand 表示同等规模网络的平均路径长度； C 表示网络的平均聚类系数； C rand 表示同等规模网络的平均聚类系数。
随着学者们对复杂网络研究的深入，寻找出了一种网络能真实地反映出现实的网络结构特性。Watts和Strogatzt（1998）发现了一种新的网络结构图，通过对相关参数的统计分析发现它具有较小的平均路径长度和较大的聚类系数（Newman, 2002），他们把具有这种现象的网络结构称作小世界网络结构图（WS网络），从此揭开了人们对复杂网络研究的新篇章。
WS网络模型演化过程如图2.8所示（Newman, 2002），由图2.8可知，节点的连接概率 p =0时表示的是完全规则网络，而当 p =1时表示的是随机网络。WS网络模型是根据改变连接概率 p 的大小，从规则网络到随机网络这一过程中演化形成的。
图2.8 WS小世界网络模型的演化
WS小世界模型的构造算法如下（Watts和Strogatz, 1998；黄霞，2009）：
（1）从规则图开始：在一个拥有 N 个节点的最近邻耦合网络，这些节点组成了一个环，其中任意一个节点均同它左右邻接的各 K/ 2个节点相连，其中 K 是偶数。
（2）随机化重连：将用边联系的两个节点中的一个节点位置不变，另一个节点以概率 p 随机连接其他节点。需要注意，网络图中任意两个节点最多只有一条边，且每个节点不能有边同自身连接。
根据上述小世界网络模型的构造可以发现，完全规则网络的节点连接概率和完全随机网络的节点连接概率分别是 p =0和 p =1，通过调节连接概率 p 的值能够使网络从规则网络过渡到随机网络，并得到具有小世界特性的复杂网络。
研究发现，判断一个实际网络是否具有小世界特性，可以把实际网络中的 L 和 C 与具有同样的节点数和边数的随机网络的值 L rand 和 C rand 进行比较（周明，2009），当符合式（2.5）、式（2.6）时，这个实际网络具有小世界特性。
在多种特殊结构被发现之后，人们又发现了一种新的复杂网络：无标度网络（Scale-free network）。
具有小世界特性的网络不仅有较小的平均路径长度，还有较大的聚类系数，与现实存在的网络比较接近，通过对其网络复杂参数分析发现，小世界网络的节点度服从指数分布。但通过大量对现实网络的研究统计结果显示，现实中的网络存在一种与随机网络和小世界网络的度分布都不相同的网络，它存在另外一种特殊的拓扑结构，这类特殊网络的度分布具有幂律形式：
通常情况下，该网络幂指数 γ 取值介于2与3之间。把其度分布具有幂律形式称为网络的无标度特性。
综上所述，通过计算并绘制所研究网络的度分布曲线是否服从幂律分布来判断该网络有没有无标度特性。由于当网络度分布是幂律函数，则满足 p （ k ）∝ k - γ ，并且累积度分布函数符合幂指数为 γ -1的幂律分布（周明，2009）。
1999年，Barabasi和Albert发现现实存在的网络具有一定的特殊性，它们中每个节点的度数不均匀，并且其中会有几个节点度较大的节点，而且这些网络的度分布函数为幂律分布函数。现实中许多网络都具有无标度的特性，例如Network、Citation、Sexual contacts网络等。他们把这样的具有无标度特性的网络模型称为BA网络模型。
复杂网络模型中也有如下两个特点引起了重视（Wang W X, Wang B H.Hu B等，2005）：
（1）增长特性：网络并非是固定不变的，就是说网络的规模是不断扩大的。
（2）优先连接特性：新出现的节点更倾向于与具有较高节点度的节点相连接。这种现象也称为“富者更富（rich get richer）”或者“马太效应（Matthew effect）”。
BA网络模型的增长性和优先连接性能更好地反映实际网络的特性，例如在学术论文网站中，每个星期或者每个月都会产生新的论文，就是BA网络的增长特性；新发表的文章在引用文献时也会选择那些被广泛应用的文献，这就是BA网络的优先连接特性。