精华内容
下载资源
问答
  • 六度空间理论

    千次阅读 2009-11-15 10:10:00
    有一个数学领域的猜想,名为Six Degrees of Separation,中文翻译包括以下几种: 六度分隔理论、六度空间理论以及小世界理论等。 六度空间理论指出:你和任何一个陌生人之间所间隔的人不会超过六个,也就是说,最多...

     

    有一个数学领域的猜想,名为Six Degrees of Separation,中文翻译包括以下几种: 六度分隔理论、六度空间理论以及小世界理论等。

      六度空间理论指出:你和任何一个陌生人之间所间隔的人不会超过六个,也就是说,最多通过六个人你就能够认识任何一个陌生人。这就是六度空间理论,也叫小世界理论。

      六度分隔的现象,并不是说任何人与人之间的联系都必须要通过六个层次才会产生联系,而是表达了这样一个重要的概念:任何两位素不相识的人之间,通过一定的联系方式,总能够产生必然联系或关系。显然,随着联系方式和联系能力的不同,实现个人期望的机遇将产生明显的区别。

      社会网络其实并不高深,它的理论基础正是“六度分隔”。而社会性软件则是建立在真实的社会网络上的增值性软件和服务。有这么一个故事,几年前一家德国报纸接受了一项挑战,要帮法兰克福的一位土耳其烤肉店老板,找到他和他最喜欢的影星马龙·白兰度的关联。结果经过几个月,报社的员工发现,这两个人只经过不超过六个人的私交,就建立了人脉关系。原来烤肉店老板是伊拉克移民,有个朋友住在加州,刚好这个朋友的同事,是电影《这个男人有点色》的制作人的女儿在女生联谊会的结拜姐妹的男朋友,而马龙·白兰度主演了这部片子。

      1967年,哈佛大学的社会心理学家米尔格兰姆(Stanley Milgram)就设计了一个连锁信件实验。他将一套连锁信件随机发送给居住在内布拉斯加州奥马哈的160个人,信中放了一个波士顿股票经纪人的名字,信中要求每个收信人将这套信寄给自己认为是比较接近那个股票经纪人的朋友。朋友收信后照此办理。最终,大部分信在经过五、六个步骤后都抵达了该股票经纪人。六度空间的概念由此而来。这个连锁实验,体现了一个似乎很普遍的客观规律:社会化的现代人类社会成员之间,都可能通过“六度空间” 而联系起来,绝对没有联系的A与B是不存在的。这是一个更典型、深刻而且普遍的自然现象。那么,怎样用数学理论揭示 “六度分隔现象”?这是现代数学领域又一个重大的数学猜想

      这有点儿像地图的邻接色问题,只不过邻接色问题是通过数学方法可以精确证明的(即最多只需要使用4种颜色即可),而六度分隔理论我个人估计只能通过不完全归纳来形成假设了吧,社会的模型还是比二维地图模型要复杂莫测得多。

      不管理论如何深奥,“六度分隔”和互联网的亲密结合,已经开始显露出商业价值。人们在近几年越来越关注社会网络的研究,很多网络软件也开始支持人们建立更加互信和紧密的社会关联,这些软件被统称为“社会性软件” (Social Software)。例如Blog就是一种社会性软件,因为Blog写作所需要的个性和延续性,已使Blogger圈这种典型的物以类聚的生态形式,越来越象真实生活中的人际圈。据致力于研究社会软件的毛向辉介绍,国外现在更流行的是一种快速交友,或者商业联系的工具,例如LinkedIN。人们可以更容易在全球找到和自己有共同志趣的人、更容易发现商业机会、更容易达到不同族群之间的理解和交流,等等。

      社会性软件的定义很多,而且还都在不断的发展演变过程之中。它的核心思想其实是一种聚合产生的效应。人、社会、商业都有无数种排列组合的方式,如果没有信息手段聚合在一起,就很容易损耗掉。WWW成功地将文本、图形聚合在一起,使互联网真正走向应用;即时通讯又将人聚合在一起,产生了ICQ这样的工具。然而这还是虚拟的,虚拟虽然是网络世界的一种优势,但是和商业社会所要求的实名、信用隔着一条鸿沟。通过熟人之间,通过“六度分隔”产生的聚合,将产生一个可信任的网络,这其中的商业潜能的确是无可估量的。

      聚合作为社会研究的对象也具有实际价值。康奈尔大学的科学家开发了一个算法,能够识别一篇文章中某些文字的“突发”增长,而这些“突发”增长的文字可以用来快速识别最新的趋势和热点问题,因此能够更有效地筛选重要信息。过去很多搜索技术都采用了简单计算文字 /词组出现频率的方法,却忽略了文字使用增加的速率。如果这种方法应用到广告商,就可以快速找到潜在的需求风尚。

      社会、网络、地域、商业、Blog,这些词汇你也许都听麻木了。然而一旦那些预见先机的人找到聚合它们的商业价值,被改变的绝不仅仅是网络世界。

      六度虽然是个社会学的理论,但是实际上它更像一个数学理论,很多人说六度和四色问题有异曲同工之妙。在我看来,六度理论很好的阐述了在一个网状结构(我们的人类社会)下,不同节点之间的联系和连接关系,然而它并不完整,并不足以指导我们的实践。

     

    关系的强弱

      ——权值问题

      首先六度肯定了人与人之间的普遍联系,但是没有对这种联系作定量分析。我们一生可能会认识千百人,他们有的对我极其重要,有的对我无足轻重,我们联系的建立的原因和方法也是千差万别,有父母亲属这类生而固有的联系,也有因为地理位置接近发展出来的,如邻里关系,还有因为共同学习生活而发展出来的同学、同事关系。六度理论中只把他们统统归结于联系,没有强弱之分。在网状结构里面,人与人的关系,需要加权处理,在这里,六度是残缺的。

     

    到达和建立联系的区别

      ——目的和结果问题

      20世纪60年代,耶鲁大学的社会心理学家米尔格兰姆(Stanley Milgram)就设计了一个连锁信件实验。他将一套连锁信件随机发送给居住在内布拉斯加州奥马哈的160个人,信中放了一个波士顿股票经纪人的名字,信中要求每个收信人将这套信寄给自己认为是比较接近那个股票经纪人的朋友。朋友收信后照此办理。最终,大部分信在经过五、六个步骤后都抵达了该股票经纪人。六度分割(也叫“六度空间”)的概念由此而来。这个故事很多六度的爱好者都知道,并奉为圣经。但是我请大家注意这个故事和我们现在流行的SNS网站的理念的重要差别。在这个故事里面,信到达了波士顿股票经纪人手里面没错,但是请注意整个过程中,每个人的朋友关系都没有发生改变。对,这点很重要,这个故事里面传递的信息,而我们现在看到的SNS网站希望在用户之间传递的是什么呢?是联系方式是朋友关系?

      说到这里想提一下前面提到的火炬的买车票的实验,在那个实验里面,传递的实际上也是信息,而不是朋友关系。

     

    传递的成本和激励

      ——阻尼问题

      在Stanley Milgram的实验和火炬的实验里面,都没有任何的花费,或者说看起来成本为0。但是是不是真的成本为0呢?每个人传递一下信件花费极低,改下msn名字更是没有成本,然而那些人肯这么做,其实是看着朋友的面子上,所以这里花费的成本实际是什么呢?是中国人说的人情债,所谓的关系成本。没有人喜欢一个整天都要人帮忙这帮忙那的人,人情债和金钱债一样,背了就一定要还,这就是传递中的成本问题。火炬的火车实验后,我们一直在想这个问题,今天我们急需车票,可以请朋友们改他们的名字,但是我们能不能天天都用这种方法来找人帮忙呢?今天买车票,明天买球票,也许一次两次可以,次数多了,朋友们肯定会觉得厌烦,甚至放弃你这个朋友。

      Gmail的邀请方式直至今日仍被很多人称颂,刚刚出现的时候,一个邀请甚至可以卖到60美金。很多人惊呼这是最伟大的营销。然而,到了今天,很多人的邀请已经变得无法送出去。为什么呢?因为一开始的时候Gmail是稀缺物品,所以价值高昂,加上Gmail带有Google的强势品牌和高度用户认同感,所以就更加被追捧,拥有Gmail成了荣誉的象征。这是这种荣誉成为了Gmail邀请在六度网络中疯狂传播的激励。然而随着Gmail的高度普及,这种荣誉感逐步下降,最终降低了激励,从来使传播陷入了停滞状态。

      阻尼是好还是坏?没有阻尼我们可以给任何人发送信息,每个SNS网站都在宣扬你只需要六度就可以认识克林顿可以认识盖茨,但是有几个人真的去认识他们了?是因为他们不值得认识么?不是,是因为联系虽然看起来只有六度,然而每度的阻尼都有可能都是无法跨越的。但是你不要悲观,如果没有阻尼也许你会更加不爽!LLF算过“举例来说吧。假设每个人有30个朋友,信息经过六度是30的6次方 =729000000,数量足够到达一个能够覆盖所有可能的人的级别。”,如果六度的连接没有任何的阻尼,估计我们每天收到的来自六度好友的各种各样的信息就会让我们的脑袋爆炸。

      在我们的生活里面,一个身份越高的人,越有名的人他就会有越多的好友,于是他也就越不想随便拓展自己的关系圈子,因为他们往往不胜其扰。前些日子的600演艺名人联系方式泄露事件就是一个例子,本来我们作为社会一分子都和这600名人有着六度的联系,然而某天因为他们的联系方式被公开,他们和我们的联系立刻被扁平化变成了一度。一瞬间,阻尼消失了,你可以随便打电话给那英、田震了,你不是想跟冯小刚聊电影么?你现在可以打电话了。但是,我们只能说结果这成了一场灾难,很多名人诉苦,说很多人打电话到他们的家里,说了句“你是XXX么?我很喜欢你!”然后就挂了电话。很多人不堪其扰停了机,甚至换了号。

      这场灾难对我们这些局外人来说是一个很有意思的故事,很有趣的一点在于此,一旦这些名人和大众的关系扁平化后(六度变成一度),他们对大众的价值也开始流失,大众们只能打电话过去,问一声,然后炫耀自己给明星打过电话,仅此而已。这个巨大的扁平化工程并没有扩展追星族们的朋友圈子,他们仍旧离那些明星很远……

     

    朋友的朋友是朋友的假设

      ——关系的方向和传递问题

      SNS网站最爱说的一句话也许就是“朋友的朋友是朋友”,然而那天我跟LLF在Msn聊天的时候就说过这个问题,我认识的某A的朋友某B是我非常反感的一个家伙,而且我的朋友里面还有个人某C对那个家伙某B更加痛恨。所以在现在的SNS服务里面我是不敢把某A和某C同时引入的,因为他们同时引入后,很可能的结果是某B和某C建立联系后,开始吵架。

     

    六度分割

      上世纪60年代,美国哈佛大学的社会心理学家米尔格伦提出了“六度分割”(Six Degrees of Separation)的理论。简单来说,“六度分隔”就是在这个社会里,任何两个人之间建立一种联系,最多需要六个人(不包括这两个人在内),无论这两个人是否认识,生活在地球上任何偏僻的地方,他们之间只有六度分隔。

      现在,大多数人都熟悉的“六度分离” 。 1993年的电影,其中主演威尔史密斯,把想法向一般公众的使用它的名称和主要议题阴谋。这个想法成为更受欢迎的“凯文培根游戏” ,即你选择任何演员并尝试联系起来,以某种方式,向演员凯文培根在“六个步骤” 。娱乐和看似琐碎尽管它们,这些车辆的普及为基础的严重的学术概念,社会互动和人际网络已在1990年代初期以来。

      这种概念,如凯文培根比赛,是由于技术进步,通讯和运输,人类正变得越来越连接。很远的距离较少影响沟通,因此,人际网络扩大远远超出了以往的限制和障碍。现代世界正在缩小。

      社会网络的核心,凯文培根游戏,以及六度分离的概念。一个社会网络是,本质上说,一系列的关系个人或联名的个人或组织。一个人或一个集团可以有许多不同的网络,例如,一个人可能有一个家庭网络,一名学校网络,网络的朋友,一个高尔夫球发挥网络,以及其他许多人。

      一个组织可能有一名雇员网络,供应商网络,客户网络等所有这些网络的特点是类型的关系,或互动,其中连接它。 A网络的员工可能是由雇主的特点,网络的选手谁发挥这些或有兴趣的高尔夫球。网络公司也开始在家庭和直接行动的国家的水平。他们是“胶水的社会,是根据所有文化。

      虽然我们可能认识到,我们每一个都是一个网络的一部分,或各种不同的网络,我们不一定把它们当作只不过我们知道的人在各种能力。当然,各种各样的网络,我们的一部分,通常反映了我们国内的生活,我们的爱好,我们的工作生活,我们的利益,因此,网络本身并没有这样的功能,作为人民代表对我们来说它。但有趣的是,考虑了一会儿,这些网络的结构。

      如果你写下的名字,所有你知道的人,并把它们分别列出相应的你如何来认识他们通过家庭,高尔夫球场,学校等,那么你将接近创造一个结构性的地图网络。如果每个人在您的名单然后也做了同样的,你可以比较清单,然后看到的真实程度的网络。您可能只知道5个选手,但他们知道每五,依此类推。您的建议,特别是俱乐部可以跨越国界根据所提出的意见给朋友,而获得通过,并通过。

      在分析社会网络,更大的重点放在那些个别人或群体,谁不仅有更多的连接在特定的网络,但也有更多的网络成员。如果您和您的所有球员的朋友住在一个孤立的城市,您只能打高尔夫球和工作,回家然后将您的网络的限制,其效力和将被视为是一个“小而严密的”网络。知识和机会,这样的网络不用不超过个人参与。

      新鲜成员不太可能加入,该网络是不太可能扩大或促进其成员的任何进一步一旦现有的知识和机会已经共享。如果,另一方面,每个成员的网络也是一个成员的其他许多网络则是“更开放”的网络将扩大,并允许更大的流通新的机遇和更广泛地利用新的信息。流动的知识和信息,在这样一个网络也大得多,有利于它的成员。

      如果我们现在适用于这些想法,在线联网,应当立即明确究竟有用和有益的可能性增加,通信网络的一个世界性的网络将。由于知识和机会可能被视为部分货币价值的网络,那么全世界的平台必须是高级形式。与在线社交网络服务,专门在这个方面的联网能力加入巨大,而且可能大大有益的,网络是“增压” 。

     

    六度分割理论的应用

      六度空间理论应用于实际当中的有许多,例如国内的校内网,各种校园交友等,其实质的应用表现:抢车位,好友买卖游戏,个人空间的“好友动态”“好友的朋友”等等。

      透过好友买卖看六度空间理论(选自SEO部落)

      原文地址:http://www.seo-tribe.com/seohtml/ZhanChangJiaoLiu/20081020/480-1.html

      随着SNS(社会性网络服务)网站的兴起,更多的社交互动创意涌现出来,社会性网络服务的优势逐渐在门户竞争中得以体现。近年来国内网站兴起了一波以SNS为主打的网络风潮,其中具有代表性的有:校内网,开心网,myspace,门户类如新浪等等。这些网站都可以算是国内SNS的典范,值得大家学习。我们以新浪空间为例。新浪在其推出新浪空间之后,这一年多最大的变化莫过于加入了一些看似简单却又耐人寻味的小游戏。这些游戏将我们的现实生活融入网络,特别适合于上班族玩。有人说:是游戏拉近了人与人的距离,这话一点不假。

      近年来,国内SNS的应用都体现在了效仿facebook而建立起来的互动游戏环节。而“好友买卖”则是一款让人娱乐之余还能结交更多朋友的游戏。

      “好友买卖”游戏中,如果您可以查看到好友的游戏情况,他有哪些“奴隶”,并且这些“奴隶”的各种属性都一一呈现在好友的奴隶列表中。如果您觉得这个“奴隶”很吸引你,你想“折磨”他,就必须让他成为你的奴隶,成为你“奴隶”的前提条件则是与他成为好友,你可以通过邀请方式加他为好友,当获得对方验证通过之后,您便可以随意对他进行买卖了,也就是说:您想玩游戏,就必须结识好友,你想玩得更深入,就必须认识更多的好友,整个过程中您通过您的好友认识了好友的“奴隶”,而且您也可以继续通过这个“奴隶”认识“奴隶”的“奴隶”。您通过好友认识更多的好友,如此重复下去,将整个网络上的人连成一家,也未尝不是一种可能,六度空间理论得以在这里真正体现出来。您最后还能通过好友信息里看到自己,那是必然的,因为别人也能够通过“好友买卖”来买卖你

      站长们可以反驳说:如果真那么神奇,六度空间理论岂不是能让我将所有网络用户吸引过来?那别的网站也效仿这种做法,也吸引了全部网络用户,但不是所有网络用户都同时使用两个网站的系统,这岂不是在理论上就出现矛盾了?当然我们所说的六度空间理论只是一种宏观上对人与人之间连接关系的理解,并不是说通过建立这么一个互动的系统,通过人吸引人,人邀请人,就能够吸引网络上所有的用户。理论结合实际,好的创意加之强大的技术支撑,你的网站距离成功也就不远了。

     

    六度分割

      所谓六度分割理论是指six degrees of separation,是在20世纪60年代由哈佛大学心理学家 stanley milgram提出的,six degrees of separation,六度分割。简单来说,六度分割就是在这个社会里,任何两个人之间建立一种联系,最多需要六个人(包括这两个人在内),无论这两个人是否认识,生活在地球的任何一个地方,他们之间只有六度分割。

      残缺的六度

      (1)关系的强弱——权值问题

      (2)到达和建立联系的区别——目的和结果问题

      (3)传递的成本和激励——阻尼问题...

      随着社会性网络的探讨逐渐走向成熟和实用化,很多网络大潮的前沿人士已经开始实践六度分割理论,国内的linkist就是在社会人脉方面的一个实践。

    展开全文
  • 在现实生活中,人际关系错综复杂,遇到难题,左右为难,致命问题保大保... 六度空间理论-在理论情况下,你与任何人的距离不超过6,即通过自我关系网,每一环节达到关系网的极值,不会超过6。然而在现实中,这个理论...

           在现实生活中,人际关系错综复杂,遇到难题,左右为难,致命问题保大保小、老妈还是老婆,这个是送命题,一般是不会出现,但是由于社会的发展,过年问题(孩子少,在哪里过年,另一方都会不热闹),这些困扰我们的问题,通过人与人的距离计算可以辅助我们做出选择。

      六度空间理论-在理论情况下,你与任何人的距离不超过6,即通过自我关系网,每一环节达到关系网的极值,不会超过6。然而在现实中,这个理论只是纸上谈兵,例如我与某某名人,他们看都不会看我一眼,关系就等同我与路边的乞丐的关系,绝不是看不起乞丐。回到主题,距离,在学校,我们知道点与点的距离可以由公式得到,那么人与人的距离如何计算呢?有什么标准呢?人与人的距离可以解决人际关系吗?

      以自己为例子,将朋友,同事,亲人划分三流九等,距离数据从1~5 ,其一为亲人初始为1, 其一为朋友初始为3,其一为其他人初始值为4,其他人包括同事、见过几面的陌生人,距离划分完成,每一个等级划分后,同等级也是有区别的,朋友有酒肉朋友,知心朋友等,等级划分完成,通过距离值得大小,即离中心的距离,决定着我们对人的态度,矛盾的时候的处理方法。有时候我也很困惑,明明距离是4甚至是5,却做着3才能做的事情,陌生人应该有陌生人的状态,在力所能及和不给他人带来麻烦的情况下,可以适当帮助。

      距离也不是一成不变的,人与人的距离随着关系的相处,可以做加减法,随着距离的变迁,等级也会跨越,比如从陌生人到达朋友,再如亲人冷漠也会变为陌生人。

    展开全文
  • 六度空间系统开发(APP理论) 首先说一下六度空间系统的含义:小世界现象(又称小世界效应),也称六度空间APP理论。 这种现象,并不是说任何人与其他人之间的联系都必须通过六个层次才会产生联系,而是表达了这样一...

    六度空间系统开发(APP理论)

    首先说一下六度空间系统的含义:小世界现象(又称小世界效应),也称六度空间APP理论。

    这种现象,并不是说任何人与其他人之间的联系都必须通过六个层次才会产生联系,而是表达了这样一个重要的概念:任何两个素不相识的人,通过一定的方式,总能够产生必然联系或关系。显然,随着联系方式和联系能力的不同,实现个人期望的机遇将产生明显的区别。

    六度空间公排分割理论:

    6度是单线竖排60人,然后二二公排横行补位,补位后再单线竖排60人,以此类推!

    5度是单线竖排50人,然后二二公排横行补位,补位后再单线竖排50人,以此类推!

    4度是单线竖排40人,然后二二公排横行补位,补位后再单线竖排40人,以此类推!

    3度是单线竖排30人,然后二二公排横行补位,补位后再单线竖排30人,以此类推!

    2度是单线竖排20人,然后二二公排横行补位,补位后再单线竖排20人,以此类推!

    1度是单线竖排10人,然后二二公排横行补位,补位后再单线竖排10人,以此类推!

    6个公排相互独立,收益可以共享,最高210层排线收益!升级1次参与1次公排。

    六度空间代码例子:

    void SDS()
    {
    	for (each V in G)
    	{
    		count = BFS(V);
    		Output(count / N);
    	}
    }
    int BFS(Vertex V)
    {
    	visited[V] = true; count = 1;	//count统计6层内元素个数
    	level = 0; last = V;		//last表示该层最后一个元素
    	Enqueue(V, Q);
    	while (!IsEmpty(Q))
    	{
    		V = Dequeue(Q);
    		for (V 的每个邻接点W)
    			if (!visited[W])
    			{
    				visited[W] = true;
    				Enqueue(W, Q); count++;
    				tail = W;
    			}
    		if (V == last){//取出结点等于该层最后一个结点,该层元素全部已经访问
    			level++; last = tail;
    		}
    		if (level == 6) break;
    	}
    	return count;
    }
    

    六度空间系统理论的真实性:

    如果你仅从数据着手,那么这个“六度空间理论”看上去似乎挺可信的。假如我们每个人都至少认识44个人,而这44个人又分别各认识另外44个人……以此类推,数学计算告诉我们,仅仅通过六个步骤,我们便能和44的6次方、即72.6亿人联系在一起——这比当前地球人口总和还要多。

    然而是否有任何实验证据来表明上述推论的正确性呢?Derek Muller解释道,这个理论的基础源于1929年的一则小故事,名为“链”。故事中,一个人向另一个人发起挑战,让对方找到地球上任意一个他无法通过5个以内的中介人联结起来的人。

    在上个世纪60年代,终于有人对此进行科学验证。一名心理学家在内布拉斯加和波士顿分发了300个包裹,并要求参与者运用自己的人脉网将其送到一个特定的人手中——居住在波士顿的一名股票经纪人。参与者不得直接将包裹寄送给他,而要将它交给一位可以直呼其名的好友,并要求这名好友再交给自己认为有可能认识他的好友。

    仅64个包裹真正抵达目标人物手里,而平均中介人数为5.2。后来这个实验便被用作“六度空间理论”的证据。但Derek对此进行了一番深入挖掘,发现在这300个人中,有100人居住在波士顿(和目标人物共享同一座城市)、有100人是股票经纪人(和目标任务共享同一个职业领域)、只有剩下100人是完全随机分配的。而在那100人中,只有18人成功完成任务。也就是说,用以支撑该理论的证据的样本容量仅仅是18个人。

    然而这并不表示这一定是个伪理论。几十年后,真正的突破降临了。一个名为“凯文·贝恩的六度空间”的大学游戏要求学生将任何演员和凯文·贝恩通过合作明星联系起来,步骤不超过6个。

    这个游戏所搜集的大量数据使得社会学研究人员得以分析好莱坞演员的连通性究竟如何,结果发现六度空间理论的确存在,但是是通过随机相识的熟人,而非好友。这才是关键所在。

    最后,就像Derek所指出的,由于网络将我们的生活紧密地联系在一起,这个“六度”空间理论事实上已经缩小了。

    展开全文
  • 六度空间算法理论简介】 有一个数学领域的猜想,名为Six Degrees of Separation,中文翻译包括以下几种: 六度分割理论或小世界理论等。 理论指出:你和任何一个陌生人之间所间隔的人不会超过六个,也就是...
    
    

    【六度空间算法理论简介】

    有一个数学领域的猜想,名为Six Degrees of Separation,中文翻译包括以下几种: 六度分割理论或小世界理论等。 理论指出:你和任何一个陌生人之间所间隔的人不会超过六个,也就是说,最多通过六个人你就能够认识任何一个陌生人。这就是六度分割理论,也叫小世界理论。


    【六度应用场景】

    六度分割通常用来描述一个广阔的社会网络(SN),现在大部分的社会网络服务都提供了搜索功能,即搜索出一个用户到达另外一个用户的最短路径,也就是找出这两个用户之间通过最少的用户的链接。

    一般的SN提供的搜索都是4度的,也就是例如A-B-C-D-E 称为4度的分隔。提供5度搜索和6度搜索的几乎寥寥无几,当然一方面是5,6度分隔的用户很少,大部分的用户都应该在4度内,另外一个方面是5,6度分隔的搜索在实际计算上也涉及非常大的运算量。


    【SN搜索算法】注:(已下所有都是不去除本身的)

    如果说寻找两个人之间的最小分隔的路径和寻找最短路径可以类比,那么唯一不同的是SN上每个节点的联系可以非常的广阔,不只是上下左右,而是十个甚至上百个联系。这是是一个多维空间内的最短路径的寻找。假设一个用户平均有n个好友,那么粗略估计一个用户的4度好友大约有n×n×n×n+n×n×n+n×n+n ~ n^4,无疑是一个非常恐怖的数目。因此采用传统的递归的方法显然是不大现实的。

    当然,事情并非这么麻烦,有简洁的方法可以加快找到用户之间的最小分隔:不单是从一个用户搜索,而是从两个用户同时搜索,而看两个用户的2度之内的用户是否有相同:
    A-B-C
    E-D-C
    A和E的处在在两度分隔的用户基本上数目估计都在n的平方。问题变成了比较n^2和n^2之间有没有相同,这个计算的时间等同于2×n^2的排序所需要的时间。


    【SN索引】

    那么能否继续加快速度?
    当然可以,可以提前对用户的好友进行索引,对好友的好友进行索引,这样在未来进行关系的搜索时会大大加快:

    A: {A1} {A2} A1为A的好友的集合,A2为A的好友的好友的集合
    E: {E1} {E2}

    那么
    1度分隔为: A 属于{E1},等同于E属于 {A1}
    2度分隔为: A 属于{E2},等同于E属于 {A2},{A1}{E1}有共同项。
    3度分隔为: {A1} {E2}有共同项,等同于A属于 {E2}
    4度分隔为: {A2} {E2}有共同项

    【SN关系的更新】

    当然,发现是一个核心问题,另外一个问题就是更新,因为SN的关系不会是一成不变的,在一个活跃的SN社区里,每天用户之间的关系的更新更是可观。这里只考虑关系添加的例子:

    A: {A1} {A2} 
    E: {E1} {E2}

    当A 与 E 直接建立了好友关系后,应该说整合系统的关系全都变化了,因为这个新的关系一定会导致一些关系的短路,从而导致很多现有的关系的调整。但是因为我们只存储2度分隔以内的关系,也只关心两度分隔以内的关系,因此当发生了一个新的关系后,2度内关系的变化一定是A和E本身或者他们的一度关系的用户,再远的用户将不受这个关系的影响。

    因此首先 所有{A1}的元素的二度分隔集合里要加上E,所有{E1}的元素的二度分隔集合里要加上A。

    然后是二度的修正。分别加上对方的1度。
    {A2} = {A2 + E1}
    {E2} = {E2 + A1}

    最后是一度的修正:A, E 的 一度{A1}{E1}需要加入E,A:
    {A1} = {A1 + E}
    {E1} = {E1 + A}

    整体操作的量大约在2n次操作,比我们通常认为的要小的多。

    展开全文
  • 六度空间

    2015-03-21 15:46:45
    六度空间理论,又名六度分隔理论,意思是你至多只要通过六个人就能认识全世界的任意一个人,可以这样算:假设一个人能认识25个人或以上,那经过7次介绍之后(间隔6人),一个人可以被介绍给25的7次方,等于6103515625...
  • 六度空间理论又称作“六度分隔(Six Degrees of Separation)”理论。这个理论可以通俗地阐述为:“你和任何一个陌生人之间所间隔的人不会超过六个,也就是说,最多通过五个人你就能够认识任何一个陌生人。”如...
  • 六度空间理论又称作“六度分隔(Six Degrees of Separation)”理论。这个理论可以通俗地阐述为:“你和任何一个陌生人之间所间隔的人不会超过六个,也就是说,最多通过五个人你就能够认识任何一个陌生人。”如...
  • PTA-六度空间-BFS

    2020-06-10 21:13:24
    六度空间理论又称作“六度分隔(Six Degrees of Separation)”理论。这个理论可以通俗地阐述为:“你和任何一个陌生人之间所间隔的人不会超过六个,也就是说,最多通过五个人你就能够认识任何一个陌生人。”如...
  • 7-7 六度空间(30 分)(图的遍历)

    千次阅读 2018-03-05 22:07:35
    六度空间理论又称作“六度分隔(Six Degrees of Separation)”理论。这个理论可以通俗地阐述为:“你和任何一个陌生人之间所间隔的人不会超过六个,也就是说,最多通过五个人你就能够认识任何一个陌生人。”如...
  • 尺度空间理论与图像金字塔

    千次阅读 2018-03-06 15:55:20
    我们之所以决定使用卷积后的特征是...1尺度空间理论每个物体,我们总可以用一些词语或部件来描述它,比如人脸的特征:两个眼睛、一个鼻子和一个嘴巴。对于图像而言,我们需要计算机去理解图像,描述图像就需要计算...
  • 章 电磁新理论

    千次阅读 2015-04-16 17:15:09
    章 电磁新理论   声明    本人自称:三空道士。可看作是社会底层的无业游民,也无不妥。虽修行于俗世,甘于过平淡艰苦的隐居生活,但从不放弃对宇宙真理的探索。因学艺不精、情关难过,在我的博客文章会充满...
  • 数据库系统概论——第章 关系数据理论 (零)引言 基于某个数据库管理系统设计数据库,如何基于数据库编程 第6章 关系数据理论 第7章 数据库设计 第8章 数据库编程 (一) 问题的提出 一、 关系数据库逻辑设计 (1...
  • 机器学习()统计学习理论

    千次阅读 2018-03-09 21:19:01
    统计学习理论的意义 统计学习理论提供了机器学习的一个理论基础。通过理论推导,从本质上说明了机器学习为什么会出现过拟合现象,以及过拟合与模型选择、训练数据之间有什么关系。 数学推导 设训练集S={(xi,yi)...
  • GIS基本理论系列是在《地理信息系统原理和应用》读书报告基础上完成的,当作自己对GIS理论的一次复习回顾。1. 空间信息处理的内容有哪些在图形数据录入完毕后,需要进行各种处理,空间信息处理包括以下内容:第一,...
  • MySQL | 数据库基础理论大设计范式详解

    千次阅读 多人点赞 2019-05-09 04:16:34
    从本篇博文开始,会陆续介绍MySQL数据库的相关内容,分为以下几个部分: 数据库基础理论 基本CURD操作(常用SQL) 索引及其底层实现原理 MySQL体系结构与存储引擎 MySQL优化之SQL和索引的优化、应用优化、MySQL ...
  • 数据可视化(全彩)(大数据丛书,首次全面细致地梳理了可视化理论,方法、工具与应用案例。马匡教授、石教英教授鼎力推荐,十二五国家重点图书出版规划项目) 陈为 沈则潜等 编著 ISBN 978-7-121-21154-6 ...
  • 上面例子中由于目标函数是二次凸函数,Taylor 展开等于原函数,所以能一次就求出最优解。 牛顿法主要存在的问题是: Hesse 矩阵不可逆时无法计算 矩阵的逆计算复杂为 n 的立方,当问题规模比较大时,计算量...
  • 维基百科上说“六度分割理论”(也叫”六度空间理论“或”小世界理论“)是19世纪60年代哈佛大学的心理学教授斯坦利·米尔格拉姆发现的。他做了一个连锁信实验,寄出60封信(有其他材料说是160封,或者300封。不过...
  • 测试理论面试题

    千次阅读 2019-11-06 09:13:26
    这个要充分准备,最好能举出例子(非常考察课外积累和工作经验!) 几种常见的测试方法:错误推断法、正交实验法、因果图法、场景分析法、判定表法,必须对这些测试方法都能说出一二,面试官很有可能根据你说的...
  • FFmpeg学习之 一 (音视频理论知识)

    千次阅读 2019-07-19 18:41:11
    FFmpeg学习之 一 (音视频理论知识)1. 音视频理论知识 1. 音视频理论知识
  • 章 内生安全与可靠性技术 网络空间最大的安全威胁是**基于目标对象内生安全问题的不确定攻击* 网络空间最大的防御难题是在缺乏先验知识条件下能否可靠应对基于未知的未知因素的不确定攻击 最大的...
  • Ramsey理论

    千次阅读 2006-10-20 08:24:00
    Ramsey理论在任意给定的6个人当中必定存在有一组3个人,这3个人要么相互认识,要么相互之间不认识。如果对有穷顶点集 的完全图的边进行红-兰染色,则一定存在一些有穷集 使得所有与 中的顶点相关联的边都具有相同的...
  • SVM理论

    万次阅读 2011-11-15 23:08:29
    二,这个形式并不局限于二维的情况,在n维空间中仍然可以使用这个表达式,只是式中的w成为了n维向量(在二维的这个例子中,w是二维向量,为了表示起来方便简洁,以下均不区别列向量和它的转置,聪明的读者一看便知)...
  • Hinton介绍胶囊理论的论文

    千次阅读 2017-10-29 21:41:21
    尽管作者们此次用矢量输出胶囊和按协议路由的最大池化替代CNN的标量输出特征检测器,他们仍然希望能够在整个空间中复制已习得的知识,所以文中构建的模型除了最后一层胶囊之外,其余的胶囊层都是卷积。与CNN一样,更...
  • OMNeT++理论算法仿真详述

    千次阅读 2019-04-26 09:14:17
    主要表现在军事、环境、医疗、家庭等商业领域,特别在空间探索和灾难拯救等特殊的领域有其得天独厚的技术优势。为评价传感器网络协议算法的性能,仅通过实验是无法实现的,特别是包含大量节点的大规模无线传感器网络...
  • 美国互联网理论是伪科学?

    千次阅读 热门讨论 2008-07-17 00:28:00
    作者:刘锋(本文章属作者原创作品,刘锋版权所有,转载引用请注明出处和作者刘锋) 从2004年,全球范围内开始对互联网进行理论总结和哲学思考,美国陆续出现了WEB2.0,长尾理论,维基经济学,免费经济学等新理论。...
  • 算法理论基础

    千次阅读 2019-03-14 13:32:37
    :利用已有样本生成更多样本,这类方法在小数据场景下有很多成功案例,比如医学图像分析等。  SMOTE为每个小众样本合成相同数量的新样本,这带来一些潜在的问题: 一方面是增加了类之间重叠的可能性,另一方面...
  • 通信的数学理论

    千次阅读 2012-07-19 18:31:40
    通信的数学理论  近年来像PCM和PPM这些交换信号噪音比带宽等的多种调制方法的发展已经增强了我们对一般通信理论的兴趣。这种理论的基础包括在重要的报纸 and 中关于此学科的内容。在当今的报纸中我们将延伸这种...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 25,725
精华内容 10,290
热门标签
关键字:

六度空间理论的例子