2.3 线性阈值模型

线性阈值模型旨在刻画传播中多个个体共同影响另一个体的情形。我们首先看它的数学表述，在线性阈值模型中，每条有向边(u, v )∈E上都有一个权重，这个权重被称为影响权重（Influence Weight）。直观上说，w( u, v )反映了u在v的所有入邻居中影响力的重要性占比，我们要求。每个结点v还有一个被影响阈值θv∈[0,1]，这个阈值在0到1的范围内均匀随机地选取，且一旦确定，在传播中不再改变。与独立级联模型一样，在0时刻有且仅有种子集合S0中的结点被激活。在之后每个时刻（t≥1），每个不活跃结点v∈ V\St-1都需要依据它所有已激活的入邻居到它的线性加权和是否已达到它的被影响阈值来判断是否被激活，即是否成立。若是，则v在时刻t被激活（v∈St）；否则，v仍然保持不活跃状态（v∈ V\ St）。当某一时刻不再有新的结点被激活时，传播过程结束。

上面的描述十分接近一般随机传播模型的框架，因此用该框架直接定义线性阈值模型（Linear Threshold Model），用θ={θv |v∈ V}表示所有结点阈值的向量。

定义2.4 （线性阈值模型）。在给定有向图G=(V, E )及每条有向边上的影响权重w( u, v )的情况下，线性阈值模型是由下列元素构成的一个随机传播模型的特例：（a）有向图G=(V, E )；（b）每个结点的状态空间Σ={0,1}；（c）由阈值向量θ={θv |v∈ V}构成的传播概率空间，即,θ的每一维都是在[0,1]中均匀采样获得的；（d）传播事件的离散时间序列{(t, v )| t=1,2,3,B,v∈ V}；（e）传播函数。种子集合。

下面通过一个例子具体解释线性阈值模型的传播。该示例与独立级联模型的示例2.1有相同的图结构和相同的结点激活顺序，但激活机制并不相同。因此读者也可以通过比较这两个例子体会两种传播模型的不同点。

示例2.2图2-2给出了线性阈值模型下一次传播的示例。在时刻0（图2-2（a）），各个结点的阈值被采样确定，以带下划线的数字显示在各个结点旁边，而且结点1和结点2被选为种子结点并被激活。在时刻1（图2-2（b）），结点1指向结点5的边权重0.4超过结点5的阈值0.2，因此结点5被激活；结点2指向结点4的边权重0.7超过结点4的阈值0.5，因此结点4也被激活；结点1和结点2指向结点3的边权重和为0.6，达到了结点3的阈值0.6，因此结点1和结点2联合激活了结点3。然而在时刻1，结点6只有一个入邻居结点2在前一时刻是活跃结点，而结点2到结点6的边权重0.4小于结点6的阈值0.7，因此在这一时刻结点6没有被激活。在时刻2（图2-2（c）），结点2、3、5指向结点6的边的权重和达到0.9，超过结点6的阈值0.7，因此结点6被激活。但是结点5没有激活结点9，因为结点5到结点9的边权重0.3没有达到结点9的阈值0.8。在时刻3，结点6也不足以激活结点7，因此传播结束。

注：每条有向边上的数字是该边上的影响权重；每个结点旁边带下划线的数字是这次传播中随机生成的该结点的阈值；原始边表示原始图中的边，尚未进行激活尝试；权重参与激活指向点的边表示这些边上的权重加在一起后超过结点阈值从而成功地激活了指向结点。

在线性阈值模型中，结点v的阈值表达了结点对一个新实体的接受倾向：阈值越高，v越不容易被影响；阈值越低，v越容易被影响。结点v的入邻居对v的影响是联合发生的：可能任何一个入邻居都不能单独激活v，但几个入邻居联合起来就可能使对v的影响力权重超过v的阈值从而激活v。比如在示例2.2中，结点2在时刻1不足以激活结点6，而在时刻2当结点2和结点3、结点5联合在一起时就足以激活结点6。这种联合影响对应了人类行为中在面对一个相对复杂的选择时（比如购买新型手机、选择移民等）经常出现的从众行为[4-5]，即一个人可能需要社交网络中多个不同的朋友或熟人都接受了一个新实体（想法、观念、产品、行为等）时，才会也接受这个新实体。这是线性阈值模型与独立级联模型相比最主要的不同点。

线性阈值模型的随机性完全是由结点被影响阈值的随机性决定的，一旦随机阈值被确定下来，后面的传播过程就是确定的。而在线性阈值模型中阈值是在0和1之间随机选取的，这反映了我们对结点阈值的不了解。然而在实际中人的被影响阈值虽然有随机性，但其应该在更窄的范围内波动。如果用更窄范围的随机阈值（比如固定阈值），会使得模型的分析和计算难度显著加大[2,6]。因此线性阈值模型在阈值选取上面临两难选择，这也是这一模型不如独立级联模型应用广泛的一个原因。关于阈值选取的问题，在下面介绍通用阈值模型时还会提及。下面先介绍线性阈值模型的一个很重要的等价模型。

