《第五章 小世界网络》由会员分享，可在线阅读，更多相关《第五章 小世界网络（38页珍藏版）》请在金锄头文库上搜索。
1、目录 第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路径
2、长度和相变 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
3、。生成一个 k-规则网络。有m=2n条链路。 对每一条链路，以概率p重连。5.1.2 一般的WS过程 从k-规则网络开始。小世界网络模型作为从完全规则网络向完全随机图的过渡，Watts和Strogtz于1998年引 入了一个小世界网络模型，称为WS小世界模型。其构造算法如下： 从规则图开始：考虑一个含有N个点的最近邻耦合网络，它们围成一个 环，其中每个节点都与它左右相邻的各K/2个节点相连，K是偶数。 随机化重连：以概率p随机地重连网络中的每个边，即将边的一个端点 保持不变，而另一个端点取为网络中随机选择的一个节点。其中规定 ，任意两个不同节点之-间至多只能有一条边，并且每一个节点都不 能有边
4、与自身相连。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 t
5、he 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.827
6、5.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小世界网络的路径长
7、度 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%路径长度与相变其它相变 接近转换
8、点的突变 材料中的相变 生物学中的突变 消费者行为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
