鲁棒影响力【鲁棒影响力】鲁棒影响力指在网路中选取若干节点作为初始节点进行信息传播所产生的影响力 。
基本介绍中文名：鲁棒影响力
外文名：robust influence
分类：社交网路特性
定义鲁棒影响力指在网路中选取若干节点作为初始节点进行信息传播所产生的影响力 。鲁棒影响力多用于研究社交网路中的影响力最大化问题，即在网路中选取若干节点，使得以他们为初始结点进行信息传播时，在网路中产生的影响能够达到最大 。鲁棒影响力最大化研究了影响力最大化的鲁棒性问题 。鲁棒影响力最大化问题求解近年来，随着影响力最大化研究逐渐深入，Xinran He 与 Wei Chen等人开始研究影响力最大化计算的鲁棒性 。即设计一种鲁棒性较高的算法来消除影响力传播模型中的噪声问题 。数学模型多样化，模型参数不确定以及数据集不完整都属于影响力传播中的噪声 。Xinran He等人提出了一个鲁棒影响力最大化最佳化目标：
文章插图
其中给定了一个影响力传播函式的集合和该传播函式下的种子集 。S*为能使得影响力传播最大化的种子集，最佳化目标是最大化 。因为影响力最大化问题被证明为多项式时间内不可解问题（NP-Hard），为了解决该问题，He 等人提出了一种不计算容量为 K 的种子集而是计算係数为的种子集的方法来近似影响力最大化问题 。在此基础上，He等人提出了饱和贪婪算法、单个贪婪算法和全体贪婪算法 。在实验中He等人比较了三种算法的鲁棒性与非鲁棒性结果的差异以及他们在不同真实数据集中的表现 。Wei Chen等人主要关注了影响力传播过程中模型係数的不确定性 。为了解决 NP-hard问题，Chen提出了一种上下界贪婪算法（Lower-Upper Greedy i.e. LUGreedy）并证明了它对鲁棒影响力最大化问题是解依赖的（Solution-dependent） 。Chen 等人设计了不同的採样方法用来确定影响力传播时的参数（边传播机率）的取值，有均匀採样（Uniform Sampling）和（非均匀）适应性採样（Adaptive Sampling） 。在实验中，Chen 等人使用LUGreedy算法，通过对不同数据集的测试，实验的结论是通过适应性採样可以较好地提高影响力最大化算法的鲁棒性 。