1 六度分隔理论
先来看两个有趣的例子。我们建立一个好莱坞演员的网络，如果两个演员在电影中合作或就将他们链接起来。我们定义一个演员的贝肯数（bacon number）是他们与演员凯文·贝肯有多少步的距离，贝肯数越高，演员离凯文·贝肯越远。研究发现，直到2007年12月，最高（有限）的贝肯数仅为\(8\)，且大约只有12%的演员没有路径链接到凯文·贝肯。
此外，在学术合作中，埃尔德什数(Erdős number)被用来描述数学论文中一个作者与Pual Erdős的“合作距离”(Pual Erdős就是我们在博客《图数据挖掘：Erdos-Renyi随机图的生成方式及其特性》中提到的那位巨佬)。菲尔茨奖获得者的艾数中位数最低时为3，CS224W讲师Jure Leskovec（也是一位图数据挖掘大佬）的Erdős数为3.
看完这两个例子我们不禁会思考，两个人之间的典型最短路径长度是多少呢？事实上，哈佛大学心理学教授斯坦利·米尔格拉（Stanley Milgram）早在1967年就做过一次连锁实验，他将一些信件交给自愿的参加者，要求他们通过自己的熟人将信传到信封上指明的收信人手里。他发现，296封信件中有64封最终送到了目标人物手中。而在成功传递的信件中，平均只需要5次转发，就能够到达目标。也就是说，在社会网络中，任意两个人之间的“距离”是6。这就是所谓的六度分隔理论，也称小世界现象。尽管他的实验有不少缺陷，但这个现象引起了学界的注意。
2 小世界网络模型
六度分隔理论令人吃惊的地方其实还不在于其任意两个人之间的路径可以如此之短，而是在保证路径如此之短的情况下还保证了高的聚集性。
短路径从直觉上可以理解，因为每个人认识了超过\(100\)个能直呼其名的朋友，而你的每个朋友除你之外也至少有\(100\)个朋友，原则上只有两步之遥你就可以接近超过\(100\times 100=10000\)个人。然而问题在于，社会网络呈三角形态，即三个人相互认识，也就是说你的\(100\)个朋友中，许多人也都相互认识。因此，当考虑沿着朋友关系构成的边到达的节点时，很多情况是从一个朋友到另一个朋友，而不是到其它节点。前面的数字\(10000\)是假设你的\(100\)个朋友连接到\(100\)个新朋友，如果不是这样则经过两步你能达到的朋友数将大大减小。
由此看来，小世界现象从局部角度看社会网络的个体被高度聚集，却还能保证任意两个人之间的路径如此之短，确实令人吃惊。
2.1 权衡聚类系数和图的直径
正如我们前面所说，聚类系数与图任意两点间的最短路径（可以通过图的直径来体现）有着矛盾的关系。比如在下面所示的这个网络虽然直径小，但聚类系数低：
而下图这个具有“局部”结构的网络聚类系数虽高（即满足三元闭包，我朋友的朋友也是我朋友），但其网络直径大：
我们是否可以同时拥有高的聚类系数与小的直径呢？直觉上，我们发现聚集性体现着边的局部性（locality），而随机产生的边会产生一些捷径（shortcuts），如下图所示：
这样，我们在保持边聚集性的条件下，随机地添加一些边，那么就能够完成要求了。根据这个思想，人们提出了许多小世界模型，我们接下来介绍Watts-Strogatz模型。
2.2 Watts-Strogatz模型
Watts-Strogatz提出的小世界模型包含两个部分：
(1) 低维的正则网格(lattice)
首先需要一个低维的正则网格模型来满足高的聚类系数。在下面的例子中我们使用一维的环状网络(ring)作为网格。
(2) 重新排布边(rewire)
接着在网格的基础上添加/移除随机边来创造捷径，以连接网格的远程部分。每条边有概率为\(p\)被随机地重新排布（将其一端点连接到一个随机节点）。
如下就是一个小世界网络的例子：
边的重新排布允许我们在正则网格和随机图之间形成一种“插值”：
如下图所示，我们直观地发现如果想破坏聚类结构需要大量的随机性注入（即边随机重排的概率大），然而只需要少量的随机性注入就可以产生捷径。
接下来我们来根据一个实例分析其聚类系数和直径。我们基础网格模型选用方格，每个节点有一个随机产生的长距离边(long-range edge)，如下图所示：
对于正中央的那个节点，我们有其聚类系数