提出在线影响力最大化新算法，显著降低累积损失
LOFA: Online Influence Maximization under Full-Bandit Feedback using Lazy Forward Selection
- 基于懒惰前向选择，利用影响函数的凹性优化种子选择
- 在真实社交网络上实验，累积损失比现有方法低23%
- 适合需要实时决策的社交网络推广场景
我们研究在线影响力最大化（IM）问题，目标是在固定时间范围内，每步从节点中选择满足基数约束的种子集以最大化期望累积影响。采用全盲反馈模型，仅观测所选种子集的影响，无网络结构或传播过程的额外信息。已知影响函数具有次模性，现有算法利用该性质实现低遗憾。本文进一步利用该性质，提出懒惰在线前向算法（LOFA），实证显示其累积遗憾更低。在真实社交网络上的实验表明，相较于现有带通算法，LOFA在累积遗憾和即时奖励方面均表现更优。
原文摘要 · Abstract (English)
We study the problem of influence maximization (IM) in an online setting, where the goal is to select a subset of nodes$\unicode{x2014}$called the seed set$\unicode{x2014}$at each time step over a fixed time horizon, subject to a cardinality budget constraint, to maximize the expected cumulative influence. We operate under a full-bandit feedback model, where only the influence of the chosen seed set at each time step is observed, with no additional structural information about the network or diffusion process. It is well-established that the influence function is submodular, and existing algorithms exploit this property to achieve low regret. In this work, we leverage this property further and propose the Lazy Online Forward Algorithm (LOFA), which achieves a lower empirical regret. We conduct experiments on a real-world social network to demonstrate that LOFA achieves superior performance compared to existing bandit algorithms in terms of cumulative regret and instantaneous reward.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。