2.2 独立级联模型

在独立级联模型中，图中的每一条有向边(u,v)∈E都有一个对应的概率值p( u,v)∈ [0,1]（如图2-1所示）。直观上说，p( u,v)表示当u被激活后u通过边(u,v)独立激活v的概率，称p( u,v)为影响概率（Influence Probability）。

定义2.2 （独立级联模型）。独立级联模型是由有向图G=(V,E)及每条有向边上的影响概率p( u,v)唯一确定的。独立级联模型下的动态传播过程从种子结点集合开始，在离散时间点t=0,1,2,B以如下形式完成：在t=0时刻，集合S0中的结点被激活，而其他结点都处于不活跃状态。这个初始结点集合被称作种子结点集合（Seed Set）。对任何时刻t≥1，用St表示到这个时刻为止所有活跃点的集合。在任何时刻点t≥1，首先St-1中的结点都在St中；其次，对任何一个在上一时刻刚被激活的点（设），u会对它的每个尚未被激活的出邻居尝试激活一次，而这次尝试成功的概率为p( u,v)，且这次激活尝试与所有其他的激活尝试事件相互独立。如果尝试成功，则v在时刻t被激活，即；如果尝试不成功，且v的其他入邻居也未在时刻t成功激活v，则v在时刻t仍为不活跃状态，即。当在某一时刻不再有新的结点被激活时，传播过程结束。

下面给出一个独立级联模型在一次传播中的示例，便于大家直观理解这一模型。

示例2.1图2-1给出了独立级联模型一次传播结果的示意图。在0时刻（图2-1（a）），结点1和结点2被选为种子结点并被激活。在时刻1（图2-1（b）），结点1成功激活结点3和结点5，同时结点2也成功激活结点3和结点4，但结点2没有成功激活结点6。在时刻2（图2-1（c）），虽然结点3激活结点6的尝试也没有成功，但结点5成功激活结点6；不过结点5没有激活结点9。在时刻3（图2-1（d）），结点6试图激活结点7，但没有成功，本次传播结束。

注：每条有向边上的数字是该边上的影响概率。原始边表示原始图中的边，尚未进行激活尝试；活跃边表示影响力在该边上成功传播（这些边也是传播中的活跃边）；阻断边表示影响力试图通过该边传播但没有成功（这些边是传播中的阻断边）。

独立级联模型是随机传播模型（定义1.1）的一个特例。状态集∑={0,1}中，0表示不活跃，1表示活跃。传播事件的序列是标准的离散时间序列{(t,v)| t =1,2,3,B, v∈ V}。传播概率空间Ω是所有边(u,v)∈E以独立的概率p( u,v)被选中的所有组合，这些随机事件的组合表达了任何一点u能激活它的任何一个出邻居v的所有可能的随机性。因为在每条边(u,v)上，u激活v的尝试只进行一次，所以上面随机事件的组合也表达了整个传播过程中可能发生的所有随机事件。更准确地说，令L是图G的一个子图，L的结点集合与G相同，而边集是E的一个子集。为便于区分，用E( G )和E( L )分别表示图G中的边和图L中的边。子图L发生的概率就是在L中的边都被选中而不在L中的边都没被选中的概率，即。我们称L为一个（随机）活跃边图（Live-Edge Graph），L中的每一条边被称为活跃边（Live Edge），而不在L中的边被称为阻断边（Blocked Edge），传播可以通过活跃边进行，但不能通过阻断边进行。在后续的模型分析和算法设计中，活跃边图是一个十分重要的概念和分析手段。在这里作为介绍模型的传播概率空间，我们自然引入了这一概念。那么传播概率空间（或可能世界空间）Ω就是所有活跃边图构成的有限离散空间，其中每一个活跃边图L就是一个随机元（或可能世界），其概率是

最后，按照定义1.1，给出传播函数Fv的定义。对于一个事件，用表示事件的示性函数，即如果事件为真，，如果事件为假，。则可以定义独立级联模型的传播函数为。这个函数的意思是说，如果前一时刻结点v的某一个在L中的入邻居u处于活跃状态（即u是活跃的且从u到v的边也是活跃边），那么在这一时刻v也是活跃的。或者v在前一时刻已经是活跃的，那么v在当前时刻仍会保持活跃。这个传播函数虽然没有显式地给出传播发生或激活的时刻，但根据随机传播模型的一般定义，可以得知传播是在u被激活后的下一个整数时刻点发生的。综上，我们可以给出独立级联模型在一般随机传播模型框架下的基于活跃边图的等价定义。

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

对于在边(u,v)上u是否激活v的随机事件，在定义2.2的描述中是在结点u被激活后的下一时刻发生的。而根据定义2.3，所有传播概率空间Ω的随机元（即活跃边图L）是在传播之前事先选定的。但根据随机事件分析中常用的延迟决定原则（Principle of Deferred Decision），随机事件是事先决定好的还是在需要的时刻再决定的没有区别。因此上述基于随机传播模型的定义2.3和定义2.2给出的对独立级联模型的直接描述是等价的。延迟决定原则在分析随机传播模型中会经常用到。定义1.1给出的随机传播模型的一般定义也是基于这一原则将所有随机事件集中用事先选定的随机元ω∈Ω来表述的。

