首页 >> 计算机科学 >> 文章

首先考考您,是这么道题:说村里的一位王嫂从电视里看到了海地的地震孤儿,精心准备了一份小礼物想送给他,但是通过电视只了解到了孤儿的姓名和所在的地区,王嫂从来没出过门,也不认识出过国的朋友,这份礼物该如何送达呢?于是想到了找村长代转,虽然她知道村长跟那个孤儿也是八竿子打不着,但在她认识的所有人当中,村长是交际最广的一个。村长也很帮忙,找人代转,一级级直到完成任务。

凭您的想象力,您认为代转的中间人大约会有多少个呢?

美国哈佛大学社会心理学家斯坦利.米尔格拉姆(Stanley Milgram)在1967年做了一项社会调查,其结论是:地球上任意两个人之间的平均距离是6,也就是说,平均只要通过5个人,你就能与地球上任何一个角落的任何一个人发生联系,“六度分离”的说法由此确立。2003年8月,Science杂志报道了一项在互联网上进行的类似实验,研究方在13个国家里随机确定了18名目标对象,并征集了166个国家和地区的6万名志愿者,要求他们通过找熟人转发的方式把邮件发给这些目标对象,其中有384封邮件完成了任务,考察其送达过程,发现邮件平均转发了6次。所以,我们可以推断,王嫂大概只需要5个中间人帮忙就可以把礼物转给孤儿,如果运气好的话,3、4个就行了,这个数字是不是要比您想像的要小得多呢?

clip_image001

Kevin Bacon

为了验证“六度分离”推断的正确性,人们又做了很多实验,其中一个名为“Kevin Bacon游戏”的实验非常有趣,这个游戏的主角是美国电影演员Kevin Bacon,就是上图中那个不太帅的小伙子。游戏给每一个演员都赋予了一个Bacon数:如果某人跟Bacon共同演过电影,则他的Bacon数就是1,如果某人没跟Bacon共同演过电影,但跟Bacon数为1的演员共同演过,那他的Bacon数就是2,以此类推。实验涉及60万名世界各地演员和30万部电影,并得出了Bacon数统计表,如下图所示。通过这个表可以看出,绝大多数演员通过不超过4部影片就与Bacon发生了联系。当时设计这个实验的计算机专家Brett Tjaden称“Bacon是世界电影界的中心”,这当然是戏谑,其实换任何一个人当这个游戏的主角,例如王宝强,结果也差不多。Bacon数数据库支持在线查询,输入任何一个演员的英文名,就可以查到他的Bacon数,地址是:http://www.cs.virginia.edu/oracle/,你可以去输入自己心目中的偶像过把瘾。

clip_image002

Bacon数统计表

一群人或团体按某种关系连接在一起,将会构成不同的社会网络,例如人际关系网、电话网、交通网等。自上世纪60年代以来,这些网络都是按随机网络来进行研究的。下面图中的a图就是随机网络,b图是无标度网络,两者都包含130个节点和215条链路,红色节点是连接度最高的几个节点,绿色节点是红色节点的直接邻居,在随机网络里面,绿色节点占27%,无标度网络里面占60%。

clip_image003

以人际关系网为例,随机网络指每个节点与外界的联系是随机的,绿色节点没有刻意要先跟红节点连接,而无标度网络中,周边的绿色节点跟其它节点的联系很少,好像王嫂一样,但她谁都可以不认识,却不能不认识村长。村长则认识一些靠近关系中心的人,这些人在社会上神通广大,之间的联系更多更紧密。无论王嫂是想去城里看病还是打官司,人托人找关系,用不了3、4步总给找到能给她办成事的人,当然人家愿不愿意给她办就是另一回事了。

