2.1 递进性影响力传播模型的基本概念

由第1章的分类可知，递进性模型也可以有单实体或多实体、二值状态或多值状态、离散时间或连续时间等多种可能模型。本章集中介绍影响力传播的最基本模型——单实体二值状态离散时间递进性模型。这类模型是其他拓展模型的基础。众多的算法问题也都是围绕这类基础模型的。后续章节会依次介绍在影响力基础模型之上的影响力最大化算法、其他影响力传播模型及其他影响力模型之上的优化问题等。

本章侧重于介绍各个模型的准确数学描述，比较它们之间的不同，给出它们的基本性质，并讨论它们可能的适用情形。影响力传播模型还有一些重要的性质，如次模性，其与影响力最大化密切相关。本章的第6节会重点介绍传播模型的次模性。

在单实体二值状态传播中，每个结点v在每个时刻t的状态有0和1两种状态。为方便描述，通常将0状态描述为不活跃（Inactive）状态，1状态描述为活跃（Active）状态。不活跃状态表示该个体还没有接受对应实体（信息、想法或产品），而活跃状态表示该个体已经接受对应的实体。结点从不活跃状态变为活跃状态表示该结点接受了对应实体，我们称之为结点被激活（Activated）。在本章中，我们考虑单实体在离散时间下的传播。在这样的模型中，传播过程在开始时某些结点处于活跃状态，被称为种子结点，而其他结点处于不活跃状态。然后从种子结点出发，更多的结点被激活为活跃结点。具体的激活过程由不同的传播模型来表述。

在单实体二值状态模型中，用St表示在时刻t≥0时图中活跃结点的集合。其中S0是种子结点集合。对于离散时间模型，后续活跃集合用S1, S2, S3, B表示，这些集合是由传播模型和给定种子集合S0确定的随机集合。用S∞表示最终被激活的结点集合。由于本章中我们考虑递进性模型，所以有，而且因为活跃集合只能增长有限次，传播过程最后一定会稳定于一个集合S∞。通过这些活跃集合，可以定义重要的影响力扩展度（Influence Spread）的概念。

定义2.1 （影响力扩展度）。在单实体二值状态递进性模型中，一个种子集合S0在时刻t≥0的影响力扩展度是时刻t活跃结点个数的期望值，用表示，即，其中期望是对传播中的所有随机性取期望，即对传播模型中的随机元ω取期望，因此也可用作为更完整的表述。种子集合S0的（最终）影响力扩展度是最终被激活结点的个数，用表示，即。

在本书研究的传播模型中，作为惯例，如果种子集合S0为空，则不会有任何结点被激活，传播不会发生，也就是说我们认为种子集合的选取由外在因素决定（在某些扩展模型中种子集合可以由外在因素随机产生），而一旦种子集合确定，传播是受种子集合的影响发生的，不考虑传播在没有外在因素的情况下自发地发生的情况（作者和合作者在近期工作中确实考虑了结点在没有种子影响下自激活的情形[1]，但这样的模型不在本书中进一步讨论）。另外在本章介绍的基本模型中，我们不考虑结点间传播的延迟。被激活的结点对未被激活结点的影响在下一时刻立即发生，而且影响的随机结果会立即体现，不会分几步完成。在这种情况下，如果从任意时刻t到下一时刻t+1活跃结点集合没有发生变化，即St=St+1，则之后活跃结点集合也不会再发生变化，传播就此结束。这意味着激活集合序列必然一开始严格递增，到某一时刻就不再变化。因为图中有n=| V |个结点，而时不会传播，所以严格递增最多发生在前n-1步，换句话说我们得到Sn-1=S∞，这种离散时间递进性模型为即时传播模型。

对于在时刻t≥1被激活的结点集合St，严格地说是由种子集合S0和随机传播模型确定的一个随机集合。当需要明确表述St与S0的关系时，用表述St，即从种子集合S0出发在t时刻被激活结点的集合。我们用表示以S0为种子集合时最终被激活结点的集合。在本章后面的叙述中我们一般用St表示，但在其他章节中有用和表达的必要。

在给定种子集合S0时，用apt (S0, v )表示S0在时刻t之内激活结点v的概率，即，其中Xv,t∈{0，1}是v在时刻t的状态；用ap(S0, v )表示S0在传播结束时激活v的概率，即ap(S0, v )=apn-1(S0, v )。基于数学期望的线性性质，引理2.1指出了种子集合的影响力扩展度就是种子集合激活结点概率的和。

引理2.1对于任意种子集合S0，在任意时刻t≥0，有，。

证明：因为，而，所以根据数学期望的线性性质，有。

影响力最终扩展度的结果可以由得到。

在后面的分析讨论中，我们会利用引理2.1将种子集合的影响力扩展度转化为结点激活概率加以讨论。

在影响力传播模型中，提出最早、研究最深入、应用最广泛的是独立级联模型（Independent Cascade Model）和线性阈值模型（Linear Threshold Model）[2]，下面首先介绍这两个模型。