Video在线视频

各位同学 大家好

欢迎来到网络 群体与市场的

在线课堂

我是这门课的主讲老师——石兵

来自武汉理工大学

在这一讲我们将会介绍一个

非常有趣的社会现象

叫做小世界现象

我们又把它称作 六度分隔

这样一个现象其实是Stanley

在1967年发现的

他做了一个实验

他选了几百名 初始者

他要求这些人努力的通过转发让

一封信发到一个指定的人手上

每一个初始者只提供了

收信人的姓名 地址 职业

但是有这样一个规定

你不能直接把信寄到那个人手里

你只能把这个信件发给你能够

直呼其名的熟人

也就是说你认识那个人才能

把信转给他 让他继续转发

并且我们要求参与者要尽快

将这个信能够达到目的地

最终有个有趣的结果

三分之一的信件经过平均六次

（转发）达到了目的

这也就是为什么称作

六度分隔的原理

这样一个实验表达了

什么意思呢

不认识的两个人可能平均经过

六个人就能产生联系

这样一个实验结果其实给

我们带来两个惊奇之处

第一个就是在一个社会网络中

两个节点间包含了非常丰富的

短路径

因为只有这些短路径的存在

你们才能尽快的建立起联系；

另外一个是什么呢

这样一个短路径可以被发现

也就是说我们通过

有意识的转发 可以

自动的 来找到这些短路径

我们现在就有这样一些问题

第一个是什么呢

为什么社会网络具有

这样一个性质

他们源于社会网络里面的哪些

基本的原理 换句话说

我们能不能依据社会网络的

某些基本原理来说明这种现象

的必然性呢

我们回忆一下形成一个社会网络

有哪些基本的原因

首先基本原因就是 同质性

还有就是 三元闭包

这就对应了社会网络中会存在

大量的 三角形

也就是说你和你的邻居那些

节点会有联系；

还有一种是什么呢 弱联系

弱联系 意思是什么呢

是指在你的日常生活中除了

跟你周围的人是朋友关系之外

你可能因为一些偶然的原因

比如说出差到了外地

你可能会认识一些在远方的朋友

这个就是 弱联系

但是你虽然认识这个远方的朋友

但是你对他所在的圈子

不一定熟悉

我们现在考虑两种形成

社会网络的基本力量

我们就要来分析我们构造一个

什么样的形式化的网络可以

体现这两种力量的作用呢

我们如果能够构造出这样一个

网络来体现出这两种力量

我们就可以分析在这样一个

网络里面是否有小世界现象

Watts在1998年就构造了

这样一个网络来体现了

这两种力量

在这样一个网络里面他们构造了

许多的 三角形

这个 三角形 就体现了

三元闭包 以及 同质性

还有少数的随机的 远程边

这就体现了 弱联系

它怎么构造的呢

它想像大量的节点构成一个

均匀的网格状

在这样一个均匀网格状的图

里面邻居间都是有联系的

比如说有很多 三角形

然后这里面的节点还可能有一定

的概率跟远方的节点产生联系

也就是说我们可以看到

它就构造了这样一个图

这个图体现了两种力量

一个是 三元闭包 和 同质性

还有一个就是 弱关系

现在对这样一个模型来进行分析

他们发现确实在这样的网络中

任何两个节点之间存在短路径

的概率非常高

也就是说两点之间我们很容易

找到一个大约六步左右的路径

可以产生联系

但是很可惜他们也发现了这样

一个模型不能很好地体现

第二个要求

第二个要求是

我们不但要证明短路径存在

还要能证明这个短路径

我们能够发现

但是这个模型不能很好的体现

这个要求

也就是说虽然这样一个

短路径存在

但是会发现搜索空间太大了

所以难以找到这样一个短路径

也就是说这个模型可能有一定的

不合理之处 需要改进

我们回顾一下这个寄信的过程

其实每个人被告知

如果你不认识目标人

就不能直接寄给他

你会转发使得离目标更近一点

当你转发的时候

你有意识的会希望这个信

要尽快的送到

但是当我们不认识这个目标人

的时候

我们会 估计 他的某个朋友

可能会 更接近于 认识他

我们会有这样一个估计

但是实际上在刚才这个模型里面

我们就没有考虑到这一点

也就是说我们要反映任何节点

