第二章 网络拓扑基本模型及其性质.ppt

《第二章 网络拓扑基本模型及其性质.ppt》由会员分享，可在线阅读，更多相关《第二章 网络拓扑基本模型及其性质.ppt（42页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第二章第二章 网络拓扑基本模型及其性质网络拓扑基本模型及其性质2.1 2.1 引言引言引言引言2.2 2.2 规则网络规则网络规则网络规则网络2.3 2.3 随机图随机图随机图随机图2.4 2.4 小世界网络模型小世界网络模型小世界网络模型小世界网络模型2.5 2.5 无标度网络模型无标度网络模型无标度网络模型无标度网络模型2.6 2.6 局域世界演化网络模型局域世界演化网络模型局域世界演化网络模型局域世界演化网络模型2.7 2.7 模块性与等级网络模块性与等级网络模块性与等级网络模块性与等级网络2.8 2.8 复杂网络的自相似性复杂网络的自相似性复杂网络的自相似性复杂网络的自相似性2.1 引

2、言引言 要理解网络结构与网络行为之间的关系，并进而要理解网络结构与网络行为之间的关系，并进而要理解网络结构与网络行为之间的关系，并进而要理解网络结构与网络行为之间的关系，并进而考虑改善网络的行为，就需要对实际的网络的结构特考虑改善网络的行为，就需要对实际的网络的结构特考虑改善网络的行为，就需要对实际的网络的结构特考虑改善网络的行为，就需要对实际的网络的结构特征有很好的了解，并在此基础上建立合适的网络结构征有很好的了解，并在此基础上建立合适的网络结构征有很好的了解，并在此基础上建立合适的网络结构征有很好的了解，并在此基础上建立合适的网络结构模型。本章介绍几类基本的模型，包括规则网络、随模型。本章

3、介绍几类基本的模型，包括规则网络、随模型。本章介绍几类基本的模型，包括规则网络、随模型。本章介绍几类基本的模型，包括规则网络、随机图、小世界网络、无标度网络、等级网络和局域世机图、小世界网络、无标度网络、等级网络和局域世机图、小世界网络、无标度网络、等级网络和局域世机图、小世界网络、无标度网络、等级网络和局域世界演化网络模型。此外，进一步介绍复杂网络的模块界演化网络模型。此外，进一步介绍复杂网络的模块界演化网络模型。此外，进一步介绍复杂网络的模块界演化网络模型。此外，进一步介绍复杂网络的模块化和自相似性等特征。化和自相似性等特征。化和自相似性等特征。化和自相似性等特征。2.2 规则网络规则网络

4、 在一个在一个在一个在一个全局耦合网络全局耦合网络全局耦合网络全局耦合网络中，中，中，中，任意两个点之间都有边直接相连。任意两个点之间都有边直接相连。任意两个点之间都有边直接相连。任意两个点之间都有边直接相连。因此，全局耦合网络具有最小的因此，全局耦合网络具有最小的因此，全局耦合网络具有最小的因此，全局耦合网络具有最小的平均路径长度平均路径长度平均路径长度平均路径长度L Lgcgc=1=1和最大的和最大的和最大的和最大的聚聚聚聚类系数类系数类系数类系数C Cgcgc=1.=1.最近邻耦合网络最近邻耦合网络最近邻耦合网络最近邻耦合网络中每一个节点中每一个节点中每一个节点中每一个节点只和周围的邻居

5、节点相连。具有只和周围的邻居节点相连。具有只和周围的邻居节点相连。具有只和周围的邻居节点相连。具有周期边界条件的最近邻耦合网络周期边界条件的最近邻耦合网络周期边界条件的最近邻耦合网络周期边界条件的最近邻耦合网络包含包含包含包含NN个围成一个环的点，其中个围成一个环的点，其中个围成一个环的点，其中个围成一个环的点，其中每个点都与它左右各每个点都与它左右各每个点都与它左右各每个点都与它左右各K/2K/2个邻居个邻居个邻居个邻居节点相连，这里节点相连，这里节点相连，这里节点相连，这里K K是一个偶数。对是一个偶数。对是一个偶数。对是一个偶数。对于较大于较大于较大于较大K K值，最近邻耦合网络的值，最

6、近邻耦合网络的值，最近邻耦合网络的值，最近邻耦合网络的聚聚聚聚类系数类系数类系数类系数为：为：为：为：Cnc=因此这样的网络是高度聚类的。然而，最近邻耦合因此这样的网络是高度聚类的。然而，最近邻耦合因此这样的网络是高度聚类的。然而，最近邻耦合因此这样的网络是高度聚类的。然而，最近邻耦合网络不是一个小世界网络，相反对固定的网络不是一个小世界网络，相反对固定的网络不是一个小世界网络，相反对固定的网络不是一个小世界网络，相反对固定的K K值，该网络值，该网络值，该网络值，该网络的的的的平均路径长度平均路径长度平均路径长度平均路径长度为：为：为：为：Lnc 星形耦合网络星形耦合网络，它有一个中心点，其

7、余的，它有一个中心点，其余的N-N-1 1个点都只与这个中心点连接，而他们彼此之间个点都只与这个中心点连接，而他们彼此之间不连接。星形网络的不连接。星形网络的平均路径长度平均路径长度为：为：Lstar=星形网络的星形网络的聚类系数聚类系数为为：Cstar=2.3 随机图随机图 假设有大量的纽扣（假设有大量的纽扣（N1N1）散落在地上，并以）散落在地上，并以相同的概率相同的概率P P给每对纽扣系上一根线。这样就会得到给每对纽扣系上一根线。这样就会得到一个有一个有N N个节点，约个节点，约pN(N-1)/2pN(N-1)/2条边的条边的ERER随机图的实随机图的实例。例。（a a）p=0,p=0,

8、给定的给定的1010个孤立点；（个孤立点；（b b）（d d）分别以连接概率）分别以连接概率p=0.1p=0.1、p=0.15p=0.15和和p=0.25p=0.25生成的随机图生成的随机图 （a a）（b b）（c c）（d d）随机图理论的一个随机图理论的一个主要研究课题主要研究课题是：当概率是：当概率p p为多为多大时，随机图会产生一些特殊的属性？大时，随机图会产生一些特殊的属性？ErdosErdos和和RenyiRenyi系统性地研究了当系统性地研究了当N N 时，时，ERER随机随机图的性质与概率图的性质与概率p p之间的关系。他们采用如下定义：之间的关系。他们采用如下定义：如果当如

9、果当N N 时产生一个具有性质时产生一个具有性质Q Q的的ERER随机图随机图的概率为的概率为1 1，那么就称几乎每一个，那么就称几乎每一个ERER随机图都具有性质随机图都具有性质Q Q。ErdosErdos和和RenyiRenyi最重要的发现是最重要的发现是ERER随机图有如下的随机图有如下的涌现或变相性质涌现或变相性质：ERER随机图的许多重要的性质都是突然涌现的，也随机图的许多重要的性质都是突然涌现的，也就是说，对于任一给定的概率就是说，对于任一给定的概率p p，要么几乎每一个图都，要么几乎每一个图都具有某个性质具有某个性质Q Q，要么几乎每一个图都不具有该性质。，要么几乎每一个图都不具

10、有该性质。ERER随机图随机图平均路径长度平均路径长度为为:L LERERlnN/lnlnN/ln。这种平均这种平均路径长度为网络规模的对数增长函数的特性就是典型的小路径长度为网络规模的对数增长函数的特性就是典型的小世界特征世界特征。ERER随机图的随机图的聚类系数聚类系数是是:C=p=/N1:C=p=/N1，这意味着大规，这意味着大规模的稀疏模的稀疏ERER随机图没有聚类特性。随机图没有聚类特性。固定固定ERER随机图的平均度随机图的平均度不变，则对于充分大的不变，则对于充分大的N N，由于每条边出现与否都是独立的，由于每条边出现与否都是独立的，ERER随机图的随机图的度分布度分布可可以用以

