1.2 级联与聚簇

我们在1.1节着重讲解了级联现象的概念及其特点，本节开始从模型的角度探究网络中的级联现象，包括级联的产生和级联程度的度量。在办公环境中，人们更倾向于选择与其他同事更兼容的技术或设备，而不是采用最先进的或最流行的；在政治生活中，人们往往会与朋友们保持一致的政治观点，尽管该观点并不普遍。足以可见人们日常生活的决策中处处蕴含着行为的传播，为了定量描述这一现象，美国麻省理工学院的莫里斯 ^[21] 提出了一个基于直接受益效应的行为传播模型： 每个人有一些特定的社会网络邻居（朋友或同事），并且采纳某种行为所获的受益随着周围采纳的邻居的增多而增大 。根据该模型，本节从级联行为下的协调博弈和网络聚簇两方面进行介绍。

1.2.1 级联行为下的协调博弈

假设在一个基本的社会网络中，每个网络节点表示一个个体，并且每个节点有 A 、 B 两种行为可选；如果节点 U ₁ 与 U ₂ 之间存在边，则表明它们之间存在行为的传播。以协调博弈描述该网络，定义其收益如下：

● 若 U ₁ 与 U ₂ 均采取 A 行为，则它们的收益均为 r _a ＞0；

● 若 U ₁ 与 U ₂ 均采取 B 行为，则它们的收益均为 r _b ＞0；

● 若 U ₁ 与 U ₂ 采取不同的行为，则它们的收益均为0。

图1-2 a反映了 U ₁ 与 U ₂ 的收益矩阵，从该矩阵中能够发现每个节点均会复制其邻居的行为，其收益为所有连边所得收益的总和。然而，当 U ₁ 的一部分邻居采取行为 A ，另一部分邻居采取行为 B 时，应该采取哪种行为才能使收益最大？这与采取每个行为的邻居的数量 r _a 与 r _b 的值有关。假设 U ₁ 共有 n 个邻居，其中比例为 p 的用户采取行为 A ，（1- p ）的用户采取行为 B ，即 pn 位邻居为 A 行为，（1- p ） n 位邻居为 B 行为，如图1-2 b所示。如果 U ₁ 采取行为 A ，所获收益为 pnr _a ，否则为（1- p ） nr _b ：

● 若 pnr _a ≥（1- p ） nr _b ，即 时，采取行为 A 收益更大；

● 若 pnr _a ＜（1- p ） nr _b ，即 时，采取行为 B 收益更大。

令 q = r _b / r _a + r _b 表示一个门槛值 ，即当每个用户周围有比例为 q 的邻居采取行为 A 时，用户也应该采取该行为。以门槛值来分析该博弈结果，当 q 较小时，说明 r _a ≫ r _b ，则行为 A 更具吸引力，仅需小部分邻居采取行为 A 目标用户就会转向 A ；当 q 较大时，说明 r _a ≪ r _b ，则行为 B 更具吸引力，用户只有在大量朋友采取行为 A 之后才会出于其他影响因素转向 A 。注意，当恰好有比例为 q 的邻居采取行为 A 时，默认目标用户也会采取行为 A 。

图1-2所展示的基本网络协调模型存在两个明显的平衡结果，即要么所有节点均采取 A 行为，要么所有节点均采取 B 行为。接下来探究另外一种更实际的平衡状态，即一部分节点采取 A 行为，而另一部分节点采取 B 行为。正像在实验室中总会有部分用户使用MacOS办公，而其他用户使用Windows办公。假设网络中每个节点最初均采用 B 行为（所有人均使用Windows办公），其中一部分用户出于某种偏好决定采取 A 行为（开始使用MacOS办公），尽管可能会使他们的短期收益下降，他们更关注的其他影响因素使这些用户忽略了下降的收益（例如他们都是忠实的“果粉”）。虽然这些用户不再遵循最高收益原则，但其他用户依然按照协调博弈的规则评估其收益。由于部分初用者采取了 A 行为，导致其部分邻居也有可能转向 A 行为，进而其邻居的邻居也有可能转向 A 行为。整个网络行为的决策过程以一个潜在的级联方式进行，什么情况下所有节点转向 A 行为？或者什么情况下 A 行为不会继续扩散？

