此猫简介：姓名滴滴（新浪微博@滴滴deedee），性别男，国籍美国。性格温顺，死宅，喜欢陪主人上班和学数据，主人是大数据文摘非专栏主编Aileen，据主人介绍，滴滴很愿意为大数据文摘“小白学数据”系列代言
你是否有过这样的经历——在火车上或者飞机上，遇到一个陌生人，因为排遣旅途中的无聊时光，你们聊了起来，后来越聊越嗨，最后你们发现竟然会有共同的朋友。
原来周围的人际圈子真小，你会不由得感慨一句，我们真的是生活在“小世界”—地球村里啊。在我们时时感叹世界很小的时候，早有科学家们已经通过理论和实践证明，这就是所谓的小世界网络。额，这个世界就是这样，在我们睡醒之后，突然发现世界变了。
Anyway，让我们也来站在巨人的肩膀上，窥探一下小世界网络中的大世界。
那么问题来了——
从很大的人口中任意挑出两个人，这两个人彼此认识的概率有多大？
任意挑出的两个人当中要达到彼此认识的最短链接（中间相隔人数）是多长？
（上图为时代周刊刊出的萨达姆人物关系网络，把每个人看成节点，有联系的两个人即有一条连边，可以绘制这样的关系网络）
小白：首先，请解释下什么叫小世界网络吧~
答：依循小白的惯用做法，咱们顾名思义一下，小世界网络，就是指网络很小，小到，你想和世界上任何另外一个陌生人建立关系，只需要6个左右的中间人。
小白：厉害！这是怎么发现的？
答：小世界网络的历史，可以追溯到1929年。
◆ ◆ ◆小世界网络历史
1929 年，当时，有一个著名的匈牙利著名作家考林蒂（F.Karinthy），他在其短篇小说《链条》中给出了著名的“六度分隔”假说。小说中的一个人可以通过其认识的网球冠军、网球冠军的球友瑞典国王、瑞典国王又是诺贝尔奖的颁奖者这一路径，以简单明了的方式就与一个诺贝尔奖的获得者连接上了。考林蒂甚至将自己与远在美国的福特汽车公司的一个工人，仅仅通过三个中间人就联系了起来。考林蒂的关于人与人之间最多需要 5 层关系就能联系起来的推断，可以说是六度分隔假说的最早表述，也是“小世界网络”概念的雏形。
1967 年，美国哈佛大学社会心理学教授米尔格拉姆 (S. Milgram) 明确提出了“小世界问题”。他通过设计一个信件传递实验，以验证“六度分隔”假说，并使其成为“小世界问题”研究的基本概念。
米尔格拉姆以美国堪萨斯州的威奇托市（Wichita）和内布拉斯加州的奥马哈（Omaha）作为实验起点，在两地随机地选择了 296 位志愿者，要求每位志愿者向指定的目标人——一位居住在马萨诸塞州首府波士顿郊区的股票经纪人传递一封信件。实验结果是其中的64位志愿者平均通过约5.3个中间人转手后，成功地将信件送达到目标人手中。这与38年前匈牙利作家考林蒂的“5个相互认识的人”的假设惊人地吻合。米尔格拉姆由此得出结论：任意两个人都可通过平均 6 个熟人联系起来，这是“六度分隔”假说的一次成功的实验验证。米尔格拉姆实验展示了大型社会网络的两个重要事实：大型社会网络一定包含了丰富的最短路径；人们只需要通过大型社会网络的局域信息，而不是全局信息，就可以找到这些最短路径。
1990 年，米尔格拉姆的有趣实验结果激发了美国百老汇剧作家格雷 (J. Guare)的创作灵感，他在电影《六度分隔》中留下了这样一句经典台词：“在这个世界上，任意两个人之间，只隔着 6 个人。在这星球上的任何两人之间，只有六度分离。”
1998 年，学术界关于“六度分隔”的研究也取得全新的进展。美国Cornell大学的博士生瓦茨（D. Watts）和他的导师斯特罗加茨（S. Strogatz）在《Nature》上发表了题为《Collective dynamic of ‘small-world’ networks》（《小世界网络的集体动力学》）一文，在 “六度分隔”假设的基础上，第一次提出了“小世界网络”的概念和模型。他们把“六度分隔”现象归类为可以由两个网络结构参数——较大的网络群聚系数和较短的网络平均距离来描述“小世界现象”。他们发现，在各种社会网络、电力网络、神经网络、生物网络中均存在小世界现象。
小白：好长的历史……看来，小世界网络是人类社会中，普遍存在的现象了。那这个网络，是怎么构建起来的呢？
答：其实，建立一个小世界网络模型很简单。
假设我们都是幼儿园的小朋友，围在一起做游戏。首先规定，我们只能和离自己最近的，左右各K/2个小朋友之间系上绳子（K要是偶数，你懂的）。接着，幼儿园老师随机的以概率p选取了若干条绳子，规定绳子一端小朋友保持不动，另外一端的小朋友可以将绳子解开，并随机选择其余小朋友进行重系。规定是：1、不可以自己和自己系绳子；2、如果我系向了你，你只能再去找别人系绳子，不可以再选择我了。
然后，现在想象，从天空中看我们和我们身上系着的绳子，这就构建起了一个小世界网络模型，称为小世界网络模型的典型代表是瓦茨--斯特罗加茨（ WS）小世界网络模型（如下图）。
我们还可以用另外一种方式来构建小世界网络。首先的规定是一样的，自己只能和左右各k/2个小朋友系上绳子。然后，幼儿园老师以概率P随机的选取NK/2对小朋友，并在他们之间再系上绳子，规定是：1、不能重复系两根绳子在同样两个小朋友身上；2、不能将一条绳子只绑在一个小朋友身上。这就是与纽曼--瓦茨（ NW）小世界网络模型（如下图）。
小世界网络的实例
小白：你说世界上存在很多小世界网络现象。能举几个例子吗？
答：好的。
实例1：互联网的节点是各个路由器，连边则是连接各个路由器的光纤。在 1995~1999 年对于互联网网站及路由器层次都进行了计算，发现互联网的平均路径长度是 L= 4.0
实例2：科学引文网络的节点是发表于科学刊物上的各篇论文，连边则是互相之间的引用，科学引文网络也是典型的小世界网络。
实例3：语言网络也是小世界网络。每一个单词是一个节点，两个单词相连接出现在一个句子中即为有连边。据计算，两个单词之间的平均距离是 d = 2~3 (Romaine, 1992)
实例4：2011年Facebook验证“六度分离”理论，Facebook和米兰大学公布了共同研究结果，这项研究以Facebook上的721,000,000用户数据为基础，通过精确的网络算法计算，得出每两个用户之间平均通过4.74个间接人就能够建立联系。在2008年，类似算法测算出的平均分离度还是5.28，如今已经降低至4.74。
小白：这样看来，那岂不是我和我偶像之间的距离，只差大概6个人？想想好激动！！
答：呃……可是，即使你知道你与世界上随机选取的一个人之间的距离也许并不大，但是这并不意味着你就能轻而易举地找到连接你们的那些人。网络的可搜索性是与网络结构关联在一起的，也就是说，你是否能找到连接你们之间的那些人，是和你与你偶像之间存在的社交网络结构所关联的。20世纪末美国Cornell大学的乔恩·克莱因伯格（J. Kleinberg）关于小世界网络可搜索性的研究是网络科学的重要突破。现在把每个人都看成一个节点。在小世界网络上可以有效地实施导航（或搜索）是有条件的前提条件是：，即网络中的节点在“距离”上是均匀分布的，且网络中两节点之间随机添加长程连接（捷径）的概率是基于两节点间的“距离”。
而在实际网络中，节点的“距离”分布往往是不均匀的，且两节点间是否实现长程连接（添加捷径）既有“距离”的因素，也有非“距离”的因素在起作用，如节点在动力学行为上的惯性与情感等。
例如，假设节点之间随机建立联系的概率正比于节点之间距离倒数的a幂次，则只有当a等于网络的维数时（如对一维网络，a=1，对二维网络，a=2），可以最有效的实施搜索。幂次a 的特定取值说明网络只有特定的结构才使寻找最短路径成为可能，这也正是米尔格拉姆实验只有在小世界网络中才能成功的原因。这部分的模型和实证相当有趣，可以参考文献【2】P245~266.
小白：你说，世界上有很多小世界网络现象。到目前为止，给我感觉就是社交网络一定是一个小世界网络。那么，还有其他什么问题可以利用小世界网络模型来解释吗？
答：那我们再来谈谈同步问题。在自然科学和社会科学中都广泛存在着同步问题。如一场精彩表演结束后，观众给予的热烈掌声，往往都是从最初零乱的鼓掌到最后趋于一致的、有节奏性的鼓掌。如果把同步问题放在复杂网络科学的视域下进行研究，就是用网络中的诸多节点来代表不同的动力系统（如不同的观众），网络节点间的连边代表不同节点（不同的观众）之间的相互作用。在不同的初始状态下，由于彼此之间的相互作用，使众多不同的动力系统（如不同观众）的状态相互接近，并最终达到（或基本达到）全同状态的过程，即网络同步。
中国学者汪小帆、陈关荣最早研究了具有小世界结构性质的复杂网络系统的同步问题。他们发现，小世界特性可以显著地提高复杂网络系统的同步能力，即小世界网络实现同步的能力远远高于其对应的规则网络。必须注意的是，“节点间的平均距离越小，同步能力越强”这一结论只适用于小世界网络，而对其他类型的复杂网络不适用。从同步问题中，研究发现，有些网络是无法自我同步的，必须要通过某种控制手段才有可能实现同步。我国学者提出的牵制控制（Pinning control），其基本思想是通过有选择地对网络中的少部分节点施加控制而使整个网络达到所预期的行为。
还有，就是流行病传播问题。例如，传染病在人群中的流行、病毒在计算机网络上的蔓延、谣言在人际社会中的扩散等，都可视为流行病在小世界网络上的传播问题。
再举一个例子，博弈问题。具有争斗或竞争性的问题，往往可以通过博弈模型来进行描述与分析，这类问题又统称为博弈问题，如生物体进化过程中的优胜劣汰问题，社会关系中的合作与背叛问题等。复杂网络上的博弈问题，是指群体博弈者之间的关系构成了一个小世界网络，基于对该网络拓扑结构的全新认识，来研究群体博弈者之间的合作与竞争问题。
小白：如果我想深入了解一下小世界网络，能给一些参考文章吗？
答：实际上，基于数据的复杂系统的数学模型正以一种全新的视角快速发展成为一个新学科：网络科学。网络科学就是旨在探究复杂网络的奥秘。关于小世界模型的聚类系数，平均距离和度分布等性质，有兴趣的读者可以参考书籍【2】。与《Collective dynamic of‘small-world’networks》这篇文章并列看做是网络科学兴起的标志的另一篇开创性的文章是时为美国Dame大学物理系教授Laszlo Barabási及其博士生Albert于1999年10月在《Science》上发表的《Emergence of Scaling in Random Networks》（《随机网络中标度的涌现》）文章。这两篇文章分别揭示了复杂网络的小世界特征和无标度性质，并建立了相应的模型以阐述这些特性的产生机理。有机会我们再介绍无标度性质。
◆ ◆ ◆结语
复杂性科学(Complexity Science)诞生于上世纪80年代。随着网络时代的到来，在本世纪得到了迅猛发展，英国著名物理学家霍金称“21世纪将是复杂性科学的世纪”。复杂性科学是一门高度交叉的科学，它以社交网络系统、金融系统、脑神经系统、交通系统等各种复杂性系统为研究对象，试图揭示和解释各种复杂系统的运行规律为主要任务，以提高人们认识世界、探究世界和改造世界的能力。尤其是近年海量大数据的涌现，为复杂性科学引入了新的科研范式。在一切都将被记录，一切都将被数据化的网络时代，让我们一起探索数据背后的奥秘。
参考文献：
【1】汪秉宏，李平. 小世界网络浅介【J】，现代物理知识，第28卷，第3期.
【2】汪小帆，李翔，陈关荣. 网络科学导论【M】北京：高等教育出版社，2012.
【3】Watts D J, Strogatz S H. Collective dynamic of ‘small-world’ networks【J】Nature,1998,393（6684）：440-442.
【4】Milgram Stanley, The small world problem【J】, Psychology Today, May 1967, pp61‐67
注：本文中大量关于小世界的历史趣味知识源于笔者学习汪秉宏老师和李平老师的《小世界网络浅介》文章所摘录，其中有大量文字均为摘录，回复“小世界网络浅析”可下载原文【1】【3】【4】学习。
关于转载
如需转载，请在开篇显著位置注明作者和出处（转自：大数据文摘|bigdatadigest），并在文章结尾放置大数据文摘醒目二维码。无原创标识文章请按照转载要求编辑，可直接转载，转载后请将转载链接发送给我们；有原创标识文章，请发送【文章名称-待授权公众号名称及ID】给我们申请白名单授权。未经许可的转载以及改编者，我们将依法追究其法律责任。联系邮箱：zz@bigdatadigest。
◆ ◆ ◆
志愿者介绍
大数据文摘后台回复“志愿者”，了解如何加入我们
◆ ◆ ◆
小白学数据：一文看懂机器学习
小白学数据：一文看懂NoSQL数据库
小白学数据：NoSQL进阶篇
小白学数据：什么是神经网络