如前所述，我们用S∞表示在传播过程结束时所有活跃结点的集合，即最终活跃点集。因为独立级联模型是一种即时传播模型，根据本章开始的讨论可知Sn-1=S∞。由于传播过程是随机过程，因此S∞是随机集合，并由种子集合S0和活跃边图L联合决定。对于一个最终活跃的非种子结点v∈S∞\ S0，不论根据定义2.2，还是定义2.3，都可以得出存在一个整数时刻t≥1，v在时刻t被激活，而必然是在时刻t-1，v的某个入邻居u被激活，且(u,v)是活跃边（(u,v)∈L），称v被u激活。激活v的结点可能不止一个，它们在同一时刻t同时激活v。在这里不区分具体是哪个结点激活了v。比如在图2-1（b）中表示的1时刻，结点1和结点2同时激活结点3。

引理2.2给出了S∞与S0和L的关系。在任何一个有向图G=(V,E)中，用表示从结点集合S沿图G中有向边能达到的结点集合，即Γ(G,S)={ v |存在G中路径(v0, v1 ,B,vk),v0∈S, vk=v }，根据定义。

引理2.2在由种子集合S0和随机活跃边图L决定的独立级联模型的一次传播中，最终活跃点集S∞是L中所有从S0中结点出发可以达到的结点的集合，即。

证明：首先证明。对任意，根据定义，存在L的路径(v0, v1 ,B,vk)，使得，vk=v。由独立级联模型的定义2.3可知，v0在0时刻被激活，即；v1在1时刻被激活，因为v0到v1的边是活跃的，即(v0, v1 )∈E( L )。为了熟悉定义，也可严格地从定义2.3做如下推导：，因为，且所以。以此类推，可得v=vk在时刻k一定是活跃的。因此v∈S∞。反之，再证明。对任意最终活跃结点v∈S∞，一定能找到一个激活序列(v0, v1 ,B,vk)，k≥0，使得v0∈S0，vk=v，vi-1激活vi，对所有的i=1,2,B,k，而这意味着(vi-1,vi )∈L。因此(v0, v1 ,B,vk)是L中的一个路径，从而v=vk可以从一个种子结点v0∈S0在L中到达，即v∈Γ(L, S0)。正反两方面综合，得到S∞=Γ(L, S0)。

根据引理2.2，可以得出下面关于影响力扩展度的重要结论。

引理2.3在独立级联模型中，种子集合S0的影响力扩展度由式（2-2）给出。

其中，Pr(L )由式（2-1）给出，求和项中L遍历所有活跃边图。

引理2.3将活跃边图及其上的可达性与影响力扩展度联系了起来。由于活跃边图可能有很多个，因此式（2-2）并不能作为计算影响力扩展度的有效算法，但是它对后面进一步分析模型的传播性质有重要作用。

注意到在独立级联模型中，任何一个结点u对它的任何一个出邻居v只有一次尝试激活机会，且发生在u刚被激活的下一时刻，这看起来似乎是模型的一个局限。比如，也许我们希望允许u对v的激活时间有一定的延迟，或者允许u对v尝试多次激活。但如果我们只关心最终活跃结点集合S∞和最终的影响力扩展度，一个结点u在何时尝试激活另一结点v或者是否多次尝试激活结点v并不重要，只要最终结点u能够激活结点v，就相当于有向边(u, v )是活跃的，而引理2.2同样适用。因此，只要p( u, v )表示u多次尝试激活v的总成功概率，就可用基本的独立级联模型等价表达最终活跃结点集合S∞的分布和影响力扩展度，无须显式地在模型里加入激活延迟或多次激活的情形。

当然，在有些情形中还要考虑中间某时刻的活跃结点集合或影响力扩展度，比如在最多t时刻内的影响力扩展度，这时加入激活延迟或多次激活就会造成不同的结果。在这种情况下，就可根据需要对独立级联模型做适当扩展以使它更适合实际情况，比如在研究t时刻内的影响力最大化时，作者与合作者引入了见面概率（Meeting Probability）来刻画在一条边上可能的传播延迟[3]（参见第5.1节）。

独立级联模型强调影响力在人与人的关系中独立传播，它抽象概括了社交网络中人与人之间独立交互影响的行为。一个人对另一个人影响力的强弱用这两者之间有向边上的概率来描述，而且在这条边上的传播不受其他关系和其他人对实体接受情况的影响。很多简单实体，如新消息在在线网络中的传播或新病毒在人际间的传播，就比较符合独立传播的特性[4]：一个个体接受一个新消息或被感染一个新病毒一般是由接受方和传播方两方面的交互作用决定的，与网络中其他人是否接受了该消息或是否被感染了该病毒关系不大。因此对这类传播，独立级联模型较为合适。在基于实际数据的影响力学习中，独立级联模型被初步验证是有效的。因此独立级联模型是目前研究最广泛且最深入的模型，很多更复杂的传播模型也是基于独立级联模型的。