小世界网络是一种数学图。在这类图中，绝大多数节点互相并不相邻，但任一给定节点的邻居们却很可能彼此是邻居，并且大多数节点都可以从任意其他节点，用较少的步或跳跃访问到。具体来说，小世界网络的定义如下：如果网络中随机选择的两个节点之间的距离L（即访问彼此所需要的步数），与网络中节点数量N的对数成比例增长，（即[1]: [math]\displaystyle{ L \propto \log N }[/math]），且网络的集聚系数 Clustering Coefficient不小，那么，这样的网络就是小世界网络。在社交网络中，这种网络属性意味着一些彼此并不相识的人，可以通过一条很短的熟人链条被联系在一起，这也就是小世界现象。许多经验网络图都展示出了小世界现象，例如社交网络、互联网的底层架构、Wikipedia的百科类网站及基因网络等。

1998年，Duncan J. Watts和Steven Strogatz提出，小世界网络是一类随机图[2]。他们指出，这类网络图可以通过两个独立的结构特征，即集聚系数和平均节点间距离（也称作平均最短路径长度）来进行识别。根据ER随机图模型构造的纯随机图，会展现出较小的最短路径长度（通常随着节点数对数值的变化而变化）以及较小的集聚系数。Watts和Strogatz验证了这一点，事实上，现实世界中很多网络的平均最短路径长度都较短，而集聚系数又远高于普通随机图。Watts和Strogatz随后提出了一种新的图模型（即现在的Watts-Strogatz模型），该模型具备两个特征：(1)平均最短路径长度较小，(2)集聚系数较大。1999年，Barthelemy和Amaral最先描述出了Watts-Strogatz模型中“大世界”（诸如栅格网络）与小世界的交叉点性质[3]。在此之后，学界又涌现出了大量的相关研究，其中不乏一些较为精确的度量结果 (Barrat and Weigt, 1999; Dorogovtsev and Mendes; Barmpoutis and Murray, 2010)。 Braunstein发现[4]，对于权值分布非常广的加权ER网络，最佳路径长度会显著增长，其增长速度为[math]\displaystyle{ N^{\frac{1}{3}} }[/math].

小世界网络中往往会包含 团 cliques 以及临近团 near-cliques ——此处的“团”，指的是内部几乎任意两个节点之间都存在连接的子网络。这遵循高集聚系数的定义属性。其次，大多数节点对之间，都至少存在一条短路径。这遵循平均最短路径较小的定义属性。许多其他属性，通常也会与小世界网络有所关联。通常情况下，网络中会存在很多的中心 hub ——它们是具有很高连接数的节点（即高度节点）。这些中心扮演了公共连接的角色，缩短了其他边之间的短路径长度。通过对比，航空航班的小世界网络，都体现出了较短的平均路径长度（例如，在任意两个城市之间飞行，你通常可能只需要乘坐三程或更少的航班数），因为很多航线都可以通过枢纽城市进行中转。这一属性的分析，通常要考虑网络中，具有相同入度的节点的比例（网络的度的分布）。网络具有较多中心，意味着度值较大的节点占比会更高，因此，在这种网络的度分布中，高度值分布更高，即俗称的厚尾分布 fat-tailed distribution 。具有不同拓扑结构的图，只要满足上述两个定义，就可以被定义为小世界网络。

网络的小世界性被量化为一个系数[math]\displaystyle{ \sigma }[/math]，可以通过比较给定网络与具备相同度分布的等价网络的集聚系数与路径长度，计算得出[5][6]。

如果[math]\displaystyle{ \sigma \gt {1} }[/math]( [math]\displaystyle{ C \gg C_r }[/math]，且[math]\displaystyle{ L \approx L_r }[/math]), 网络即为小世界网络

另一个量化网络小世界性的方法，是利用小世界网络的原始定义，比较给定网络与等价随机网格网络的集聚系数及路径长度[7]。小世界所用的度量（[math]\displaystyle{ \omega }[/math]）定义如下[8]：

其中，对于所选受测网络而言，L是特征路径长度，C是集聚系数。[math]\displaystyle{ C_l }[/math]是等价栅格网络的集聚系数， 而[math]\displaystyle{ L_r }[/math]则是等价随机网络的的特征路径长度。

R. Cohen和Havlin分析出[9][10]，无标度网络是超小世界。在这种情况下，由于中心的存在，最短路径会变得非常小，并且满足如下关系：

结果表明，在存在白噪音的小世界网络中，会出现随机同步，这意味着，白噪音有助于系统针对中等噪声强度进行更好地同步，而非减少噪音[11][12]。这种现象，与白噪音在随机图或无标度网络中的效果形成了鲜明的对比，即应用噪声会降低这些网络中的同步幅度，使同步的效率提高。

