六度分离计算法

‘壹’ 六度分离的六度分离理论

“六度分离”理论可以算是社交网络研究中最着名的理论之一：生活这个世界上的每个人平均只需要通过6个中间人就能与全世界任何一个人建立联系。在网络社交逐渐发达的今天，“六度分离”理论的论证变得容易起来，Yahoo联合Facebook一同开始对这个理论进行了名为“小世界实验”的再度验证。
小世界实验”的具体流程是：参加调查的用户A会被分配一个他不认识的目标对象X；然后选择自己认为最有可能认识“目标对象”的一个Facebook好友B，系统会发出信息给B，让B去选择好友C，一环扣一环，最后找到目标对象X。最后，经过大量的筛选和统计我们就能验证“六度分离”理论在当下的正确性了。这个实验的最后结果会作为重要的社会学研究成果发表在相关的科学杂志上 。

‘贰’ 六度分离的算法实现

建议实现2个 2度查询,然后求交集. 单向6度的数据量广度太大.不适合目前的数据库软件.
不要盲目的使用完全数学的方法.变通为实用的算法才是最有算法.

‘叁’ 六度分离理论指的是什么如题 谢谢了

六度分离理论（Six Degrees of Separation）：“你和任何一个陌生人之间所间隔的人不会超过五个，也就是说，最多通过五个人你就能够认识任何一个陌生人。”根据这个理论，你和世界上的任何一个人之间只隔着五个人，不管对方在哪个国家，属哪类人种，是哪种肤色。 详述1967年美国社会心理学家米尔格伦（Stanley Milgram）提出了一个“六度分离”理论。简单地说，该理论认为在人际交往的脉络中，任意两个陌生人都可以通过“亲友的亲友”建立联系，这中间最多只要通过五个朋友就能达到目的。这个看似非常简单，却又很玄妙的理论引起了数学家、物理学家，以及电脑科学家们的关注。他们研究发现世界上许多其它的网络也有极相似的“六度分离”结构，例如经济活动中的商业联系网络结构、生态系统中的食物链结构，甚至人类脑神经元结构，以及细胞内的分子交互作用网络结构。 2001年哥伦比亚大学社会学系的一个研究小组开始在互联网上进行了这个实验。他们建立了一个实验网站，终点是分布在不同国家的18个人（包括纽约的一位作家、澳大利亚的一名警察以及巴黎的一位图书管理员等等），志愿者通过这个网站把电子邮件发给最可能实现任务的亲友。结果一共有384个志愿者的邮件抵达了目的地，电子邮件大约只花了五到七步就传递到了目标。这个活动现在还在继续。 美国的一个脱口秀节目有一次请了三个大学生来参加，主题是证明好莱坞的任何其他明星与演技派男星凯文·贝肯之间都能通过五个人联系起来。他们甚至成功的把已经去世了的卓别林与凯文·贝肯之间通过三个人建立了联系。节目引起了巨大反响。 六度分离理论告诉我们，有时候小数字，却蕴含着巨大的威力。就像我问你，如果你想象一下把一张足够大的纸对折50次，会有多高？如果你告诉我100米，这并不是你的错。有些东西是想象不出来的。真正答案可能更趋近于次，它的高度能把你送到太阳的肚子里。 有人把世界65亿人开了7次方根，结果是25.2257，从不科学方式说，我们每个人只要认识20几个人就可以满足此理论。

‘肆’ 什么是六度分离定理

认为世界上任何两个人之间最多通过6个人，就能建立联系的“六度分离理论”，曾在理论界引起一阵狂热，无论是数学家还是电影演员都想“实践”这一定理。六度分离理论于1967年首次用信件试验的形式被证明。如果浏览最近的英国《每日邮报》，你会发现微软公司声称，他们的一项研究——2006年6月份的ＭＳＮ网上消息传递试验证明，任何两个人平均需要6．6个人搭桥，就能建立联系。中间值是7个人，最多的则是29个人。

虽然这项实验比40年前的研究方法有了较大进步，但这远远不能说明问题。因为研究的局限性使得这样的结论不具说服力。

2006年，大约有2．4亿人使用微软公司的ＭＳＮ服务——那就意味着全球96．3％的人口根本没有参与这项活动。那些被排除在外的人不成比例地分布在非洲、南美洲、亚洲和东欧。这些被排除的人很可能会与被研究的某些人建立起沟通桥梁。另一方面，有些人或许根本没有通讯设施，这些几乎被隔绝的人需要的“人桥”恐怕远远超过6个。参与研究的一位学者表示，这正是研究的“有失偏颇之处。”

