0小世界宣讲培训.pptVIP

计算机算法设计与分析 @ Ningbo University * * 小世界 李纲 2008 宁波大学 信息科学与工程学院 六度分离 所谓小世界现象，或称“六度分离（six degrees of separation）”，是社会网络（social networks）中的基本问题，即每个人只需要很少的中间人（平均6个）就可以和全世界的人建立起联系。在这一理论中, 每个人可看作是图（graph）的节点，并有大量路径连接着他们，相连接的节点表示互相认识的人。这是一个涉及社会学，数学和计算科学问题的多学科交叉问题。该问题源于社会心理学家Stanley Milgram上世纪60年代作的实验：“追踪美国社交网络中的最短路径”。 六度分离 Milgram寄出了数百封信给内布拉斯加州的公众，并请求他们把信转交给某位相识的人，条件是对方必须是最有可能把信再转给波士顿一位股票经纪人手里的人。为了跟踪每一条不同的传送路径，Milgram请求参与者在转寄信件的同时，也给他寄一张明信片。结果，Milgram发现，信件到达最终收信人之前平均要经过6个人之手。人与人之间存在所谓六度分离的说法就来源于这个实验。 六度分离 虽然Milgram的结果很难说是定论，因为绝大部分的信件并未到达最终收信人手里，不过科学家最近发现，其他网络也具有这种小世界的特性。例如，我们发现，细胞内的任意两种化学物质，几乎都能通过三个化学反应组成的路径连结起来。在万维网上，虽然页面数高达30亿，但一般只要经过19个连结，就可以从一个网页到达另一个。 电子邮件使得世界变小 然而，在2003年哥伦比亚大学的邓肯·瓦茨及其同事发现了一些米尔格的理论成立的证据，并在报刊科学专栏上发表。他们用电子邮件试图通过传递的方式转发给13个不同国家的18个指定接受人。 通过朋友及所认识的人的帮助下顺利完成了这项实验。参与转发人数达60,000人，实验发现这个成功的转发链条全部在5到7环之间，与米尔格的理论相符。 遗憾的是，这个电子邮件转发链条有米尔格最初试验同样的弊端：很多链条很容易就断了。如同米尔格的研究一样，这些指定接受人都是社会上有头有脸的人物。一个是兽医，一个是警察，另一个是高级技术顾问。这些抽样调查中，都是企业骨干或者便利店中的工作人员。 必威体育精装版研究结果：6.6°的分隔 但微软研究所的兰斯科维克和霍维茨一项新的研究提到一些关于分隔理论的观点。2006年的某月，微软从300亿即时短信中分析得出的结果。他们用数据超越了阶级和国界的限制，弥补了米格尔时期人们在实验上的不足。 根据数据分析——史无前例的网络数据分析——他们发现两个即时信息用户的平均值是6.6°，比米格尔发现的数值稍微高一些。 兰斯科维克和霍维茨表示他们的实验证明了米格尔理论的正确性：每两个人的距离只是6°。然而，仍然有一个问题。很难概括上网和不上网人群的区别。人们在上网和不上网的时候的行为举止是不一样的。 必威体育精装版研究结果：6.6°的分隔 最大的问题是兰斯科维克和霍维茨假定两个发送即时信息的人作为一对关系。比如说，我跟一个邮递员说话，但他并不是我社会关系网中的一员——也就并不是米格尔所指的。数据已经高估了多少对即时信息发送者可以作为一对可研究的社会关系。 一个相关的问题是在网络上人们总是比较外向。他们想说什么就说什么，想做什么就做什么，根本不用考虑社会压力而忍气吞声或者跟随社会主流。因此，在网络上人们在发送即时信息时比较健谈，但现实社会中他们并不是这样子的。这样在网络上拓展社会关系十分容易。 这就是两个只要的问题——另外的问题是这个数据偏向于年轻人，以及那些社会上对电子技术较为熟悉的人群。 必威体育精装版研究结果：6.6°的分隔 这种小世界特性，并不意味着网络中存在神奇的组织原则。即使是一个完全随机连结的大型网络，也是一个小世界。想想看，假设你认识1000个人，他们中的每一个人又认识1000个人，那么你只要通过一层中间人，就可以认识100万人。通过两层中间人，你就可以认识10亿人。要认识地球上所有的人，三层中间人已经绰绰有余了。这样看来，世界上任意两个陌生人之间存在六度分离的说法，简直就是废话了。然而，进一步的研究让我们对这一说法有了更深刻的认识。 上面我们的简单计算有个前提，那就是你的熟人都是彼此不相识的。但是在实际生活中，他们中有许多人是互相认识的。事实上，人类社会可以区分为一个个具有相似特质(例如收入或者兴趣)的小集群。自从1970年代Granovetter在哈佛大学读研究生时首开对此问题的研究之后，已有大量的社会心理学文献对这种社会特质进行了探讨。集群现象在其他多种网络中也普遍存在。1998年，美国