3.2 小世界网络模型

上一节中主要描述了六度分隔实验与小世界现象的直观解释。这一节将从模型角度介绍小世界网络模型以及小世界网络的特性。

3.2.1 W-S模型

存在小世界现象的社交网络有两个特征：一是拥有许多三元闭包，二是存在较短的短路径（短路径即某节点到达另一节点所经最短距离的路径）。同质性是指人们更愿意与同自己志趣相投的人建立关系，这样可以形成大量三元闭包，同时弱连接能让人们与网络中较远的人建立关系，因此能够实现不同的社会群体的跨越，这为短路径的存在提供条件。1998年，Duncan Watts和Steve Strogatz ^[9] 根据这种朴素的思想，提出基于同质性和弱连接的网络模型——Watts Strogatz（W-S）模型，开拓了小世界网络的定量分析新纪元。下面介绍模型的具体内容。

首先假设每个人都生活在一个二维网格中，可以将网格距离看作是一种地理关系或某种抽象社会关系的近似。图3-4 a显示了以网格形式排列的一组节点，在水平或垂直方向上直接相邻的两个节点，称它们相距一个网格步。

如图3-4 b所示，该模型中每个节点拥有两种连接，一种是同质性连接，一种是弱关系连接。同质性连接用以连接那些相互熟悉的人，具体地是指某个节点到那些相距 r 网格步以内的节点的连接， r 为常数。另外，对于弱关系连接，每个节点也形成与网格中其他较远的 k 个节点的连接，这些节点以概率 P 随机均匀地选择。这些连接对应于弱关系连接。

图3-4 b展示了W-S模型的网络示意图，可以看出，它是同质连接形成的基本结构之上散落着少量随机连接。由于两个相邻的节点在 r 网格步内的朋友有许多重叠，因此该网络结构拥有大量闭包。同时，该网络存在短路径的可能性较高。这是因为随机弱连接能够实现不同社会群体之间的跨越，在较短的步数下就能够接触大量节点，于是到达目的节点的短路径存在概率就比较高。Boliobas和Chung以精确的数学模型论证了这种观点 ^[10] ，并确定了典型的路径长度 ^[11] 。

以上主要从概念描述的角度讲解了W-S模型的构建及其拥有大量三元闭包和存在短路径概率较高的特征。接下来从数学角度介绍W-S小世界模型的网络特征和通用性。

W-S模型是建立在规则网格基础之上，通过调节参数——概率 p ，将连接边进行随机断链重连，从而实现规则网络到随机网络的过渡。这里的断链重连就是前文提到的“弱连接”。如图3-5所示是一维网格对应概率 p 从0到1变化的网络结构。随着断链重连的概率越来越高，也就是产生弱连接越来越多时，规则网络变为随机网络。而在 p 变化为某个数值所对应的网络具有小世界特性。

从本质上说，小世界网络是指在规则网络上增加随机性，因此可以把小世界网络理解为介于规则网络和随机网络之间的一种网络，结合了规则网络的高聚集系数特征和随机网络的短平均路径长度特征。聚集系数和特征路径长度是研究小世界网络的重要网络属性。具体的介绍如下。

1.特征路径长度

描述网络的连通性，从全局角度，量化网络中任意顶点对间的最短距离的平均值：

其中， L 为特征路径长度， n 为网络节点总数目， d （ v _i ， v _j ）是任意节点 i 、 j 间的最短路径长度。

2.聚类系数

表示一个网络中节点的聚集程度，用来描述网络中节点间连接的紧密度。假设某一节点为 i ，它与 k _i 个相邻节点直接相连。假设节点 i 的所有近邻点间都两两相连，则这 k _i 个近邻点间最多有 k _i （ k _i -1）/2条边。而实际网络中，节点 i 的 k _i 个近邻点间未必都是两两相连。假设 i 实际连接边数为 e _i ，则聚类系数可以表示为

其中， C _i 为节点 i 的聚类系数， k _i 为节点 i 的近邻点数， e _i 为节点 i 实际连接边数。

接下来考察 p 对网络特征的具体影响。从一个有 n 个顶点，每个顶点 k 条边的晶格，随机采用概率 p 进行布线。 p =0为规则网络。 p =1为随机网络，使用聚集系数 C （ p ）和平均路径长度 L （ p ）来衡量网络的属性。图3-6展示了 p 的变化对聚集系数 C （ p ）和平均路径长度 L （ p ）的影响。

可以发现，当 p 值较小时，引入随机边对 L （ p ）有着很大的非线性影响， L （ p ）迅速减小。但较小的 p 对聚集系数 C （ p ）影响很小，且几乎保持不变。这说明采用较小的概率 p 时，所形成的网络具有高聚集系数和短路径特征。大量研究表明，该结论具有鲁棒性，通过选用不同的规则网格和不同的随机布线算法都能够得出相似的结论。