假设一个初用节点集采用 A 行为，其他所有节点均采用 B 行为。每个时间步下节点依据门槛值决定是否由 B 行为转向 A 行为。当所有节点的行为均转向 A 行为时，级联停止；或者所有节点均不再想要变更行为，达到 A 行为与 B 行为共存的状态。令 r _a =4， r _b =3，即行为 A 的收益是行为 B 的4/3倍。根据门槛值计算公式 q ，一个节点至少有 q = r _b /（ r _a + r _b ）=3/7比例的邻居采取 A 行为，该节点才会从行为 B 转向 A 。该过程如图1-3所示（实线圈为采取行为 A 的节点，虚线圈为采取行为 B 的节点）。

● t ₀ 时刻假设 U ₄ 、 U ₇ 为采取行为 A 的初用节点集，其余节点均采取行为 B ；

● t ₁ 时刻， U ₆ 和 U ₈ 因为有比例1/2＞3/7的邻居为 A 行为而转向 A 行为，其余节点仍为 B 行为；

● t ₂ 时刻， U ₃ 和 U ₅ 因为有比例2/3＞3/7的邻居为 A 行为而转向 A 行为，其余节点仍为 B 行为；

● t ₃ 时刻， U ₁ 和 U ₂ 因为有比例2/3＞3/7的邻居为 A 行为而转向 A 行为，全部节点均转为 A 行为，级联停止。

图1-3展示的级联中，网络的所有节点全部转向 A 行为。如果最终采用 A 行为的级联导致整个网络节点均从 B 行为转向 A 行为，则认为该初用节点集产生了一个门槛值为 q 的 完全级联 。实际上完全级联的产生依赖于一个连锁反应，起初节点 U ₄ 和 U ₇ 对节点 U ₃ 、 U ₅ 并没有足够的影响力，但当节点 U ₆ 和 U ₈ 被初用节点集影响后， U ₃ 和 U ₅ 也会被影响。然而，并不是所有的级联都会产生完全级联。接下来变更一下初用节点集，再对级联行为进行一次探究。例如，以 U ₃ 和 U ₄ 为行为 A 的初用节点集，其级联行为如图1-4所示。

● t ₀ 时刻假设 U ₃ 、 U ₄ 为采取行为 A 的初用节点集，其余节点均采取行为 B ；

● t ₁ 时刻， U ₆ 因其全部邻居为 A 行为而转向 A 行为， U ₁ 有比例2/3＞3/7的邻居为 A 行为而转向 A 行为，其余节点仍为 B 行为；

● t ₂ 时刻， U ₂ 因为有比例2/3＞3/7的邻居为 A 行为而转向 A 行为，其余节点为 B 行为；

● 此后，级联停止， U ₁ 、 U ₂ 、 U ₃ 、 U ₄ 、 U ₆ 采取 A 行为， U ₅ 、 U ₇ 、 U ₈ 仍保持 B 行为。

经过两步之后，级联停止， U ₅ 、 U ₇ 和 U ₈ 组成的“小团体”仍然保持 B 行为。从图1-4能够看到一个网络中的密集区域可以阻止一个新行为或者一项新事物的传播。 A 行为可以在节点 U ₁ 、 U ₃ 、 U ₄ 和 U ₆ 构成的小社区内扩散传播，然而却无法进入 U ₅ 、 U ₇ 和 U ₈ 的小社区，最终使得 A 行为同 B 行为一起在网络中共存。

1.2.2 网络聚簇对级联的影响

了解了级联的形成过程之后，现在进一步讨论到底有哪些因素会导致级联行为停止运行。图1-4中似乎揭示网络中的密集区域可能会阻碍完全级联行为的发生。借鉴同质现象中的知识，同质性是否会成为级联的障碍？

为了对网络中的“密集区域”进行量化，定义“ 聚簇 ”的概念如下 ^[22] ：

若一个节点集合中的每个节点至少有比例为 q 的网络邻居也属于该节点集合，则称该节点集为密度为 q 的聚簇。

例如，图1-5中节点 U ₁ 、 U ₂ 、 U ₃ 、 U ₄ 构成了一个密度为2/3的聚簇，同样， U ₅ 、 U ₆ 、 U ₇ 、 U ₈ 也构成了一个密度为2/3的聚簇。聚簇中的每个节点都有一定比例的邻居也在聚簇中，这表明结构上的聚簇实际上代表了一种“凝聚力”。然而，同一聚簇中的节点并非一定有某种相似性，例如，某个社区中的居民并没有什么共同的特征，只是因为居住地相接近。同时也说明每个节点都处在密度为1的聚簇中，另外，两个密度为 q 的聚簇的交集也是一个密度为 q 的聚簇。 以上均说明网络中的聚簇可以以不同的规模并立存在 。

