复杂网络可以刻画自然和社会中的大量复杂系统。复杂网络由许多节点及节点之间的相连接边构成。节点代表系统的构成元素，连边则描述两个元素之间的相互作用。一个网络的规模大小和稀疏稠密性质由网络的平均路径长度及网络的群聚性这两个网络结构性质度量。网络的平均路径长度指网络中任意两个节点之间的最短路径长度的平均值。网络的群聚性指对于网络中各个节点的群聚系数的平均值。网络中一个节点的群聚系数定义为该节点的所有邻居节点之间的实际连边数目除以该节点的所有这些邻居节点之间可能出现的最大连边数。刻画人与人之间朋友关系的社交网络和刻画各个互联网网页彼此链接特性的互联网网络，都是小世界网络。

1929年，匈牙利作家F.凯伦斯^[注]在其小说《链条》^[注]中给出了著名的“六度分隔”假说。在凯伦斯的小说中，一个人可以通过其认识的网球冠军及网球冠军的球友瑞典国王、瑞典国王是诺贝尔奖的颁奖者这一路径，以简单明了的方式与一个诺贝尔奖的获得者连接上了。凯伦斯甚至将自己与远在美国福特汽车公司的一个工人，仅仅通过三个中间人就联系了起来。凯伦斯关于人与人之间最多需要5层关系就能联系起来的推断，可以说是六度分隔假说的最早表述，也是“小世界网络”概念的雏形。

1967年，美国哈佛大学社会心理学教授S.米尔格拉姆^[注]明确提出了“小世界问题”。他通过设计一个信件传递实验，以验证六度分隔假说，并使其成为“小世界问题”研究的基本概念。米尔格拉姆以美国堪萨斯州的威奇托和内布拉斯加州的奥马哈作为实验起点，在两地随机地选择了296位志愿者，要求每位志愿者向指定的目标人——一位居住在马萨诸塞州首府波士顿郊区的股票经纪人传递一封信件。实验结果是其中的64位志愿者平均通过约5.3个中间人转手后，成功地将信件送达到目标人手中。这与38年前的匈牙利著名作家凯伦斯的“六度分割”假说惊人地吻合。米尔格拉姆由此得出结论：任意两个人都可通过平均6个熟人联系起来，这是“六度分隔”假说的一次成功的实验验证。米尔格拉姆实验展示了大型社会网络的两个重要事实：大型社会网络一定包含了丰富的最短路径；人们只需要通过大型社会网络的局域信息，而不是全局信息，就可以找到这些最短路径。

1998年，“六度分隔”假说研究取得新进展。美国康奈尔大学的博士生D.J.沃茨^[注]和他的导师S.H.斯特罗加茨^[注]在《自然》（Nature）上发表了名为《小世界网络的群体动力学》^[注]一文，在“六度分隔”假说的基础上，第一次提出了“小世界网络”的概念和模型。他们把“六度分隔”假说归类为可以由两个网络结构参数——较大的网络群聚系数和较短的网络平均距离来描述的“小世界现象”。他们发现在各种社会网络、电力网络、神经网络、生物网络中均存在小世界现象。

“小世界”问题最早是在社会学研究中被提出的。20世纪末，一批数学、物理学和计算机专家创造性地为这个社会学概念构建了数学模型，引用网络平均路径长度和网络群聚系数这两个网络结构参数来刻画社会学系统的规模大小和密集稀疏性质。小世界网络模型的典型代表是沃茨-斯特罗加茨小世界网络模型与纽曼-沃茨小世界网络模型。

第一个小世界网络模型是由美国康奈尔大学的沃茨和斯特罗加茨于1998年在著名学术期刊《自然》上发表的《小世界网络的集体动力学》一文中提出的。他们发现：规则网络的群聚性较高，网络的平均距离较大；而随机网络的群聚性较低，网络的平均距离较短。真实世界的网络既非完全规则，也非完全随机，而是介于两者之间。因此，他们以一个规则网络为基础，然后以概率对规则网络中的每条边进行随机重连（剔除节点的自我连接和重边连接），这些随机重连的边在规则网络中既引入了随机性，又引入了长程连接（或称为捷径）。这些少量的、随机的长程连接大大地减小了网络节点之间的平均距离，却又保持了原有网络较高的群聚性，使网络具有了小世界特性（图1）。

图1 瓦茨-斯特罗加茨小世界网络模型

美国学者M.E.J.纽曼^[注]和沃茨对沃茨-斯特罗加茨小世界网络模型做了改进，通过在规则网络上随机加边来取代随机重连，同样在规则网络中既引入了随机性，又引入了长程连接，从而使网络具有了小世界特性（图2）。

图2 纽曼-瓦茨小世界网络模型

定量分析小世界网络特性的特征参数包括平均路径长度，平均群聚系数和小世界商。

①网络的平均路径长度。如果表示网络中第节点与第节点之间的最短路径长度。则对于所有节点对的平均值被称为网络的平均路径长度（又称特征路径长度或平均最短路径长度）。理论分析、数值模拟和大量的实证研究表明：小世界网络的平均路径长度正比于网络规模（网络的节点总数）的对数：

(1)

式中符号“”为“正比于”的意思。

②网络的平均群聚系数。对于一般的无向网络，网络中第节点的群聚系数定义为：

(2)

式中为第节点的邻居节点数目，又称度。则为个邻居节点之间的实际连接边数。个邻居节点之间的最大连接边数为：

(3)

网络的平均群聚系数定义为网络中所有节点的群聚系数的平均值。群聚系数是用来描述网络中的节点之间群聚成团程度的参数，表征了一个节点的邻居节点之间相互连接的程度。显然，群聚系数是一个介于0与1之间的数，越接近1，表示这个节点的所有邻居节点间越有“抱团”的趋势。群聚系数描述了网络节点间的局域连接密集程度。

