第六章 无标度网络.ppt

目录 •第1章 网络科学的起源 •第2章 图 •第3章 规则网络 •第4章 随机网络 •第5章 小世界网络 •第6章 无标度网络 •第7章 涌现 •第8章 传染病 •第9章 同步 •第10章 影响网络 •第11章 脆弱性 •第12章 NetGain网络 •第13章 生物学 •第14章 最新动态第6章 无标度网络6.1 生成一个无标度网络 6.1.1 barabasi￿￿ albert（ba）网络 6.1.2 生成ba网络 6.1.3 无标度网络幂律分布 6.2 无标度网络的属性 6.2.1 ba网络熵 6.2.2 hub度与密度对应关系 6.2.3 ba网络平均路径长度 6.2.4 ba网络紧度 6.2.5 无标度网络聚类系数 6.3 无标度网络中的导航 6.3.1 最大度导航与密度对应关系 6.3.2 最大度导航与hub度的对应关系 6.3.3 在无标度pointville网络中的弱联系 6.4 分析 6.4.1 熵 6.4.2 路径长度和通信 6.4.3 聚类系数 6.4.4 hub度 练习• 无标度网络是度分布服从幂律分布的网络 • 无标度网络具有少量高度节点、大量低度 节点 • Scale-free网络的特性：• 度分布呈幂率分布 • 中枢节点出现 • 稳健性 • 脆弱性6.1 生成一个无标度网络6.1.1 barabasi￿￿ albert（ba）网络 6.1.2 生成ba网络 6.1.3 无标度网络幂律分布6.1.1 barabasi￿￿ albert（ba）网络• 无标度模型由Albert-László Barabási和Réka Albert在1999年首先提出，现实网络的无标 度特性源于众多网络所共有的两种生成机 制： • （ⅰ）网络通过增添新节点而连续扩张； • （ⅱ）新节点择优连接（偏好连接）到具 有大量连接的节点上。

• 增长和择优连接这两种要素激励了Barabási－Albert模型的 提出，该模型首次导出度分布按幂函数规律变化的网络 • 模型的算法如下：（1）增长：开始于较少的节点数量（m0），在每个时间间隔 增添一个具有m（≤m0）条边的新节点，连接这个新节点 到m个不同的已经存在于系统中的节点上2）择优连接：在选择新节点的连接点时，假设新节点连 接到节点i的概率p取决于节点i的度数即• 经过t时间间隔后，该算法程序产生一具有 N=t+m0个节点，mt条边的网络 • 数量模拟表明具有k条边的节点的概率服从 指数为r=3的幂指数分布P(k) ~k-3A.-L.Barabási, R. Albert, Science 286, 509 (1999)6.1.2 生成ba网络6.1.3 无标度网络幂律分布• A.-L. Barabási, R. Albert. Emergence of scaling in random networks. Science 286, 509–512 (1999) • 可参考《复杂网络度分布的研究》文 • BA模型构造的网络度符合幂指形式的证明• Newman, M. E. J., The structure and function of complex networks, SIAM Rev. Soci. Industr. Appl. Math. 45(2):167–256 (2003).• 6.1.3 Scale-Free Network Power Law(p.186- 189)(中文p.122-123)• 运行网络平台之scalefree.m（参考“基于 Matlab的无标度网络仿真.pdf ”），取教材 图6-2之参数。

可得网络的邻接矩阵 • 然后用Ucinet绘图 • 用Degree_Distribution.m给出度分布图• Density No. of Ties • 6-2 0.0579 562.0000 • clustering coefficient: 0.168 • Average distance = 2.577• 可对此网络的度分布拟合给出幂律分布表 达式• 关于无标度网络的进一步认识，可参考： • 《无标度网络的争议》 • 《复杂网络的随机刻画和演化规律》 • 等网络教学平台文献6.2 无标度网络的属性• 6.2.1 ba网络熵 6.2.2 hub度与密度对应关系 6.2.3 ba网络平均路径长度 6.2.4 ba网络紧度 6.2.5 无标度网络聚类系数6.2.1 ba网络熵6.2.2 hub度与密度对应关系6.2.3 ba网络平均路径长度6.2.4 ba网络紧度6.2.5 无标度网络聚类系数• scale-free networks have large hubs and small clustering. Small-world networks have large clusters and small hubs. • Scale-free network structure is vested in high- degree hubs, while small world structure is vested in high-degree clustering.6.3 无标度网络中的导航6.3.1 最大度导航与密度对应关系 6.3.2 最大度导航与hub度的对应关系 6.3.3 在无标度pointville网络中的弱联系最大度导航与密度、hub度的对应关系无标度pointville网络中的弱联系• 随机：D=3.18, R=2.77, Close=0.427(P.84); • SW： L=2.17, Close=0.30(P.112); • SF： L=1.75, Close=0.07(P.135);6.4 分析6.4.1 熵 6.4.2 路径长度和通信 6.4.3 聚类系数 6.4.4 hub度。