下载掌阅APP，畅读海量书库
立即打开
网络级联模型能够表征级联传播的机制，对于理解和解释现实生活中的级联现象至关重要。本节主要介绍独立级联模型（Independent Cascade Model，ICM）与线性阈值模型（Linear Threshold Model，LTM） [23-24] ，前者强调网络中的节点依概率被邻居节点激活，而后者强调每个网络节点基于已做出相同决策的邻居节点数量或所占比例（阈值）决定是否被激活。作为典型的级联模型，现有工作均基于ICM与LTM进行改进和优化。
2001年，美国哥伦比亚大学教授雅各布·戈登堡在研究市场营销规律时提出了独立级联模型。该模型本质上是一个概率模型，节点之间的影响程度由概率 p 决定。以社交网络信息传播为例，构造有向图 G =〈 V，E 〉，其中 V 表示网络用户节点集合， E ⊆ V × V 表示有向边集合，每个节点 v ∈ V 表示一个用户。每条边（ u，v ）∈ E 表示用户 u 到用户 v 的影响力关系， u 为 v 的一个入邻居， v 为 u 的一个出邻居。令 N + （ v ）表示节点 v 的所有出邻居集合， N - （ v ）表示节点 v 的所有入邻居集合。
针对网络中所有的传播实体（信息、观点等），有向图 G 将其抽象为激活节点和非激活节点两类。激活节点表示该节点已经接收了对应的传播实体，而非激活节点表示该节点未接收传播实体。独立级联模型对激活节点集合与非激活节点集合描述的传播过程进行建模，并存在如下基本假设：
● 节点 u 以概率 p （ u，v ）（0＜ p ＜1）尝试激活其邻居节点 v ，且 p （ u，v ）与其他试图激活节点 v 的节点相互独立；
● 节点 u 只具备一次尝试激活邻居节点的机会，无论是否激活成功，该节点不再具备影响力（但仍然保持自身的激活状态）。
根据基本假设，独立级联算法描述如下：
1）给定初始种子节点集合 S 0 ，任意节点 u ∈ S 0 均处于激活状态，其他节点 v ∈ V \ S 0 处于非激活状态。
2） t 时刻（ t ≥1），新近被激活节点 m ∈ S t -1 \ S t -2 （ S t 表示截止到时刻 t 所有激活节点构成的集合）以概率 p （ m，n ）尝试激活其邻居节点 n ∈ N + （ m ）\ S t -1 ；若存在多个已激活节点可以对节点 n 产生影响，那么这些节点将以任意顺序试图激活节点 n 。如果节点 n 被成功激活，则 t +1时刻 n 转入已激活节点集合，即 n ∈ S t \ S t -1 ；否则，节点 n 仍保持非激活状态，即 n ∈ V \ S t 。
3）迭代运行至网络中不再出现新的被激活节点，传播过程停止。
如图1-7所示，以实心圆表示激活节点，空心圆表示非激活节点，有向边上的值表示成功激活目标节点所需的概率值。为便于理解节点的激活过程，假设已激活节点尝试激活邻居节点时系统生成一个随机数，若概率值大于该随机数，则激活成功，否则激活失败。 t =0， U 0 为种子节点，处于激活状态； t =1， U 0 分别以0.5、0.4的概率尝试激活 U 1 、 U 2 ，由于随机数0.4＜0.5，则 U 1 被激活，同理由于随机数0.6＞0.4，则 U 2 未被激活； t =2， U 1 以0.3的概率尝试激活 U 2 ，由随机数0.2＜0.3，则 U 2 被激活； t =3， U 2 分别以0.3、0.2的概率尝试激活 U 3 、 U 4 ，由于随机数0.1＜0.3、0.6＞0.2，则 U 3 被激活、 U 4 未被激活； t =4， U 3 以0.2的概率尝试激活 U 4 ，然而随机数0.4＞0.2， U 4 仍未被激活，此时整个系统中无新增激活节点，迭代结束。
图1-7 独立级联模型有向图示例
此外，独立级联模型同样可应用于无向图中，算法与有向图相同而激活概率满足 p （ u，v ）= p （ v，u ）。以图1-8为例， t =0时， V 0 作为种子节点处于激活状态； t =1， V 0 分别以0.5、0.8的概率尝试激活 V 1 、 V 2 ，由于随机数0.4＜0.5则 V 1 被成功激活，而随机数0.9＞0.8，则 V 2 未被激活； t =2， V 1 以0.4的概率尝试激活 V 3 ，随机数0.2＜0.4，则 V 3 被成功激活； t =3， V 3 分别以概率0.7、0.3和0.6尝试激活节点 V 2 、 V 4 和 V 5 ，同理根据随机数0.9＞0.7、0.2＜0.3、0.5＜0.6可知 V 2 未被成功激活，而 V 4 和 V 5 均被成功激活，迭代结束。
图1-8 独立级联模型无向图示例
以上两个实例表明独立级联模型能够简洁地描述级联现象发生的过程。该模型以消息发布者/行为发起者为起点，一旦网络中任一节点被激活，它将尽力去激活自身的邻居节点。由于节点的激活是随机发生的，采用相同的初始节点也可能得到不同的传播结果。
独立级联模型假设邻居节点对目标节点的影响力是相同的，然而现实生活中不同用户的影响力存在明显的差异，随用户权力、亲密关系等变化。为了应对这一缺陷，线性阈值模型对多个邻居节点的影响力进行了更细致的刻画。
有向图 G =〈 V，E 〉中，节点 v 与 u 之间以权重为 w （ v，u ）的有向边相连接，其中 w （ v，u ）表示节点 v 对节点 u 的影响程度，且0＜ w （ v，u ）＜1。定义节点 u 的所有入邻居对 u 的影响程度之和小于等于1，即
根据公式（1-1）可知实际上 w （ v，u ）表示节点 v 在节点 u 的所有入邻居中对 u 的影响力占比。除权重外，网络中每个节点 u 自身存在一个阈值 θ u （0＜ θ u ＜1），当节点 u 周围所有已激活的入邻居对 u 的影响超过阈值 θ u 时，节点 u 被激活，否则保持非激活状态。事实上 θ u 体现了每个节点被激活的难易程度， θ u 值越大，节点越倾向于维持自身的状态而拒绝周围节点的影响（对级联行为的发生存在一定的抑制）。假定网络中每个节点的阈值不会随着信息的传播而改变，则节点 u 在 t +1时刻被激活时，有公式（1-2）成立，当某一时刻网络中不再有新的节点被激活时，传播过程停止：
线性阈值算法描述为
1）给定初始种子节点集合 S 0 ，任意节点 u ∈ S 0 均处于激活状态，其他节点 v ∈ V \ S 0 处于非激活状态。
2）
t
时刻（
t
≥1），未激活节点
m
∈
V
\
S
t
-1
依据它所有已激活入邻居影响程度之和
与自身阈值
θ
m
的关系决定是否被激活：
若
成立，则
t
+1时刻
m
转入已激活节点集合，即
m
∈
S
t
\
S
t
-1
；否则，节点
m
仍保持非激活状态，即
m
∈
V
\
S
t
。
3）迭代运行至网络中不再出现新的被激活节点。
如图1-9所示，同样以实心圆表示激活节点，空心圆表示非激活节点，有向边上的值表示对目标节点的影响程度，此外每个节点上的值表示激活该节点所需的影响力阈值。 t =0时， V 0 作为种子节点处于激活状态； t =1，已激活节点 V 0 尝试激活出邻居 V 1 和 V 2 ，对于 V 1 而言， V 0 的影响力0.5小于阈值0.8，则 V 1 未能被成功激活，同理由于影响力0.8大于 V 2 自身的阈值0.7，则 V 2 被成功激活； t =2， V 2 尝试激活 V 3 ，由于 V 2 对 V 3 的影响力0.7大于 V 3 的阈值0.6，则 V 3 被成功激活； t =3，已激活节点 V 3 尝试激活出邻居 V 4 和 V 5 ，易知 V 4 无法被激活而 V 5 被成功激活。
图1-9 线性阈值模型有向图示例
线性阈值模型中任一节点 u 的所有入邻居对 u 是联合影响的，虽然单独一个入邻居可能无法成功激活节点 u ，但是多个入邻居共同影响可能将其激活。由此可以发现入邻居的联合作用类似于1.2节所讲的“聚簇”这一概念。事实上节点阈值的随机性导致了线性阈值模型的随机性，一旦每个节点的阈值确定，则整个网络的传播过程也随之确定。然而，网络中节点自身的阈值事先是不可知的，只能通过先验知识近似推断，尽量逼近其真实阈值。