IM

The Independent Cascade Model (IC Model) IC模型，即独立级联模型。 $v$表示图$G=（V,E)$中的一个节点（用户），$v$可以被它的传入邻居（incoming neighbor）以一个影响概率$p_{u,v}$的情况下独立激活。 在时间步为0的时候，给定一个种子集（seed set）$S$,即$k$个已经是激活着的节点。 在时间步$t$时，每一个激活状态的节点$u$将会以一定的概率$p_{u,v}$来激活每一个和它连接的未激活节点$v$。时间步$t$之后，如果$v$依然是未激活状态，那么$v$将无法再次被$v$激活。结束一次上述过程后，$u$保持激活状态并且失去激活其他节点的能力。当网络$G$中没有其他节点可以被激活时，扩散过程结束。 值得注意的是，当$S$是原始的激活节点集，那么上述随机激活过程完成后，所得到的影响分布（Influence Spread）是所期望的激活节点数。 The Linear Threshold Model (LT Model) LT模型，即线性阈值模型。基本思想是，如果一个未被激活的节点有足够的传入邻居是激活状态的，那么该节点可以被激活。 形式上， 在图$G$中每条边$e=(u,v) \in E$有一个权重$b_{u,v}$。 我们定义$\mathcal{N}_I (v)$表示节点$v$的传入节点， 满足$\sum_{u \in \mathcal{N}_I (v)} b_{u,v} \leq 1$, 即所有$v$的传入节点与$v$组成的边的权重只和小于1。 另外，每个节点$v$具有一个阈值$\theta_v$。 LT模型首先为每个节点$v$的阈值$\theta_v$在$[0,1]$上均匀随机采样。在时间步0时，设置$S$中的节点状态为激活，其他节点为未激活，然后迭代的更新每个节点的状态。 在时间步$t$时，所有$t-1$时刻是激活状态的节点依旧保持激活状态，与此同时，其他未激活的节点$v$, 如果任意一个节点$v$的激活传入邻居总权重的值至少为$\theta_v$,那么将$v$激活。 当没有节点将要被激活时，传播结束。