Adaptive Influence Maximization in Social Networks: Why Commit when You can Adapt?
(27.04.2016)Zusammenfassung
Most previous work on influence maximization in social networks is limited to
the non-adaptive setting in which the marketer is supposed to select all of the
seed users, to give free samples or discounts to, up front. A disadvantage of
this setting is that the marketer is forced to select all the seeds based
solely on a diffusion model. If some of the selected seeds do not perform well,
there is no opportunity to course-correct. A more practical setting is the
adaptive setting in which the marketer initially selects a batch of users and
observes how well seeding those users leads to a diffusion of product
adoptions. Based on this market feedback, she formulates a policy for choosing
the remaining seeds. In this paper, we study adaptive offline strategies for
two problems: (a) MAXSPREAD -- given a budget on number of seeds and a time
horizon, maximize the spread of influence and (b) MINTSS -- given a time
horizon and an expected number of target users to be influenced, minimize the
number of seeds that will be required. In particular, we present theoretical
bounds and empirical results for an adaptive strategy and quantify its
practical benefit over the non-adaptive strategy. We evaluate adaptive and
non-adaptive policies on three real data sets. We conclude that while benefit
of going adaptive for the MAXSPREAD problem is modest, adaptive policies lead
to significant savings for the MINTSS problem.
