“六度分离”和 洪泛(Search flooding)搜索

“六度分离”是社会学家在研究社交网络(social networks)时提出的一个概念。该问题源于社会学家 Stanley Milgram 上世纪60年代作的实验:“追踪美国社交网络中的最短路径”。他要求每个参与者设法寄信给一个住在波士顿附近的“目标人物”,规定每个参与者只能转发给一个他们认识的人。Milgram发现完整的链平均长度为6个人。

“六度分离”理论是已经得到证实的,通过微软的一个实验: “六度分离”理论获证实

可是关键的问题在于:该如何找到这样一条路径?

按照该理论,我们和很多“八杆子打不着”的人只要通过六个人就可以扯上关系,也就是“六杆子就打着了”,比如胡哥,比如迈克尔.杰克逊。但是关键的问题在于,我们根本不知道这六个人的路径是什么。

可选的办法是:我们询问我们认识的每一个人,向他们发出指令,

1.假如你认识迈克尔,就告诉我

2.假如不认识,将这个问题询问你认识的每个人。

这个方式假如能够执行,我们最后可以和迈克尔扯上关系,但是全球几十亿人,这个查询的可能路径几乎是无穷的,查询的成本将是可怕的。

在P2P系统里,早期的 Gnutella 采用的就是多少类似于上述的查找方式,假如网络一大,找到东西就只能撞大运了。

image

其实我们不必追求一定要6次找到迈克尔,只要我们在可以接受的有限次数内找到他就可以了。现实生活中,我们不一定会问每一个人,而是问我们所知的"交游广泛,消息灵通"的人士,最好这个人还在娱乐圈,并且和一些美国要人有来往,假如他愿意帮你,他又会询问他认为最有可能和迈克尔有关的人士。这就是p2p中 Super Node 的概念。


下面是我的其他博客:
博客园,写一些工作和学习的笔记: http://www.cnblogs.com/peon
/

博客堂,开发方面的一些文章:http://blog.joycode.com/peon/
流媒体博客,流媒体方面的一些文章:http://blog.lmtw.com/b/peon/
原文地址:https://www.cnblogs.com/peon/p/1552460.html