11、用PoissionPoission分布来表示分布来表示:P(kP(k)=p)=pk k(1-p)(1-p)N-kN-k2.4 小世界网络模型小世界网络模型 作为从完全规则网络向完全随机图的过渡，作为从完全规则网络向完全随机图的过渡，WattsWatts和和StrogtzStrogtz引入了小世界网络模型，称为引入了小世界网络模型，称为WSWS小世界模型小世界模型。其。其构造算法构造算法如下：如下：从规则图开始：考虑一个含有从规则图开始：考虑一个含有N N个点的最近邻耦合个点的最近邻耦合网络，它们围成一个环，其中每个节点都与它左右相邻网络，它们围成一个环，其中每个节点都与它左右相邻的各的各K/2

12、K/2节点相连，节点相连，K K是偶数。是偶数。随机化重连：以概率随机化重连：以概率p p随机地重新连接网络中的每随机地重新连接网络中的每个边，即将边的一个端点保持不变，而另一个端点取为个边，即将边的一个端点保持不变，而另一个端点取为网络中随机选择的一个节点，其中规定，任意两个不同网络中随机选择的一个节点，其中规定，任意两个不同的节点之间至多只能有一条边，并且每一个节点都不能的节点之间至多只能有一条边，并且每一个节点都不能有边与自身相连。有边与自身相连。在上述模型中，在上述模型中，p=0p=0对应于完全规则网络，对应于完全规则网络，p=1p=1则对则对应于完全随机网络，通过调节应于完全随机网络

13、，通过调节p p的值就可以控制从完全规的值就可以控制从完全规则网络到完全随机网络的过渡，如下图所示。则网络到完全随机网络的过渡，如下图所示。这类既具有较短的平均路径长度又具有较高的聚类这类既具有较短的平均路径长度又具有较高的聚类系数的网络就称为系数的网络就称为小世界网络小世界网络 WSWS小世界模型构造算法中的随机化过程可能破坏网小世界模型构造算法中的随机化过程可能破坏网络的连通性。另一个研究较多的小世界模型是由络的连通性。另一个研究较多的小世界模型是由NewmanNewman和和WattsWatts提出的提出的NWNW小世界模型小世界模型。该模型是通过。该模型是通过”随机化加边随机化加边”取

14、代取代WSWS小世界模型中的随机化重连而得小世界模型中的随机化重连而得到的。具体的到的。具体的构造算法构造算法如下：如下：从规则图开始：考虑一个含有从规则图开始：考虑一个含有N N个点的最近邻耦个点的最近邻耦合网络，它们围成一个环，其中每个节点都与它左右相合网络，它们围成一个环，其中每个节点都与它左右相邻的各邻的各K/2K/2节点相连，节点相连，K K是偶数。是偶数。随机化重连：以概率随机化重连：以概率p p在随机选取的一对节点之间在随机选取的一对节点之间加上一条边。其中，任意两个不同的节点之间至多只能加上一条边。其中，任意两个不同的节点之间至多只能有一条边，并且每一个节点都不能有边与自身相连

15、。有一条边，并且每一个节点都不能有边与自身相连。在在NWNW小世界模型中，小世界模型中，p=0p=0对应于原来的最近邻耦合网对应于原来的最近邻耦合网络，络，p=1p=1对应于全局耦合网络。对应于全局耦合网络。下面介绍小世界网络模型的一些统计性质。下面介绍小世界网络模型的一些统计性质。1.1.聚类系数聚类系数WSWS小世界网络的小世界网络的聚类系数聚类系数为：为：NWNW小世界网络的小世界网络的聚类系数聚类系数为：为：2.2.平均路径长度平均路径长度 迄今为止，人们还没有关于迄今为止，人们还没有关于WSWS小世界模型的平均路径长小世界模型的平均路径长度度L L的精确解析表达式，不过，利用重正化群

