论文标题
相关性强大影响最大化
Correlation Robust Influence Maximization
论文作者
论文摘要
我们为影响最大化问题提出了一个分布强大的模型。与经典的独立级联模型\ citep {kempe2003maximization}不同，该模型的扩散过程在对抗中适应了种子集的选择。因此，我们没有在网络中的所有影响关系都是独立的假设下优化的，而是寻求一个种子集，其在最坏的相关性下的预期影响，即“最糟糕的，预期的影响”是最大化的。我们表明，这种最坏的影响可以有效地计算出来，尽管优化是NP-HARD，但（$ 1-1/e $）的近似保证保证了。我们还分析了对手选择扩散过程的结构，并与既定模型形成鲜明对比。除了关键的计算优势之外，我们还强调了独立性假设的成本优化程度，并提供了比较对抗和独立级联模型的数值实验的见解。
We propose a distributionally robust model for the influence maximization problem. Unlike the classic independent cascade model \citep{kempe2003maximizing}, this model's diffusion process is adversarially adapted to the choice of seed set. Hence, instead of optimizing under the assumption that all influence relationships in the network are independent, we seek a seed set whose expected influence under the worst correlation, i.e. the "worst-case, expected influence", is maximized. We show that this worst-case influence can be efficiently computed, and though the optimization is NP-hard, a ($1 - 1/e$) approximation guarantee holds. We also analyze the structure to the adversary's choice of diffusion process, and contrast with established models. Beyond the key computational advantages, we also highlight the extent to which the independence assumption may cost optimality, and provide insights from numerical experiments comparing the adversarial and independent cascade model.
