rxf6chen的个人博客分享 http://blog.sciencenet.cn/u/rxf6chen

博文

你的朋友圈能延伸多远,有办法推断预测吗?六度分离理论的反问题

已有 741 次阅读 2023-4-10 20:26 |系统分类:科研笔记

很多朋友都知道小世界理论或者六度分离理论,简单来讲,就是任何两个人可以通过少量的中间人建立关系。我们再回顾一下哈佛大学的社会学家斯坦利•米尔格拉姆(Stanley Milgram)的一个实验。他在内布拉斯卡州的奥马哈市随机挑选了大约 300 人,并给他们各自一封信,然后以这些人各自为起点,通过人传人转接的方式把手上的信交给一个波士顿的股票经纪人,在转接过程中,每个当前拿到信的人都把信交给一个他认识的、且他认为能更快将信送达给股票经纪人的人。实验结束,米尔格拉姆教授通过统计发现每个人大约只需要5个人中转就能将信送达。

其实这个实验除了表现出了小世界现象,还隐藏了一个更深刻的现象。是什么呢?可以想象,每个参加实验的人和股票经纪人之间有多条不同中转路径,有些包含的中间人多,有些包含的中间人少。而这个实验还表明,每个人仅通过局部信息(即他认识的人)做决策,居然把较短的路径给找出来了!!!很多研究人员研究了为什么会这样。作为对比,如果每个人有一个上帝视角知道全局信息,即谁和谁认识每个人都知道,那么很容易找到任何两人之间的最短路径。

我接下来要讲一个跟上面相反的两个问题

1、假设你在你的微信联系人里面选择一个朋友B,给他发一条消息;B将该消息转发给他自己的一个之前没接收到过该消息的朋友C;依次类推。请问:每个人如何仅用局部信息做决策使得该消息传给更多的人或者说传得更远,或者问每个人仅用局部信息做决策能将该消息传多远?

2、你有没有办法预测,从你这里开始,能把消息传多远,即以你为起点的最长路径有多长?

注意问题1、2并不完全相同,特别地,第2个问题并没有发生实际的传递过程。比如,从你开始,每个人都随机选择一个没有接收过消息的朋友作为下一棒,也许可以把消息传到第100个人小明,而小明的朋友圈所有人都接收过这个消息了,从而传递过程停止。此时,问题1的答案为至少为100;但是,你根本没办法预测出以你为起点的最长路径至少为100那么长,你能确定的预测可能还是长度为1或2。

微信朋友圈其实构成了一个网络结构,上面我提出的问题抽象出来就是:给一个网络,如何仅利用网络局部结构信息搜索出一条尽量长的传播路径(问题1)?如何仅利用局部结构信息预测以一个网络节点为起点的最长路径的长度(问题2)?

据我所了解,除了上面提到的(都比较容易想到的)随机选择方案,之前没有任何其它解决方案。显然研究这两个问题具有重要的理论意义,其应用(大规模商用)意义也许暂时不是很明确。相信迟早会有研究人员进行系统地研究。当然这两个问题应该没有办法一次性给出最优解决方案,只能靠众多研究人员进行大量、长期研究,逐步优化解决方案。

我最近对这两个问题做了一些研究,依赖于一些严格的新概念和理论结果,给出了一个解决方案,大量的计算机仿真评估性能也不错。

最后再讲一个场景。大家在影视剧里面经常看到,情报人员A问情报人员B:“C是不是我们的人?”,B一般回答“我不知道,我也是只跟我接头的人单线联系。”也就是说,对于情报网络,每个人只知道网络的局部信息,这样风险小。如果某种形势下,为了尽可能保存一份重要情报或物件,需要倒腾越多的人越好,怎么办?






https://blog.sciencenet.cn/blog-3428175-1383705.html

上一篇:比尔.盖茨的煎饼排序算法,基因组重组距离问题
收藏 IP: 36.57.146.*| 热度|

0

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2023-9-28 03:10

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部