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

《网络拓扑基本模型及其性质.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章网络拓扑基本模型及其性质2.1引言2.2规则网络2.3随机图2.4小世界网络模型2.5无标度网络模型2.6局域世界演化网络模型2.7模块性与等级网络2.8复杂网络的自相似性2.1引言要理解网络结构与网络行为之间的关系，并进而考虑改善网络的行为，就需要对实际的网络的结构特征有很好的了解，并在此基础上建立合适的网络结构模型。本章介绍几类基本的模型，包括规则网络、随机图、小世界网络、无标度网络、等级网络和局域世界演化网络模型。此外，进一步介绍复杂网络的模块化和自相似性等特征。2.2规则网络在一个全局耦合网络中，任意两个点之间都有边直接相连。因此

2、，全局耦合网络具有最小的平均路径长度Lgc=1和最大的聚类系数Cgc=1.最近邻耦合网络中每一个节点只和周围的邻居节点相连。具有周期边界条件的最近邻耦合网络包含N个围成一个环的点，其中每个点都与它左右各K/2个邻居节点相连，这里K是一个偶数。对于较大K值，最近邻耦合网络的聚类系数为：Cnc=因此这样的网络是高度聚类的。然而，最近邻耦合网络不是一个小世界网络，相反对固定的K值，该网络的平均路径长度为：Lnc星形耦合网络，它有一个中心点，其余的N-1个点都只与这个中心点连接，而他们彼此之间不连接。星形网络的平均路径长度为：Lstar=星形网络的聚类

3、系数为：Cstar=2.3随机图假设有大量的纽扣（N>>1）散落在地上，并以相同的概率P给每对纽扣系上一根线。这样就会得到一个有N个节点，约pN(N-1)/2条边的ER随机图的实例。（a）p=0,给定的10个孤立点；（b）~（d）分别以连接概率p=0.1、p=0.15和p=0.25生成的随机图（a）（b）（c）（d）随机图理论的一个主要研究课题是：当概率p为多大时，随机图会产生一些特殊的属性？Erdos和Renyi系统性地研究了当N时，ER随机图的性质与概率p之间的关系。他们采用如下定义：如果当N时产生一个具有性质Q的ER随机图的概率为1，那么

4、就称几乎每一个ER随机图都具有性质Q。Erdos和Renyi最重要的发现是ER随机图有如下的涌现或变相性质：ER随机图的许多重要的性质都是突然涌现的，也就是说，对于任一给定的概率p，要么几乎每一个图都具有某个性质Q，要么几乎每一个图都不具有该性质。ER随机图平均路径长度为:LER∝lnN/ln。这种平均路径长度为网络规模的对数增长函数的特性就是典型的小世界特征。ER随机图的聚类系数是:C=p=/N<<1，这意味着大规模的稀疏ER随机图没有聚类特性。固定ER随机图的平均度不变，则对于充分大的N，由于每条边出现与否都是独立的，ER

5、随机图的度分布可以用Poission分布来表示:P(k)=pk(1-p)N-k2.4小世界网络模型作为从完全规则网络向完全随机图的过渡，Watts和Strogtz引入了小世界网络模型，称为WS小世界模型。其构造算法如下：①从规则图开始：考虑一个含有N个点的最近邻耦合网络，它们围成一个环，其中每个节点都与它左右相邻的各K/2节点相连，K是偶数。②随机化重连：以概率p随机地重新连接网络中的每个边，即将边的一个端点保持不变，而另一个端点取为网络中随机选择的一个节点，其中规定，任意两个不同的节点之间至多只能有一条边，并且每一个节点都不能有边与自身相连。

6、在上述模型中，p=0对应于完全规则网络，p=1则对应于完全随机网络，通过调节p的值就可以控制从完全规则网络到完全随机网络的过渡，如下图所示。这类既具有较短的平均路径长度又具有较高的聚类系数的网络就称为小世界网络WS小世界模型构造算法中的随机化过程可能破坏网络的连通性。另一个研究较多的小世界模型是由Newman和Watts提出的NW小世界模型。该模型是通过”随机化加边”取代WS小世界模型中的随机化重连而得到的。具体的构造算法如下：①从规则图开始：考虑一个含有N个点的最近邻耦合网络，它们围成一个环，其中每个节点都与它左右相邻的各K/2节点相连，K是

7、偶数。②随机化重连：以概率p在随机选取的一对节点之间加上一条边。其中，任意两个不同的节点之间至多只能有一条边，并且每一个节点都不能有边与自身相连。在NW小世界模型中，p=0对应于原来的最近邻耦合网络，p=1对应于全局耦合网络。下面介绍小世界网络模型的一些统计性质。1.聚类系数WS小世界网络的聚类系数为：NW小世界网络的聚类系数为：2.平均路径长度迄今为止，人们还没有关于WS小世界模型的平均路径长度L的精确解析表达式，不过，利用重正化群的方法可以得到如下公式：其中f(u)为一普适标度函数，满足Newman等人基于平均场方法给出了如下的近似表达式：

8、但目前为止还没有f(u)的精确显示表达式。3.度分布在基于“随机化加边”机制的NW小世界模型中，每个节点的度至少为K。因此当k>>K时，一个随机选取的