无标度网络-高级计算机网络PPT课件

目录,网络科学与网络基础知识规则网络随机网络小世界网络无标度网络涌现,1,.,无标度网络,生成一个无标度网络无标度网络的属性无标度网络中的导航分析小结,2,.,生成一个无标度网络,Barabasi-Albert(BA)网络,(1)实际网络中，认为无标度网络是动态的而不是静止的，因此会出现增长的现象。(2)偏好连接规则:用于连接节点对的链路的概率与新节点的度成比例。,3,.,生成一个无标度网络,BA无标度网络的生成过程：从三个节点和三条链路开始，通过每个时间步t添加一个节点来增长网络；使用偏好连接将新的节点链接到个其他节点上；重复上述过程，直到所有n个节点都添加到网络上为止。,4,.,生成一个无标度网络,无标度网络的度序列的分布是服从幂律分布的。且当幂指数q在2和3之间时，网络就被认为是无标度的。,5,.,无标度网络的幂律分布问题,6,.,幂律分布,7,.,幂律分布,8,.,幂律分布,9,.,幂律分布,10,.,幂律分布,11,.,幂律分布,无标度网络的度序列的分布是服从幂律分布的。且当幂指数q在2和3之间时，网络就被认为是无标度的。,12,.,无标度网络的属性,BA网络熵随着网络的大小变化而导致密度的变化时，熵仍旧保持不变。无标度网络的熵随着的对数函数的增加而增加，直接与密度成比例。,13,.,无标度网络的熵无标度网络的熵随着密度的增加而单调地增加，因为到此为止它的度序列仍旧是幂律分布的。当密度接近100%时，无标度网络就会失效并且它的度序列分布不再是幂律分布。随机网络的熵会随着密度增加而增加，到达峰值(在密度接近50%处)，然后随着密度接近100%而降低到零。,14,.,无标度网络的属性,Hub度与密度对应关系极高hub度是无标度网络的主要属性随着可用链路数量的增加，网络的最大hub的度也会增加。因此，hub度会随着密度的增加而增加。,15,.,无标度网络的属性,无论是随机网络还是无标度网络，hub度都会按密度的对数增长，但是无标度网络hub度增长的速率更快。,16,.,无标度网络的属性,BA网络平均路径长度随着密度的增长路径长度逐渐减少，但是无标度网络中的平均路径长度下降在稀疏的无标度网络中要比在稀疏随机网络中更加显著。这是因为在稀疏无标度网络中hub节点要比在随机网络中的度要高得多。,17,.,无标度网络的属性,在同等的密度下无标度网络与随机网络平均路径长度的不同。由于无标度网络显示出了小世界效应它们具有比同等随机网络稍小的平均路径长度。当密度接近零时，差距就会越显著，显示出的小世界效应在随机网络中要比无标度网络中更明显。,18,.,无标度网络的属性,显示一种稳定的但是杂乱的随着稀疏无标度网络中的hub度增加平均路径长度减少的特点。无标度网络的hub度越高，平均路径长度就越短。Hub的度越高，就越有机会使用远距离链路遍历网络。Hub是在无标度网络中建立小世界效应的基础。,19,.,无标度网络的属性,BA网络紧度一般来讲，密度会增加紧度直到达某一点然后由拓扑接管，再确定高密度网络是否增加或减少紧度。平均紧度平滑地增加到一个峰值，然后随着更少的节点脱离与主导hub的直接连接，会平滑地下降到50%密度之下。,20,.,无标度网络的属性,无标度网络的平均紧度远远低于同等的随机网络和小世界网络。一般来说，无标度网络中节点的平均紧度是其他类网络节点的一半。这是由于hub是唯一的中间节点，中间节点的有用性要超过所有其他的节点。,21,.,无标度网络的属性,无标度网络聚类系数,聚类是一种结构，结构是一种负熵。在小世界网络中，结构随着密度的增加而增加。小世界网络中较大百分比的结构进入聚类，而在无标度网络中更大百分比的结构进入hub度。随着密度的增加，小世界网络迁移进入高度聚类网络，而无标度网络迁移进入高度hub网络。这是底层k-规则网络的高聚类系数的一个直接结果。,22,.,无标度网络中的导航,最大度导航与密度对应关系与平均最短路径相比而言，增加无标度网络密度将会更快地减少导航时间。添加链路将会缩减传送时间。但是，平均路径要远远小于最大度路径长度的大小，因为最短路径算法使用网络拓扑的全局知识。,23,.,无标度网络中的导航,最大度导航与hub度的对应关系网络的最大度越高，信息通过无标度网络的速度就越快。这是因为hub倾向于直接连接到较大百分比的节点上。它们提供许多直接到每个邻居的远距离路径，需要较少的短距离“跳”到达最终目的地。,24,.,分析,按照拓扑范围，无标度网络介于小世界和随机网路之间。除了聚类系数之外，无标度网络类要比其他三类更加平衡。熵、平均路径长度和hub度相对高，但是聚类系数较低。,25,.,分析,熵随机网络的熵会随着密度增加而增加，到达峰值(在密度接近50%处)，然后随着密度接近100%而降低到零。小世界网络的熵随着密度的增加缓慢地增加，然后随着密度或重联概率的增加而平缓下来。无标度网络显示随着密度的增加而增加，随着密度接近100%，熵呈指数级下降，之所以发生这种现象是由于度序列分布的崩溃的结果（所有节点都最大限度的连接起来了，以至于所有节点之间距离是1或2）。,26,.,随机网络的熵会随着密度增加而增加，到达峰值(在密度接近50%处)，然后随着密度接近100%而降低到零。,27,.,小世界网络的熵随着密度的增加缓慢地增加，然后随着密度或重联概率的增加而平缓下来。,28,.,无标度网络显示随着密度的增加而增加，随着密度接近100%，熵呈指数级下降，之所以发生这种现象是由于度序列分布的崩溃的结果（所有节点都最大限度的连接起来了，以至于所有节点之间距离是1或2）。,29,.,分析,路径长度随机网络的平均路径长度随着网络的链路数目的增加而减少。小世界网络的平均路径长度随着熵的增加呈指数减少，但是却不会减少到同等的随机网络之下。无标度网络的平均路径长度随着网络密度的增加而降低。,30,.,随机网络的平均路径长度随着网络的链路数目的增加而减少。,31,.,小世界网络的平均路径长度随着密度的增加呈指数减少，但是却不会减少到同等的随机网络之下。,32,.,无标度网络的平均路径长度随着网络密度的增加而降低。,33,.,分析,聚类系数随机网络的聚类系数随着密度的增加而增加。小世界网络的聚类系数随着密度的增加而增加。无标度网络的聚类系数随着密度的增加而增加。,34,.,随机网络的聚类系数随着密度的增加而增加。,35,.,小世界网络的聚类系数随着密度的增加而增加。,36,.,无标度网络的聚类系数随着密度的增加而增加。,37,.,分析,熵在无标度网络中变的像hub似的拓扑，在小世界网络中变的聚类化，而在随机网络中变的无序。这就是为什么无标度网络被称为“带有hub的类”，以及小世界网络类被称为“带有聚类的类”的原因。Hub度随着密度的增加而增加。,38,.,小结,BA生成过程，通过偏好连接过程生成一个规范化的无标度网络。无标度网络的hub度与密度的对数成比例。规范的BA无标度网络的密度依赖于偏好连接的参数，这是一个将每一个新的节点连接到其他节点构造过程中使用的链路的数量。其决定了规范化的无标度网络中的链路数量。,39,.,小结,规范的无标度网络的度序列分布属于幂律分布。规范的无标度网络的熵随着密度的增加而增减但是在接近100%密度是骤减至零。稀疏BA无标度网络的平均路径长度低于稀疏的随机网络的平均路径长度。无标度网络的平均紧度有其密度和最大的hub来决定。无标度网络的聚类系数随着密度线性的