在现实世界的很多现象中，都能够看到小世界属性，这包括网络中的导航菜单、食物网、电网、代谢处理网络 metabolite processing networks 、脑神经网络、选民网络、电话呼叫图、社交影响网络等等。文化网络[13]与单词共现网络[14]也被证明是小世界网络。

相连的蛋白质网络同样具有小世界性质，例如遵从幂律的度分布。[15]类似地还有转录网络，其节点为基因，如果某一个基因对另一个基因有上调或下调的遗传影响，且这些基因彼此相连，这一网络就具有小世界网络的性质。[16]

另一个例子就是人与人之间的“六度分离”理论。该理论的适用条件是假设涉及到的人都同时活着，或者在短期内处于同一组织之中。阿尔伯特·爱因斯坦与亚历山大大帝之间的分离度，几乎肯定是大于30的[17]，而且这个世界并不具备小世界属性。一个同样不具备小世界性质的网络还有“曾去同一家学校上学”的网络：如果两个人加入某一所大学的时间差了10年，他们不太可能在学生团体中有共同的熟人。

类似的，消息传播过程中必须要通过的中继站点的数量并不总是很少的。回溯到邮件还需要手工投递或骑马寄送的时期，一封信件从它的起点到终点所需要转手的次数，会比现在大上很多。可视电报（约存在于1800-1850年）时代，消息易手的次数，要由两个站点之间是否是在视线连接范围内决定。

如果没有检验隐含假设，可能会对图“望图生义”，偏向于寻找小世界网络（一个例子就是发表性偏倚导致的文件抽屉问题 file drawer ）。

Barabási等研究人员提出假设，认为小世界网络在生物系统中的普遍存在，可能反映了这种结构的进化优势。一种可能性是，小世界网络相比其他网络架构，对扰动的鲁棒性更强。如果这种假设成立，小世界网络将为受到突变或病毒感染损害的生物系统提供优势。

在一个具备遵循幂律分布现象的度分布的小世界网络中，随机删除节点，极少能导致平均最短路径长度显著增加（或集聚系数的显著降低）。这是因为，节点之间的最短路径通过中心点流动，而且，如果一个外围节点被删除，不太可能干扰其他外围节点之间的通路。由于小世界网络中，外围节点的比例要远高于中心的比例，因此，删除重要节点的概率非常低。例如，如果爱达荷州太阳谷的小型机场被关闭，不会增加在美国旅行的其他乘客到达各自目的地所需的平均航次。但是，如果随机删除的节点是中心枢纽，那么平均路径长度就会急剧增加。每年都可以看到，当芝加哥奥黑尔机场等北部枢纽因大雪关闭时，经常会出现这种状况；许多乘客不得不搭乘更多航班，以达到目的地。

相反，在随机网络中，所有节点具有数量大致相同的连接，随机删除节点可能会略微增加平均最短距离，但删除任意节点都会带来这样的影响。从这个意义上来讲，随机网络容易受到随机扰动的影响，而小世界网络则具备鲁棒性。但是，小世界网络容易受到针对中心的攻击，而目标攻击无法对随机网络造成灾难性故障。

病毒已经进化到可以干扰中枢蛋白的活动，诸如p53，并因此产生有利于病毒复制的细胞行为的巨大变化。渗流理论是分析网络鲁棒性的一个有效方法。

构建小世界网络的主要机制是Watts-Strogatz机制。

小世界网络也可引入延时[18]，这不仅会产生分形，而且在特定条件下，还会形成混沌[19]，或者在动态网络中转变为混沌[20]。

构造度直径图 Degree–diameter graph 的方法是：网络中每个顶点的邻居数量是有界的，而网络中从任意给定顶点到其他顶点（网络直径）是最小的。构建这样的小世界网络，其实是为寻找临近摩尔边界的图的秩，而做出的一部分努力。

Barmpoutis等人给出的从零开始构建小世界网络的另外一种方法[21]，构建了一种平均距离极小且平均集聚度极高的网络。他们提到了一种复杂度恒定的快速算法，以及不同生成图鲁棒性的度量。根据每个网络的应用，可以从一个这样的“超小世界”网络开始，然后重新连接一些边，或者使用几个这样的小网络作为子图，构筑一个更大的图。

通过双相演化 dual-phase evolution 过程，小世界属性可以在社交网络和其他现实世界系统中自然产生。在顶点之间的连接增长受到时间或空间的制约时，小世界网络尤其常见。该机制通常涉及相位之间的周期性变换，其中，在“全局”阶段——连接建立，而在“本地”阶段——连接被移除。

参考：扩散限制凝聚，模式构成。

此时得到的图片是下图所示: