Relative influence maximization in competitive social networks_综合

竞争性社交网络中的相对影响力最大化

一、本文的主要工作

研究了CIC模型下的RIM问题。我们利用目标函数的单调和亚模性质提出了一个贪心算法，即GreedyRIM。我们进一步提出了一种新的基于距离敏感（DS）的启发式方法。实验表明，GreedyRIM取得了良好的效果，DS启发式算法比其他启发式算法具有更高的效率和更好的有效性。

二、简介

1. CIC模型

基于IC模型，每个节点都有三个状态：非活动态（inactive）、P活动态（P-active）和N活动态（N-active）。处于非活动状态的个体不受影响。处于P（N）活动状态的个体表示接受正面（负面）影响。正面和负面影响的传播过程与IC模型一样独立展开。当一个人同时受到正面和负面意见的影响时，负面影响胜于正面影响。

2.相对影响最大化问题(RIM)

在存在消极个体的情况下选择初始个体作为正影响种子集，从而最大程度地扩大积极意见传播与消极意见传播之间的差异。
现有方法通过促进积极影响的扩散或通过限制消极影响的扩散来近似解决该问题。
网络 $G=(V,E)$ ，初始化消极个体 $I_N$ ，RIM的目标是选择具有k个节点的最优正种子集 $I_P$ ，从而使扩散结束时，P活动态比N活动态的个体要多。
形式化定义：
$I_P=arg \underset{|I_P|=k,I_P\subseteq V \backslash I_N}{max} \{\sigma_P(I_P|I_N)-\sigma_N(I_P|I_N) \}$
其中 $\sigma_P(I_P|I_N)$ 和 $\sigma_N(I_P|I_N)$ 分别代表正面和负面影响的传播。
为了确保上式是非负的，转换为：
$I_P=arg \underset{|I_P|=k,I_P\subseteq V \backslash I_N}{max} \{\sigma_P(I_P|I_N)+\sigma_{R_N}(I_P|I_N) \}$
其中 $\sigma_{R_N}(I_P|I_N)=\sigma_N(\empty|I_N)-\sigma(I_P|I_N)$ ，为了便利，我们定义 $f(I_P|I_N)=\sigma_P(I_P|I_N)+\sigma_{R_N}(I_P|I_N)$ 。

3.贪心算法（GreedyRIM）

$f(I_P|I_N)$ 是非负、单调和次模的，我们提出一种贪婪算法GreedyRIM，该算法可实现（1-1/e）近似比。我们提前确定扩散子图G_i（方法参考论文中文献4）。对于第i个节点的选择，我们使用CIC扫描子图，将每个节点添加到集合I_P中，并最终获得了正负节点的影响。为了获得准确的影响近似值，将运行了R次子图的平均值用作最终结果。最后，我们将一个节点v添加到所选集合I_P中，以使v与I_P一起最大化 $f(I_P|I_N)$ 。

4.启发式算法（DS）

距离敏感( Distance-Sensitive)的启发式中心性，称为DS。 DS的主要思想是同时考虑正面和负面观点的传播。 v的DS中心度由下式计算而得：
$DS(v)=(1+p^x) \cdot \sum_{d=1}^{D}(logN_d(v)\cdot p^d)$
其中：p是传播概率，x是节点v到集合I_N的距离， $N_{d(v)}$ 是d跳内节点v可以到达的节点数目。
DS算法依据：

v的DS中心性与距集合I_N的距离成反比，即它倾向于选择集合I_N附近的节点，从而有助于限制负面意见的传播。
v的中心性与邻居的数量成正比，并且接近v的节点更有可能被激活。

另外本文还将DS细分为静态DS（StaticDS）和动态DS（DynamicDS），以区分DS中心度是否是动态计算的。但并未给出详细描述。

通过本文需要进一步探究的问题是：提前确定扩散子图（参考文献4）。