小世界（Small World）模型

ybu2008

    在小世界模型中，每个节点都表现出某些可以被捕捉到的兴趣，而兴趣相近的节点所保存的内容和提交的查询也呈现出一定的相关性，将节点按照它们表现出来的相关性组成网络，使得相关性高的节点在网络中比较近。这种按节点间的相关性所组成的网络表现出和社会网络相近的特性，为“小世界（Small World）”。

    Stanley Milgram实验发现，通过平均6人次的熟人传递就可以把社会中任意两人联系起来，这种现象被称为“Small World”。他揭示了：短链效应普遍存在和人们可以找到短链。

    幂规律和小世界特征证明：实际网络的拓扑结构既不是非结构化网络中的一个完全随机图，也不是结构化网络中的确定性拓扑图。小世界模型特征指出，网络拓扑具有高***度和短链特性。在以小世界特性为基础的网络模型中，节点按照自身的***度被划分为若干簇，在每个簇中至少有一个“度”最高的节点作为中心节点。在DHT路由算法中，“小世界”特性产生了重大的影响：从如何缩短路径长度的问题变成了如何找到“短链”的问题。以概率P断开与其连接的边，并从网络中的其他节点随机选择进行重新连接。当P=0时，该网络就是规则网络；当P=1时，该网络就是随机网络；但P为0-1间某个值时，将存在很大区域，拥有较高的集聚程度和较小的最小距离。

    聚类分布（CD）算法属于一种非结构化的DHT算法，其基本原理是，将一个环状覆盖网络划分为两层——AUT层和HUB层，AUT负责数据管理，HUB负责节点路由，每层在局部节点上以聚类方式组织信息。CD算法初步解决了已有非结构化算法的数据无组织性和搜索盲目性。

    CD算法的索引采用了DHT，利用高位散列函数将查询词和文件的描述信息（如文件名或关键词等）映射为Key，Key按照升序排列，首尾相接，构成一个环形空间，Key与Key的距离等于它们在环形空间上的最短距离。

    搜索时，查询词若与本地文件匹配，则返回结果的同时，更新路径上各个节点的路由表；否则，在AUT表中查找查询词，若匹配，则发送消息至对应节点；若AUT表不匹配，则再从HUB表中寻找最接近查询词的节点（即节点中心与查询词接近），并发送查询词至该节点。

参考：《P2P网络技术原理与C++开发案例》