复杂网络第二讲

《复杂网络第二讲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、复杂网络第二讲网络拓扑基本模型及其性质李凯凯规则网络随机图小世界网络模型无标度网络模型局域世界演化网络模型模块性与等级网络复杂网络的自相似性规则网络系统中节点及其与边的关系是固定的。（a）全局耦合网络；（b）最近邻耦合网络；（c）星形网络全局耦合网络具有最小的平均路径长度Lgc=1和最大的聚类系数Cgc=1；最近邻耦合网络:包含N个围成一个环的点，其中每个节点都与它左右各K/2个邻居点相连（K为偶数），对于较大的K值，最近邻耦合网络的聚类系数为因此，这样的网络是高度聚类的。对于固定的K值，网络平均路径长度为星形耦合网络：有一个中心点，其余N-1个点都只与这个中心点连接，其平均路径长度为聚

2、类系数为随机图随机图是与规则网络相反的网络，一个典型模型是Erdos和Renyi于40多年前开始研究的随机图模型。假设有大量的纽扣（N》1）散落在地上，并以相同的概率p给每对纽扣系上一根线。这样就会得到一个有N个节点，约pN(N-1)/2条边的ER随机图的实例。ER随机图的性质随机图理论的一个主要研究课题是：当概率p为多大时，随机图会产生一些特殊的属性？Erdos和Renyi系统地研究了当时，ER随机图的性质与概率p之间的关系，他们采用了如下定义：如果当时产生一个具有性质Q的ER随机图的概率为1，那么就称几乎每一个ER随机图都具有性质Q。Erdos和Renyi的最重要的发现时ER随机图具

3、有如下的涌现或相变性质：ER随机图的许多重要的性质都是突然涌现的。也就是说，对于任意给定的概率p，要么几乎每一个图都具有性质Q，要么几乎每一个图都不具有该性质。上述纽扣网络，如果p大于某个临界值，那么几乎每一个随机图都是连通的。ER随机图的平均度是,平均路径长度。LER为网络规模的对数增长函数是典型的小世界特征。ER随机图的聚类系数是C=p=/N《1，这意味着大规模的稀疏ER随机图没有聚类特性。实际网络的聚类系数要比相同规模的ER随机图的聚类系数要高得多。ER随机图的度分布可用Poission分布来表示：因此，ER随机图也称为“Poission随机图”。小世界网络模型作为从完全规则

4、网络向完全随机图的过渡，Watts和Strogtz于1998年引入了一个小世界网络模型，称为WS小世界模型。其构造算法如下：①从规则图开始：考虑一个含有N个点的最近邻耦合网络，它们围成一个环，其中每个节点都与它左右相邻的各K/2个节点相连，K是偶数。②随机化重连：以概率p随机地重连网络中的每个边，即将边的一个端点保持不变，而另一个端点取为网络中随机选择的一个节点。其中规定，任意两个不同节点之-间至多只能有一条边，并且每一个节点都不能有边与自身相连。P=0对应于完全规则网络，p=1对应于完全随机网络。具有较短的平均路径长度又具有较高的聚类系数的网络就称为小世界网络。Newman和Watts

5、提出了NW小世界模型，用“随机化加边”取代WS小世界模型构造中的“随机化重连”。算法如下：①从规则图开始：含有N个节点的最近邻耦合网络。②随机化加边：以概率P在随机选取的一对节点之间加上一条边。NW小世界模型中，p=0对应于原来的最近邻耦合网络，p=1对应于全局耦合网络。小世界网络的性质1.聚类系数WS小世界网络的聚类系数为NW小世界网络的聚类系数为2.平均路径长度其中f（u）为一普适标度函数，满足Newman等人基于平均场方法给出了如下近似表达式：3.度分布在基于“随机化加边”机制的NW小世界模型中，每个节点的度至少为K，因此当时，一个随机选取的节点的度为k的概率为：而当k

6、k）=0。无标度网络模型研究发现许多复杂网络的连接度分布函数具有幂律形式，由于这类网络的节点的连接度没有明显的特征长度，故称为无标度网络。Barabasi和Albert提出了一个无标度网络模型，称为BA模型。该模型考虑到了实际网络的两个重要特性：①增长特性；②优先连接特性。基于这两个特性，BA无标度网络模型构造算法如下：①增长：从一个具有m0个节点的网络开始，每次引入一个新的节点，并且连到m个已存在的节点上，这里。②优先连接：一个新节点与一个已经存在的节点i相连接的概率与节点i的度ki，节点j的度kj之间满足如下关系：无标度网络的性质1.平均路径长度，表明该网络具有小世界特性。2.聚类系

7、数3.度分布BA无标度网络的度分布函数为这表明BA无标度网络的度分布函数可由幂指数为3的幂律函数近似描述。幂律分布函数的无标度性质：考虑一个概率分布函数f(x)，如果对任意给定常数a，存在常数b使得函数f(x)满足如下“无标度条件”:f(ax)=bf(x)那么必有(假定)也就是说，幂律分布函数是唯一满足“无标度条件”的概率分布函数。鲁棒性与脆弱性假定一个网络，每次从该网络中移走一个节点，同时移走与该节点相连的所有边，从而可能使得网络