小世界网络

第五章小世界网络王梦琦21513751目录5.1生成一个小世界网络5.2小世界网络的属性5.3相变5.4小世界网络中的导航5.5分析25.1生成一个小世界网络小世界网络是可扩展的（它们几乎像规则网络一样结构化，从而造成很低的熵），或者是某种程度的随机性(具有可以与随机网络相比较的高熵)。熵的扩展性是由重联概率p(也就是用以确定将每条链路的一端交换连接到一个随机选定的节点上的概率)确定。35.1生成一个小世界网络通过以概率p将k-规则网络的链路重联变成小世界网络：结果产生的小世界部分是结构化的、部分是随机的——因此他的度序列分布落在k-规则网络峰值和随机网络的泊松分布之间。45.1生成一个小世界网络Watts-Strongatz(WS)过程方法：从一个2-规则网络开始并重联一定百分比的链路加以“随机化”。最后生成的小世界网络是一种半结构化、半随机的网络。平均来讲，pm条链路是随机的，(1-p)m条链路是结构化的。缺点：不能保证网络是连通的。55.1生成一个小世界网络小世界网络的度序列小世界是部分k-规则和部分随机网络的混合。小世界网络的度分布随着重联概率的增加变得更平更广。65.2小世界网络属性小世界具有相对小的平均路径长度、高的聚类系数和可以调整的熵(根据重联概率p可以更改)。相对较小的随机性就会对路径长度、聚类和熵有很大的影响，这是小世界网络最显著的属性。一般来讲，轻微的小世界网络要比它之下的规则网络具有更高的聚类系数和更低的平均路径长度。小世界网络的平均路径长度受制于导入的随机性，但是其他属性如聚类系数受制于起始网络的拓扑。75.2小世界网络属性熵与重联概率对于小概率p，随机性上升非常快，然后当p接近100%时就平缓下来。接近一半熵的增加发生在1%和10%之间。对于足够大的重联概率p，熵随着p呈对数地增长。85.2小世界网络属性熵与密度通过允许k=2,3,4…来更改底层的k-规则网络，因而更改网络的密度。小世界的熵缓慢的增加，然后随着密度或重联概率的增加而平缓下来。95.2小世界网络属性小世界网络的路径长度WS小世界网络的平均路径长度随着熵的增加呈指数减少，但是不会减少到同等随机网络以下。这意味着，随着重联概率的增加，小世界变的更加随机化了，并且它的平均路径长度接近随机网络，但是小世界的平均路径长度决不会小于同等随机网络的。快速减少平均路径长度及具有较大的聚类系数是小世界网络的独特特点。小世界的路径长度随着重联概率的增加而收缩，达到p=100%为极限。105.2小世界网络属性小世界网络的路径长度115.2小世界网络属性小世界网络的聚类系数聚类随着熵的增加而减少，因为聚类是一种结构(有序)，而重联链路是一种随机性(无序)。增大重联概率就增大了无序，也就降低了聚类。熵与k-规则网络的最初顺序相反。保持重联概率不变而让密度变化。聚类系数会随着密度的提高而缓慢提高，因为提高密度会使网络更加接近完全网络（完全网络的聚类系数是1.0）。聚类系数随着密度接近100%而渐近1.0。125.2世界网络属性小世界中的紧度紧度随着密度的增加而增加，到达某一点，然后向下再向上，随之网络开始更像k-规则网络而非小世界网络。向下再向上之后，重新变的规律性，紧度再次提高直到接近100%峰值为止。135.2世界网络属性小世界中的紧度随机网络在密度接近100%之前没有规律性；小世界网络具有大量与密度无关的规则性——随着密度的增加规则性对平均紧度的影响会增加。在大约50%左右到达“临界点”，这就导致小世界行为更像k-规则网络而非随机网络。这种规则性在决定紧度时成为最重要的因素。一般来讲，超过20%密度，聚类倾向于增加平均紧度，而随机性倾向于减少平均紧度。145.3相变小世界网络的结构随着重联概率的增加，从规则变成半规则，再到半随机，最后到完全的随机拓扑。对于非常小的重联概率增加，网络半径和直径也会降低，并随着小世界迁移到随机网络而继续降低。从“大多数垂直”到“大多数水平”线的迁移被称为相变点，对应于相变的重联概率被称为转换点，又称为相变阀值。阀值明显地标示出从垂直到水平的交界点，并标记为从“大多数k-规则”到“大多数随机”拓扑的迁移。155.4小世界网络中的导航网络导航网络导航是一种搜索过程，据此一条信息仅使用如节点度、向心性或紧度等本地信息找到一条从源到目的节点的路径。165.4小世界网络中的导航四种搜索算法：随机——在导航路径上的下一个节点随机地选择最大度——具有最高度的邻接节点作为下一次选择最小半径——越高中心的邻接点作为下一次的选择（节点根据半径排序）最大紧度——具有最大紧度比率的邻接节点作为下一次选择（邻居节的根据它的中间状态或紧度进行排序）175.4小世界网络中的导航在上述算法中随机导航算法并非是最差的算法。对于2-规则WS小世界网络，随机要比最大紧度和最小半径好。一般来讲，最大紧度是最差的，因为他需要最多跳数才能到达目的节点。在所有情况下（小世界网络除外），最大度算法是最佳导航算法。从最大（最多跳数）到最好（最少跳数）排行导航算法，结果如下：最慢：最大紧度慢：随机中等：最小半径最快：最大度185.5分析小世界网络是可扩展的、高度聚类的、相对稀疏的。19Thanks20