Watts等人为了验证W-S模型的通用性，构建真实网络以测试其是否存在小世界网络的特性。他们分别计算演员合作网络（先前提到的Bacon网络）、电力传输动态网络以及秀丽隐杆线虫的神经网络的路径长度和聚类系数。最终发现在相同的节点和连接情况下，路径长度与随机图十分接近，但聚类系数更大（见表3-1），正如W-S模型取较小 p 时的小世界网络特征。由此可见，W-S模型具有通用性。

然而，由于W-S小世界模型在其生成过程中可能会产生孤立节点，从而影响网络的连通性。为此，Newman和Watts对模型进行修正，提出了N-W小世界网络模型 ^[12] 。该模型将W-S小世界模型的随机化重连用随机化加边来代替，以免模型产生孤立节点。随机加边是指在规则网格的基础上以概率随机选取两个顶点，加入一条边。任意两个不同的节点之间至多只能有一条边，并且每一个节点都不能有边与自身相连。随机化加边的策略有效解决了W-S模型网络连通性的问题。

除此之外，W-S模型的可搜索性如何也是一个关键的问题。在上文中提到，米尔格兰姆实验展示了关于社会网络两个显著事实： 一是社会网络包含丰富的短路径；二是人们能够自发找到这些短路径 。在小世界实验中人们搜索路径的方式被称为分散式搜索，即将当前的信件寄给下一个最有可能到达目标的人，是一种有目标的局部信息搜索。具体地，随机选择起始节点和目标节点，在这里分别设为节点 s 和节点 t 。从节点 s 开始，消息沿着网络中的边传递到目标节点 t ，每个路经的节点都只知道自身节点的连接状况以及目标节点 t 在网络中的位置，而且它们必须选择某个邻居转发该消息，最终确定节点 s 到达节点 t 的步骤数。通常通过构建某个模型的分散搜索来检验其可搜索性。研究证明基于W-S模型的分散搜索到达一个目标需要相当多的步骤（比实际最短路径长的多） ^[13] 。因此W-S虽然能够有效构建与社交网络类似的特征（拥有大量三元闭包、存在短路径），但很难获得人们在网络中共同合作从而找到路径的能力。原因是在该模型中，“弱连接”太随机，只描述弱连接可跨越远距离的特性，但没有考虑产生弱连接的方式与同质性之间的关系。因此需要一种不仅引入弱连接同时还能描绘出弱连接与同质性间关系的模型，从而获得既包含短路径又能够通过分散搜索发现这些短路径的网络，在下一小节中，将介绍提供有效分散搜索的W-S-K模型。

3.2.2 W-S-K模型

W-S模型用随机边来代表弱关系，每当使用一次断链重连建立一条捷径时，一个相邻节点被释放，然后从整个网络中再随机选取一个节点。这种随机性意味着每个节点（除其自身外）被选中的概率是相同的，忽略了节点间的差别。然而研究表明，人们建立关系时会考虑自身与他人的身份标识，这种身份标识涉及距离、职业、种族等因素 ^[11] 。由于W-S模型忽视个体间和身份标识相关的同质性，因此其建立的随机“弱连接”无法有效地搜寻到最短路径。于是，Kleinberg等 ^[13] 提出了Watts Strogatz Kelinberg（W-S-K）模型，该模型在建立随机连接时考虑了地理距离这一因素，两个节点间产生随机连接的可能性会随着它们之间的地理距离增大而减小。

对于 n × n 的网格，对 p ≥1， q ≥1，每个节点 u 和在 p 步长的晶格距离内的邻居都有一条有向短距离边，以及与 q 个随机选择的节点 v _i 之间有一条有向长距离边，其中 v _i 的选取是根据 u 和 v _i 之间的晶格距离 r 的负幂次 α （ α ≠0，且是固定值）作为概率进行选择。如图3-7所示，展示了当 p =1， q =1时较为特殊的情况，此时节点 u 与步长为1的晶格距离内的邻居产生有向短距离边（即图3-7中的 a ， b ， c ， d ），与一个随机选择的节点（即图3-7中的 v ）产生有向长距离边。在此规则下，不同的 α 值会得到不同的模型。当 α 非常小时，如图3-8 a所示，距离较远的节点也能建立连接，因此产生的连接随机性太强，不能有效用于分散搜索；当 α 非常大时，如图3-8 b所示，只有距离比较近的点才能建立连接，因此产生的连接“不够随机”，没有提供足够多的远距跳跃（即弱联系）。试想，是否存在一个最佳的 α 取值，使得随机连接的分布能够在这两种极端间达到平衡，从而实现快速的分散搜索呢？