由定义2.4可知线性阈值模型的随机性是由结点阈值的随机性确定的。然而，线性阈值模型还有一种基于随机活跃边图的等价模型，就像独立级联模型有一个基于活跃边图的等价定义2.3一样。与定义2.3唯一不同的是随机活跃边图的概率分布。这个基于活跃边图的等价定义对后续的研究十分重要。

针对线性阈值模型，以如下方式随机采样活跃边图。对于任意结点v∈ V，随机选取v的一条入边或不选入边，且选取入边(u, v )的概率是该边的权重w( u, v )，而不选取任何一条边的概率是。这样构成的活跃边图L是原图G的一个子图，且每个结点最多有一条入边, 即。在这样的活跃边图中，我们定义结点v的前驱predL (v )为v的唯一入邻居，如果v没有任何入邻居，则。那么我们可以将线性阈值模型对应的活跃边图的概率分布总结为

线性阈值模型可以表达为：先采样一个活跃边图L，然后在L上从种子结点出发沿出边进行传播，只要可达到的结点都被激活。这可以在随机传播模型的框架下如下定义。这个定义与独立级联模型的定义2.3几乎相同，唯一的不同点是随机活跃边图的采样概率不同。这说明两个模型遵循同样的在随机活跃边图上按可达性传播的机制，但活跃边图的性质不同。

定义2.5 （基于活跃边图的线性阈值模型的等价定义）。在给定有向图G=(V, E )及每条有向边上的影响权重w( u, v )的情况下，线性阈值模型是由下列元素构成的一个随机传播模型的特例：（a）有向图G=(V, E )；（b）每个结点的状态空间Σ={0,1}；（c）由随机活跃边图L组成的有限传播概率空间Ω，L的概率由式（2-3）给出；（d）传播事件的离散时间序列{(t, v )| t=1,2,3,B,v∈ V}；（e）传播函数，即只要结点v自己或有一个在L中的入邻居在前一时刻是活跃的，那么v在当前时刻也是活跃的。种子集合。

上面基于活跃边图的定义在表面上和基于随机阈值的定义2.4有所不同，但是两者实际是等价的。在讨论两者的等价性之前，先给出等价模型的一般定义。对于二值离散时间递进性模型，在给定种子结点集合S0的情况下，传播过程可以表示为一个集合序列，其中，集合St是在时刻t的活跃结点集合。两个二值离散时间递进性模型的等价就是指其产生这样序列的分布是一样的。

定义2.6 （二值离散时间递进性模型的等价性）。我们说两个二值离散时间递进性模型在图G=(V, E )上是等价的，如果对任意集合序列，两个模型在以S0为种子时产生这一序列（即时刻t的活跃结点集恰为St，对所有t=1,2,B,n-1）的概率都相等。

定义2.4和定义2.5等价的直观原因如下。对于任意结点v，假设在某时刻t，v的入邻居N-(v )中的一个子集已被激活。令是A中结点到v的边的权重和。根据定义2.4，如果W≥θv，v就被激活。而是在[0,1]中均匀随机选取的，因此W≥θv的概率就是W。而如果从定义2.5出发，v被激活的条件是当且仅当v随机选取的入边(u, v )满足u∈A。因为入边的选取是以权重为概率进行的，所以选得的入边(u, v )满足u∈A的概率也是。因此两个定义对于激活结点v的概率是相等的。将这个直观化的讨论加以严格化就能得到下面的等价结论。

定理2.1关于线性阈值模型的定义2.4和定义2.5是等价的。

证明：给定一个种子集合S0，要证明在两种定义下产生任意序列的概率总是相等的。

为方便起见，对于任意不在图中的边，定义w( u, v ) =0。我们很容易检验这一改动不会对定义2.4和定义2.5描述的传播过程产生任何影响。当把不在图中的边看成权重为零的边后，对结点v就不用再特别讨论它的入邻居，而只需讨论所有点即可。定义集合函数，显然。

固定一个结点集合序列，用表示产生序列的事件。先根据定义2.4计算。在给定序列的情况下，对任意t=1,2,B,n-1，考虑任意v∈St\St-1。根据定义2.4，当且仅当v的阈值满足时，v恰好出现在St\St-1而不在St-1中。这里为方便起见，规定，。因为是在[0,1]中均匀随机选取的，所以上面条件发生的概率是fv( St-1)-fv( St-2)。我们再考虑最终没有被激活的点。当且仅当时，结点u没有被激活，而这个条件发生的概率是。又因为所有结点的阈值都是独立随机选取的，所以得到序列发生的概率是

