第二章第二章 网络拓扑基本模型及其性质网络拓扑基本模型及其性质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.1 引言引言要理解网络结构与网络行为之间的关系，并进而要理解网络结构与网络行为之间的关系，并进而 考虑改善网络的行为，就需要对实际的网络的结构特考虑改善网络的行为，就需要对实际的网络的结构特 征有很好的了解，并在此基础上建立合适的网络结构征有很好的了解，并在此基础上建立合适的网络结构 模型本章介绍几类基本的模型，包括规则网络、随模型本章介绍几类基本的模型，包括规则网络、随 机图、小世界网络、无标度网络、等级网络和局域世机图、小世界网络、无标度网络、等级网络和局域世 界演化网络模型此外，进一步介绍复杂网络的模块界演化网络模型此外，进一步介绍复杂网络的模块 化和自相似性等特征化和自相似性等特征。
2.2 规则网络在一个全局耦合网络中，任意两个点之间都有边直接相连 因此，全局耦合网络具有最小的 平均路径长度Lgc=1和最大的聚 类系数Cgc=1.最近邻耦合网络最近邻耦合网络中每一个节点中每一个节点 只和周围的邻居节点相连具有只和周围的邻居节点相连具有 周期边界条件的最近邻耦合网络周期边界条件的最近邻耦合网络 包含包含NN个围成一个环的点，其中个围成一个环的点，其中 每个点都与它左右各每个点都与它左右各K/2K/2个邻居个邻居 节点相连，这里节点相连，这里K K是一个偶数对是一个偶数对 于较大于较大K K值，最近邻耦合网络的值，最近邻耦合网络的聚聚 类系数类系数为：为：Cnc=因此这样的网络是高度聚类的然而，最近邻耦合因此这样的网络是高度聚类的然而，最近邻耦合 网络不是一个小世界网络，相反对固定的网络不是一个小世界网络，相反对固定的K K值，该网络值，该网络 的的平均路径长度平均路径长度为：为：Lnc星形耦合网络星形耦合网络，它有一个中心点，其余的，它有一个中心点，其余的N-N- 1 1个点都只与这个中心点连接，而他们彼此之间个点都只与这个中心点连接，而他们彼此之间 不连接星形网络的不连接。
星形网络的平均路径长度平均路径长度为：为：Lstar=星形网络的星形网络的聚类系数聚类系数为为：：Cstar=2.3 随机图假设有大量的纽扣（N>>1）散落在地上，并以 相同的概率P给每对纽扣系上一根线这样就会得到 一个有N个节点，约pN(N-1)/2条边的ER随机图的实 例a a））p=0,p=0,给定的给定的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为多 大时，随机图会产生一些特殊的属性？Erdos和Renyi系统性地研究了当N 时，ER随机 图的性质与概率p之间的关系他们采用如下定义：如果当N 时产生一个具有性质Q的ER随机图 的概率为1，那么就称几乎每一个ER随机图都具有性质 Q。
Erdos和Renyi最重要的发现是ER随机图有如下的 涌现或变相性质：ER随机图的许多重要的性质都是突然涌现的，也 就是说，对于任一给定的概率p，要么几乎每一个图都 具有某个性质Q，要么几乎每一个图都不具有该性质ERER随机图随机图平均路径长度平均路径长度为为: :L LERER∝∝lnN/lnlnN/ln这种平均这种平均路径长度为网络规模的对数增长函数的特性就是典型的小路径长度为网络规模的对数增长函数的特性就是典型的小 世界特征世界特征ERER随机图的随机图的聚类系数聚类系数是是:C=p=/N/N不变，则对于充分大的不变，则对于充分大的N N ，由于每条边出现与否都是独立的，，由于每条边出现与否都是独立的，ERER随机图的随机图的度分布度分布可可 以用以用PoissionPoission分布来表示分布来表示: :P(kP(k)= p)= pk k(1-p)(1-p)N-kN-k2.4 小世界网络模型作为从完全规则网络向完全随机图的过渡，Watts和 Strogtz引入了小世界网络模型，称为WS小世界模型其 构造算法如下：①① 从规则图开始：考虑一个含有从规则图开始：考虑一个含有N N个点的最近邻耦合个点的最近邻耦合 网络，它们围成一个环，其中每个节点都与它左右相邻网络，它们围成一个环，其中每个节点都与它左右相邻 的各的各K/2K/2节点相连，节点相连，K K是偶数。
是偶数②②随机化重连：以概率随机化重连：以概率p p随机地重新连接网络中的每随机地重新连接网络中的每 个边，即将边的一个端点保持不变，而另一个端点取为个边，即将边的一个端点保持不变，而另一个端点取为 网络中随机选择的一个节点，其中规定，任意两个不同网络中随机选择的一个节点，其中规定，任意两个不同 的节点之间至多只能有一条边，并且每一个节点都不能的节点之间至多只能有一条边，并且每一个节点都不能 有边与自身相连有边与自身相连在上述模型中，在上述模型中，p=0p=0对应于完全规则网络，对应于完全规则网络，p=1p=1则对则对 应于完全随机网络，通过调节应于完全随机网络，通过调节p p的值就可以控制从完全规的值就可以控制从完全规 则网络到完全随机网络的过渡，如下图所示则网络到完全随机网络的过渡，如下图所示这类既具有较短的平均路径长度又具有较高的聚类这类既具有较短的平均路径长度又具有较高的聚类 系数的网络就称为系数的网络就称为小世界网络小世界网络WSWS小世界模型构造算法中的随机化过程可能破坏网小世界模型构造算法中的随机化过程可能破坏网 络的连通性另一个研究较多的小世界模型是由络的连通性另一个研究较多的小世界模型是由 NewmanNewman和和WattsWatts提出的提出的NWNW小世界模型小世界模型。
该模型是通过该模型是通过” ” 随机化加边随机化加边” ”取代取代WSWS小世界模型中的随机化重连而得到小世界模型中的随机化重连而得到 的具体的的具体的构造算法构造算法如下：如下：①① 从规则图开始：考虑一个含有从规则图开始：考虑一个含有N N个点的最近邻耦个点的最近邻耦 合网络，它们围成一个环，其中每个节点都与它左右相合网络，它们围成一个环，其中每个节点都与它左右相 邻的各邻的各K/2K/2节点相连，节点相连，K K是偶数②②随机化重连：以概率随机化重连：以概率p p在随机选取的一对节点之间在随机选取的一对节点之间 加上一条边其中，任意两个不同的节点之间至多只能加上一条边其中，任意两个不同的节点之间至多只能 有一条边，并且每一个节点都不能有边与自身相连有一条边，并且每一个节点都不能有边与自身相连在在NWNW小世界模型中，小世界模型中，p=0p=0对应于原来的最近邻耦合网对应于原来的最近邻耦合网 络，络，p=1p=1对应于全局耦合网络对应于全局耦合网络下面介绍小世界网络模型的一些统计性质下面介绍小世界网络模型的一些统计性质1.1.聚类系数聚类系数WSWS小世界网络的小世界网络的聚类系数聚类系数为：为：NWNW小世界网络的小世界网络的聚类系数聚类系数为：为：2.2.平均路径长度平均路径长度迄今为止，人们还没有关于迄今为止，人们还没有关于WSWS小世界模型的平均路径长小世界模型的平均路径长 度度L L的精确解析表达式，不过，利用重正化群的方法可以得的精确解析表达式，不过，利用重正化群的方法可以得 到如下公式：到如下公式：其中其中f(uf(u) )为一普适标度函数，满足为一普适标度函数，满足NewmanNewman等人基于平均场方法给出了如下的近似表达式：等人基于平均场方法给出了如下的近似表达式：但目前为止还没有但目前为止还没有f(uf(u) )的精确显示表达式。
的精确显示表达式3.3.度分布度分布在基于在基于“ “随机化加边随机化加边” ”机制的机制的NWNW小世界模型中，每个节小世界模型中，每个节 点的度至少为点的度至少为K K因此当k>>Kk>>K时，一个随机选取的节点的度时，一个随机选取的节点的度 为为k k的概率为：的概率为：而当而当k=K/2k>=K/2时有：时有：而当而当k=mM>=m），作为新加入节点的局域世界新加），作为新加入节点的局域世界新加 入的节点根据优先连接概率入的节点根据优先连接概率来选择与局域世界中的来选择与局域世界中的mm个节点相连接，其中个节点相连接，其中LWLW由新选的由新选的MM 个节点组成个节点组成显而易见，在显而易见，在t t时刻，时刻，m1.1Nrand>1.1Nrandi i 网络模体检测示意图网络模体检测示意图2.7.2 2.7.2 等级网络等级网络为了说明许多实为了说明许多实 际系统中同时存在的际系统中同时存在的 模块性、局部聚类和模块性、局部聚类和 无标度拓扑特性，需无标度拓扑特性，需 要假设模块以某种迭要假设模块以某种迭 代方式生成一个等级代方式生成一个等级 网络研究表明，一网络研究表明，一 些网络中的拓扑模块些网络中的拓扑模块 确实是按等级组织起确实是按等级组织起 来的。
来的等级模块性的一个最重要的量化标志是节点聚类系数服等级模块性的一个最重要的量化标志是节点聚类系数服 从幂律从幂律C(kC(k) ) ∝∝k k-1-1这表明度很小的节点具有高的聚类系这表明度很小的节点具有高的聚类系 数且属于高度连接的小模块相反，度很高的数且属于高度连接的小模块相反，度很高的hubhub节点具节点具 有低的聚类系数，其作用只是把不同的模块连接起来有低的聚类系数，其作用只是把不同的模块连接起来 需要注意的是，需要注意的是，ERER随机图和随机图和BABA无标度网络都不具有等级无标度网络都不具有等级 拓扑；在这两类网络中节点聚类系数拓扑；在这两类网络中节点聚类系数C(kC(k) )与该节点的度与该节点的度k k 无关2.7.3 2.7.3 超家族超家族小世界和无标度是许多实际网络的共同全局结构特征，小世界和无标度是许多实际网络的共同全局结构特征， 那么不同德网络是否也有可能具有相似的局部结构特征？网那么不同德网络是否也有可能具有相似的局部结构特征？网 络模体的研究有助于人们从局部结构上来理解复杂网络的设络模体的研究有助于人们从局部结构上来理解复杂网络的设 计原理在此基础上，计原理。
在此基础上，MiloMilo等人提出了基于重要性剖面等人提出了基于重要性剖面(SP)(SP) 比较网络局部结构的方法计算比较网络局部结构的方法计算SPSP的基本思想仍然是把一个的基本思想仍然是把一个 实际网络与其对应的随机化网络作对比，这样就可避免不同实际网络与其对应的随机化网络作对比，这样就可避免不同 网络的规模和度序列的影响网络的规模和度序列的影响网络中每个子图网络中每个子图i i的统计重要性用的统计重要性用来描述，其中来描述，其中NrealNreali i和和NrandNrandi i仍然分别表示该子图在实际网络仍然分别表示该子图在实际网络 和对应的随机化网络中出现的次数，和对应的随机化网络中出现的次数， >和和std(Nrandstd(Nrandi i) )分别是分别是NrandNrandi i的均值和标准方差对的均值和标准。