第三章 规则网络.pptVIP

目录 第1章 网络科学的起源 第2章 图 第3章 规则网络 第4章 随机网络 第5章 小世界网络 第6章 无标度网络 第7章 涌现 第8章 传染病 第9章 同步 第10章 影响网络 第11章 脆弱性 第12章 NetGain网络 第13章 生物学 第14章 必威体育精装版动态 第3章 规则网络 31直径、中心性和平均路径长度32二叉树网络321二叉树网络的熵322二叉树网络的路径长度323二叉树网络的链路效率33超环形网络331超环形网络的平均路径长度332超环形网络的链路效率34超立方网络341超立方网络的平均路径长度342超立方网络的链路效率 平均路径长度L 其中dij表示节点i,j之间的距离。N表示网络的规模，即节点的个数。 直径、半径和中心 What is the most efficient regular network? An efficient network （有效网路，最优网络） （1） is sparse, （稀疏，即链路数少） （2）has a small diameter, and （较小的直径） （3）has a short characteristic path length.（较小的平均路径长度） 最优网络：高性能(1),低成本(2)(3)，两个指标在网络优化设计中是一对矛盾，需要折中和权衡。 链路效率E 最简单的一种度量方法是链路效率： 本章主要介绍三个常见的规则网络：二叉树网络、超环形网络、超立方网络。描述它们的构造，计算它们的链路数、直径和平均路径长度等重要网络参数。 网络的节点数n，链路数m、直径D和平均路径长度L。 3.2 二叉树网络 平衡二叉树设有k层，则 随着层数k的增大，平均路径长度l近似等于直径D-4 3.3超环形网络 超环形网络 超环形网络T设有k*k网格，则 超环形网络的平均路径长度 3.4超立方网络Qk 超立方网络Qk 超立方网络Qk 平均路径长度的计算，以及超立方网络的其它性质详见《组合网络理论》之第六章，或者网络优化设计章节。 总结 二叉树网络、超环形网络、超立方网络的比较，见教材第63页。 从链路效率来看，超立方网络更加有效。 从链路数来看，n16时，超立方网络的链路数更大，故适宜“小”系统。 从平均路径长度来看，超立方网络的更小。 超立方网络易扩展。 熵 教材P.36-37 熵度量图的随机性。 图2-4（a）度分布 g’=（h1,h2,…,hh）=（0,0,3/4,0,1/4） 其中hi为度数i的节点的数目与总节点数的比值。 图的熵 图的熵 规则图的熵为0. 线性图的熵为0.1414. 随机图的熵为2.9. 熵、聚类系数、密度 平衡二叉树网络的熵：1+log_2(n)/n. (P.55) 超环形网络、超立方网络的熵0. 平衡二叉树网络、超环形网络、超立方网络的聚类系数0. 密度（P.35）