之间短路径的存在

还要反映这种转发方式通过

短路径达到目的地的可能性

也就是说要能够证明这样一个

短路径能够被找到

由于刚才那个模型

不能体现第二个要求

我们就需要改良这个模型

Jon在2000年的时候

提出一个改良的模型

他的思路是什么呢

他会考虑为什么说

Watts的模型不凑效

不凑效的原因就在于

这样一个 弱关系 的边

太过于随机了

我们回忆一下刚才这样一个图

那里面任何节点跟远方的节点

产生联系的可能性是随机的

但是在现实中人们其实会

有意识的向比较接近目标的

朋友转发信件

也就是说刚开始的

模型没有体现这一点

所以我们现在要对这样

一个模型做一个改进

改进的时候

随机边的形成要体现

离得越近 机会越多

我们现在看他是怎么改进

这个模型呢

改进的目的主要是要支持

有意识的向目标转发

首先节点依然是在这上面排布的

然后 同质性 局部的连接

这些相邻的节点

对随机远程的边我们以

这样一个方式来进行控制

我们让两个节点之间存在

连接的概率与它们的网格距离

的 幂次 成反比

这就体现了 离得越远概率越小

离得越近两点之间有关系的

可能性就越高

具体来说

我们用d(v,w)记作

v到w的距离

也就是说网格步数

这个时候v到w产生一条

随机边的概率是多少呢

是跟d(v,w)-q成正比关系

我们从理论上可以证明

对于一个适当的q的值

在这样一个网络里面

我们这个分散搜索有很高的效率

也就是说平均步数可能是6左右

我们就可以找到这样一个短路径

那么这个 适当的q 是多少呢

我们看一下就不同的q值

对这样一个随机连接长度

其实是有重要的影响的

我们看q值比较小的时候

这个随机边倾向于较远的的节点

而如果q值较大的时候

随机边就会倾向于较近的节点

之前那个最早的Watts模型

对应于q=0的情况

也就是说完全随机

这个q的取值我们要注意一下

太近了不好

因为太近的话就相当于是只考虑

同质性 和 三元闭包

没有考虑弱关系了

太远了也不好

因为太远了就没有体现出

这样一个离得越近产生

可能性的概率就越大

其实我们通过仿真实验可以发现

在q介于1.5到2.0的时候

搜索效果最佳

并且随着网络规模的扩大

这个值会越来越接近于2

也就是说其实有这样一个

理论结果 当q=2时

这样一个分散搜索达到了

一个最佳效果

而这边我们只是从仿真的角度

证明了这一点

那我们能不能从理论的角度

对这个q=2加以说明呢

我们看一下

为什么q=2的时候

模型的效果最佳

我们考虑一下节点v随机落到

距离在d到2d环内

区域的概率

也就是说这个节点v产生

一个随机边随机落到d到

2d这个环里面的概率

显然首先环里面的节点数跟

d2是成正比的

因为它是均匀分布的

节点数是跟面积成正比例的

而q=2意味着随机连接到

其中一个节点的概率

与d2成反比

也就是说与d-2成正比例

因此我们可以说从v发出的

随机连接到该区域的概率

跟d无关

这就说明无论一个转发的节点

跟目标节点相距多远

他都可能找到一个离目标距离

近一半的朋友

还可以说明当这个信件

离目标越近

则它与目标有边的

可能性的概率就越大

我们刚才就介绍了

小世界 现象

小世界 现象又称作

六度分隔 原理

我们可以看一下

首先在1967年的时候

这个现象被发现

他们发现了 六度分隔

还发现了这样一个路径能够找到

在1998年

Watts采用一个理论上的

网络模型对这样一个现象

进行分析

但是他只能对第一个 六度分隔

做一个解释

也就是说这个短路径是存在的

这个改进的模型对第二个

也就是可以找到这个短路径

来做了分析

在教材的内容中还有很多

使用大规模的在线社交网络数据

来对这样一个模型做了一些验证

大家感兴趣可以去查阅一下

其实这也体现了我们

做研究的一个思路

首先我们有实验现象

根据这些实验现象我们尝试着

提出一些模型 数学框架

对它进行解释

在这个解释的基础上我们进一步

希望用一些实际的大规模的数据

来对它做进一步的测量验证

以上就是本讲的内容 谢谢