偶看新闻江苏恒伟建设有限公司:小世界现象和分散式搜索
来源：百度文库 编辑：偶看新闻 时间：2024/04/29 06:40:11
The Small-World Phenomenon and Decentralized Search
【Jon Kleinberg, SIAM News, Volume 37, Number 3, April 2004, Young 译】所谓小世界现象，或称“六度分离（six degrees of separation）”，是社会网络（social networks）中的基本问题，即每个人只需要很少的中间人（平均6个）就可以和全世界的人建立起联系。在这一理论中, 每个人可看作是图（graph）的节点，并有大量路径连接着他们，相连接的节点表示互相认识的人。这是一个涉及社会学，数学和计算科学问题的多学科交叉问题。该问题源于社会心理学家Stanley Milgram上世纪60年代作的实验：“追踪美国社交网络中的最短路径”。他要求每个参与者寄信给一个住在波士顿附近的“目标人物”，规定每个参与者只能转发给一个他们认识的人。Milgram发现完整的链平均长度为6个人。那么为什么社会网络中只包含了如此短的路径呢？
最近，应用数学家Duncan Watts和Steve Strogatz提出利用小世界性质（small-world property）来研究网络：一个高度聚集的包含了“局部连接”节点的子网，连同一些随机的有助于产生短路径的长距离无规连接（random long-range shortcuts）。除了对社会、技术和生物网络的唯象研究（empirical studies），Watts和Strogatz还考虑了以下简单模型系统：以一个d维格点网络开始（d-dimensional lattice network），给每个节点添加一些少量随机长距离连接，把它们连接到随机选择的一些终点上。这样构建的网络将会有局域聚集（local clustering）现象及短的路径，如同现实世界中发现的大多数网络一样。(图1，2) 
图1.带有单个随机连接的二维格点网络
图2. 带有多个随机连接的二维格点网格（Watts-Strogatz模型）
Milgram的研究有两大发现，社交网络中短路径的存在仅是其一，其二是社会中的人们，他们仅知道自己认识的人，就能很快地把信件转发到任何远方目标。用计算术语来讲，就是关于路由算法（routing algorithm）的效率问题，这一算法可完全依靠本地信息来找到到达目的地的有效路径。这一分散路由方案也有力地揭示了社会网络中一些潜在的惊人特点。
模拟小世界现象的这一特点向人们提出了进一步的挑战：我们能找到可以证明Milgram式分散路由生成的短路径的模型系统吗？对Watts-Strogatz模型及其变量的数学分析结果令人惊讶。首先，在一个带均匀随机连接（uniformly random shortcuts）的d-维网络中，没有找到关于搜索短路径的分散算法；第二，这是一个具体的例子，在网络中存在着短路径，但本地信息不足以构建这些路径。
然而，更进一步研究，我们发现对Watts-Strogatz模型做一些微小改动就会使搜索更有效：不是均匀地加入长距离连接，而是按某种分布率在网络结点间添加连接，即让在d-维空间中节点连接的几率随距离的增大以d次幂衰减。实际上，随距离的d-次幂几率衰减统一了所有距离的“尺度”——与一个节点距离为1 - 10节点构成连接的数目大致和它与距离为10 - 100，100 - 1000等的节点构成连接的数目一样(图3)。 
图3. 按d次幂衰减带有多个不同距离的随机连接生成的结点
在互联网的点对点（P2P）文件共享系统中，这一利用连接几率随距离衰减的连接方式能够建立搜索得到了证明。在P2P中，文件内容需要通过一个节点以分散方式检索另一节点。换句话说，结点执行搜索协议时就像是在参与Milgram的实验——令人惊奇地说明了在计算和社会科学中传递信息的方式。在计算世界里，数学模型被转换为简易的设计原则。
作者Jon Kleinberg是康奈尔大学计算机系的副教授。
相关连接：http://mathforum.org/mam/04/essays/smallworld.html