独立级联模型&线性阈值模型

预备知识

• 一个社交网络描述成一张有向图G，其中V是节点的集合，$E\subseteq V*V$E⊆V∗V是有向边的集合。
• 每一个节点$v\in V$v∈V代表一个社交网络中的人，每一条边$(u,v)\in E$(u,v)∈E代表节点$u$u到节点$v$v的影响力关系。
• 边是有向的，表明影响力是有方向的。对于一条有向边$(u,v)\in E$(u,v)∈E，它叫做节点$u$u的出边，节点$v$v的入边，节点v是节点u的一个出邻居，而节点u是节点v的一个入邻居。一个节点v的所有出邻居的集合用$N^{+}(v)$N+(v)表示，所有入邻居的集合用$N^{-}(v)$N−(v)表示。
• 通常情况下，针对某一具体传播的实体（信息、想法、产品等），将图中的每个点描述为两种可能状态：不活跃（inactive）和活跃（active）。不活跃状态表示该个体还没有接受对应实体（信息、想法或产品），而活跃状态表示该个体已经接受对应的实体。节点从不活跃状态变为活跃状态表示该节点接受了对应实体，也称之为被**。
• 影响力传播模型用来刻画影响力在社交网络中的传播模式，也即社交网络中节点的状态如何影响其相邻节点的状态，并造成某一状态（通常指活跃状态）在网络中扩散传播。
• 传播模型分很多种类。其中的离散时间模型将影响力传播和节点的状态转换规定在离散的时间点发生，以便于计算和分析。我们要介绍的模型就是离散时间模型。

独立级联模型

如上图所示，在独立级联模型中，每一条图中的有向边(????,????)∈????都有一个对应的概率值p(????,????)∈[0,1] 。

独立级联模型下的动态传播过程在离散时间点以如下形式完成：

1. 在????=0时刻，一个预先选好的初始集合$s_0$s0​首先被**，而其他节点都处于不活跃状态。这个初始节点集合被称作种子节点集合。
2. 对任何时刻$t\geq1$t≥1，用$s_t$st​表示到这个时刻为止所有活跃点的集合。对任何一个在上一时刻刚被**的节点????∈$s_{t-1}$st−1​ \ $s_{t-2}$st−2​，节点????会对它的每个尚未被**的出邻居节点v∈$N^+(v)$N+(v) \ $s_{t-1}$st−1​，尝试**一次，而这次尝试成功的概率为$p(u,v)$p(u,v)，且这次**尝试与所有其他的**尝试事件相互独立。如果尝试成功，则节点????在时刻????被**，即v∈$s_{t}$st​ \ $s_{t-1}$st−1​；如果尝试不成功，且节点????的其他入邻居也未在时刻????成功**节点????，则节点????在时刻 ????仍为不活跃状态，即v∈$V$V\ $s_{t}$st​。
3. 当在某一时刻不再有新的节点被**时，传播过程结束。

实例

上图给出了独立级联模型一次传播结果的示意。
实心方框表示种子节点，空心方框表示传播结束时被**的节点；圆圈表示未被**的节点；实线边表示影响力在该边上成功传播，虚线边表示影响力未在其上传播；边上的数字是该边上影响力传播的概率。
在t=0时刻，种子节点1和2被**；在t=1时刻，节点1、2分别**节点5、4，并且同时**了节点3；在t=2时刻，节点5成功**节点6但没有成功**节点9；在t=3时刻，节点6没有成功**节点7；传播至此结束，节点7、8和9没有在这次传播中被**。
任何一个节点u对它的任何一个出邻居v只有一次尝试**机会，且发生在节点u刚被**的下一时刻。一个节点u在何时尝 试**另一节点v或者是否多次尝试 ***节点v并不重要，只要用p(u,v)表示节点u多次尝试**节点v的总成功概率。

线性阈值模型

• 在线性阈值模型中，每条有向边(????,????)∈????上都有一个权重w(????,????)∈[0,1] 。
• 直观上说， w(????,????)反映了节点???? 在节点v的所有入邻居中影响力的重要性占比。
• 每个节点v还有一个被影响阈值????????∈[0,1]，这个阈值在0到1的范围内均匀、随机地选取，一旦确定在传播中就不再改变。
• 与独立级联模型一样，在t=0时刻有且仅有种子集合$s_0$s0​中的节点被**。
• 在之后每个时刻????≥1，每个不活跃节点$v∈V$v∈V \ $S_{t−1}$St−1​都需要依据它所有已**的入邻居到它的线性加权和是否已达到它的被影响值来判断是否被**；若是，则节点v在时刻t被**(????∈????????)；否则，节点v仍然保持不活跃状态。
• 当某一时刻不再有新的节点被**时，传播过程结束。