下面我们再按定义2.5推导。在给定序列的情况下，对任意t=1,2,B,n-1，考虑任意v∈St\St-1，即所有在St中但不在St-1中的元素。根据定义2.5，随机选取的v恰好出现在St\St-1而不在St-1中的条件是当且仅当其入边(u, v )满足（如果u∈St-2，那么u会在时刻t-1或之前就被激活，而如果，u在时刻t结束时也不会被激活）。条件u∈St-1\St-2发生的概率是。再考虑最终没有被激活的结点，结点u没有被激活的条件是当且仅当没有随机选取的入边或随机选取的u的入边(x, u )满足，而这个条件发生的概率是。因为每个结点的入边是独立随机选取的，所以综合上面讨论，可以得到序列发生的概率仍然是式（2-4）。因此定义2.4和定义2.5是等价的。

上面的引理说明线性阈值模型也可以像独立级联模型一样有一个基于活跃边图上可达性的定义。这在后面的模型性质分析和算法设计中都很有用处。

从定义上，我们能理解独立级联模型和线性阈值模型是不同的。在独立级联模型中，影响力在各条边上独立传播，而在线性阈值模型中影响力是在若干入邻居的联合作用下共同完成的。那么对于一个独立级联模型，有没有可能通过合理配置参数用一个线性阈值模型来表达它呢？或者反之用某一个独立级联模型来表达一个线性阈值模型呢？回答是否定的，即在一般情况下这两个模型不能互相表达，它们是不等价的。下面的示例给出了一个不等价的简单情况。

示例2.3图2-3给出了一个简单的3个结点的有向图，其中结点1和结点2分别有一条有向边指向结点3。对于这个图上的一个独立级联模型，设边(1,3)有影响概率p(1,3)，边(1,2)有影响概率p(1,2)。同样地，对于这个图上的一个线性阈值模型，设边(1,3)有影响权重w(1,3)，边(1,2)有影响权重w(1,2)。下面讨论如果要使这个图中的独立级联模型和独立阈值模型等价，这些影响概率和影响权重必须满足什么样的要求。首先，当结点1是唯一的种子时，在独立级联模型下，结点1激活结点3的概率是p(1,3)；在线性阈值模型下，结点1激活结点3的概率是w(1,3)。因此，要使两个模型等价，只能使p(1,3)=w(1,3)。同理，当结点2是唯一种子时，要保证结点2对结点3的激活概率相等，只能使p(2,3)=w(2,3)。现在我们考虑结点1和结点2同为种子结点，在独立级联模型下，两个种子结点试图独立激活结点3，因此结点3被激活的概率是1- (1-p(1,3))(1-p(2,3))。在线性阈值模型下，两个结点的权重合起来与结点3的阈值进行比较，结点3被激活的概率是w(1,3)+w(2,3)。因为已知p(1,3)=w(1,3)和p(2,3)=w(2,3)，所以当且仅当p(1,3)=0或p(2,3)=0时概率1- (1-p(1,3))(1-p(2,3))等于概率w(1,3)+w(2,3)。因此，只要p(1,3)和p(2,3)都不为0，结点1和结点2共为种子结点时激活结点3的概率在两种模型上就不会相同。在一般情况下，图2-3不存在等价的独立级联模型和线性阈值模型。

图2-3虽然只有3个结点，但它反映了独立级联模型和线性阈值模型的实质区别。图2-3的这种多点指向一点的结构是实际图中经常出现的结构，因此在一般的实际图中独立级联模型和线性阈值模型也是不等价的。

与独立级联模型中关于影响力延迟的讨论类似，在线性阈值模型中，我们也可以允许一个已被激活的结点u将它对结点v的影响权重延迟一点时间再施加在结点v上。只要我们关心的是最终的激活结点集合S∞或最终的影响力扩展度，引入延迟与否对结果没有影响。这一点在基于活跃边图的等价定义中更易于理解。在一个边上的延迟，可以理解为该边被延迟加入活跃边图中。但我们只关心最终边图的可达性，因此活跃边的延迟加入对结果没有影响。

备注2.1我们还要提醒读者，对线性阈值模型的表述在文献中不太一致。本节中的描述和最早介绍线性阈值模型的Kempe等人[2]的描述是一致的。其中各结点的阈值是在[0,1]中均匀随机选取的。而在后续的文献中，有些将对阈值的固定选取或其他选取方法也称作线性阈值模型。这样的描述只采纳了在描述模型中的权重线性相加的部分，然而这样的模型与均匀随机选取阈值的线性阈值模型有截然不同的性质。为了避免混淆，我们着重强调在本书中的线性阈值模型要求阈值是在[0,1]中均匀随机选取的。而对于其他的阈值选取方法，在后面的通用阈值模型中再加以讨论。我们也建议读者在自己的工作中表述线性阈值模型时，依照本书及Kempe等人[2]的描述明确表明阈值的均匀随机选取方法，如果用别的阈值选取方法，请给它取一个有别于线性阈值模型的名称。这样可以避免产生歧义和误解。