理论上，存在这样的 α 取值能够使得模型实现最佳搜索效果。在大型网络规模下，当 α =2时分散搜索最有效，此时随机连接遵循反平方分布。接下来将从数学角度给出简化解释：图3-9使用分散搜索算法来传递消息 ^[13] ，如前文提到，其根据模型生成的网络中的随机源和目标之间转发消息所需的预期步骤数 T ，进而判断模型的搜索效果。 T 的下界是一个与log N 成比例的函数（ N 是模型包含的节点数）。当 α =2时，是唯一的指数，使得分散搜索算法实现的交付时间能够以log N 的多项式为界，也就是在 α =2时，搜索所花的时间最小，因此在此时模型的搜索效果最好。

下面，进一步解释当 α =2时，可以实现最高效的分散搜索。给定一个网络节点 v 和一个固定的距离 d ，考虑到 v 的距离在 d 到2 d 范围内的节点组，如图3-10所示。考虑 v 与该节点组中节点产生连接的概率。首先，因为 d 到2 d 这个范围的面积与半径平方成正比，所以组中节点总数与 d ² 成正比。其次，节点 v 到该组节点产生连接的概率与 d ^-2 成正比，故该两个分项可近似相互抵消。据此可以得出结论： v 与这个环上某个节点产生随机连接的概率近似地独立于 d 值。换句话说，随机连接在不同的分辨尺度上的数量是近似相等的。这使得无论目标相距多远，人们都能够在转发过程中不断找到缩短到目标距离的路径，这样一级一级地缩小范围，比如从国家再到省再到市到区最后到街道，最终能成功抵达目的地。

用W-S-K来刻画现实世界的网络时，会发现其只考虑了地理距离因素。然而现实网络通常是更加丰富和复杂的，往往需要融合更多的因素实现对于真实网络过程的理论化建模。下一小节将介绍更符合现实社交网络情况的网络模型。

3.2.3 其他改进的W-S模型

W-S-K模型中的晶格距离只刻画了个体间的地理位置距离，但在现实社会网络中，人与人之间的社会性距离，不仅会考虑地理位置，同时还会考虑种族、职业、宗教信仰、教育、阶级、兴趣爱好和组织从属关系等方面。与W-S-K模型类似，Watts等人 ^[15] 提出了改进的W-S模型，融合考虑了影响社会性距离的多种因素，从多个标度衡量晶格距离。由于两个模型的构建过程一致，故本节只介绍如何建模社会性距离的问题。

在社会性距离建模方面，改进的W-S模型从多个标度计算社会性距离，其计算的规则为： 多个标度下的距离最小值作为相似度 。该规则的现实基础是：若两个人在某一标度上很接近时，他们也许会认为在绝对意义上是接近的，即便在其他的标度上距离很远。下面首先介绍基于单一维度的距离度量，然后介绍多个维度下社会性距离的计算。

基于某个衡量维度，可以将大规模的研究群体分为不同的种类，在不同种类下又可以进一步分为更小的子类，依次类推。最终可以将整个研究群体划分为不同的小群组（如家庭或工作组等），形成从属关系网络，如图3-11所示。

针对单一标度下的从属网络而言，所有的研究对象为树形结构中的叶子节点。该模型中，当两个节点属于同一个群组时，距离为0；当两个节点属于不同的群组时，任意两个节点的距离通过它们最近的公共祖先节点的高度来确定。例如，在图3-11中，由于 A 和 B 分别属于不同的群组，它们的距离则由最近公共上级节点的高度来确定，即 A 和 B 的距离为2。

现在考虑多标度下计算社会性距离的情况。根据改进的W-S模型的思想：选取多个标度下距离最近的那个距离作为社会性距离。首先分别计算每个标度下的距离，最后选取距离最小的那个数值作为最终计算结果。

这里以两个标度下的距离计算为例进行说明。多个标度与两个标度计算方法类似。图3-12考虑了地理和职业两种维度。节点 A 和 C 在维度1上距离为1，在维度2上距离为3，则 A 和 C 之间的社会性距离为1；类似地， B 和 C 的距离在维度1上距离为3，在维度2上距离为1，则 B 和 C 之间的距离为1。 A 和 B 的距离在两种维度下都为3，因此它们之间的社会性距离为3。

在社会性距离建模完毕后，将这些距离带入W-S-K网络模型中，基于改进的W-S建模过程进行远程弱关系的生成。实验发现，使用多维的社会标度可以相对容易地在一个大型的网络中搜索到选定的目标。除此之外，如图3-13所示， H 代表社会标度的数目， α 代表社会群体的相似程度。当模型参数落入图3-13中阴影区域时，搜索网络就存在。这表明搜索路径的存在性不依赖于相似度或者社会标度的数量，只要当人们在衡量相似度时考虑一个以上的社会标度。这与Kleinberg条件（即W-S-K模型中 α =2）在某种意义上不同，后者要求网络在所有尺度上每个节点都拥有相等数目的链接才能保证网络的可搜索性，而前者实验结果表明只要人们在衡量相似度时考虑超过一个社会标度，则所构建的网络具有可搜索性。直观上思考，使用多种标度下的关系能够实现社会空间上更大的跨越，因此可以帮助更有效地搜索。