1.3 网络级联模型

网络级联模型能够表征级联传播的机制，对于理解和解释现实生活中的级联现象至关重要。本节主要介绍独立级联模型（Independent Cascade Model，ICM）与线性阈值模型（Linear Threshold Model，LTM）[23-24]，前者强调网络中的节点依概率被邻居节点激活，而后者强调每个网络节点基于已做出相同决策的邻居节点数量或所占比例（阈值）决定是否被激活。作为典型的级联模型，现有工作均基于ICM与LTM进行改进和优化。

1.3.1 独立级联模型

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）给定初始种子节点集合S0，任意节点u∈S0均处于激活状态，其他节点v∈V\S0处于非激活状态。

2）t时刻（t≥1），新近被激活节点m∈St-1\St-2（St表示截止到时刻t所有激活节点构成的集合）以概率p（m，n）尝试激活其邻居节点n∈N+（m）\St-1；若存在多个已激活节点可以对节点n产生影响，那么这些节点将以任意顺序试图激活节点n。如果节点n被成功激活，则t+1时刻n转入已激活节点集合，即n∈St\St-1；否则，节点n仍保持非激活状态，即n∈V\St。

3）迭代运行至网络中不再出现新的被激活节点，传播过程停止。

如图1-7所示，以实心圆表示激活节点，空心圆表示非激活节点，有向边上的值表示成功激活目标节点所需的概率值。为便于理解节点的激活过程，假设已激活节点尝试激活邻居节点时系统生成一个随机数，若概率值大于该随机数，则激活成功，否则激活失败。t=0，U0为种子节点，处于激活状态；t=1，U0分别以0.5、0.4的概率尝试激活U1、U2，由于随机数0.4＜0.5，则U1被激活，同理由于随机数0.6＞0.4，则U2未被激活；t=2，U1以0.3的概率尝试激活U2，由随机数0.2＜0.3，则U2被激活；t=3，U2分别以0.3、0.2的概率尝试激活U3、U4，由于随机数0.1＜0.3、0.6＞0.2，则U3被激活、U4未被激活；t=4，U3以0.2的概率尝试激活U4，然而随机数0.4＞0.2，U4仍未被激活，此时整个系统中无新增激活节点，迭代结束。

图1-7 独立级联模型有向图示例

此外，独立级联模型同样可应用于无向图中，算法与有向图相同而激活概率满足p（u，v）=p（v，u）。以图1-8为例，t=0时，V0作为种子节点处于激活状态；t=1，V0分别以0.5、0.8的概率尝试激活V1、V2，由于随机数0.4＜0.5则V1被成功激活，而随机数0.9＞0.8，则V2未被激活；t=2，V1以0.4的概率尝试激活V3，随机数0.2＜0.4，则V3被成功激活；t=3，V3分别以概率0.7、0.3和0.6尝试激活节点V2、V4和V5，同理根据随机数0.9＞0.7、0.2＜0.3、0.5＜0.6可知V2未被成功激活，而V4和V5均被成功激活，迭代结束。

图1-8 独立级联模型无向图示例

以上两个实例表明独立级联模型能够简洁地描述级联现象发生的过程。该模型以消息发布者/行为发起者为起点，一旦网络中任一节点被激活，它将尽力去激活自身的邻居节点。由于节点的激活是随机发生的，采用相同的初始节点也可能得到不同的传播结果。

1.3.2 线性阈值模型

独立级联模型假设邻居节点对目标节点的影响力是相同的，然而现实生活中不同用户的影响力存在明显的差异，随用户权力、亲密关系等变化。为了应对这一缺陷，线性阈值模型对多个邻居节点的影响力进行了更细致的刻画。

有向图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）给定初始种子节点集合S0，任意节点u∈S0均处于激活状态，其他节点v∈V\S0处于非激活状态。

2）t时刻（t≥1），未激活节点m∈V\St-1依据它所有已激活入邻居影响程度之和与自身阈值θm的关系决定是否被激活：

若成立，则t+1时刻m转入已激活节点集合，即m∈St\St-1；否则，节点m仍保持非激活状态，即m∈V\St。

3）迭代运行至网络中不再出现新的被激活节点。

如图1-9所示，同样以实心圆表示激活节点，空心圆表示非激活节点，有向边上的值表示对目标节点的影响程度，此外每个节点上的值表示激活该节点所需的影响力阈值。t=0时，V0作为种子节点处于激活状态；t=1，已激活节点V0尝试激活出邻居V1和V2，对于V1而言，V0的影响力0.5小于阈值0.8，则V1未能被成功激活，同理由于影响力0.8大于V2自身的阈值0.7，则V2被成功激活；t=2，V2尝试激活V3，由于V2对V3的影响力0.7大于V3的阈值0.6，则V3被成功激活；t=3，已激活节点V3尝试激活出邻居V4和V5，易知V4无法被激活而V5被成功激活。

图1-9 线性阈值模型有向图示例

线性阈值模型中任一节点u的所有入邻居对u是联合影响的，虽然单独一个入邻居可能无法成功激活节点u，但是多个入邻居共同影响可能将其激活。由此可以发现入邻居的联合作用类似于1.2节所讲的“聚簇”这一概念。事实上节点阈值的随机性导致了线性阈值模型的随机性，一旦每个节点的阈值确定，则整个网络的传播过程也随之确定。然而，网络中节点自身的阈值事先是不可知的，只能通过先验知识近似推断，尽量逼近其真实阈值。