同时，这项研究只进行了一个月，而且只考虑了信息的数量，而忽略了人们之间的关系。“爷爷或许不会用ＭＳＮ和孙子交流，但这明摆着是稳健的亲属关系。”微软研究中心的主要负责人埃里克·霍尔维茨说，“研究未涉及真实世界的社会关系。”

但改善研究方法绝非易事。使用电子邮件网络来开展此项研究会有更大的弊端，比如对使用Ｈｏｔｍａｉｌ邮件地址进行联络的人开展研究，可能会漏掉其中使用Ｇｍａｉｌ地址的联系人。就算电话号码也可能被多个人共享，这还会涉及个人隐私，于是微软公司并未采纳上述研究方式。

研究人员请求了解ＭＳＮ使用者的年龄、性别和住址，并获得了受访者的许可。霍尔维茨先生说：“如果要获取更多数据，会耗费更大精力，而且会严重侵犯他人隐私。”不过他提出了另一种可能性：在受访者当中提取一小部分样本，然后分析他们所有的通信方式，用来估计可能被丢失或遗漏的数据。但随机取样同样存在问题：可能会破坏社会关系本来的结构，一些原本和样本有联系的人或许恰巧未被抽到。

1967年，美国社会学家杰弗里·特拉维斯和斯坦利·迈尔戈兰在研究社交网络时，提出了“六度分离”理论。在他们主导的名为“追踪美国社交网络最短路径”的试验中，他们要求每个参与者设法寄信给一个住在波士顿附近的“目标人物”，规定每个参与者只能转发给一个他们认识的人。试验结束后，迈尔戈兰声称“最短路径”的平均长度为6个人。

后来，迈尔戈兰教授在一项未公开的报告称，在试验开始时，他们只抽取了居住在美国波士顿和内布拉斯加的296人，这些人通过信件相互联系，只有64封信到达了它们预期的地址。他发现，人与人之间的分离程度远远超过了“六度”。

‘伍’ 六度分离理论的理论证实

微软研究院一款名为“人立方”的搜索引擎新鲜出炉，能够一网打尽搜索对象的人际关系网，引发诸多关注。在人际关系的研究中，美国着名的社会心理学家斯坦利·米尔格兰姆提出了“六度分离”理论，称只需六步就能将彼此毫不相关的两个人以某种方式联系到一起。这听起来像是天方夜谭，但科学家近期证实了这种奇妙的理论。这个星球上的所有人，从某种意义上来说，都是可以通过个人的关系网以特殊的方式联系起来。
两个陌生人六步就能搭上关系
我们可以举例来解释“六度分离”理论：A和B曾在舞会上共舞一曲，B曾是C的室友，C又从D那借过一辆自行车，以此类推，最终第一个人A就和最后一个人以这种方式联系到了一起。
也就是说，通过个人的关系网，任何两个素不相识的人中间其实最多只隔着6个人，只用6个人就可以将两个陌生人联系在一起，这就是“六度分离”理论的基础。 “六度分离”理论最早可以追溯到1929年，匈牙利作家考林西在他的短篇小说《枷锁》中就写到，两个陌生人最多通过5个人就能建立起联系。
但理论的提出和成形，还得归功于美国着名的社会心理学家斯坦利·米尔格兰姆，斯坦利通过一个着名的试验，最终系统地提出并证实了“六度分离”理论。
1967年，当时是哈佛大学心理学教授的米尔格兰姆随便招募了300多名志愿者，请他们邮寄一个信函，目的地是米尔格兰姆指定的一位住在波士顿的股票经纪人。由于几乎可以肯定信函不会直接寄到目的地，米尔格兰姆就让志愿者把信函发送给他们认为最有可能与目标建立联系的亲友，并要求每一个转寄信函的人都回发一个信件给米尔格兰姆本人。出人意料的是，有60多封信最终到达了目标股票经济人手中，并且这些信函经过的中间人的数目平均只有5个，也就是说，陌生人之间建立联系的最远距离是6个人。
1967年5月，米尔格兰姆在《今日心理学》杂志上发表了实验结果，并提出了着名的“六度分离”理论，表示虽然世界很大,但是如果将每个人的人际关系网考虑进去，人与人的距离其实很小。 微软公司的研究人员为证实这种理论的可行性而开展实验，随意挑选了2006年的某一月，记录下当月所有通过微软网络发送短信的用户地址，分析了300多亿条地址信息，最终统计得出，多达78%的用户仅通过发送平均6.6条短信，或者说通过6.6步，就可以和一个陌生人建立起联系。按照这种理论，每个人都可以利用关系网与陌生人搭上关系，甚至像麦当娜、英国女皇这样的名人从某种意义上来说都是我们的“熟人”。
当年，米尔格兰姆的实验只涉及到300余人，但借助先进的科技，研究所用的信息量被扩大到300亿条之多，为理论提供了更坚实的基础。现在，“六度分离”理论已在实践中得到广泛应用，不少商人和求职的大学生更是将它作为认识朋友、扩展人脉的金玉良言加以实践。

