答疑：关于小世界网络

“小世界”（small world）现象是指两位偶然邂逅的陌生人在攀谈之后意外发现有共同的熟人，因而发出这样的感叹“天呐！这世界真小！”，这是我们在日常生活中有时会遇到的现象。已知最早以书面方式表述这个现象的人是匈牙利作者考林西，他在1929年的一篇短篇小说《连环链》里写道：“我们从15亿地球居民（1929年全球人口大约只有15亿）中任选一人——随便什么地方的随便什么人都行。他和我们打赌，通过不超过五个人，其中一人是他的熟人，只要利用他熟人的人际网络，他就可以联系到这个被选中的人。” 从1929年以来，小说中的“小世界”猜想启发了很多自然科学家（物理学家和数学家）和社会科学家的思考：这个猜想能够被验证吗？我们人类社会具有什么样的结构性质？“小世界”现象是不是由人类社会的特殊结构决定的必然结果？对这个猜想的证明有很多科学家参与，并且取得了几个里程碑式的研究成果，但是“小世界”猜想的证明和“小世界网络”的提出，直到1998年才由康奈尔大学应用数学系博士生邓肯.瓦兹（Duncan Watts）完成。

瓦兹的证明思路很简单，他用两个基本概念来刻画“小世界网络”，即平均聚集系数（clustering coefficient）和平均路径距离。聚集系数是网络结构化程度的表征，人类社会的网络是一个结构化程度很高的网络，其平均聚集系数必然远大于随机网络，因此小世界网络必须同时满足平均聚集系数很大而且平均路径距离很小的条件。证明“小世界猜想”意味着要证明人类社会确实同时具备这两个条件，并且这样的网络能够以简单的方式产生（因为只有这样才可能在自然界里出现）。

Watts证明所使用的聚集系数和平均距离，可简要解释如下：我们把网络描述为节点和边构成的图：G=(V, E), V表示N个节点(Node)构成的的集合，E表示边(Edge)的集合。如下图所示。

假设网络中有一个节点, 周边与其链接的有个节点，那么节点的局部聚集系数（clustering coefficient）定义为以下式子：

那么我们可以求出整个网络的平均聚集系数

我们用表示节点与节点之间的距离，那么整个网络任意两个节点之间的平均路径距离为

小世界网络的特征是平均聚集系数很高，同时又是平均路径距离很小。

关于阅读材料《六度分隔》里的图，HW葳同学有以下疑问，现以直接标注的方式解答如下：

这张图源自小世界网络的提出者D. Watts与他导师S. Strogatz合作在《自然》期刊上发表的论文。其原图如下：

C(p)表示随机概率为p的条件下网络的平均聚集系数，C(0)表示随机概率为0的条件下网络的平均聚集系数，C(p)/C(0)约等于1，表示网络的平局聚集系数接近于随机概率为0时网络的平均聚集系数。L(p)/L(0)的意义以此类推。原始文献：Watts, D., & Strogatz, S. (1998). Collective Dynamics of Small-World Networks. Nature, 393, 440-442.  答FWJ同学提问：C(P)/C(0)和L(P)/L(0)确实是相关的，但是C(P)/C(0)随着P增加而递减的速度较慢。

     让人们感叹“天呐！这世界真小！”所要求网络平均路径距离应该多小呢？应该相当于随机网络的平均路径距离。对于人口即将达到100个亿的人类社会而言，随机网络的平均路径距离大约等于5，即100的五次方。实际测量人类社会的平均路径距离也在这个范围之内。

       理解小世界网络和人类社会网络结构本身所固有的小世界特性对于理解社交媒体条件下的传播现象非常重要，人类社会复杂网络当中的任意两个人通过熟人建立起来的联系链条是很短的，足够使信息很容易被扩散到网络的每个角落。