当前的各种社会网络已经越来越脱离了随机网络的形态,而向“小世界”模式迅速转变。大家在建立自己的社会关系时,都是以最快找到能帮我办事的人为原则。于是乎,社会关系广的人被结识的速度,就远远大于像王嫂这样的人。随着网络中人数的增加,这种人际关系权重的差别就越来越大,形成了极端不平衡状态。b图是无标度网络,无标度表明的是一种差距巨大的状况:一头大象和一只跳蚤比体重,用什么标度单位呢?若用毫克,大象的值就大得惊人,若用吨,跳蚤的值又小得可怜,它们的体重差异度太大,以致于用什么标度都不合适,干脆就不使用标度了。

无标度网络有两个核心特性,一是增长性,二是优先连接性。增长性是指网络在不断扩充,网络节点权重的巨大差别,是在网络规模不断扩充的情况下形成的,而不是静态的结构重组。优先连接是指新加入的节点,总是倾向于跟重要的节点相连接,从而使其愈加重要。

上面这段话好像有点晦涩,但其实讲的道理非常简单,还是以上面的村子为例,里头人际关系网的无标度性是如何形成的呢?首先要有外来户不断加进来,而不是为了突显差异性,去命令人们都跟王嫂绝交而去结识村长。外来户要想在村里立住脚,就要以最快速度结识村里更多的人,找交际广的人当然最方便,不二之选就是村长,长此以往,随着村子规模扩展,村长结识新人的数量与王嫂结识的人数相比,差距越来越悬殊。

不是你不明白,这世界变化快。不仅人际关系网,电话网、互联网、交通网等等也都越来越向无标度的小世界网络方向发展。特别是互联网,它的增长性和优先选择性特别突出,其结构就非常不平衡,以前有人说20%的人掌握着80%的财富,现在则是1%的博客吸引着99%的眼球。如果您想找到失去联系的前女友,我建议您在韩寒这位“超级村长”的博客蹲点,抢占沙发并把寻人启示贴上去,言辞一定要悲切得呕血——让人觉得不帮忙就跟看《孔子》不哭一样简直不是人——这招绝对比在电线杆子上刷一万张寻人广告有效得多。

clip_image004

北美航线图

由上面的北美航线图可以看出,纽约或休斯顿机场的航路比其它小机场多得多,根本不在同一个数量级,而且随着经济的发展,这种差别会越来越大。与传统领域相比,信息领域的无标度化更为惊人,下图是国际电话网的流量示意图,红线的流量是蓝线的1千万倍,而且越红的线越倾向于聚集在一起,聚集后形成了不断加速扩张的超级节点。

clip_image005

国际电话网的流量示意图

当下,各种社会网络正在变得越来越不平衡,越来越无标度化,这给我们带来前所未有的高效率,但同时也带来了前所未有的危险,由于对超级节点的过份依赖,使得因超级节点的崩溃而造成的损伤也越来越惊人,美国一个工厂事故导致了半个美国停电,中国一场大雪就引起了重大的灾难。

不过,现在已经有了一些成功的应对办法,举例来说,美国的电信网络管理中心一定是个聚集度越来越大的超级大节点,如果它失效了,星条国就会乱套。于是该国有关部门分别在东西海岸建了两个网管中心,各备全套的数据,都能独立支撑起全部业务。平时两个中心完成的任务量三七开,而且轮流唱主角,一旦某个中心崩溃,另一个能几乎实时地把全部业务接过来。这就是对超级节点的热备份方法。

无标度网络不怕随机攻击,因为影响全局的超级大节点的数量是极少的,例如上级随机关闭几个博客,几乎可以肯定,倒霉的一定会是那些基本无人问津的博客,因为这种博客一抓一把,访问过千万的博客则寥寥可数。但是上级往往更想收拾那些访问过千万的超级博客,比如找韩寒开涮,这种方式就是智能攻击了。无标度网络怕就怕智能攻击,几个超级大节点一被毁,网络可能就崩溃了,因此某市的黑社会网络,恐怕没十年是重组不起来了。

韩寒这位“超级村长”该如何保护自己博客的安全呢?备份当然是个好办法,而且备份方式的差异度越大越好,以应对不同的攻击手段和策略。例如在传统媒体而不是网络上备份,一旦网络全面崩溃,再多的镜像也化为乌有,但我的杂志还在。但是,这招对文化市场整顿无效,韩寒可以把备份放在美国和俄罗斯,毕竟,中美俄三国联合发文对文化市场进行整顿,在可以遇见的未来不可能发生。

