复杂网络基础理论3

复杂网络基础理论第三章网络机制模型第三章网络机制模型3.1引言3.2规则网络3.3随机网络3.4小世界网络3.5无标度网络3.6层次网络3.7确定性网络3.8自相似网络23.1引言复杂网络的研究大致可以描述为三个密切相关但又依次深入的方面：①大量的真实网络的实证研究，分析真实网络的统计特性；②构建符合真实网络统计性质的网络演化模型，研究网络的形成机制和内在机理；③研究网络上的动力学行为，如网络的鲁棒性和同步能力，网络的拥塞及网络上的传播行为等。本章针对第二个方面，以得知网络模型需如何构成才会展现这些特定的统计性质。33.1引言每一种网络系统都有其自身的特殊机制，有其自身的演化机制，但由于都可以使用网络分析的方法进行分析，所以也有其共性。研究网络的集合性质、网络的形成机制、网络演化的统计规律、网络上的模型性质以及网络的结构稳定性，并把它与现实系统结合起来加以研究比较是复杂网络研究的主要任务。4返回目录3.2规则网络3.2.1全局耦合网络3.2.2最近邻耦合网络3.2.3星型耦合网络53.2.1全局耦合网络1.概念全局耦合网络是指任意两个节点之间都有边相连的网络，也称完全图。对于无向网络来说，节点数为N的全局耦合网络拥有N（N－1）／2条边，如下图所示；而对于有向网络来说，节点数为N的全局耦合网络拥有N（N－1）条弧。63.2.1全局耦合网络2.特性各节点的度均为N－1，因此度分布为单尖峰，可以表示为Delta函数P（k）＝δ（k－N＋1）。每个节点vi的集聚系数均为Ci＝1，故整个网络的集聚系数为C＝1。从任意一个节点到另外一个节点的最短路径长度都为1，故整个网络的平均距离为L＝1。在具有相同节点数的所有网络中，全局耦合网络具有最小的平均距离和最大的集聚系数。该模型作为实际网络模型的局限性很明显：全局耦合网络是最稠密的网络，然而大多数大型实际网络都是很稀疏的，它们边的数目一般至多是O（N）而不是O（N2）。73.2.2最近邻耦合网络1.概念对于拥有N的节点的网络来讲，通常将每个节点只与它最近的K个邻居节点连接的网络称为最近邻耦合网络，这里K是小于等于N－1的整数。若每个节点只与最近的2个邻居节点相连，这样所有节点相连就构成了一维链或环，如下图（a）所示。如下图（b）所示的二维晶格也是一种最近邻耦合网络。一般情况下，一个具有周期边界条件的最近邻耦合网络包含N个围成一个环的节点，其中每个节点都与它左右各K／2个邻居节点相连，这里K是偶数，如下图（c）所示。83.2.2最近邻耦合网络2.特性每个节点vi的度均为K，因此度分布为单尖峰，可以表示为Delta函数P（k）＝δ（k－K）。最近邻耦合网络的平均集聚系数就是每个节点的集聚系数：C＝Ci＝3（K－2）／［4（K－1）］。对较大K值，容易得到C≈0.75。可见，最近邻耦合网络集聚程度还是很高的。最近邻耦合网络不是小世界网络，因为对固定K值，该网络直径D和平均距离L分别为D=N／K，L≈N／（2K）。当N→∞，L→∞。93.2.2最近邻耦合网络【例3.1】用Matlab程序绘制最近邻耦合网络，并给出具体程序代码。解：（1）最近邻耦合网络绘制的Matlab程序如下：103.2.2最近邻耦合网络113.2.2最近邻耦合网络（2）当N＝20，K＝6时，该程序的仿真结果如下图所示。123.2.3星型耦合网络1.概念星形耦合网络，它有一个中心点，其余的N－1个点都只与这个中心点连接，而彼此之间不连接，如下图所示。133.2.3星型耦合网络2.特性中心节点的度为N－1，而其它节点的度均为1，所以星型耦合网络的度分布可以描述为如下函数星形网络的平均距离为L＝2－2／N。当N→∞，L→2。假设定义一个节点只有一个邻居节点时，其集聚系数为1，则中心节点的集聚系数为0，而其余N－1个节点的集聚系数均为1，所以整个网络的平均集聚系数为C＝（N－1）／N。当N→∞，C→1。由此可见，星型耦合网络是比较特殊的一类网络，它具有稀疏性、集聚性和小世界特性。14返回目录3.3随机网络3.3.1随机网络模型3.3.2随机网络的度分布3.3.3随机网络的直径和平均距离3.3.4随机网络的集聚系数3.3.5随机网络的特征谱153.3.1随机网络模型随机网络构成有两种等价方法：①ER模型：给定N个节点，最多可以存在N（N－1）／2条边，从这些边中随机选择M条边就可以得到一个随机网络，显然一共可产生种可能的随机图，且每种可能的概率相同；②二项式模型：给定N个节点，每一对节点以概率p进行连接。这样，所有连线的数目是一个随机变量，其平均值为M＝pN（N－1）／2。若G0是一个节点为v1，v2，…，vN和M条边组成的图，则得到该图的概率为P（G0）＝pM（1－p）N(N-1)/2-M，其中pM是M条边同时存在的概率，（1－p）N(N-1)/2-M是其他边都不存在的概率，二者是独立事件，故二概率相乘即得图G0存在的概率。163.3.1随机网络模型ER模型的一个伟大发现是：当连接概率p超过某个临界概率pc（N），许多性质就会突然涌现。例如，针对随机图的连通性，若p大于临界值（lnN）／N，那么几乎每一个随机图都是连通的。若当N→∞时，连接概率p＝p（N）的增长比pc（N）慢，则几乎所有连接概率为p（N）的随机图都不会有性质Q。相反，若连接概率p（N）的增长比pc（N）快，则几乎每一个随机图都有性质Q。因此，一个有N个节点和连接概率p＝p（N）的随机图有性质Q的概率满足：173.3.2随机网络的度分布在连接概率为p的ER随机图中，可知其平均度为而某节点vi的度ki等于k的概率遵循参数为N－1和p的二项式分布值得注意的是，若vi和vj是不同的节点，则P（ki＝k）和P（kj＝k）是两个独立的变量。为了找到随机图的度分布，需得到度为k的节点数Xk。为此，需要得到Xk等于某个值的概率P（Xk＝r）。连接度为k的平均节点数为即。183.3.2随机网络的度分布Xk值的概率接近如下泊松分布这样一来，度为k的节点数目Xk满足均值为λk的泊松分布。上式意味着Xk的实际值和近似结果Xk＝N·P（ki＝k）并没有很大偏离，只是要求节点相互独立。这样，随机图的度分布可近似为二项式分布在N比较大的条件下，它可以被泊松分布取代由于随机网络中节点之间的连接是等概率的，因此大多数节点的度都在均值＜k＞附近，网络中没有度特别大的节点。193.3.2随机网络的度分布对于大范围内的p值，最大和最小的度值都是确定性的和有限的。例如，若p（N）∝N-1-1/k，几乎没有图有度大于k的节点。另外一个极值情况是，若p＝［ln（N）＋kln（ln（N））＋c]／N，几乎每个随机图都至少有最小的度k。下图给出N＝1000，p＝0.0015时随机网络的度分布，其中图中的点代表Xk／N（度分布），而连续曲线代表期望值E（Xk）／N＝p（ki＝k），可以发现两者偏离确实很少。203.3.3随机网络的直径和平均距离对于大多数的p值，几乎所有的图都有同样的直径。这就意味着连接概率为p的N阶随机图的直径的变化幅度非常小，通常集中在一些重要的性质：若＜k＞小于1，则图由孤立树组成，且其直径等于树的直径。若＜k＞大于1，则图中会出现连通子图。当＜k＞大于等于3.5时，图的直径等于最大连通子图的直径且正比于ln（N）。若＜k＞大于等于ln（N），则几乎所有图是完全连通的，其直径集中在ln（N）／ln（pN）左右。213.3.3随机网络的直径和平均距离随机网络的平均最短距离可以进行如下估计：考虑随机网络的平均度＜k＞，对于任意一个节点，其一阶邻接点的数目为＜k＞，二阶邻接点的数目为＜k＞2。也就是说，在ER随机图中随机选择一个节点vi，网络中大约有＜k＞Lrand个节点与节点vi的距离为Lrand。依此类推，当l步后达到网络的总节点数目N，有N＝＜k＞l，故可以看出，随机网络的平均最短距离随网络规模的增加呈对数增长，这是典型的小世界效应。因为lnN随N增长得很慢，所以即使是一个很大规模的网络，它的平均距离也很小。223.3.4随机网络的集聚系数由于随机网络中任何两个节点之间的连接都是等概率的，因此对于某个节点vi，其邻居节点之间的连接概率也是p，所以随机网络的集聚系数为然而，真实网络并不遵循随机图的规律，相反，其集聚系数并不依赖于N，而是依赖于节点的邻居数目。通常，在具有相同的节点数和相同的平均度的情况下，ER模型的集聚系数Crand比真实复杂网络的要小得多。这意味着大规模的稀疏ER随机图一般没有集聚特性，而真实网络一般都具有明显的集聚特性。规则网络的普遍特征是集聚系数大且平均距离长，而随机网络的特征是集聚系数低且平均距离小。233.3.5随机网络的特征谱考查连接概率p（N）＝cN-z的随机网络GN,p的特征谱。该网络的平均度为＜k＞＝Np＝cN1-z。当连接概率中的参数变化时，随机网络的特征谱会发生逾渗转变或者尖锐的相变，具体表现如下所述。当0≤z＜1，图GN,p中将出现无限聚类体，并且当N→∞，＜k＞→∞，任何节点都是几乎完全属于无限的聚类体。在这种情况下，随机图的频谱密度发散到如下半圆形分布，如下图所示。图中p值固定为0.05。由上图可见，最大的特征值λ1是和频谱孤立的，并且随着网络大小衰减为pN。243.3.5随机网络的特征谱当z＞l时（N取3000），ρ（λ）偏离半圆形分布，如下图的点划线所示，而且当N→∞时，＜k＞→0，此时ρ（λ）的奇数阶矩等于0，这意味着要回到原节点的路径只能是沿来时经过的相同节点返回，这正好表明网络具有树状结构。当z＝l且N→∞时，节点的平均度数＜k＞＝c。此时，若c≤1时，网络仍基本上为树状结构；而若c＞1时，谱密度的奇数阶矩远远大于0，说明网络的结构发生了显著的变化，出现了环和分支（集团）。当z＝l，N＝3000时的谱密度如下图所示。25返回目录3.4小世界网络3.4.1小世界网络模型3.4.2小世界网络的度分布3.4.3小世界网络的平均距离3.4.4小世界网络的集聚系数3.4.5小世界网络的特征谱263.4.1小世界网络模型1.WS小世界模型WS小世界模型的构造算法如下：①从规则图开始：考虑一个含有N个节点的最近邻耦合网络，它们围成一个环，其中每个节点与它左右相邻的各K／2个节点相连，K是偶数。参数满足NKln（N）1。②随机化重连：以概率p随机地重新连接网络中的每条边，即将边的一个端点保持不变，而另一个端点取为网络中随机选择的一个节点。其中规定，任意两个不同的节点之间至多只能有一条边，且每个节点都不能有边与自身相连。这样就会产生pNK／2条长程的边把一个节点和远处的节点联系起来。273.4.1小世界网络模型在上述模型中，p＝0对应于完全规则网络，p＝1则对应于完全随机网络，通过调节p值就可以控制从完全规则网络到完全随机网络的过渡，如下图所示。由上述算法得到网络模型的集聚系数C（p）和平均距离L（p）都可看作是重连概率p的函数，如下图所示。图中对集聚系数和平均距离作了归一化处理。283.4.1小世界网络模型最近邻耦合网络（对应p＝0）是高度集聚的（C（0）≈3／4），但平均距离很大（L（0）≈N／2K1）。当p较小时（0＜p1），重新连线后得到的网络与原始的规则网络的局部属性差别不大，从而网络的集聚系数变化也不大（C（p）∝C（0），但其平均距离下降很快（L（p）L（0））。这个结果是不难想象的：一方面，只要几条边的随机重连就足以减小网络的平均距离；另一方面，几条随机重连的边并不足以改变网络的局部集聚特性。这类既具有较短的平均距离又具有较高的集聚系数的网络就是典型的小世界网络。293.4.1小世界网络模型2.NW小世界模型NW小世界模型是通过用“随机化加边”取代WS小世界模型构造中的“随机化重连”而得到的，具体构造算法如下：①从规则图开始：考虑一个含有N个点的最近邻耦合网络，它们围成一个环，其中每个节点与它左右相邻的各K／2个节点相连，K是偶数。参数满足NKln（N）1。