《复杂网络基础理论3》由会员分享，可在线阅读，更多相关《复杂网络基础理论3（92页珍藏版）》请在金锄头文库上搜索。
1、复杂网络基础理论,第三章 网络机制模型,第三章 网络机制模型,3.1 引言 3.2 规则网络 3.3 随机网络 3.4 小世界网络 3.5 无标度网络 3.6 层次网络 3.7 确定性网络 3.8 自相似网络,2,3.1 引言,复杂网络的研究大致可以描述为三个密切相关但又依次深入的方面：大量的真实网络的实证研究，分析真实网络的统计特性；构建符合真实网络统计性质的网络演化模型，研究网络的形成机制和内在机理；研究网络上的动力学行为，如网络的鲁棒性和同步能力，网络的拥塞及网络上的传播行为等。本章针对第二个方面，以得知网络模型需如何构成才会展现这些特定的统计性质。,3,3.1 引言,每一种网络系统都有
2、其自身的特殊机制，有其自身的演化机制，但由于都可以使用网络分析的方法进行分析，所以也有其共性。研究网络的集合性质、网络的形成机制、网络演化的统计规律、网络上的模型性质以及网络的结构稳定性，并把它与现实系统结合起来加以研究比较是复杂网络研究的主要任务。,4,返回 目录,3.2 规则网络,3.2.1 全局耦合网络3.2.2 最近邻耦合网络3.2.3 星型耦合网络,5,3.2.1 全局耦合网络,1.概念全局耦合网络是指任意两个节点之间都有边相连的网络，也称完全图。对于无向网络来说，节点数为N的全局耦合网络拥有N（N1）2条边，如下图所示；而对于有向网络来说，节点数为N的全局耦合网络拥有N（N1）条弧
3、。,6,3.2.1 全局耦合网络,2.特性各节点的度均为N1，因此度分布为单尖峰，可以表示为Delta函数P（k）（kN1）。每个节点vi的集聚系数均为Ci1，故整个网络的集聚系数为C1。从任意一个节点到另外一个节点的最短路径长度都为1，故整个网络的平均距离为L1。在具有相同节点数的所有网络中，全局耦合网络具有最小的平均距离和最大的集聚系数。该模型作为实际网络模型的局限性很明显：全局耦合网络是最稠密的网络，然而大多数大型实际网络都是很稀疏的，它们边的数目一般至多是O（N）而不是O（N2）。,7,3.2.2 最近邻耦合网络,1.概念对于拥有N的节点的网络来讲，通常将每个节点只与它最近的K个邻居节
4、点连接的网络称为最近邻耦合网络，这里K是小于等于N1的整数。若每个节点只与最近的2个邻居节点相连，这样所有节点相连就构成了一维链或环，如下图（a）所示。如下图（b）所示的二维晶格也是一种最近邻耦合网络。一般情况下，一个具有周期边界条件的最近邻耦合网络包含N个围成一个环的节点，其中每个节点都与它左右各K2个邻居节点相连，这里K是偶数，如下图（c）所示。,8,3.2.2 最近邻耦合网络,2.特性每个节点vi的度均为K， 因此度分布为单尖峰，可以表示为Delta函数P（k）（kK）。最近邻耦合网络的平均集聚系数就是每个节点的集聚系数：CCi3（K2）4（K1）。对较大K值，容易得到C0.75。可见，
5、最近邻耦合网络集聚程度还是很高的。最近邻耦合网络不是小世界网络，因为对固定K值，该网络直径D和平均距离L分别为D=NK，LN（2K）。当N ，L。,9,3.2.2 最近邻耦合网络,【例3.1】用Matlab程序绘制最近邻耦合网络，并给出具体程序代码。 解：（1）最近邻耦合网络绘制的Matlab程序如下：,10,3.2.2 最近邻耦合网络,11,3.2.2 最近邻耦合网络,（2）当N20，K6时，该程序的仿真结果如下图所示。,12,3.2.3 星型耦合网络,1.概念星形耦合网络，它有一个中心点，其余的N1个点都只与这个中心点连接，而彼此之间不连接，如下图所示。,13,3.2.3 星型耦合网络,2
6、.特性中心节点的度为N1，而其它节点的度均为1，所以星型耦合网络的度分布可以描述为如下函数星形网络的平均距离为L22N 。当N，L2。假设定义一个节点只有一个邻居节点时，其集聚系数为1，则中心节点的集聚系数为0，而其余N1个节点的集聚系数均为1，所以整个网络的平均集聚系数为C（N1）N 。当N ，C1。由此可见，星型耦合网络是比较特殊的一类网络，它具有稀疏性、集聚性和小世界特性。,14,返回 目录,3.3 随机网络,3.3.1 随机网络模型3.3.2 随机网络的度分布3.3.3 随机网络的直径和平均距离3.3.4 随机网络的集聚系数3.3.5 随机网络的特征谱,15,3.3.1 随机网络模型,
7、随机网络构成有两种等价方法：ER模型：给定N个节点，最多可以存在N（N1）2条边，从这些边中随机选择M条边就可以得到一个随机网络，显然一共可产生 种可能的随机图，且每种可能的概率相同；二项式模型：给定N个节点，每一对节点以概率p进行连接。这样，所有连线的数目是一个随机变量，其平均值为MpN（N1）2。若G0是一个节点为v1，v2，vN和M条边组成的图，则得到该图的概率为P（G0）p M（1p）N(N-1)/2-M，其中p M是M条边同时存在的概率，（1p）N(N-1)/2-M是其他边都不存在的概率，二者是独立事件，故二概率相乘即得图G0存在的概率。,16,3.3.1 随机网络模型,ER模型的一
8、个伟大发现是：当连接概率p超过某个临界概率pc（N），许多性质就会突然涌现。例如，针对随机图的连通性，若p大于临界值（lnN）N，那么几乎每一个随机图都是连通的。若当N时，连接概率pp（N）的增长比pc（N）慢，则几乎所有连接概率为p（N）的随机图都不会有性质Q。相反，若连接概率p（N）的增长比pc（N）快，则几乎每一个随机图都有性质Q。因此，一个有N个节点和连接概率pp（N）的随机图有性质Q的概率满足：,17,3.3.2 随机网络的度分布,在连接概率为p的ER随机图中，可知其平均度为而某节点vi的度ki等于k的概率遵循参数为N1和p的二项式分布值得注意的是，若vi和vj是不同的节点，则P（k
9、ik）和P（kjk）是两个独立的变量。为了找到随机图的度分布，需得到度为k的节点数Xk。为此，需要得到Xk等于某个值的概率P（Xkr）。连接度为k的平均节点数为即 。,18,3.3.2 随机网络的度分布,Xk值的概率接近如下泊松分布这样一来，度为k的节点数目Xk满足均值为k的泊松分布。上式意味着Xk的实际值和近似结果XkNP（kik）并没有很大偏离，只是要求节点相互独立。这样，随机图的度分布可近似为二项式分布在N比较大的条件下，它可以被泊松分布取代由于随机网络中节点之间的连接是等概率的，因此大多数节点的度都在均值k附近，网络中没有度特别大的节点。,19,3.3.2 随机网络的度分布,对于大范围
10、内的p值，最大和最小的度值都是确定性的和有限的。例如，若p（N）N-1-1/k，几乎没有图有度大于k的节点。另外一个极值情况是，若pln（N）kln（ln（N）cN，几乎每个随机图都至少有最小的度k。下图给出N1000，p0.0015时随机网络的度分布，其中图中的点代表XkN（度分布），而连续曲线代表期望值E（Xk）Np（kik），可以发现两者偏离确实很少。,20,3.3.3 随机网络的直径和平均距离,对于大多数的p值，几乎所有的图都有同样的直径。这就意味着连接概率为p的N阶随机图的直径的变化幅度非常小，通常集中在一些重要的性质：若k小于1，则图由孤立树组成，且其直径等于树的直径。若k大于1，
11、则图中会出现连通子图。当k大于等于3.5时，图的直径等于最大连通子图的直径且正比于ln（N）。若k大于等于ln（N），则几乎所有图是完全连通的，其直径集中在ln（N）ln（pN）左右。,21,3.3.3 随机网络的直径和平均距离,随机网络的平均最短距离可以进行如下估计：考虑随机网络的平均度k，对于任意一个节点，其一阶邻接点的数目为k，二阶邻接点的数目为k2。也就是说，在ER随机图中随机选择一个节点vi，网络中大约有kLrand个节点与节点vi的距离为Lrand。依此类推，当l步后达到网络的总节点数目N，有Nkl，故可以看出，随机网络的平均最短距离随网络规模的增加呈对数增长，这是典型的小世界效应
12、。因为lnN随N增长得很慢，所以即使是一个很大规模的网络，它的平均距离也很小。,22,3.3.4 随机网络的集聚系数,由于随机网络中任何两个节点之间的连接都是等概率的，因此对于某个节点vi，其邻居节点之间的连接概率也是p，所以随机网络的集聚系数为然而，真实网络并不遵循随机图的规律，相反，其集聚系数并不依赖于N，而是依赖于节点的邻居数目。通常，在具有相同的节点数和相同的平均度的情况下，ER模型的集聚系数Crand比真实复杂网络的要小得多。这意味着大规模的稀疏ER随机图一般没有集聚特性，而真实网络一般都具有明显的集聚特性。规则网络的普遍特征是集聚系数大且平均距离长，而随机网络的特征是集聚系数低且平
13、均距离小。,23,3.3.5 随机网络的特征谱,考查连接概率p（N）cN-z的随机网络GN,p的特征谱。该网络的平均度为kNpcN1-z。当连接概率中的参数变化时，随机网络的特征谱会发生逾渗转变或者尖锐的相变，具体表现如下所述。当0z1，图GN,p中将出现无限聚类体，并且当N，k，任何节点都是几乎完全属于无限的聚类体。在这种情况下，随机图的频谱密度发散到如下半圆形分布，如下图所示。图中p值固定为0.05。由上图可见，最大的特征值1是和频谱孤立的，并且随着网络大小衰减为pN。,24,3.3.5 随机网络的特征谱,当zl时（N取3000），（）偏离半圆形分布，如下图的点划线所示，而且当N时，k0，
14、此时（）的奇数阶矩等于0，这意味着要回到原节点的路径只能是沿来时经过的相同节点返回，这正好表明网络具有树状结构。当zl且N时，节点的平均度数kc。此时，若c1时，网络仍基本上为树状结构；而若c1时，谱密度的奇数阶矩远远大于0，说明网络的结构发生了显著的变化，出现了环和分支（集团）。当zl，N3000时的谱密度如下图所示。,25,返回 目录,3.4 小世界网络,3.4.1 小世界网络模型3.4.2 小世界网络的度分布3.4.3 小世界网络的平均距离3.4.4 小世界网络的集聚系数3.4.5 小世界网络的特征谱,26,3.4.1 小世界网络模型,1.WS小世界模型WS小世界模型的构造算法如下：从规
15、则图开始：考虑一个含有N个节点的最近邻耦合网络，它们围成一个环，其中每个节点与它左右相邻的各K2个节点相连，K是偶数。参数满足NKln（N）1。随机化重连：以概率p随机地重新连接网络中的每条边，即将边的一个端点保持不变，而另一个端点取为网络中随机选择的一个节点。其中规定，任意两个不同的节点之间至多只能有一条边，且每个节点都不能有边与自身相连。这样就会产生pNK2条长程的边把一个节点和远处的节点联系起来。,27,3.4.1 小世界网络模型,在上述模型中，p0对应于完全规则网络，p1则对应于完全随机网络，通过调节p值就可以控制从完全规则网络到完全随机网络的过渡，如下图所示。由上述算法得到网络模型的
16、集聚系数C（p）和平均距离L（p）都可看作是重连概率p的函数，如下图所示。图中对集聚系数和平均距离作了归一化处理。,28,3.4.1 小世界网络模型,最近邻耦合网络（对应p0）是高度集聚的（C（0）34），但平均距离很大（L（0）N2K1）。当p较小时（0p1），重新连线后得到的网络与原始的规则网络的局部属性差别不大，从而网络的集聚系数变化也不大（C（p）C（0），但其平均距离下降很快（L（p）L（0）。这个结果是不难想象的：一方面，只要几条边的随机重连就足以减小网络的平均距离；另一方面，几条随机重连的边并不足以改变网络的局部集聚特性。这类既具有较短的平均距离又具有较高的集聚系数的网络就是典型的小世界网络。,