科学编辑:fwjmath

文字编辑:小庄

0
为您推荐

37 Responses to “小世界与超级村长”

  1. 猛犸说道:

    沙个发先,哈哈

  2. 打破的管道说道:

    想起微软亚洲研究院弄的一个“人立方”,用来展现人际关系网,还是蛮好玩的
    给个链接: http://renlifang.msra.cn/GuanxiMap.aspx

  3. mt可爱多说道:

    板个凳再

  4. 说道:

    想到某市的黑社会网络,我就想笑。

  5. 小C说道:

    张家有财一千万,邻居九个穷光蛋,平均起来算一算,各个都是张百万。。。所谓平均基本就是这么个意思么。
    另外有没有人从数学的角度算一算,有鉴于大量关系亲密的人之间的距离全都是一,那么要在人群里平均到六,那关系远的群体里面关系要远到什么程度啊?

  6. c2blog说道:

    首先,祝贺剃刀兄。
    其次,需要补充下:

    1)“换任何一个人当这个游戏的主角,例如王宝强,结果也差不多”
    这个说法有点模糊了学理。实际上,位于电影圈的中心或边缘,还是很有讲究的。

    “对于演员网络,这种节点(网络的真正中心)就是那些饰演过多种类型影片的演员。”
    ——《链接:网络新科学》 第5章 中心节点和连接者 P73
    也就是说,一个演员要成为演员网络的中心,不仅要拍戏的数量多,
    而且要戏路广,最好是很多不同类型的影片都拍过。
    这就可以解释演员们为什么有动机尝试不同的角色,并视之为自身演艺事业的真正突破。

    2)“自上世纪60年代以来,这些网络都是按随机网络来进行研究的。”这一句是没有问题的。
    但是,“当前的各种社会网络已经越来越脱离了随机网络的形态,而向“小世界”模式迅速转变。”
    这一句就不对了。实际上是研究范式的进步和转变,而不是社会网络本身真有大的转变。
    就是说,主要不是社会网络改变了,而是科学家对社会网络的认识改变了。

    3)韩寒这位“超级村长”
    所说的“超级村长”的定义是什么,如果是指认识的人超级多,那么韩寒其实不是“超级村长”。
    因为,事实上的情况只能是,在中国认识韩寒的人超级多,但韩寒肯定不认识其中的绝大部分人。

    如果是指不但认识人多,而且认识一些靠近关系中心的人,那么韩寒的确可以算是“超级村长”。
    因为他跨几个行业,且多接近网络中心:赛车、小说家、网络作家、杂志主编,还涉足音乐创作。

  7. 窗敲雨说道:

    给剃刀兄撒个花先~~~

  8. liutianren说道:

    引:“由于对超级节点的过份依赖,使得因超级节点的崩溃而造成的损伤也越来越惊人,美国一个工厂事故导致了半个美国停电,中国一场大雪就引起了重大的灾难。”

    这两个例子似乎不太合适,电网本事并不是无标度网络。
    美国当时电网崩溃是因为输电能力不足,操作人员低能,具体在《科学美国人》某期上有。
    而中国的雪灾。??这和无标度网络有什么关系??中国南方是无标度网络?或有标度的网络就不怕雪灾??

    文章我很喜欢,顶一下。
    不是针对文章,仅对这俩例子的使用有异议。

  9. wanda说道:

    这篇文内容很有趣,语言也简洁、生动,好文

  10. williamjen说道:

    毕竟,中美俄三国联合发文对文化市场进行整顿,在可以遇见的未来不可能发生。

  11. 奥卡姆剃刀说道:

    c2blog网友:首先感谢你的祝贺。我尝试着回答一下你的三个疑问:

    1、举个例子,Alice一辈子只演了一部电影,在Bacon某个影片中演了一具尸体。重新定义一下Alice数,同样在60万演员和30万部电影中进行统计,你会发现,Alice数统计表跟Bacon数几乎完全一样,只是右栏整体下降了一格。王宝强的演员关系网肯定要比Alice强,他一定介于Bacon和Alice之间,王宝强数统计表跟Bacon表差不多。

    2、网络结构的确变了,并不只是研究方法变了。其原因在于科技发展,支持了超级节点的产生及它们之间的密集连接。

    3、韩寒可能没见过他的某个具体粉丝,但要找到他,只需一步即可。

    • c2blog说道:

      1)谢谢作者来说明了:文章中所说的“差不多”,原来是指那个统计表差不多。

      的确,那个数值仅仅是差之毫厘,还不到 1。
      但是,如果具体到该演员在演员关系网的现实中的社会地位,那就谬以千里啰。
      所以,文中说法能表现演员关系的紧密,但模糊了真正中心与戏谑中心的差别。

      2)你所说的“网络结构的确变了”的情况,我并非不知道。
      实际上,我在松鼠学堂你文章后面的40#贴,就已引用关于其成因的一种解释。
      关于网络结构与研究方法,我和你一样,都同意两者是有在改变的。
      不过,你强调的是前者,而我强调的是后者。

      我以为,“各种社会网络”,例如演员关系网、科学家合作网、人类性关系网。
      它们从来就是无尺度网络,现代科技的进步只不过是使这种效应更为加剧而已。
      从网络结构来讲,因为它们本来就不是“随机网络”,所以就不存在从“随机网络的形态”开始的“偏离”。

      只有从研究方法改变的角度来看,才说得上是“越来越脱离了随机网络的形态”。
      所以我说,“科学家对社会网络的认识改变”是主要的。

      当然,我所知也很有限。如果你有证据证明并不吝列举出,
      人类一些原有的“各种社会结构”的确是随机网络,又或者是比无尺度网络更相近于随机网络。
      那么,我可以承认,你文章中那句不仅是对的,而且你还真正解答了我的疑问。

      3)“韩寒可能没见过他的某个具体粉丝,但要找到他,只需一步即可。”
      你的意思,是对“超级村长“比喻的定义,只在于”被超级多的人所认识”?不会吧?
      我相信你对“超级村长”的本意是,不但认识人多而且认识一些靠近关系中心的人。

      “没见过”这一条,本身就已经违反了米尔格拉姆的研究定下的规则:
      “3.只有当你亲自见过目标人物,而且知道对方姓名时才可以这样做。”
      ——《链接:网络新科学》 第3章 六度分隔 P33

      “要找到他,只需一步即可”——没有媒体和互联网的情况下,这是不可能做到的。
      即使是在有媒体和互联网的情况下,也不一定能“一步即可”。
      我举例子吧:住在深山里的韩寒小说的读者粉丝,在电视上看过韩寒赛车的观众粉丝,
      韩寒就不可能知道这一些粉丝的具体地址,更不可能一步就联系到ta们。

      只有在互联网等其他关系网的帮助下,韩寒才有可能一步就联系到特定某位粉丝。
      但是,你把几个不同的网都运用上了,实际上已经超出“村长”它本来的寓意了。
      “村长”的比喻,本来是从人际关系网引出来的。现已经超出社交网络的范畴了。

      • 奥卡姆剃刀说道:

        你的回帖很有道理,我基本都同意,可以看出你对这个问题确有研究。有两点需要解释:人际网等的确从来就不是随机网络,但以前未必呈现出幂律分布,过早地称之为无标度网络似有不妥。

        科学家在以前研究时,使用的是随机网络理论,近年来才开始使用无标度理论,这点你说的对。

        至于韩寒的博客,它是围博中的一个重要节点,围博的“围”字,指的是重要节点之间的紧密联系。

        我理解你的意见,我基本都同意,分歧只在表述上,这种比较复杂的理论,很难用通俗的语言完全表述得没有歧义啊.....

  12. 奥卡姆剃刀说道:

    liutianren:电网本身不是无标度网络,能指出这一点说明你对此颇有了解。我在文中特意规避了“电网”这个词,就是想避开这种联想,结果还是被你指出来了,呵呵。

    我在文中指的是社会组织结构,其中“电能”就是个巨型节点,它失效了则整个社会就基本停摆了。而在过去,社会组织结构不像现在这样无标度时,某个节点的失效引起的社会动荡,根本不会像现在这样剧烈。

    中国雪灾也指的是社会组织结构的无标度化。

  13. 雨雨说道:

    在中国估计传到第三人就掉了..

  14. 拟南芥说道:

    哈哈,剃刀兄第一篇,
    留个印子~

  15. win说道:

    好文,期待系列文章。

  16. hubert说道:

    平均距离是6?那些没有传送到的邮件应该算多少,无穷大?毕竟6万个邮件仅仅有384个抵达目的地。应该把那些虽然失败,但是传送了至少6次的邮件计算进来。

    • 奥卡姆剃刀说道:

      失败的转发过程不重要,我们关注的是成功的转发过程,即回溯成功的转发过程,看平均中转了几次。有384个样本,已经可以说明问题了。

  17. 闪雷高德说道:

    很好,周杰伦这家伙因为一个青蜂侠就2了。

  18. Shadow说道:

    让我找到个反例,哈哈:

    silvia saint has a Kevin Bacon number of infinity.
    silvia saint cannot be linked to Kevin Bacon using only feature films. Do you want to include documentaries or TV shows?

    Did you mean a different silvia saint?

    About 12% of all actors cannot be linked to the rest of the movie universe, either because they have appeared only in video games or straight-to-video releases that the Oracle doesn't count, or because they have not appeared in any films with actors from the Hollywood mainstream.

  19. Ent说道:

    为啥我想起了Erdos数……

  20. 老寻说道:

    写得比方舟子好多了

  21. 老寻说道:

    需要审核!??

  22. p0mz1说道:

    (60*10^8)^(1/6)=42.62769748
    log200(60*10^8)=4.249467095
    但是这个也有点理想化,每个人的社交在计算时都是没有交集的

  23. hhwm说道:

    林青霞的bacon数是3,就是时间跨度大了点 嘿嘿

  24. nobody说道:

    既然如此,怎么网络上还有那么多找人广告这么久还没找到人的呢?

  25. 已经非常浅显易懂了
    很棒啊:)支持

  26. 宛若初夏说道:

    很有意思,开眼界了

  27. yuni说道:

    文章很好,不过其中也有一些值得商榷的地方,希望一起讨论。

    1. ”小世界“特征是说一幅图,在特征路径长度上,比“规则图”短,比“随机图”长;在聚集系数上,比“规则图”小,比“随机图”大。也就是说”小世界“网络是介于“随机图”和“规则图”之间的。从你文中“找熟人”的角度看,即特征路径长度,“小”世界比随机图要“大”。

    2. "无标度"网络应该翻译成“无尺度”,指网络节点度(节点的直接邻居数)分布服从幂律。因为幂律分布的方差,即描述分布尺度的统计量,在节点数无穷时为无穷大,所以说分布没有有限尺度,并非“大象”和“蚂蚁”不能比。

    3. “绿节点”如何相连并不是用"无标度"和“小世界”来描述的,而应该用“相配性”,即节点度不同的节点间如何相连:是高度节点之间更倾向于相连,还是高度节点更倾向于与低度节点相连。

  28. 递牛奶说道:

    非常受教育。谢谢分享!

  29. crazy_piggy说道:

    谢谢剃刀老师,这对我的论文有益,哇哈哈

  30. 金坷拉说道:

    超级村长....................

  31. ZHX说道:

    很幽默,很深刻。
    受益了。

  32. 林帆说道:

    作者系一个有智慧嘀银

  33. William H.Wei说道:

    解释的很明白,其中的顺便吐槽也很犀利,哈哈。。。

Leave a Reply for William H.Wei