2010年2月28日

小世界与超级村长

我当年本科对小世界网络很有点儿兴趣,研究过这个模型在软件中的应用,呵呵,今天在松鼠会上看到这篇科普文章,写得很有点儿意思。

——————

Source:http://songshuhui.net/archives/33960.html

小世界与超级村长

| Tags 标签:六度分离, 原创, 小世界, 无标度网络 奥卡姆剃刀 发表于 2010-02-28 10:08

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

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

美国哈佛大学社会心理学家斯坦利.米尔格拉姆(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

文字编辑:小庄

没有评论: