Robust Influence Maximization: (Extended Abstract)
Robust Influence Maximization: (Extended Abstract)
复制标题
稳健影响力最大化：（扩展摘要）
DOI：
10.5555/2936924.2937177
复制
发表时间：
2016
影响因子：
2.2
通讯作者：
Akshat Kumar
中科院分区：
文献类型：
--
作者：
Meghna Lowalekar;Pradeep Varakantham;Akshat Kumar
影响最大化[2]是找到固定尺寸的节点集的问题，这将最大程度地提高社交网络中预期的受影响节点的数量。受影响的节点的数量取决于可能非常嘈杂的边缘的影响强度。可以使用随机噪声或对抗噪声模型对影响强度中的噪声进行建模。已经表明，所有独立影响图边缘的随机过程都可以吸收到激活概率本身中，因此可以在独立的级联模型中捕获随机噪声。另一方面，类似于He等人。 [1]，我们考虑了对抗性噪声，其中影响边缘的强度可以属于该间隔中的任何点：p u，v，p u，v，确切的值是从此间隔中选择的对手。评估给定解决方案的鲁棒性和计算鲁棒最佳解决方案的鲁棒性问题在文献中受到了很少的关注，并且在本文中引起了关键的兴趣。具体而言，我们旨在最大程度地减少（在所有可用种子集中）最大值（在所有影响力强度的实例上）遗憾。具体而言，关键的贡献是：（1）我们表明，当对每个边缘的影响强度设置为边缘的极端值之一时，给定解决方案的最大遗憾就会达到。 （2）我们提供了一种考虑样本来说明所有边缘影响力的噪声的新方法。 （3）我们开发了一个框架，该框架提供了一种方法，以获得最佳的遗憾解决方案，更重要的是一个度量，以根据遗憾的最佳解决方案评估给定解决方案的鲁棒性。 （4）最后，我们显示了评估众所周知的贪婪方法的鲁棒性的结果。令人惊讶的是，即使没有明确考虑影响力强度的噪音，贪婪的方法也可以在小型中等社会网络实例上实现高度强大的解决方案。
Influence Maximization [2] is the problem of finding a fixed size set of nodes, which will maximize the expected number of influenced nodes in a social network. The number of influenced nodes is dependent on the influence strength of edges that can be very noisy. The noise in the influence strengths can be modeled using a random noise or adversarial noise model. It has been shown that all random processes that independently affect edges of the graph can be absorbed into the activation probabilities themselves and hence random noise can be captured within the independent cascade model.On the other hand, similar to He et al. [1], we consider the adversarial noise where influence strength for an edge can belong to any point in the interval: P u,v, P u,v and the exact values are chosen by an adversary from this interval. The problems of evaluating robustness of a given solution and computing robust optimal solutions have received scant attention in the literature and are of key interest in this paper. Specifically, we aim to minimize (over all available seed sets) the maximum (over all instantiations of influence strengths) regret. Concretely, the key contributions are: (1) We show that maximum regret for a given solution is attained when influence strength on each of the edges is set to one of the extreme values of the influence strength intervals on edges. (2) We provide a novel way of considering samples that accounts for the noise in influence strength on all edges. (3) We develop a framework which provides an approach to get an optimal regret solution and more importantly a metric to evaluate robustness of a given solution based on the regret optimal solution. (4) Finally, we show results on evaluating the robustness of the well known greedy approach. Surprisingly, even without considering noise in influence strengths explicitly, greedy approach achieves highly robust solutions on small-medium scale social network instances.