小世界与超级村长

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

——————

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个就行了，这个数字是不是要比您想像的要小得多呢？

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/，你可以去输入自己心目中的偶像过把瘾。

Bacon数统计表

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

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

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

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

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

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

北美航线图

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

国际电话网的流量示意图

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

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

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

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

科学编辑：fwjmath

文字编辑：小庄