‘陆’ 六度分隔假说的历史

六度分隔实验
1967年，美国哈佛大学社会心理学教授斯坦利·米尔格兰姆对这个问题做了一个着名的实验，他从内布拉斯加州和堪萨斯州招募到一批志愿者，随机选择出其中的三百多名，请他们邮寄一个信函。信函的最终目标是米尔格兰姆指定的一名住在波士顿的股票经纪人。由于几乎可以肯定信函不会直接寄到目标，米尔格兰姆就让志愿者把信函发送给他们认为最有可能与目标建立联系的亲友，并要求每一个转寄信函的人都回发一个信件给米尔格兰姆本人。出人意料的是，有六十多封信最终到达了目标股票经济人手中，并且这些信函经过的中间人的数目平均只有5个。也就是说，陌生人之间建立联系的最远距离是6个人。1967年5月，米尔格兰姆在《今日心理学》杂志上发表了实验结果，并提出了着名的“六度分隔”假说。
尚未证明的“理论”
但是在30多年的时间里，米尔格兰姆的理论从来没有得到过严谨的证明，虽然屡屡应验，虽然很多社会学家一直都对其兴趣浓厚，但它只是一种假说。现在，美国两所不同大学的社会学家们正在分别对此进行研究，它们都不约而同地使用了网络时代的新型通讯手段 —— Email —— 来对“小世界现象（small worldphenomenon）”进行验证。
2001年，哥伦比亚大学社会学系的登肯·瓦兹主持了一项最新的对“六度分隔”理论的验证工程。166个不同国家的六万多名志愿者参加了该研究。瓦兹随机选定18名目标（比如一名美国的教授、一名澳大利亚警察和一名挪威兽医），要求志愿者选择其中的一名作为自己的目标，并发送电子邮件给自己认为最有可能发送邮件给目标的亲友。到目前为止，瓦兹在世界最顶级的科学学术期刊《科学》杂志上发表最新论文表明邮件要达到目标，平均也只要经历5～7个人左右。
为什么是“六”度
“六度分隔”假说的出现使得人们对于自身的人际关系网络的威力有了新的认识。但为什么偏偏是“六度分隔”而不是“七度、八度”或者“千网络”呢？这可能要从人际关系网络的小世界性质的另外一个特征“150定律”来寻找解释。
《纽约客》杂志的专栏作家马可姆·格兰德威尔在他的着作《引爆流行》中考证了一个名为“郝特兄弟会”的欧洲农民组织，这个组织有个约定俗成的规定：一个聚居点的人员规模超过150个人时，就要将该聚居点变成两个，这两个点再进行“…… 150-分离-150……”的循环。格兰德威尔说：“把人群控制在150人以下似乎是管理人群的一个最佳和最有效的方式”。在古往今来，许多团体建制都无意识地采用了这条规律。例如：在14世纪以后瑞典陆军编有旅，每旅辖3个营，每营辖4个连，每连编150人。我国建国后人民公社的建制人数也为150人。人们不免要问为什么偏偏是150人这个数字呢？人类学家特蕾茜·H·约菲研究发现人类所能处理的社会信息与人类的大脑的视觉和社会认知能力的发达程度有关。由罗宾·邓巴领导的研究小组1993年报道了动物种群的规模与其大脑新皮层相对于整个大脑比例相关，在现代人，这个规模大概是147人左右。进而，邓巴在2002年通过西方人比较熟悉圣诞卡片交换行为的调查发现这个人数在153左右。类似的大量研究都表明“150定律”的科学性。只要稍微计算一下就可以知道，如果每个人的日常密切联系的人际网络是150人左右的话，通过6个人的人际关系网络就可能有的人数是 150*150*150*150*150*150=11，390，625，000，000è1.1*1013。这个数字远超过人类历史上所有各代的人数之和。

‘柒’ 六度分隔是什么

六度分隔理论也叫六度分割理论。
有一个数学领域的猜想，名为Six Degrees of Separation，中文翻译包括以下几种： 六度分割理论或小世界理论等。 理论指出：你和任何一个陌生人之间所间隔的人不会超过六个，也就是说，最多通过六个人你就能够认识任何一个陌生人。这就是六度分割理论，也叫小世界理论。 涵义
这种现象，并不是说任何人与人之间的联系都必须要通过六个层次才会产生联系，而是表达了这样一个重要的概念：任何两位素不相识的人之间，通过一定的联系方式，总能够产生必
六度空间理论示意图
然联系或关系。显然，随着联系方式和联系能力的不同，实现个人期望的机遇将产生明显的区别。
社会网络其实并不高深，它的理论基础正是“六度分割”。而社会性软件则是建立在真实的社会网络上的增值性软件和服务。有这么一个故事，几年前一家德国报纸接受了一项挑战，要帮法兰克福的一位土耳其烤肉店老板，找到他和他最喜欢的影星马龙·白兰度的关联。结果经过几个月，报社的员工发现，这两个人只经过不超过六个人的私交，就建立了人脉关系。原来烤肉店老板是伊拉克移民，有个朋友住在加州，刚好这个朋友的同事，是电影《这个男人有点色》的制作人的女儿在女生联谊会的结拜姐妹的男朋友，而马龙·白兰度主演了这部片子。 价值
不管理论如何深奥，“六度分割”和互联网的亲密结合，已经开始显露出商业价值。人们在近几年越来越关注社会网络的研究，很多网络软件也开始支持人们建立更加互信和紧密的社会关联，这些软件被统称为“社会性软件” （Social Software）。例如Blog就是一种社会性软件，因为Blog写作所需要的个性和延续性，已使Blogger圈这种典型的物以类聚的生态形式，越来越象真实生活中的人际圈。据致力于研究社会软件的毛向辉介绍，国外现在更流行的是一种快速交友，或者商业联系的工具，例如LinkedIN。人们可以更容易在全球找到和自己有共同志趣的人、更容易发现商业机会、更容易达到不同族群之间的理解和交流，等等。
社会性软件的定义很多，而且还都在不断的发展演变过程之中。它的核心思想其实是一种聚合产生的效应。人、社会、商业都有无数种排列组合的方式，如果没有信息手段聚合在一起，就很容易损耗掉。WWW成功地将文本、图形聚合在一起，使互联网真正走向应用；即时通讯又将人聚合在一起，产生了ICQ这样的工具。然而这还是虚拟的，虚拟虽然是网络世界的一种优势，但是和商业社会所要求的实名、信用隔着一条鸿沟。通过熟人之间，通过“六度分割”产生的聚合，将产生一个可信任的网络，这其中的商业潜能的确是无可估量的。
聚合作为社会研究的对象也具有实际价值。康奈尔大学的科学家开发了一个算法，能够识别一篇文章中某些文字的“突发”增长，而这些“突发”增长的文字可以用来快速识别最新的趋势和热点问题，因此能够更有效地筛选重要信息。过去很多搜索技术都采用了简单计算文字 /词组出现频率的方法，却忽略了文字使用增加的速率。如果这种方法应用到广告商，就可以快速找到潜在的需求风尚。
社会、网络、地域、商业、Blog、sns，这些词汇你也许都听麻木了。然而一旦那些预见先机的人找到聚合它们的商业价值，被改变的绝不仅仅是网络世界。

‘捌’ 关于六度分离

目前，科学家还不知道为什么是“六级分离”，而不是“60级分离”或者“100级分离”。“据我所知还没有什么理论原因说明为什么数字是6，”穆罕穆德说。

‘玖’ 什么是6度分割理论

是一个对社会的调查分析总结出来的规律

六度分隔”无限网络

1967年，美国着名的心理学教授斯坦利·米尔格兰姆想要描绘一个联结人与社区的人际联系网，做了一个着名的连锁信实验。他招募一批志愿者，随机选出其中300多名，请他们邮寄一个信函。信函的最终目标是米尔格兰姆指定的一名股票经纪人。由于几乎可以肯定信函不会直接寄到目标，米尔格兰姆就让志愿者把信函发送给他们认为最有可能与目标建立联系的亲友，并要求每一个转寄信函的人都回发一个信件给米尔格兰姆本人。出人意料的是，有60多封信最终到达了目标股票经纪人手中，并且这些信函经过的中间人的数目平均只有五到六个。也就是说，陌生人之间建立联系的最远距离是六个人。这就是着名的“六度分隔”假说：最多通过六个人你就能够认识任何一个陌生人。