人们将既有小的平均路径长度又有大的平均群聚系数特征的网络称为小世界网络。在沃茨-斯特罗加茨小世界网络模型中，在调节节点间连边的随机重连概率从0逐渐增大到1的过程中，可以观察到初始的规则网络将历经“规则网络—小世界网络—随机网络”三个阶段。在沃茨-斯特罗加茨小世界网络模型中，归一化的平均路径长度和平均群聚系数随重连概率增长的变化关系（图3）。

图3 瓦茨-斯特罗加茨小世界网络模型归一化示意图

③小世界商。社会学中描述网络是否呈现小世界特性的特征参数是小世界商，它是将实际网络的平均群聚系数与网络的平均路径长度的比值，除以对应的具有相同节点数和边数的随机网络的平均群聚系数与平均路径长度的比值，得到的一个商值：

(4)

若大于1，则表明该网络具有小世界特性。商值越大，网络的小世界特性越显著。

网络的结构对于以这个网络为基础架构的系统的集体动力学行为具有重要影响。小世界网络上的动力学主要讨论小世界网络上的导航（搜索）、同步、传播及博弈等问题。

网络导航又称网络搜索。美国康奈尔大学的J.M.克莱因伯格^[注]研究了均匀网络上有向化的纽曼-沃茨小世界网络模型的导航问题，如果随机加边的概率正比于两个节点“距离”倒数的幂次，这里的“距离”既可以是纯粹的地理上的距离，也可以是一种隐喻意义上的社会距离，如职业、种族、收入、教育、信仰等方面的差别或不同。当恰好等于网络的维数时（如对一维网络，，对二维网络，），应用网络的局域信息，并通过贪婪算法（即每次导航到的下一个节点都应离目标节点更近，以保证最终可以达到目标），可以最有效地实施导航（搜索）。幂次的特定取值说明网络只有特定的结构才能寻找到最短路径，这也正是米尔格拉姆服从实验只有在小世界网络中才能成功的原因。显然，在小世界网络可以有效地实施导航（搜索）是有条件的，即网络中的节点在“距离”上是均匀分布的，且网络中两节点之间随机添加长程连接（捷径）的概率是基于两节点间的“距离”。而在实际网络中，节点的“距离”分布往往是不均匀的，且两节点间是否存在长程连接（添加捷径）既受“距离”因素影响，又受非“距离”因素影响。

斯特罗加茨认为同步实质上是小世界效应的一种表征，即小世界网络中节点间具有较短的平均距离，使得处于网络不同部分的节点能够共享网络的共同属性而形成同步。小世界网络的基本结构是具有较大的局域群聚特性，同时又具有较短的全局性平均距离。其局域群聚特性使得网络耦合更加紧密，促进了局域范围中节点间的相互关联，使相应网络具有了较强的同步能力；由于较短的全局性平均距离，使规模越大的网络其同步能力越强。随着重连概率的增长，网络系统会发生从非同步相到同步相的相变。必须注意的是，“节点间的平均距离越小，同步能力越强”这一结论只适用于小世界网络，而对其他类型的复杂网络不适用。如对于无标度网络，这一结论恰好相反。

传染病在人群中的流行、病毒在计算机网络上的蔓延、谣言在人际社会中的扩散等，都可视为流行病在网络上的传播问题。

阿根廷学者G.艾布拉姆森^[注]和M.库珀曼^[注]研究了沃茨-斯特罗加茨小世界网络上的SIRS模型（易感-感染-恢复-再易感模型）的传播行为。发现当重连概率很小的时候，疾病可以在网络中长期存在，但患病比例很小且波动不大，可以近似地看作收敛到一个不动点。而当重连概率很大的时候，患病人数会出现周期性波动。即随着重连概率逐渐增加，对应于一定的人群结构，网络中被传染的人数从不规则的、小幅度的增加发展到自发的、大范围的振荡状态。特别在附近传染人数明显增加，显示出小世界效应。

纽曼等研究了纽曼-沃茨小世界网络上的SIR模型（易感-感染-恢复模型）的传播行为。他们把小世界网络上的疾病传播问题对应于愈渗（座愈渗、健愈渗、座健混合愈渗）问题，给出了愈渗的临界值与网络长程边（捷径）密度的函数关系，发现随着长程边（捷径）的出现，流行病在网络上的传播阈值（即愈渗的临界值）迅速下降，即使少量的长程边（捷径）也可以显著地增加流行病在网络中的传播能力。

流行病在小世界网络上的传播行为与小世界网络的规模、重连概率（或加入长程边的概率）和（网络上单方向连接的边数）等网络结构参数密切相关。这些网络结构参数对流行病在小世界网络上的传播规律和趋势有很大影响。改变这些网络结构参数的数值，可以得到在不同情况下的流行病传播规律，显示流行病的发展过程，预测流行病的传播趋势，分析流行病的传播扩散原因及其关键因素，从而寻找对流行病进行控制和预测的最佳策略。

复杂网络上的博弈问题指群体博弈者之间的关系构成了一个复杂网络，基于对复杂网络拓扑结构的全新认识，研究群体博弈者之间的合作与竞争问题。特别关注网络的拓扑结构如何影响合作行为的涌现与演化特性。社会网络都具有明显的小世界效应，因此，在小世界网络上探讨群体博弈行为在理论研究和实际应用等方面具有重要意义。人们在对小世界网络上的博弈问题进行研究中发现，博弈群体的演化行为与小世界网络的拓扑结构参数密切相关，其较短的平均路径长度和较高的平均群聚系数特性，使得信息可以在网络中快速传递并且在局域群体中群体会较快达成共识，有利于合作行为的涌现，其典型特征表现为重连概率与合作的涌现程度有着显著明显的关联性。