0%

从网络信息传播到影响最大化算法

信息传播模型

网络信息传播的特点

信息传播模型

线性阈值模型


独立级联模型

节点影响范围


影响最大化算法

影响最大化问题的描述

  • 影响最大化问题是一个 $NP-hard$ 问题,蛮力计算的复杂度为 $O \left( \begin{pmatrix} n \\ k \\ \end{pmatrix}T \right) $ ,其中,$n$ 是节点个数,$T$ 是估计节点影响范围的平均代价。
  • 对于 $NP-hard$ 问题,通常有两种求解办法,一种是贪心算法,精度有保障,但是速度较慢,一种是启发式算法,速度较快,但是精度无保障。

影响最大化问题的性质

次模性也被称为子模性,直观的理解是一个节点对越大集合的影响度越小。即添加一个节点 $v$ 到节点集合 $S$ 中所获得的边际效益应当大于把 $v$ 添加到 $S$ 的父集合中所得到的边际效益。

影响最大化问题的贪心算法

Basic Greedy

算法步骤

  1. 在 $S$ 为空的条件下,一次算出 $G$ 中每个节点 $v$ 的边际影响力 $\Delta infs$,其中,节点 $v$ 的 $\Delta infs$ 等于 $v$ 加入当前种子集 $S$ 后形成的新种子集 $S^,$ 的影响力与当前 $S$ 的影响力的差,并把各个节点按照 $\Delta infs$ 降序排列
  2. 把 $\Delta infs$ 最大的节点加入 $S$
  3. 在新种子集 $S$ 条件下,重新计算各个节点的边际影响力 $\Delta infs$ ,把 $\Delta infs$ 最大的加入 $S$
  4. 重复 $step 3$,直至种子集的节点个数达到 $K$ ,输出 $S$,退出

由以上步骤可知,$Basic Greedy$ 面临的最大的问题就是算法过程较慢,每轮迭代都要重新计算剩余所有节点的边际影响力。其中,对影响最大化贪心算法的加速最典型的方法就是 $CELFGreedy$。

CELF Greedy

考虑如下图中描述的问题,在 $CELF$ 算法中,根据影响最大化问题的性质,节点的 $\Delta infs$ 符合次模性,于是在节点 $A$ 加入到 $S$ 之后,在下一轮计算各个节点的 $\Delta infs$ 时,如果计算出节点 $B$ 的 $\Delta infs$ 大于等于上一轮中仅次于它的那个节点 $C$,那么在这一轮就可以直接把节点 $B$ 加入到 $S$ 中,而不用重复计算后面节点的 $\Delta infs$ ,因为他们在这一轮的 $\Delta infs$ 必定比上一轮中自己的 $\Delta infs$ 小,所以 $B$ 一定是本轮最大 $\Delta infs$ 的节点。

若 $\Delta b \ge 8$,那么 $B$ 就是 $\Delta infs$ 最大的节点,可直接加入 $S$ ,不用再计算 $\Delta c$ , $\Delta d$ , $\Delta e$ ,因为依据次模性,种子集 $S$ 加入了 $A$ 之后, $\Delta c$ 必定小于等于 $8$,$\Delta d$ 必定小于等于 $7$,$\Delta e$ 必定小于等于 $6$。这就是 $CELF$ 算法能节省时间提高速度的根本原因。

若 $\Delta b \lt 8$,则需要逐个算出每个节点的 $\Delta infs$ ,排序再挑最大 $\Delta infs$ 的节点放进 $S$,然后重复上述过程。

影响最大化贪心算法的困境

单调性的破坏
$$\sigma_1({v_2}) \gt \sigma_2({v_2, v_5})$$
在第一轮快照中,$\sigma_1({v_2})=4$
在第二轮快照中,$\sigma_2({v_2, v_5})=3$

次模性的破坏
$$\sigma_1({v_4}) - \sigma_1({\emptyset}) \lt \sigma_2({v_2, v_4}) - \sigma_2({v_2}) $$

在第一轮快照中,$\sigma_1({v_4}) - \sigma_1({\emptyset}) =1-0=1$
在第二轮快照中,$\sigma_2({v_2, v_4}) - \sigma_2({v_2}) =6-3=3$

究其原因,是因为贪心算法在每一轮迭代时都进行一次采样,而采样是蒙特卡洛模拟的随机结果,每一轮迭代的采样产生的传播快照都可能不同,这也就导致了在传播过程中单调性和次模性的破坏。

影响最大化贪心算法的改进



策略一:通过进行足够多的模拟次数来提高快照的质量
策略二:使用同一组快照,对于不同的集合 $S$ 和 $T$ 进行蒙特卡洛模拟,同一次模拟的结果相同

网络推断问题

问题描述

点对型性模型

点对型模型的描述

点对型模型的缺陷

点对型模型的改进

虽然网络推断是目前的研究热点之一,但是其效率较低,不适用于大规模的网络,精度依赖于传播模型的设计。在此类问题上,表达学习将成为主流,稀疏模型将会是发展方向。

流行度预测

流行度预测的三类数据

基于时序分析的预测

基于结构多样性的预测

可预测性与不可预测性

人在回路:人在回路打破了一个现象的自然发展规律,早就了信息的不可预测,例如在导弹发射后,人在回路时,人可以通过制导系统继续控制导弹
级联效应:是由一个动作影晌系统而导致一系列意外事件发生的效应,关于“睡美人”的例子,永远无法预测睡美人在哪个时刻醒过来。

基于自增强泊松过程的预测

参考文献:
[1] 沈华伟,《网络数据挖掘》,中国科学院大学2017年秋季研究生课程
[2] http://www.cnblogs.com/aaronhoo/p/6548760.html
[3] Cheng S, Shen H, Huang J, et al. StaticGreedy: solving the scalability-accuracy dilemma in influence maximization[C]// ACM International Conference on Information & Knowledge Management. ACM, 2013:509-518.