然而，在近40年的时间里，米尔格兰姆的理论没有得到过严谨证明，但是却实实在在影响着大众的生活和社会人脉网络。有这么一个故事：

几年前一家德国报纸接受了一项挑战，要帮法兰克福的一位土耳其烤肉店老板，找到他和他最喜欢的影星马龙·白兰度的关联。结果经过几个月，报社的员工发现，这两个人只经过不超过六个人的私交，就建立了人脉关系。原来烤肉店老板是伊拉克移民，他有位朋友住在加州，刚好这个朋友的同事的女朋友在女生联谊会有一位结拜姐妹，这位结拜姐妹是电影《这个男人有点色》的制作人的女儿，而马龙·白兰度主演了这部片子。

哥伦比亚大学社会学系的登肯·瓦兹主持了一项最新的对“六度分隔”理论的验证工程。166个不同国家的6万多名志愿者参加了该研究。瓦兹发现，通过电子邮件，从志愿者到达目标的过程，平均也只要经历6个人左右。

其实，人脉网络、社会网络并不高深，它的理论基础正是“六度分隔”。

‘拾’ 六度分离理论的详述

1967年美国社会心理学家米尔格伦（Stanley Milgram）提出了一个“六度分离”理论。简单地说，该理论认为在人际交往的脉络中，任意两个陌生人都可以通过“亲友的亲友”建立联系，这中间最多只要通过五个朋友就能达到目的。这个看似非常简单，却又很玄妙的理论引起了数学家、物理学家，以及电脑科学家们的关注。他们研究发现世界上许多其它的网络也有极相似的“六度分离”结构，例如经济活动中的商业联系网络结构、生态系统中的食物链结构，甚至人类脑神经元结构，以及细胞内的分子交互作用网络结构。2001年哥伦比亚大学社会学系的一个研究小组开始在互联网上进行了这个实验。他们建立了一个实验网站，终点是分布在不同国家的18个人（包括纽约的一位作家、澳大利亚的一名警察以及巴黎的一位图书管理员等等），志愿者通过这个网站把电子邮件发给最可能实现任务的亲友。结果一共有384个志愿者的邮件抵达了目的地，电子邮件大约只花了五到七步就传递到了目标。这个活动现在还在继续。
美国的一个脱口秀节目有一次请了三个大学生来参加，主题是证明好莱坞的任何其他明星与演技派男星凯文·贝肯之间都能通过五个人联系起来。他们甚至成功的把已经去世了的卓别林与凯文·贝肯之间通过三个人建立了联系。节目引起了巨大反响。
六度分离理论告诉我们，有时候小数字，却蕴含着巨大的威力。就像我问你，如果你想象一下把一张足够大的纸对折50次，会有多高？如果你告诉我100米，这并不是你的错。有些东西是想象不出来的。真正答案可能会让你大吃一惊，它的高度能把你送到太阳的肚子里。
有人把世界65亿人开了7次方根，结果是25.2257，从不科学方式说，我们每个人只要认识20几个人就可以满足此理论。
有一个数学领域的猜想，名为Six Degrees of Separation，中文翻译有以下几种：六度分割理论、六度空间理论以及小世界理论等。20世纪60年代，耶鲁大学的社会心理学家米格兰姆就设计了一个连锁信件实验。他将一套连锁信件随机发送给居住在内布拉斯加州奥马哈的160个人，信中放了一个波士顿股票经纪人的名字，信中要求每个收信人将这套信寄给自己认为是比较接近那个股票经纪人的朋友。朋友收信后照此办理。最终，大部分信在经过五、六个步骤后都抵达了该股票经纪人。六度分割（也叫“六度空间”）的概念由此而来。这个连锁实验，体现了一个似乎很普遍的客观规律：社会化的现代人类社会成员之间，都可能通过“六度空间”而联系起来，绝对没有联系的A与B是不存在的。这是一个更典型、深刻而且普遍的自然现象。那么，怎样用数学理论揭示“六度分割现象”？这是现代数学领域又一个重大的数学猜想。这有点儿像地图的邻接色问题，只不过邻接色问题是通过数学方法可以精确证明的（即最多只需要使用4种颜色即可），而6度分割理论我个人估计只能通过不完全归纳来形成假设了吧，社会的模型还是比二维地图模型要复杂莫测得多啦！ 六度分隔的现象，并不是说任何人与人之间的联系都必须要通过六个层次才会产生联系，而是表达了这样一个重要的概念：任何两位素不相识的人之间，通过一定的联系方式，总能够产生必然联系或关系。显然，随着联系方式和联系能力的不同，实现个人期望的机遇将产生明显的区别。