资源预览内容
第1页 / 共38页
第2页 / 共38页
第3页 / 共38页
第4页 / 共38页
第5页 / 共38页
第6页 / 共38页
第7页 / 共38页
第8页 / 共38页
第9页 / 共38页
第10页 / 共38页
亲,该文档总共38页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
目录 第1章 网络科学的起源 第2章 图 第3章 规则网络 第4章 随机网络 第5章 小世界网络 第6章 无标度网络 第7章 涌现 第8章 传染病 第9章 同步 第10章 影响网络 第11章 脆弱性 第12章 NetGain网络 第13章 生物学 第14章 最新动态第5章小世界网络5 1生成一个小世界网络 5 1 1Watts Strogatz (WS)过程 5 1 2一般的WS过程 5 1 3小世界网络的度序列 5 2小世界网络属性 5 2 1熵与重联概率 5 2 2熵与密度 5 2 3小世界网络的路径长度 5 2 4小世界网络的聚类系数 5 2 5小世界中的紧度 5 3相变 5 3 1路径长度和相变 5 3 2材料中的相变 5 4小世界网络中的导航 5 5小世界网络中的弱联系 5 6分析 练习 小世界网络是具有高聚类系数、相对较小 的平均路径长度、可变化的熵的稀疏网络 Milgram六度分离。 WS(Watts,Strogatz,1998)提出小世界网络 模型。 小世界网络介于规则网络和随机网络之间 。许多实际网络都是小世界网络。其研究 有广泛应用价值。5.1 生成一个小世界网络5.1.1 Watts Strogatz (WS)过程 5.1.2 一般的WS过程 5.1.3 小世界网络的度序列5.1.1 Watts Strogatz (WS)过程 给定节点数n,重连概率p,k=2。生成一个 k-规则网络。有m=2n条链路。 对每一条链路,以概率p重连。5.1.2 一般的WS过程 从k-规则网络开始。小世界网络模型作为从完全规则网络向完全随机图的过渡,Watts和Strogtz于1998年引 入了一个小世界网络模型,称为WS小世界模型。其构造算法如下: 从规则图开始:考虑一个含有N个点的最近邻耦合网络,它们围成一个 环,其中每个节点都与它左右相邻的各K/2个节点相连,K是偶数。 随机化重连:以概率p随机地重连网络中的每个边,即将边的一个端点 保持不变,而另一个端点取为网络中随机选择的一个节点。其中规定 ,任意两个不同节点之-间至多只能有一条边,并且每一个节点都不 能有边与自身相连。P=0对应于完全规则网络,p=1对应于完全随机网络。 D. J. Watts, and S. H. Strogatz, Nature, 393, 440-442 (1998). 美国康奈尔(Cornell)大学理论论和应应用力 学系的博士生Watts及其导师导师 、非线线性动动力 学专专家Strogatz教授于1998年6月在Nature 杂杂志上发发表的题为题为 “小世界”网络络的集体 动动力学(Collective Dynamics of Small- World Networks)的文章5.1.3 小世界网络的度序列 Barrat, A. and M. Weigt, On the properties of small-world network models, Eur. Phys. J. B 13:547 (2000). 运行网络平台之smallnetwork.m(参考“基 于Matlab的小世界网络仿真.pdf ”),取教 材图5-2之参数。可得网络的邻接矩阵。 然后用Ucinet绘图。 用Degree_Distribution.m给出度分布图。 Density No. of Ties 5-2 0.3265 768.0000 Overall graph clustering coefficient: 0.631 Average distance = 1.8275.2 小世界网络属性规则网络结构上的较小变化将对网络的属性产生 巨大的影响,见表5-2(P.94)。如下列两个网络 的平均路径长度、聚类系数、熵等。(作业) 小世界网络的最终形状极大地受最初网络 的影响。表5-2(P.94)给出了最初网络分 别是2-规则和超环形网络的结论。试实验验 证。如果从二叉树或者其它规则网络开始 根据WS方法生成,结论如何? 5.2.1熵与重联概率 5.2.2熵与密度 5.2.3小世界网络的路径长度 5.2.4小世界网络的聚类系数 5.2.5小世界中的紧度5.2.1熵与重联概率 I=Alog2(100p). A=0.4375.2.2熵与密度5.2.3小世界网络的路径长度 Newman, M. E. J., C. Moore, and D. J. Watts, Mean-field solution of the small-world network model, Phys. Rev. Lett. 84(14):3201 3204 (2000).5.2.4小世界网络的聚类系数5.2.5小世界中的紧度小世界中的紧度更象规则网络 而非小世界网络5.3 相变 小世界网络介于规则网络和随机网络之间 随着重连概率的增加,从规则到半规则、 半随机和完全随机。 从规则到随机的转换点(突变点)(相变 阈值)如何界定? P=1% P=0.2%路径长度与相变其它相变 接近转换点的突变 材料中的相变 生物学中的突变 消费者行为5.4小世界网络中的导航 如何选择到达给定节点的导航路径? Navigation in a Small World. Nature 406(2000), 845. J. Kleinberg 四种搜索算法:随机、最大度、最小半径 、最大紧度。以最小跳数导航。 结论(p110-111)5.5小世界网络中的弱联系同等规模(n),小世界网络要比随机网络更 加隔离(平均距离大)。同等密度,小世界网络与随机网络的中间影 响力也有很大不同(平均紧度)5.5小世界网络中的弱联系同等规模(n),小世界网络要比随机网络更 加隔离(平均距离大)。同等密度(density),小世界网络与随机网 络的中间影响力也有很大不同(平均紧度 小)5.6分析基于Matlab 的小世界网络仿真Density No. of Ties sn 0.2105 80.0000 Overall graph clustering coefficient: 0.250 Average distance = 2.200
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号