复杂网络基础理论ppt课件.ppt

复杂网络基础理论,第三章 网络机制模型,2,第三章 网络机制模型,3.1 引言3.2 规则网络3.3 随机网络3.4 小世界网络3.5 无标度网络3.6 层次网络3.7 确定性网络3.8 自相似网络,3,3.1 引言,复杂网络的研究大致可以描述为三个密切相关但又依次深入的方面： 大量的真实网络的实证研究，分析真实网络的统计特性； 构建符合真实网络统计性质的网络演化模型，研究网络的形成机制和内在机理； 研究网络上的动力学行为，如网络的鲁棒性和同步能力，网络的拥塞及网络上的传播行为等。 本章针对第二个方面，以得知网络模型需如何构成才会展现这些特定的统计性质。,4,3.1 引言,每一种网络系统都有其自身的特殊机制，有其自身的演化机制，但由于都可以使用网络分析的方法进行分析，所以也有其共性。 研究网络的集合性质、网络的形成机制、网络演化的统计规律、网络上的模型性质以及网络的结构稳定性，并把它与现实系统结合起来加以研究比较是复杂网络研究的主要任务。,返回 目录,5,3.2 规则网络,3.2.1 全局耦合网络3.2.2 最近邻耦合网络3.2.3 星型耦合网络,6,3.2.1 全局耦合网络,1.概念 全局耦合网络是指任意两个节点之间都有边相连的网络，也称完全图。对于无向网络来说，节点数为N的全局耦合网络拥有N（N1）2条边，如下图所示；而对于有向网络来说，节点数为N的全局耦合网络拥有N（N1）条弧。,7,3.2.1 全局耦合网络,2.特性 各节点的度均为N1，因此度分布为单尖峰，可以表示为Delta函数P（k）（kN1）。 每个节点vi的集聚系数均为Ci1，故整个网络的集聚系数为C1。 从任意一个节点到另外一个节点的最短路径长度都为1，故整个网络的平均距离为L1。 在具有相同节点数的所有网络中，全局耦合网络具有最小的平均距离和最大的集聚系数。该模型作为实际网络模型的局限性很明显：全局耦合网络是最稠密的网络，然而大多数大型实际网络都是很稀疏的，它们边的数目一般至多是O（N）而不是O（N2）。,8,3.2.2 最近邻耦合网络,1.概念 对于拥有N的节点的网络来讲，通常将每个节点只与它最近的K个邻居节点连接的网络称为最近邻耦合网络，这里K是小于等于N1的整数。若每个节点只与最近的2个邻居节点相连，这样所有节点相连就构成了一维链或环，如下图（a）所示。如下图（b）所示的二维晶格也是一种最近邻耦合网络。一般情况下，一个具有周期边界条件的最近邻耦合网络包含N个围成一个环的节点，其中每个节点都与它左右各K2个邻居节点相连，这里K是偶数，如下图（c）所示。,9,3.2.2 最近邻耦合网络,2.特性 每个节点vi的度均为K， 因此度分布为单尖峰，可以表示为Delta函数P（k）（kK）。 最近邻耦合网络的平均集聚系数就是每个节点的集聚系数：CCi3（K2）4（K1）。对较大K值，容易得到C0.75。可见，最近邻耦合网络集聚程度还是很高的。 最近邻耦合网络不是小世界网络，因为对固定K值，该网络直径D和平均距离L分别为D=NK，LN（2K）。当N ，L。,10,3.2.2 最近邻耦合网络,【例3.1】用Matlab程序绘制最近邻耦合网络，并给出具体程序代码。解：（1）最近邻耦合网络绘制的Matlab程序如下：,11,3.2.2 最近邻耦合网络,12,3.2.2 最近邻耦合网络,（2）当N20，K6时，该程序的仿真结果如下图所示。,13,3.2.3 星型耦合网络,1.概念 星形耦合网络，它有一个中心点，其余的N1个点都只与这个中心点连接，而彼此之间不连接，如下图所示。,14,3.2.3 星型耦合网络,2.特性 中心节点的度为N1，而其它节点的度均为1，所以星型耦合网络的度分布可以描述为如下函数 星形网络的平均距离为L22N 。当N，L2。 假设定义一个节点只有一个邻居节点时，其集聚系数为1，则中心节点的集聚系数为0，而其余N1个节点的集聚系数均为1，所以整个网络的平均集聚系数为C（N1）N 。当N ，C1。 由此可见，星型耦合网络是比较特殊的一类网络，它具有稀疏性、集聚性和小世界特性。,返回 目录,15,3.3 随机网络,3.3.1 随机网络模型3.3.2 随机网络的度分布3.3.3 随机网络的直径和平均距离3.3.4 随机网络的集聚系数3.3.5 随机网络的特征谱,16,3.3.1 随机网络模型,随机网络构成有两种等价方法：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存在的概率。,17,3.3.1 随机网络模型,ER模型的一个伟大发现是：当连接概率p超过某个临界概率pc（N），许多性质就会突然涌现。例如，针对随机图的连通性，若p大于临界值（lnN）N，那么几乎每一个随机图都是连通的。 若当N时，连接概率pp（N）的增长比pc（N）慢，则几乎所有连接概率为p（N）的随机图都不会有性质Q。相反，若连接概率p（N）的增长比pc（N）快，则几乎每一个随机图都有性质Q。因此，一个有N个节点和连接概率pp（N）的随机图有性质Q的概率满足：,18,3.3.2 随机网络的度分布,在连接概率为p的ER随机图中，可知其平均度为 而某节点vi的度ki等于k的概率遵循参数为N1和p的二项式分布 值得注意的是，若vi和vj是不同的节点，则P（kik）和P（kjk）是两个独立的变量。为了找到随机图的度分布，需得到度为k的节点数Xk。为此，需要得到Xk等于某个值的概率P（Xkr）。连接度为k的平均节点数为即 。,19,3.3.2 随机网络的度分布,Xk值的概率接近如下泊松分布这样一来，度为k的节点数目Xk满足均值为k的泊松分布。上式意味着Xk的实际值和近似结果XkNP（kik）并没有很大偏离，只是要求节点相互独立。这样，随机图的度分布可近似为二项式分布在N比较大的条件下，它可以被泊松分布取代 由于随机网络中节点之间的连接是等概率的，因此大多数节点的度都在均值k附近，网络中没有度特别大的节点。,20,3.3.2 随机网络的度分布,对于大范围内的p值，最大和最小的度值都是确定性的和有限的。例如，若p（N）N-1-1/k，几乎没有图有度大于k的节点。另外一个极值情况是，若pln（N）kln（ln（N）cN，几乎每个随机图都至少有最小的度k。下图给出N1000，p0.0015时随机网络的度分布，其中图中的点代表XkN（度分布），而连续曲线代表期望值E（Xk）Np（kik），可以发现两者偏离确实很少。,21,3.3.3 随机网络的直径和平均距离,对于大多数的p值，几乎所有的图都有同样的直径。这就意味着连接概率为p的N阶随机图的直径的变化幅度非常小，通常集中在 一些重要的性质：若k小于1，则图由孤立树组成，且其直径等于树的直径。若k大于1，则图中会出现连通子图。当k大于等于3.5时，图的直径等于最大连通子图的直径且正比于ln（N）。若k大于等于ln（N），则几乎所有图是完全连通的，其直径集中在ln（N）ln（pN）左右。,22,3.3.3 随机网络的直径和平均距离,随机网络的平均最短距离可以进行如下估计：考虑随机网络的平均度k，对于任意一个节点，其一阶邻接点的数目为k，二阶邻接点的数目为k2。也就是说，在ER随机图中随机选择一个节点vi，网络中大约有kLrand个节点与节点vi的距离为Lrand。依此类推，当l步后达到网络的总节点数目N，有Nkl，故可以看出，随机网络的平均最短距离随网络规模的增加呈对数增长，这是典型的小世界效应。因为lnN随N增长得很慢，所以即使是一个很大规模的网络，它的平均距离也很小。,23,3.3.4 随机网络的集聚系数,由于随机网络中任何两个节点之间的连接都是等概率的，因此对于某个节点vi，其邻居节点之间的连接概率也是p，所以随机网络的集聚系数为 然而，真实网络并不遵循随机图的规律，相反，其集聚系数并不依赖于N，而是依赖于节点的邻居数目。通常，在具有相同的节点数和相同的平均度的情况下，ER模型的集聚系数Crand比真实复杂网络的要小得多。这意味着大规模的稀疏ER随机图一般没有集聚特性，而真实网络一般都具有明显的集聚特性。 规则网络的普遍特征是集聚系数大且平均距离长，而随机网络的特征是集聚系数低且平均距离小。,24,3.3.5 随机网络的特征谱,考查连接概率p（N）cN-z的随机网络GN,p的特征谱。该网络的平均度为kNpcN1-z。当连接概率中的参数变化时，随机网络的特征谱会发生逾渗转变或者尖锐的相变，具体表现如下所述。 当0z1，图GN,p中将出现无限聚类体，并且当N，k，任何节点都是几乎完全属于无限的聚类体。在这种情况下，随机图的频谱密度发散到如下半圆形分布，如下图所示。图中p值固定为0.05。 由上图可见，最大的特征值1是和频谱孤立的，并且随着网络大小衰减为pN。,25,3.3.5 随机网络的特征谱,当zl时（N取3000），（）偏离半圆形分布，如下图的点划线所示，而且当N时，k0，此时（）的奇数阶矩等于0，这意味着要回到原节点的路径只能是沿来时经过的相同节点返回，这正好表明网络具有树状结构。 当zl且N时，节点的平均度数kc。此时，若c1时，网络仍基本上为树状结构；而若c1时，谱密度的奇数阶矩远远大于0，说明网络的结构发生了显著的变化，出现了环和分支（集团）。当zl，N3000时的谱密度如下图所示。,返回 目录,26,3.4 小世界网络,3.4.1 小世界网络模型3.4.2 小世界网络的度分布3.4.3 小世界网络的平均距离3.4.4 小世界网络的集聚系数3.4.5 小世界网络的特征谱,27,3.4.1 小世界网络模型,1.WS小世界模型 WS小世界模型的构造算法如下： 从规则图开始：考虑一个含有N个节点的最近邻耦合网络，它们围成一个环，其中每个节点与它左右相邻的各K2个节点相连，K是偶数。参数满足NKln（N）1。 随机化重连：以概率p随机地重新连接网络中的每条边，即将边的一个端点保持不变，而另一个端点取为网络中随机选择的一个节点。其中规定，任意两个不同的节点之间至多只能有一条边，且每个节点都不能有边与自身相连。这样就会产生pNK2条长程的边把一个节点和远处的节点联系起来。,28,3.4.1 小世界网络模型,在上述模型中，p0对应于完全规则网络，p1则对应于完全随机网络，通过调节p值就可以控制从完全规则网络到完全随机网络的过渡，如下图所示。 由上述算法得到网络模型的集聚系数C（p）和平均距离L（p）都可看作是重连概率p的函数，如下图所示。图中对集聚系数和平均距离作了归一化处理。,29,3.4.1 小世界网络模型,最近邻耦合网络（对应p0）是高度集聚的（C（0）34），但平均距离很大（L（0）N2K1）。当p较小时（0p1），重新连线后得到的网络与原始的规则网络的局部属性差别不大，从而网络的集聚系数变化也不大（C（p）C（0），但其平均距离下降很快（L（p）L（0）。 这个结果是不难想象的：一方面，只要几条边的随机重连就足以减小网络的平均距离；另一方面，几条随机重连的边并不足以改变网络的局部集聚特性。 这类既具有较短的平均距离又具有较高的集聚系数的网络就是典型的小世界网络。,30,3.4.1 小世界网络模型,2.NW小世界模型 NW小世界模型是通过用“随机化加边”取代WS小世界模型构造中的“随机化重连”而得到的，具体构造算法如下： 从规则图开始：考虑一个含有N个点的最近邻耦合网络，它们围成一个环，其中每个节点与它左右相邻的各K2个节点相连，K是偶数。参数满足NKln（N）1。 随机化加边：以概率p在随机选取的一对节点之间加上一条边。其中，任意两个不同的节点之间至多只能有一条边，并且每一个节点都不能有边与自身相连。,31,3.4.1 小世界网络模型,在NW小世界模型中，p=0对应于原来的最近邻耦合网络，p=1则对应于全局耦合网络，如下图所示。在理论分析上，NW小世界模型要比WS小世界模型简单一些。当p足够小和N足够大时，NW小世界模型本质上等同于WS小世界模型。,32,3.4.1 小世界网络模型,在现实朋友关系网络中，小世界网络模型反映了如下一种特性：大部分人的朋友都是和他们在一条街上的邻居或在同一单位工作的同事；另一方面，也有些朋友住得较远，甚至远在异国他乡，这种情景对应于WS小世界模型中通过重连或在NW小世界模型中通过加入连线产生远程连接。 实际上，除了WS小世界模型和NW小世界模型，还有许多改进模型：加点，加边，去点，去边及不同形式的交叉，可产生多种形式的小世界模型。,33,3.4.1 小世界网络模型,【例3.2】用Matlab程序分别绘制WS、NW小世界网络模型，并给出具体程序代码。解：由于两个小世界模型都是在最近邻耦合网络的基础上进行的改变，因此各自对应的Matlab程序与例3.1中的差别就在于：在“开始画最近邻耦合网络”的代码段前分别添加以下代码：（1）WS小世界需添加代码：,34,3.4.1 小世界网络模型,（2）NW小世界需添加代码：,35,3.4.1 小世界网络模型,（3）当N20，K6，p0.2（重连或加边概率）时程序生成的WS、NW小世界网络如下图所示。,36,3.4.2 小世界网络的度分布,在基于“随机化加边”机制的NW小世界模型中，每个节点的度至少为K。因此，当kK时，一个随机选取的节点的度为k的概率为而当kK时，P（k）0。 在基于“随机化重连”机制的WS小世界模型中，对于p0，度分布显然是一个Delta函数，中心位于kK。对于p0，每个节点vi的度至少为K2，可以描述为kiK2uiri，ui表示保留不动的边（概率为1p），ri表示重新连向节点vi的边（概率为1N）。ui和ri的概率分布分别为,37,3.4.2 小世界网络的度分布,因此，综合上述两部分概率，当kK2时，一个随机选取的节点的度为k的概率为而当kK2时，P（k）0。,38,3.4.2 小世界网络的度分布,N1000，K6的WS模型的数值模拟结果如下图所示，其中实心黑点表示的是ER随机网络。可见，与ER随机图模型类似，WS小世界模型也是所有节点的度都近似相等的均匀网络。,39,3.4.3 小世界网络的平均距离,Watts等认为小世界网络的平均距离下降的原因在于两个节点间出现了最短路径（捷径）。每一条捷径都是随机产生的，都有把网络中分散部分连接起来的趋势。Watts发现，当p2（NK）时，即在确保至少存在一条捷径的情况下，平均距离L开始下降。即使是相当少的捷径也能显著减小网络的平均距离。这是因为每出现一条捷径，它对整个系统的影响是非线性的，它不仅影响到被这条线直接连着的两点，也影响到这两点的最近邻、次近邻，以及次次近邻等。 这也就意味着p依赖于系统尺度N。反过来说，存在一个依赖于p的交叉长度N*，如果NN*，L就与N成正比；如果NN*，L与ln（N）成正比。,40,3.4.3 小世界网络的平均距离,到目前为止，人们还没有关于WS小世界模型的平均距离L的精确解析表达式，不过，利用重正化群分析方法可以得到如下公式式中， 为一普适尺度函数，满足Newman等人利用基于平均场方法给出了如下的近似表达式但目前为止还没有精确的显式表达式。,41,3.4.4 小世界网络的集聚系数,除了平均距离小的特性外，小世界网络还具有较高的集聚系数。 对于WS模型来说，当重新连接概率p0，对应的最近邻耦合规则网络的集聚系数不受网络阶数N大小的影响，而仅仅受其拓扑连接方式影响。此时，每个节点左右两边各有K2个邻近节点，容易得到这些邻近节点间的连接数为N03（K2）K212，于是对应的集聚系数C（0）N0K（K1）23K212（K1）。对于p0，原先p0时连接节点vi的两个邻近节点仍然作为节点vi的邻近节点相连的概率为（1p）3，偏差不超过O（N-1）。于是一个节点的邻近节点之间的平均连接数为 N0（1p）3O（N-1）。若定义近似平均集聚系数,42,3.4.4 小世界网络的集聚系数,C（p）为每个节点的邻居节点之间的平均连接数除以每个节点的邻居节点之间的平均最大可能连接数，则WS网络的平均集聚系数近似为 经过仿真验证，C（p）和实际C（p）偏差很小，偏差数量级确实为O（N-1）。因此，可以近似认为：C（p）C（0）（1p）3，且基本不受N影响。总之，只要网络足够大，小世界行为在0p1范围内肯定会出现。 类似可证明NW模型的平均集聚系数为,43,3.4.5 小世界网络的特征谱,WS模型的谱密度与重连概率p有关，如下图所示（图中N1000，K50）。,44,3.4.5 小世界网络的特征谱,当重连概率p0时，WS模型是一个规则的圆环，由于其谱密度包含许多奇异点，故形状非常不规则。 当p0.01时，这些奇异点变得模糊，谱密度形状变得比较规则了，但（）仍然有严重偏斜，说明虽然只有少量的随机重连边，但网络的结构已经发生了改变，不再是规则的圆环。 最后，随着p1，谱密度（）逐渐趋向于半圆形分布（随机网络的特性）。 当p1时，WS模型已经是一个完全的随机网络，只是此时节点的最小度数不是任意的，而是K2。,45,3.4.5 小世界网络的特征谱,尽管谱密度细节随着p的不同有着很大的变化，（）的三阶矩一直很大，这意味着WS小世界网络的基本性质是具有大量的三角形。 为了避免与重连概率p在符号表示上的冲突，图中坐标轴的per指的是随机网络中的连接概率，这里perKN0.05。,返回 目录,46,3.5 无标度网络,3.5.1 Price模型3.5.2 BA模型3.5.3 BA无标度网络的度分布和度相关3.5.4 BA无标度网络的平均距离和集聚系数3.5.5 BA无标度网络的特征谱,47,3.5.1 PRICE模型,Price主要对论文间的引用关系网络及其入度进行了研究，其思想是：一篇论文被引用的比率与它已经被引用的次数成比例。从定性角度来看，如果某篇文章被引用的次数越多，你碰到该论文的概率越大。于是，Price和Simon提出了一个简单的假设“论文的引用概率与它以前的引用数量之间存在严格的线性关系”。 考虑一个包含N个节点的有向图构成的论文引用关系网络，假定P（k）是节点中入度为k的节点所占比例。新的节点不断地加入到网络中，每个新加入的节点都有一定的出度，该出度在节点一经产生后便保持不变，平均出度为,48,3.5.1 PRICE模型,在网络不断增长的过程中，新边连接到旧节点的概率与旧节点的入度成比例。然而，因每个节点开始时入度均为0，这便使得该节点获取新边的概率为0。为了解决这一问题，新边连接到节点的概率与kk0成比例，其中k01，即认为论文首次出版时的引用次数为1（自己引用自己）。一条新边连接到任何度为k的节点的概率为其度分布为,49,3.5.2 BA模型,Barabsi和Albert指出现实中的网络有两个方面在以前的网络模型中未包含进去。 首先，没有考虑现实网络的增长特性（网络的规模是不断扩大的）。在ER、WS和NW模型中，均假设网络从固定的节点数N开始，然后随机连接（ER 模型）或者重连（WS模型）或者加边（NW模型），没有修改节点数N。相比而言，大部分现实网络是开放的，即它们由不断加进系统中的新节点组成，因此节点数目N的增长伴随网络的终生。,50,3.5.2 BA模型,其次，没有考虑现实网络的优先连接特征（新的节点更倾向于与那些具有较高度的“大”节点相连接）。随机网络模型假设两个节点被连接的概率是随机的或统一的。相比之下，大部分现实网络展现出择优连接的性质。这种现象也称为“富者更富”或“马太效应”。 Barabsi等人证明了在这两个基本假定的基础上，网络必然最终发展成无标度网络，即BA网络模型。 基于网络的增长和优先连接特征，BA无标度网络模型的构造算法如下： 增长：从一个具有m0个节点的网络开始，每次引入一个新的节点，与m个已存在的节点相连，这里mm0。,51,3.5.2 BA模型,优先连接：一个新节点与一个已经存在的节点vi相连接的概率i与节点vi的度ki成正比，即 在经过t步后，这种算法产生一个有Ntm0个节点，mt条边的网络。下图举例说明了当mm02时，初始网络为孤立节点的BA网络的演化过程。初始网络有两个节点，每次新增加的一个节点按优先连接机制与网络中已经存在的两个节点相连。,52,3.5.2 BA模型,根据增长性和择优选择，网络将最终演化成一个标度不变的状态，即网络的度分布不随时间而改变（同样也就是不随网络节点数N而改变），经计算得到度值为k的节点的概率正比于幂次项k-3。下面对该结论作适当的证明。 在BA模型中，从网络中某一节点vi的度值ki随时间变化的角度出发，假设其度值连续，有如下方程 （1）由于每一时间步，我们加入m条边，即网络总度值增加2m，于是第t步的总度值为 （2）,53,3.5.2 BA模型,将式（2）代入式（1），可以得到 （3）解方程得 （4）由初始条件，节点vi在时刻ti以ki（ti）m加入到系统中，可以得到 （5）因此，将式（5）代入式（4）可得 （6）,54,3.5.2 BA模型,由（6）式可以得到节点连接度ki（t）小于某定值k的概率为 （7）假设我们等时间间隔地向网络中增加节点，则ti值就有一个常数概率密度 （8）由式（7）和式（8）可以得到 （9）所以度值的分布P(k)为 （10）当t 时，P(k) = 2m2k-3 ，完全符合幂律分布。,55,3.5.2 BA模型,【例3.3】用Matlab程序绘制BA网络，并给出具体程序代码。解：（1）程序代码如下：,56,3.5.2 BA模型,57,3.5.2 BA模型,58,3.5.2 BA模型,（2）当m0=2、m=2、N=20且从孤立节点开始（pp=1）的程序运行结果如下图所示。,59,3.5.3 BA无标度网络的度分布和度相关,1.度分布 对BA无标度网络的度分布的理论研究主要有三种方法：连续场理论（前面已介绍），主方程法和速率方程法。 速率方程法 主方程法,60,3.5.3 BA无标度网络的度分布和度相关,主方程法和速率方程法是等价的，而在渐进极限下，也和连续场理论得到的结果一致。因此，在计算度分布标度行为时，它们可以相互转化。 BA模型标度3与m无关。度分布渐进地与时间无关，进而也与系统尺度Nm0t无关。这就意味着，尽管网络在不断增长，最后都能达到一个稳定的无标度状态，而且幂律分布的系数与m2成正比。2.度相关 考虑有边连接的所有度值为k和l的节点对，不失一般性，设度值为k的节点是新近加入系统的节点。为简化起见，令m1，用符号Nkl（t）表示t时刻连接度为k的和度为l的节点对的数量，则,61,3.5.3 BA无标度网络的度分布和度相关,右边第一项表示由于增添了一条边到度为k1或度为k的节点，并把它连接到度值为l的节点，在Nkl中产生的变化。由于增添的新边使节点的度数加1，分子中的第一项对应着Nkl的增加，而第二项对应损失。右边第二项用于其它节点，与第一项有相同的效果。最后一项为kl时的概率。因此，添加到了度为l1的节点的边是连接这两个节点的同一条边。该式中可用和 转换成与时间无关的递归关系，求得,62,3.5.3 BA无标度网络的度分布和度相关,对一个具有任意度分布的网络，若边随机连接，则 。而上式最重要的特性是联合度分布不能进行因子分解，即 。这表明连通节点度之间的相关性自然产生。仅当1kl，nkl才可以简化为因子分解表达式， 。正如所期望的那样，若网络缺少相关性，在这种情况下都与nklk-3l-3不同。该结果首次证明了产生无标度网络的动态过程建立了节点间的非平凡相关。,63,3.5.4 BA无标度网络的平均距离和集聚系数,1.平均距离 下图给出了平均度k4的BA模型平均距离LBA随网络规模N的变化曲线，跟它比较的是相同规模和相同平均度条件下的随机图的平均距离Lrand。,64,3.5.4 BA无标度网络的平均距离和集聚系数,从图中可以看出，对任意N，BA网络中的平均距离比随机图中的要小得多，这说明异质性无标度网络拓扑比同质性随机图拓扑在“拉拢节点”方面效率更高。从模拟结果上看，BA模型网络中的平均距离是随N按指数增长的，它很好地符合下式 LBAAln（NB）C式中，A，B和C为常数。 然而这是有争议的，因为大多数学者提出的BA网络的平均距离随N按指数增长关系为 LBAlnNln（lnN） 由此可见BA网络的平均距离比较小，表明该网络具有小世界特性。,65,3.5.4 BA无标度网络的平均距离和集聚系数,2.集聚系数 下图给出了平均度k4的BA模型集聚系数CBA随网络规模N的变化曲线，跟它比较的是相同规模和相同平均度条件下的随机图的集聚系数Crand。,66,3.5.4 BA无标度网络的平均距离和集聚系数,从图中可以看出：无标度网络的集聚系数几乎是随机图的5倍，随节点数的增加，这个倍率还会稍微地随着增加；BA模型网络的集聚系数是随着网络尺度N的增加而减小的，其大概遵循幂指数规律，即CBAN-0.75；BA模型网络的集聚系数比随机图Crand的衰减要慢；由于无标度网络的集聚系数依赖于N，因此它的行为与小世界模型（集聚系数与N无关）不同。 因此，BA模型不仅平均距离很小，集聚系数也很小，但比同规模随机图的集聚系数要大，不过当网络趋于无穷大时，这两种网络的集聚系数均近似为零。目前，学者们已经给出了BA无标度网络集聚系数的解析公式为,67,3.5.5 BA无标度网络的特征谱,BA模型的谱密度是连续的，但它与随机图的半圆形分布的形状有很大的不同。BA模型谱密度（）的主体部分基本上关于0对称，呈三角形，顶部位于半圆形曲线的上方，尾部以幂律形式衰减，如下图所示。这个幂律衰减是由于特征矢量集中在具有最高度值的节点上。,68,3.5.5 BA无标度网络的特征谱,当mm01时，BA模型是一棵树，因此它的谱密度一定是关于0对称的。当m1时，BA模型谱密度的主体部分基本上是关于0对称的三角形,中部指数衰减，尾部为幂律分布，谱密度在0点附近有最大值（说明存在大量的模较小的特征值）。 与随机图情况类似（与小世界网络不同），主特征值1与谱的主体部分明显分离。1的下界由网络最大度值k1的平方根给出。由于BA网络的度值随着网络规模以N0.5的速度增长，因此1以N0.25的速度增长。数值结果表明对于小规模网络，1偏离期望的行为，只有当N才能渐进地达到期望行为。这种现象表明了最长行矢量间相关性的存在，也为BA模型中存在相关性提供了额外的证据。,69,3.5.5 BA无标度网络的特征谱,需要指出的是，主特征值对谱（）的矩起到重要作用，因为它决定了网络的回路结构。和次临界的随机图（即p1N）相比（其回路所占的比例可忽略不计），BA网络中四条边以上回路所占比例随N的速度增长，且增长速率随着回路边数的增加而加快。但是，三角形所占比例随N下降。,返回 目录,70,3.6 层次网络,3.6.1 模块性和模体3.6.2 层次网络概念和特性3.6.3 层次网络构造方法,71,3.6.1 模块性和模体,1.模块性 一般而言，模块是指一组物理上或功能上连接在一起的、共同完成一个相对独立功能的节点。 由于大量系统中都存在模块性特征，复杂网络的模块分析方法可以应用于很多领域。例如生物网络。2.模体 模体是网络中由少量节点按照一定拓扑结构构成并且相对于随机网络在网络中富集出现的小规模模式。模体是在网络中反复出现的相互作用的基本模式，这种模式在现实网络中出现的频率远远高于其在随机网络中出现的频率。实际上，模式就是网络中大量出现的具有相同结构的小规模子图，并且这种子图从局部层次刻画了网络内部相互连接的特定模式。,72,3.6.2 层次网络概念和特性,1.层次网络概念 层次模块性表现为：度很小的节点具有高的集聚系数且属于高度连接的小模块；相反，度很高的hub节点具有低的集聚系数，其作用只是把不同的模块连接起来。也就是说，在具有层次模块性的网络中，很多内部关联密集的小规模节点组之间松散关联，从而形成更大规模的拓扑模块。 层次模块性的一个重要标志是聚度相关性满足幂律分布。在许多现实网络中，C（k）与k之间存在倒数关系，即C（k）k1。把这种倒数关系的聚度相关性称为层次性，把具有层次性的网络称作层次网络。更严格地讲，层次模块性用幂律来刻画就是：C（k）ka，其中a为层次指数。,73,3.6.2 层次网络概念和特性,2.层次网络的特征谱密度 下图给出了节点数为256的随机层次网络的特征谱密度示意图。由图可以看出，层次网络的特征谱和其他网络的特征谱明显不同。尤其是（0），它与网络的自我平衡有着重要的关系，不同类型的网络其值明显不同。对于层次网络而言，该值非常小；而对于随机网络或无标度网络来说，该值最大。,74,3.6.3 层次网络构造方法,1.确定性层次网络 构造方法可以描述为：首先生成一个具有M个节点组成的完全图模块，定义其中一个节点为中心节点，其它M1个节点为外围节点；然后制作M1个复制品，并将每个复制品的M1个外围节点与原来完全图的中心节点进行连接，这样就得到一个具有M2个节点的模块；接着将刚获得的新模块复制M1个，把每个复制品的（M1）2个外围节点连接到原模块的中心节点上，于是形成一个M3个节点的模块；这一复制和连接过程可以无限地进行下去，直到形成所需大小的网络规模为止。这样得到的层次网络的度指数为,75,3.6.3 层次网络构造方法,2.自组织层次网络 曹继伟提出的自组织层次网络的构建步骤如下： 在一个矩形中随机均匀分布一些点代表网络节点。 初始化：给每个节点分配一个定时器，即到达某个时间后，节点才开始活动。 节点活动：节点的活动分为发送消息和接收消息。每条消息含有节点ID及节点的度等信息。节点的度等参数决定了该节点发出的消息的辐射范围，还决定了该节点能够收到来自多大范围内的消息。 每个节点将一定时期内收到的消息用相应的规则计算选择其中一个消息源与之建立连接。,76,3.6.3 层次网络构造方法,经过一段时间的进化后，一个具有层次结构的复杂网络就涌现出来。下图给出了基于消息传递的自组织拓扑演化示意图。与确定性层次网络构造不同，自组织层次网络模型的层次特征是自动涌现出来的。,返回 目录,77,3.7 确定性网络,3.7.1 确定性均匀递归树3.7.2 确定性小世界模型3.7.3 确定性无标度网络,78,3.7.1 确定性均匀递归树,均匀递归树是一棵生长树，其构造方法如下：从单一节点开始，在每个时间步中生成一个新节点，该新节点与网络中均匀选择的一个老节点相连接。该模型与ER模型的不同之处在于：ER随机图是静态模型，均匀递归树为动态增长的模型。 确定性均匀递归树是均匀递归树的确定性版本，如下图所示。,79,3.7.1 确定性均匀递归树,它是通过迭代的方式构造的，设Ut（t0）表示经过t步迭代后得到的网络，则网络的生成方法如下：当t0时，U0是由两个节点及连接这两个节点的一条边构成；当t1时，Ut通过对Ut-1进行操作得到：将网络Ut-1的每个节点连接一个新节点；不断重复这个过程，可得到确定性均匀递归树。 该模型的主要特性为：度分布为指数分布，集聚系数为0，平均距离随着节点数的增加以对数方式增长。因集聚系数为0，该网络不是小世界网络。,80,3.7.2 确定性小世界模型,通过迭代方式构造确定性小世界网络是最简单的一种构造方法，若用G（t）表示经过t步迭代后生成的小世界网络，则网络G（t）的生成算法如下：当t0，初始网络G（0）为一个三角形；当tl时，G（t）通过下面的方式得到：对G（t1）中在t1步生成的每一条边，都加入一个新节点，并与该边的两个端点建立连接。下图给出了利用这种迭代方法构造的确定性小世界网络的前四步迭代结果。,81,3.7.2 确定性小世界模型,该确定性小世界网络是一个指数网络。网络的平均集聚系数为0.6931，网络集聚程度非常高。网络的直径和平均距离短。这些特性都完全满足小世界网络的主要特性。节点的平均度为 。当t趋于无穷大时，kt趋于4。因此，当t足够大时，该网络是一个稀疏的网络。 事实上，确定性小世界模型的构造方法有很多种。例如，可以通过改造现有的非小世界网络模型使其变成小世界网络模型。一般来说，这种改造需从小世界网络的两个重要特点来入手：较高的集聚系数和较小的平均距离。可以通过在原有模型迭代的基础上附加一些自定义规则，从而使重建网络具有上述两个重要特点，以达到目的。,82,3.7.2 确定性小世界模型,【例3.4】求出下图所示网络的度分布、集聚系数、直径的表达式，并证明该模型为小世界网络。解：假设网络经过t次迭代，网络拥有的节点数和边数分别用Nt和Mt表示，则从上图可以看出N0=1、M0=0，而不难推出Nt=2t+11和Mt=52t7。通过对网络进行分析之后，可以得出以下表达式：,83,3.7.2 确定性小世界模型,（1）度分布（2）集聚系数（3）直径（4）总结 由于上面网络的直径增长速度与节点的对数成线性关系，因此网络的平均距离将比对数增长缓慢。至此可以得出结论：网络具有较高集聚系数且具有较短平均距离，符合小世界特性。,84,3.7.3 确定性无标度网络,阿波罗填充问题的迭代生成过程为：初始时有三个相切的圆盘，它们的空隙是边为曲线的一个三角形（曲线三角形）。然后在第一个迭代步，将一个合适大小的圆盘放到空隙处，使得圆盘与曲线三角形的三边相切。当然新放入的圆盘没有填满空隙，而是产生三个更小的空隙。在第二个迭代步，将三个圆盘插入到新产生的空隙中，使得每个圆盘与相应的曲线三角形的三边相切。这一过程如此不断地重复下去。当经过无限步此项过程后，便得到阿波罗填充问题。如果每次只是随机选择一个空隙进行填充，经过长时间的填充后，便得到随机阿波罗填充问题，根据这一随机填充过程构造的网络叫随机阿波罗网络。,85,3.7.3 确定性无标度网络,而确定性阿波罗网络的构造算法为：将每个圆盘对应网络的一个节点，如果节点所对应的圆盘相切，则节点间有边相连，这样便得到二维确定性阿波罗网络。下图显示了二维确定性阿波罗网络的形成过程。 与二维确定性阿波罗网络类似，还可以用相同的迭代方法构造高维阿波罗网络。所有与d维阿波罗填充问题有关的网络均为无标度网络，它们的集聚系数较大，平均距离较小，因此阿波罗网络是同时具备无标度和小世界特征。,返回 目录,86,3.8 自相似网络,3.8.1 复杂网络的自相似性3.8.2 自相似复杂网络的构造方法,87,3.8.1 复杂网络的自相似性,1.几何维数、豪斯道夫维数 几何维数（拓扑维数）：零维的点、一维的线、二维的面、三维的立体、乃至四维的时空。是整数。 豪斯道夫维数：设想有一个由三维空间内具有有限大小的点组成的集合，N是用来覆盖这个集合内所有点所需的半径为R的球体的最少个数，则这个最小数N是R的一个函数，记作N（R）。显然R越小，则N越大，假设N（R）和Rd之间存在一个反比的关系，记作N（R）1Rd，当R趋向于0时，得到 就是这个集合的豪斯道夫维数。可能会是一个非整的有理数或者无理数。,88,3.8.1 复杂网络的自相似性,2.分形 分形具有如下五个基本特性： 在任意小尺度上具有精细的结构。 分形不能用传统的欧氏几何语言来描述，它既不是满足某些条件的点的轨迹，也不是某些简单方程的解集。 分形具有某种自相似形式，可能是近似的自相似或者统计的自相似。 一般来说，分形的豪斯道夫“分形维数”，严格大于它相应的拓扑维数。 分形具有简单的递归定义。,89,3.8.1 复杂网络的自相似性,3.复杂网络的自相似性 复杂系统的自相似性是指某种结构或过程的特征从不同的空间角度或时间尺度来看都是相似的，或者某系统或结构的局域性质或局域结构与整体类似。 一般而言，分形的网络总是自相似的，但是自相似的网络并不总是分形的。4.超家族 有些不同类型的