  Influence maximization is the problem of finding influential users, or nodes,
in a graph so as to maximize the spread of information. It has many
applications in advertising and marketing on social networks. In this paper, we
study a highly generic version of influence maximization, one of optimizing
influence campaigns by sequentially selecting "spread seeds" from a set of
influencers, a small subset of the node population, under the hypothesis that,
in a given campaign, previously activated nodes remain "persistently" active
throughout and thus do not yield further rewards. This problem is in particular
relevant for an important form of online marketing, known as influencer
marketing, in which the marketers target a sub-population of influential
people, instead of the entire base of potential buyers. Importantly, we make no
assumptions on the underlying diffusion model and we work in a setting where
neither a diffusion network nor historical activation data are available. We
call this problem online influencer marketing with persistence (in short,
OIMP). We first discuss motivating scenarios and present our general approach.
We introduce an estimator on the influencers' remaining potential -- the
expected number of nodes that can still be reached from a given influencer --
and justify its strength to rapidly estimate the desired value, relying on real
data gathered from Twitter. We then describe a novel algorithm, GT-UCB, relying
on upper confidence bounds on the remaining potential. We show that our
approach leads to high-quality spreads on both simulated and real datasets,
even though it makes almost no assumptions on the diffusion medium.
Importantly, it is orders of magnitude faster than state-of-the-art influence
maximization methods, making it possible to deal with large-scale online
scenarios.
