1.2 级联与聚簇

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

1.2.1 级联行为下的协调博弈

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

●若U1与U2均采取A行为，则它们的收益均为ra＞0；

●若U1与U2均采取B行为，则它们的收益均为rb＞0；

●若U1与U2采取不同的行为，则它们的收益均为0。

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

图1-2 基本网络协调博弈模型

●若pnra≥（1-p）nrb，即时，采取行为A收益更大；

●若pnra＜（1-p）nrb，即时，采取行为B收益更大。

令q=rb/ra+rb表示一个门槛值，即当每个用户周围有比例为q的邻居采取行为A时，用户也应该采取该行为。以门槛值来分析该博弈结果，当q较小时，说明ra≫rb，则行为A更具吸引力，仅需小部分邻居采取行为A目标用户就会转向A；当q较大时，说明ra≪rb，则行为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行为共存的状态。令ra=4，rb=3，即行为A的收益是行为B的4/3倍。根据门槛值计算公式q，一个节点至少有q=rb/（ra+rb）=3/7比例的邻居采取A行为，该节点才会从行为B转向A。该过程如图1-3所示（实线圈为采取行为A的节点，虚线圈为采取行为B的节点）。

●t0时刻假设U4、U7为采取行为A的初用节点集，其余节点均采取行为B；

●t1时刻，U6和U8因为有比例1/2＞3/7的邻居为A行为而转向A行为，其余节点仍为B行为；

●t2时刻，U3和U5因为有比例2/3＞3/7的邻居为A行为而转向A行为，其余节点仍为B行为；

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

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

图1-3 以U4、U7为初用节点的级联行为图

图1-4 以U3、U4为初用节点的级联行为图

●t0时刻假设U3、U4为采取行为A的初用节点集，其余节点均采取行为B；

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

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

●此后，级联停止，U1、U2、U3、U4、U6采取A行为，U5、U7、U8仍保持B行为。

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

1.2.2 网络聚簇对级联的影响

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

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

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

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

图1-5 聚簇实例

图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-6 级联与聚簇关系[22]

通过以上证明可以得出结论聚簇是级联的唯一障碍，无论何时当网络中的级联行为停止时，一定存在一个聚簇阻挡级联的继续进行。那么级联的能力到底有多大？实际上，网络的级联能力不可能超过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。详细的证明过程请自行完成。