16、的方法可以得的精确解析表达式，不过，利用重正化群的方法可以得到如下公式：到如下公式：其中其中f(uf(u)为一普适标度函数，满足为一普适标度函数，满足NewmanNewman等人基于平均场方法给出了如下的近似表达式：等人基于平均场方法给出了如下的近似表达式：但目前为止还没有但目前为止还没有f(uf(u)的精确显示表达式。的精确显示表达式。3.3.度分布度分布 在基于在基于“随机化加边随机化加边”机制的机制的NWNW小世界模型中，每个小世界模型中，每个节点的度至少为节点的度至少为K K。因此当。因此当kKkK时，一个随机选取的节点的时，一个随机选取的节点的度为度为k k的概率为：的概率为：而当而

17、当kKk=K/2k=K/2时有：时有：而当而当kK/2kK/2时时P(kP(k)=0)=0。类似于类似于ERER随机图模型，随机图模型，WSWS小世界模型也是所有节点的小世界模型也是所有节点的度都近似相等的均匀网络。度都近似相等的均匀网络。2.5 无标度网络模型无标度网络模型2.5.1 BA2.5.1 BA无标度网络无标度网络 近年来在复杂网络研究上的另一个重大发现就是近年来在复杂网络研究上的另一个重大发现就是许多复杂网络，包括许多复杂网络，包括InternetInternet、WWWWWW以及姓陈代谢网以及姓陈代谢网络等的连接度分布函数具有幂律形式。由于这类网络络等的连接度分布函数具有幂律形

18、式。由于这类网络的节点的连接度没有明显的特征长度，故称为的节点的连接度没有明显的特征长度，故称为无标度无标度网络网络。为了解释幂律分布的产生机理，为了解释幂律分布的产生机理，BarabasiBarabasi和和AlbertAlbert提出了一个无标度网络模型，现被称为提出了一个无标度网络模型，现被称为BABA模型。模型。他们认为以前的许多网络模型都没有考虑到实际网络他们认为以前的许多网络模型都没有考虑到实际网络的如下两个重要特性：的如下两个重要特性：增长特性：即网络规模是不断扩大的。例如每个增长特性：即网络规模是不断扩大的。例如每个月都会有大量的新的科研文章发表，而月都会有大量的新的科研文章发

19、表，而WWWWWW上则每天上则每天有大量新的网页产生。有大量新的网页产生。优先连接特性：即新的节点更倾向于与那些具有优先连接特性：即新的节点更倾向于与那些具有较高连接度的较高连接度的“大大”节点相连接。这种现象也被称为节点相连接。这种现象也被称为“富者更富富者更富”或或“马太效应马太效应”。例如新发表的文章更倾向。例如新发表的文章更倾向于引用一些已被广泛引用的重要文献，新的个人主页上于引用一些已被广泛引用的重要文献，新的个人主页上的超文本链接更有可能指向新浪、雅虎等著名的站点。的超文本链接更有可能指向新浪、雅虎等著名的站点。基于网络的增长和优先连接特性，基于网络的增长和优先连接特性，BABA无

20、标度网络模无标度网络模型的型的构造算法构造算法如下：如下：增长：从一个具有增长：从一个具有mm0 0个节点的网络开始，每次引入个节点的网络开始，每次引入一个新的节点，并且连接到一个新的节点，并且连接到mm个已存在的节点上，这里个已存在的节点上，这里m=mm=m0 0。优先连接：一个新节点与一个已经存在的节点优先连接：一个新节点与一个已经存在的节点i i相连相连接的概率接的概率 与节点与节点i i的度的度k ki、节点、节点j j的度的度k k j之间满足如下关系：之间满足如下关系：在经过在经过t t步后，这种算法产生一个有步后，这种算法产生一个有N=t+mN=t+m0 0个节点、个节点、mtm

21、t条边的网络。条边的网络。BABA无标度网络的演化无标度网络的演化(m=m(m=m0 0=2)=2)1.1.平均路径长度平均路径长度BABA无标度网络的无标度网络的平均路径长度平均路径长度为：为：这表明该网络具有小世界特性。这表明该网络具有小世界特性。2.2.聚类系数聚类系数BABA无标度网络的无标度网络的聚类系数聚类系数为：为：这表明与这表明与ERER随机图类似，当网络规模充分大时随机图类似，当网络规模充分大时BABA无标度网络无标度网络不具有明显的聚类特征不具有明显的聚类特征3.3.度分布度分布BABA网络的网络的度分布函数度分布函数为：为：这表明这表明BABA网络的度分布函数可由幂指数为

22、网络的度分布函数可由幂指数为3 3的幂律函数近似的幂律函数近似描述。描述。2.5.2 2.5.2 鲁棒性与脆弱性鲁棒性与脆弱性 对于一个给定的网络，如果在移对于一个给定的网络，如果在移走少量节点后网络中的绝大部分节点走少量节点后网络中的绝大部分节点仍是连通的，那么就称该网络的连通仍是连通的，那么就称该网络的连通性对节点故障具有性对节点故障具有鲁棒性鲁棒性去除节点对网络连通性的影响去除节点对网络连通性的影响 下面比较下面比较ERER随机图和随机图和BABA无标度网络的连通性对节点去除无标度网络的连通性对节点去除的鲁棒性。现考虑两种去除策略：一是随机故障策略，即完的鲁棒性。现考虑两种去除策略：一是

23、随机故障策略，即完全随机地去除网络中的一部分节点；二是蓄意攻击策略，即全随机地去除网络中的一部分节点；二是蓄意攻击策略，即从去除网络中度最高的节点开始，有意识地去除网络中一部从去除网络中度最高的节点开始，有意识地去除网络中一部分度最高的节点。假设去除的节点数占原始网络总节点数的分度最高的节点。假设去除的节点数占原始网络总节点数的比例为比例为f f，可以用最大连通子图的相对大小，可以用最大连通子图的相对大小S S和平均路径长度和平均路径长度l l与与f f的关系来度量网络的鲁棒性。研究发现，的关系来度量网络的鲁棒性。研究发现，ERER随机图和随机图和BABA无标度网络之间存在极其显著的差异。无标

24、度网络对随机节无标度网络之间存在极其显著的差异。无标度网络对随机节点故障具有极高的鲁棒性：与随机图相比，最大连通子图的点故障具有极高的鲁棒性：与随机图相比，最大连通子图的相对大小在相对高得多的相对大小在相对高得多的f f 时才下降到零，而其平均路径长时才下降到零，而其平均路径长度的增长则要缓慢得多。无标度网络的这种对随机故障的高度的增长则要缓慢得多。无标度网络的这种对随机故障的高度鲁棒性，来自于网络度分布的极端非均匀性：绝大多数节度鲁棒性，来自于网络度分布的极端非均匀性：绝大多数节点的度都相对很小，而有少量节点的度相对很大。然而正是点的度都相对很小，而有少量节点的度相对很大。然而正是这种非均匀

25、性使得无标度网络对蓄意攻击具有高度的脆弱性：这种非均匀性使得无标度网络对蓄意攻击具有高度的脆弱性：只要有意识地去除网络中极少量度最大的节点就会对整个网只要有意识地去除网络中极少量度最大的节点就会对整个网络的连通性产生大的影响。络的连通性产生大的影响。方块对应随机故障，圆点对应蓄意攻击方块对应随机故障，圆点对应蓄意攻击2.5.3 2.5.3 适应度模型适应度模型 BABA无标度模型把实际复杂网络的无标度特性，归结为增无标度模型把实际复杂网络的无标度特性，归结为增长和优先连接这两个非常简单明了的机制。但这也不可避免长和优先连接这两个非常简单明了的机制。但这也不可避免地使地使BABA无标度网络模型和

26、真实网络相比存在一些明显的限制。无标度网络模型和真实网络相比存在一些明显的限制。例如，例如，BABA模型只能生成度分布的幂律指数固定为模型只能生成度分布的幂律指数固定为3 3的无标度的无标度网络，而各种实际的复杂网络的幂律指数则不甚相同，而且网络，而各种实际的复杂网络的幂律指数则不甚相同，而且大都属于大都属于2 2至至3 3的范围内。此外，实际网络常常具有一些非幂的范围内。此外，实际网络常常具有一些非幂律特征。律特征。在在BABA无标度网络的增长过程中，节点的度也在发生变化无标度网络的增长过程中，节点的度也在发生变化并且满足如下幂律关系：并且满足如下幂律关系：其中，其中，k ki i(t(t)

27、为第为第i i个节点在时刻个节点在时刻t t的度，的度，t ti i是第是第i i个节点加入到网个节点加入到网络中的时刻。上式表明，在络中的时刻。上式表明，在BABA无标度网络中，越老的节点具无标度网络中，越老的节点具有越高的度。然而在许多实际网络系统中，节点的度及其增有越高的度。然而在许多实际网络系统中，节点的度及其增长速度并非只与该节点的年龄有关。例如，社会关系网络长速度并非只与该节点的年龄有关。例如，社会关系网络中的某些人具有较强的交友能力，他们可以较为容易地把一中的某些人具有较强的交友能力，他们可以较为容易地把一次随机相遇变为一个持续的社会连接。显然，这些例子都是次随机相遇变为一个持续

28、的社会连接。显然，这些例子都是与节点的内在性质相关的。与节点的内在性质相关的。BianconiBianconi和和BarabasiBarabasi把这一性质称把这一性质称为节点的适应度，并提出了为节点的适应度，并提出了适应度模型适应度模型，其构造算法如下：，其构造算法如下：增长：从一个具有增长：从一个具有mm0 0个节点的网络开始，每次引入个节点的网络开始，每次引入一个新的节点，并且连接到一个新的节点，并且连接到mm个已存在的节点上，这里个已存在的节点上，这里m=mm=mM=m），作为新加入节点的局域世界。新加），作为新加入节点的局域世界。新加入的节点根据优先连接概率入的节点根据优先连接概率来

29、选择与局域世界中的来选择与局域世界中的mm个节点相连接，其中个节点相连接，其中LWLW由新选的由新选的MM个节点组成。个节点组成。显而易见，在显而易见，在t t时刻，时刻，m=M=mm=M1.1Nrand1.1Nrandi i。网络模体检测示意图网络模体检测示意图2.7.2 2.7.2 等级网络等级网络 为了说明许多实为了说明许多实际系统中同时存在的际系统中同时存在的模块性、局部聚类和模块性、局部聚类和无标度拓扑特性，需无标度拓扑特性，需要假设模块以某种迭要假设模块以某种迭代方式生成一个等级代方式生成一个等级网络。研究表明，一网络。研究表明，一些网络中的拓扑模块些网络中的拓扑模块确实是按等级组

30、织起确实是按等级组织起来的。来的。等级模块性的一个最重要的量化标志是节点聚类系数服等级模块性的一个最重要的量化标志是节点聚类系数服从幂律从幂律C(kC(k)k k-1-1。这表明度很小的节点具有高的聚类系。这表明度很小的节点具有高的聚类系数且属于高度连接的小模块。相反，度很高的数且属于高度连接的小模块。相反，度很高的hubhub节点具节点具有低的聚类系数，其作用只是把不同的模块连接起来。有低的聚类系数，其作用只是把不同的模块连接起来。需要注意的是，需要注意的是，ERER随机图和随机图和BABA无标度网络都不具有等级无标度网络都不具有等级拓扑；在这两类网络中节点聚类系数拓扑；在这两类网络中节点聚

31、类系数C(kC(k)与该节点的度与该节点的度k k无关。无关。2.7.3 2.7.3 超家族超家族 小世界和无标度是许多实际网络的共同全局结构特征，小世界和无标度是许多实际网络的共同全局结构特征，那么不同德网络是否也有可能具有相似的局部结构特征？网那么不同德网络是否也有可能具有相似的局部结构特征？网络模体的研究有助于人们从局部结构上来理解复杂网络的设络模体的研究有助于人们从局部结构上来理解复杂网络的设计原理。在此基础上，计原理。在此基础上，MiloMilo等人提出了基于重要性剖面等人提出了基于重要性剖面(SP)(SP)比较网络局部结构的方法。计算比较网络局部结构的方法。计算SPSP的基本思想仍

32、然是把一个的基本思想仍然是把一个实际网络与其对应的随机化网络作对比，这样就可避免不同实际网络与其对应的随机化网络作对比，这样就可避免不同网络的规模和度序列的影响。网络的规模和度序列的影响。网络中每个子图网络中每个子图i i的统计重要性用的统计重要性用来描述，其中来描述，其中NrealNreali i和和NrandNrandi i仍然分别表示该子图在实际网络仍然分别表示该子图在实际网络和对应的随机化网络中出现的次数，和对应的随机化网络中出现的次数，和和std(Nrandstd(Nrandi i)分别是分别是NrandNrandi i的均值和标准方差。对的均值和标准方差。对Z Zi i作规范化处理

33、就得到对作规范化处理就得到对应的应的SPSPi i：研究表明，相同类型的网络不仅具有相同的网络模体，研究表明，相同类型的网络不仅具有相同的网络模体，而且各个模体在网络中的相对重要性也是相似的。此外，一而且各个模体在网络中的相对重要性也是相似的。此外，一个网络超家族中可能包含着规模差异很大的功能极其不同的个网络超家族中可能包含着规模差异很大的功能极其不同的网络。网络。2.8 复杂网络的自相似性复杂网络的自相似性 左图中的等级网络看上去左图中的等级网络看上去有一个非常明显的特征，那就有一个非常明显的特征，那就是该网络的部分与整体具有很是该网络的部分与整体具有很明显的相似性；而局部在某种明显的相似性

34、；而局部在某种意义上与整体相似，即自相似意义上与整体相似，即自相似性，正是分型的一个基本特征。性，正是分型的一个基本特征。与自相似性密切相关的一与自相似性密切相关的一个概念是分数维。计算自相似分形的维数的一种常用方法是个概念是分数维。计算自相似分形的维数的一种常用方法是盒记数法。该方法的基本思想是用边长为盒记数法。该方法的基本思想是用边长为l lB B的盒子来覆盖该的盒子来覆盖该图形，并统计完全覆盖该图形所需要的最少的盒子数图形，并统计完全覆盖该图形所需要的最少的盒子数N NB B(l(lB B).).这里的盒子在一位情况下是线段，二维情况下是正方形，这里的盒子在一位情况下是线段，二维情况下是

35、正方形，三维情况下是立方体，三维情况下是立方体，l l B B是盒子的尺寸。图形的维数的近是盒子的尺寸。图形的维数的近似计算公式为：似计算公式为：等价地有幂律标度公式等价地有幂律标度公式一般情况下，在理论上只有当盒子尺寸一般情况下，在理论上只有当盒子尺寸l lB B趋于零时，才能由趋于零时，才能由公式等到维数的精确值。人们通常在对数坐标系中画出公式等到维数的精确值。人们通常在对数坐标系中画出N NB B(l(lB B)和和l lB B之间的关系，拟合直线的斜率的负值就是之间的关系，拟合直线的斜率的负值就是d dB B 盒记数法用于复杂网络的只要困难是：对于大多数实盒记数法用于复杂网络的只要困难

36、是：对于大多数实际网络并不存在包含这些网络的自然地欧式空间，而且复际网络并不存在包含这些网络的自然地欧式空间，而且复杂网络上两个节点之间的距离，并不是指这两个节点之间杂网络上两个节点之间的距离，并不是指这两个节点之间的欧式距离，而是指连接这两个节点的最短路径包含的边的欧式距离，而是指连接这两个节点的最短路径包含的边的数目。也就是说，不能直接用上面介绍的欧式空间中的的数目。也就是说，不能直接用上面介绍的欧式空间中的盒子来覆盖复杂网络。盒子来覆盖复杂网络。SongSong等人对于用于覆盖复杂网络的等人对于用于覆盖复杂网络的尺寸为尺寸为l lB B的盒子的规定为：盒子中任意两个节点之间的距离的盒子的

37、规定为：盒子中任意两个节点之间的距离都小于都小于l lB B。这样就可以把一个网络分割成一组布重叠的盒子，。这样就可以把一个网络分割成一组布重叠的盒子，也就是说网络中的每一个节点都属于某个盒子，并且一个也就是说网络中的每一个节点都属于某个盒子，并且一个节点只能属于一个盒子。但是存在的问题是，对大规模的节点只能属于一个盒子。但是存在的问题是，对大规模的网络存在不同德分割方式，如下图所示。网络存在不同德分割方式，如下图所示。在在l lB B=2=2的情形下，一个包含的情形下，一个包含8 8个节点的网络的两种分割方式个节点的网络的两种分割方式SongSong等人进一步通过重整化过程，揭示出自相似性和

38、无等人进一步通过重整化过程，揭示出自相似性和无标度的度分布在网络的所有粗粒化阶段都成立。在把所标度的度分布在网络的所有粗粒化阶段都成立。在把所有节点都分配到盒子中之后，再把每个盒子用单个节点有节点都分配到盒子中之后，再把每个盒子用单个节点来表示，这些节点称为重整化节点。如果在两个未重整来表示，这些节点称为重整化节点。如果在两个未重整化盒子之间至少存在一条边，那么两个重整化节点之间化盒子之间至少存在一条边，那么两个重整化节点之间就有一条边相连。这样就等到一个重整化网络。这种重就有一条边相连。这样就等到一个重整化网络。这种重整化过程可以一直进行下去，直到整个网络被规约为单整化过程可以一直进行下去，

39、直到整个网络被规约为单个节点。个节点。一个包含一个包含8 8个节点的网络在不同的个节点的网络在不同的l lB B情形下的重整化情形下的重整化重整化网络的度分布重整化网络的度分布P(kP(k)在重整化下具有不变性：在重整化下具有不变性：重整化网络中每个节点的度重整化网络中每个节点的度k k 与未重整化网络的每个盒子中与未重整化网络的每个盒子中的节点最大度的节点最大度k k之间满足标度律：之间满足标度律：经验观察表明，标度因子经验观察表明，标度因子s(1)s(1)与与l lB B之间满足具有幂指数之间满足具有幂指数d dk k的的幂律关系：幂律关系：SongSong等人还推出，在幂律度分布公式等人还推出，在幂律度分布公式 中的中的幂指数幂指数 与幂律标度变换公式与幂律标度变换公式 和式和式 中的两个幂指数中的两个幂指数 和和 之间存在如下的关系：之间存在如下的关系：值得指出的是，对一个网络存在多种粗粒化方法。值得指出的是，对一个网络存在多种粗粒化方法。在一种粗粒化过程下具有自相似性的一个网络在另一种粗在一种粗粒化过程下具有自相似性的一个网络在另一种粗粒化过程下却可能具有非自相似性。粒化过程下却可能具有非自相似性。