We study the online influence maximization (OIM) problem in social networks,
where the learner repeatedly chooses seed nodes to generate cascades, observes
the cascade feedback, and gradually learns the best seeds that generate the
largest cascade in multiple rounds. In the demand of the real world, we work
with node-level feedback instead of the common edge-level feedback in the
literature. The edge-level feedback reveals all edges that pass through
information in a cascade, whereas the node-level feedback only reveals the
activated nodes with timestamps. The node-level feedback is arguably more
realistic since in practice it is relatively easy to observe who is influenced
but very difficult to observe from which relationship (edge) the influence
comes. Previously, there is a nearly optimal $\tilde{O}(\sqrt{T})$-regret
algorithm for OIM problem under the linear threshold (LT) diffusion model with
node-level feedback. It remains unknown whether the same algorithm exists for
the independent cascade (IC) diffusion model. In this paper, we resolve this
open problem by presenting an $\tilde{O}(\sqrt{T})$-regret algorithm for OIM
problem under the IC model with node-level feedback.

本研究提出了一种应对节点级反馈的独立级联模型（IC）的在线影响最大化问题的算法，通过使用该算法，可以在社交网络中找到最优种子节点来刺激信息在网络中最大范围的传播。

基于独立级联模型的节点级反馈在线影响最大化

Online Influence Maximization under the Independent Cascade Model with  Node-Level Feedback

We consider the problem of \emph{influence maximization}, the problem of
maximizing the number of people that become aware of a product by finding the
`best' set of `seed' users to expose the product to. Most prior work on this
topic assumes that we know the probability of each user influencing each other
user, or we have data that lets us estimate these influences. However, this
information is typically not initially available or is difficult to obtain. To
avoid this assumption, we adopt a combinatorial multi-armed bandit paradigm
that estimates the influence probabilities as we sequentially try different
seed sets. We establish bounds on the performance of this procedure under the
existing edge-level feedback as well as a novel and more realistic node-level
feedback. Beyond our theoretical results, we describe a practical
implementation and experimentally demonstrate its efficiency and effectiveness
on four real datasets.

本文考虑影响最大化问题，提出一种基于组合多臂老虎机范式的策略来估计影响概率，实现了较高的效率和效果，同时在四个真实数据集上得到了验证。