图1-5的例子提示网络中的聚簇可能是导致级联成功或失败的因素，本质上当级联遇到密度较高的聚簇时便会停止，并且这也是级联停止的唯一原因 ^[21] 。为了精确描述这一性质，给出如下断言 ^[22] ：

考虑网络中一个采用行为 A 的初用节点集，其他节点以门槛值 q 采取行为 A ，则如果网络其他节点中包含一个密度大于（1- q ）的聚簇，则该初用节点集不能形成一个完全级联；如果一个初用节点集不能形成一个完全级联，并且门槛值为 q ，则网络其他节点中一定包含一个密度大于（1- q ）的聚簇。

分别对以上两个断言进行证明：

1）如果网络其他节点中包含一个密度大于（1- q ）的聚簇，则该初用节点集不能形成一个完全级联。

欲证明初用节点集不能形成完全级联，只需证明聚簇中的所有节点不会选择行为 A ，如图1-6 a。利用反证法，假设聚簇中存在节点 U 选择 A 。

U 是否选择 A 取决于已经选择 A 的节点集，因为 U 是目标聚簇中第一个选择 A 的节点，则在 U 决定转向 A 时，只有在聚簇外的节点选择行为 A ；因为该聚簇的密度大于（1- q ），则 U 有比例大于（1- q ）的邻居与 U 在同一聚簇，小于 q 的邻居节点不属于该聚簇；因为小于 q 的邻居节点是应该选择行为 A 的节点，不符合门槛规则，它们不能选择行为 A ，与条件产生矛盾，因此假设不成立，原假设的反面成立，聚簇中的所有节点不会选择行为 A ；综上所述，如果网络其他节点中包含一个密度大于（1- q ）的聚簇，则该初用节点集不能形成一个完全级联，证毕。

2）如果一个初用节点集不能形成一个完全级联，并且门槛值为 q ，则网络其他节点中一定包含一个密度大于（1- q ）的聚簇。

考虑行为 A 的传播过程，从初用节点集开始到级联停止，网络中仍然存在节点采用行为 B ，如图1-6 b所示。设 N 是级联停止时采用 B 的节点集，只需证明 N 的密度大于（1- q ）；任取 N 中的一个节点 V ，因为 V 不会采取 A 行为，那么 V 的邻居中采取 A 行为的比例一定小于门槛值 q ，即 V 的邻居中采取 B 行为的比例大于（1- q ）；因为整个网络中所有采取 B 行为的节点都属于 N ，因此 V 的邻居中属于 N 的比例一定大于（1- q ）；由于节点 V 是 N 中的任意一个节点，则如果一个初用节点集不能形成一个完全级联，并且门槛值为 q ，则网络其他节点中一定包含一个密度大于（1- q ）的聚簇，证毕。

通过以上证明可以得出结论 聚簇是级联的唯一障碍，无论何时当网络中的级联行为停止时，一定存在一个聚簇阻挡级联的继续进行 。那么级联的能力到底有多大？实际上， 网络的级联能力不可能超过1/2 。为了证明这一结论，只需证明：当门槛值 q ＞1/2时，任意网络结构中，一个有限的初用节点集均无法实现完全级联。

假设 N 是行为 A 的一个初用节点集，以大于1/2的门槛值进行传播。随着时间步的推移，网络中可能有越来越多的节点转向行为 A ，那么在某个时间步状态下，网络中一定存在三种类型的边： A - A 边、 A - B 边、 B - B 边。令 A - B 边组成的集合为 S ，若 S 的大小随着行为 A 的传播而严格递减，则足以说明行为 A 不会形成完全级联。因为 A 的初始行为节点集是有限的，每个初始节点仅有有限的邻居节点，则 S 的大小一定会减为0，即只有有限的节点转向 A 。详细的证明过程请自行完成。 P9AK8e9XGm8pvZpTNvsUgbHV2QWcFMkvZh/UWhbftkO4HDkm/obqTlaE/oteQYeD