复杂网络第二讲课件

复杂网络第二讲网络拓扑基本模型及其性质李凯凯复杂网络第二讲1规则网络随机图小世界网络模型无标度网络模型局域世界演化网络模型模块性与等级网络复杂网络的自相似性规则网络2规则网络系统中节点及其与边的关系是固定的。(a)全局耦合网络;(b)最近邻耦合网络;(c)星形网络全員耦合网具有最小的平均路径长度L。=1和最大的聚类系数C=1规则网络3最近邻命参包含N个围成一个环的点,其中每个节点都与它左右各K/2个邻居点相连(K为偶数),对于较大的K值,最近邻耦合网络的聚类系数为3(K-2)34(K-1)4因此,这样的网络是高度聚类的。对于固定的K值,网络平均路径长度为(N→∞)2K星形耦合网參:有一个中心点,其余N-1个点都只与这个中心点连接,其平均路径长度为2(N-1)N-1→>2(N→)聚类系数为N-1最近邻命参包含N个围成一个环的点,其中每个节点都4随机图随机图是与规则网络相反的网络,一个典型模型是Erdos和Renⅵi于40多年前开始研究的随机图模型假设有大量的纽扣(N》1)散落在地上,并以相同的概率p给每对纽扣系上一根线。这样就会得到一个有N个节点,约pN(N-1)/2条边的ER随机图的实例ep=15随机图5ER随机图的性质随机图理论的一个主要研究课题是当概率p为多大时,随机图会产生一些特殊的属性?巸rdos和Renyi系统地研究了当N→∞时,BR随机图的性质与概率p之间的关系,他们采用了如下定义:如果当M_时产生一个具有性质Q的即随机图的概率为1,那么就称几乎每一个ER随机图都具有性质QErdos和Renyi的最重要的发现时B随机图具有如下的涌现或变性质ER随机图的许多重要的性质都是突然涌现的。也就是说,对于任意给定的概率p,要么几乎每一个图都具有性质Q,要么几乎每一个图都不具有该性质上述纽扣网络,如果p大于某个临界值Pc∞(mM/N,那么几乎每一个随机图都是连通的ER随机图的性质6ER随机图的平均度是<k>=p(N-1)≈pN,平均路径长度LE1nN/lnxk>。L为网络规模的对数增长函数是典型的小世界特征。ER随机图的聚类系数是C=p=<k>/N《1,这意味着大规模的稀疏ER随机图没有聚类特性。实际网络的聚类系数要比相同规模的BR随机图的聚类系数要高得多ER随机图的度分布可用Poission分布来表示P(k)kp(-p)*sskses因此,ER随机图也称为“Poission随机图”ER随机图的平均度是<k>=p(N-1)≈pN,平均路径长度7小世界网络模型作为从完全规则网络向完全随机图的过渡,Watts和Strogtz于1998年引入了一个小世界网络模型,称为W小世界模型。其构造算法如下①从规则图开始:考虑一个含有N个点的最近邻耦合网络,它们围成个环,其中每个节点都与它左右相邻的各2个节点相连,是偶数②随机化重连:以概率p随机地重连网络中的每个边,即将边的一个端点保持不变,而另一个端点取为网络中随机选择的一个节点。其中规定,任意两个不同节点之一间至多只能有一条边,并且每一个节点都不能有边与自身相连小}界网缗阿网络Pao增人阳机连概嶂p小世界网络模型8气p}F口s小世网络的聚类系数平均长度连概率P要化具有较短的平均路径长度又具有较高的聚类系数的网络就称为小世界网络Newman和Watts提出了NW小世界模型,用“随机化加边”取代WS小世界模型构造中的“随机化重连”。算法如下①从规则图开始:含有N个节点的最近邻耦合网络。②随机化加边:以概率P在随机选取的一对节点之间加上条边Nw小世界模型中,p=0对应于原来的最近邻耦合网络p=1对应于全局耦合网络气p}F口9小世界网络的性质聚类系数NS小世界网络的聚类系数为3(K-2)C(p)(14(K-1)NW小世界网络的聚类系数为3(KC(p)4(K-1)+4Kp(P+2)·2.平均路径长度2NL(P)Kf(NKp/2)小世界网络的性质10复杂网络第二讲课件11复杂网络第二讲课件12复杂网络第二讲课件13复杂网络第二讲课件14复杂网络第二讲课件15复杂网络第二讲课件16复杂网络第二讲课件17复杂网络第二讲课件18复杂网络第二讲课件19复杂网络第二讲课件20复杂网络第二讲课件21复杂网络第二讲课件22复杂网络第二讲课件23复杂网络第二讲课件24复杂网络第二讲课件25复杂网络第二讲课件26复杂网络第二讲课件27复杂网络第二讲课件28复杂网络第二讲课件29复杂网络第二讲课件30复杂网络第二讲课件31复杂网络第二讲课件32复杂网络第二讲课件33复杂网络第二讲课件34复杂网络第二讲课件