The Influence Maximization problem is a classic and well-studied problem in the area of Social Networks Analysis. In this problem you have a social network, a given information diffusion model, and a budget B, and you have to select a set of at most B nodes (seeds) to activate in order to start an information diffusion campaign that is able to reach the largest (expected) number of nodes in the network. Recently, to better model viral marketing scenarios where advertisers conduct multiple rounds of viral marketing to promote one product, attention has been given to the adaptive and the multi-round versions of the problem. Here the campaign is orchestrated on a horizon of T rounds and at the beginning of each round a different set of seeds is activated that can be adaptively selected given previous observations. In this work we generalize this setting to the case where the diffusion probabilities of the network links are not known and have to be learned while the campaign is running. We study the problem under the lens of online bandit algorithms, and we propose an online learning algorithm that is able to achieve a constant approximation of the optimal solution with only constant regret with respect to T. Despite these guarantees, the algorithm turns out to be unpractical in many settings. To address this issue, we propose an alternative approach and experimentally show that it provides satisfying guarantees both for regret and computational complexity.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Adaptive Multi-round Influence Maximization with Limited Information

  • Vincenzo Auletta,
  • Francesco Carbone,
  • Diodato Ferraioli,
  • Cosimo Vinci

摘要

The Influence Maximization problem is a classic and well-studied problem in the area of Social Networks Analysis. In this problem you have a social network, a given information diffusion model, and a budget B, and you have to select a set of at most B nodes (seeds) to activate in order to start an information diffusion campaign that is able to reach the largest (expected) number of nodes in the network. Recently, to better model viral marketing scenarios where advertisers conduct multiple rounds of viral marketing to promote one product, attention has been given to the adaptive and the multi-round versions of the problem. Here the campaign is orchestrated on a horizon of T rounds and at the beginning of each round a different set of seeds is activated that can be adaptively selected given previous observations. In this work we generalize this setting to the case where the diffusion probabilities of the network links are not known and have to be learned while the campaign is running. We study the problem under the lens of online bandit algorithms, and we propose an online learning algorithm that is able to achieve a constant approximation of the optimal solution with only constant regret with respect to T. Despite these guarantees, the algorithm turns out to be unpractical in many settings. To address this issue, we propose an alternative approach and experimentally show that it provides satisfying guarantees both for regret and computational complexity.