Effective Large-Scale Online Influence Maximization - Archive ouverte HAL Access content directly
Conference Papers Year :

Effective Large-Scale Online Influence Maximization


In this paper, we study a highly generic version of influence maximization (IM), one of optimizing influence campaigns by sequentially selecting " spread seeds " from a set of candidates, 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. We call this problem online influence maximization with persistence. We introduce an estimator on the candidates' missing mass – the expected number of nodes that can still be reached from a given seed candidate – and justify its strength to rapidly estimate the desired value. We then describe a novel algorithm, GT-UCB, relying on upper confidence bounds on the missing mass. We show that our approach leads to high-quality spreads on classic IM datasets, even though it makes almost no assumptions on the diffusion medium. Importantly, it is orders of magnitude faster than state-of-the-art IM methods.
Fichier principal
Vignette du fichier
lagree2017effective.pdf (1004.94 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-01687722 , version 1 (18-01-2018)



Paul Lagrée, Olivier Cappé, Bogdan Cautis, Silviu Maniu. Effective Large-Scale Online Influence Maximization. ICDM 2017 - IEEE International Conference on Data Mining, Nov 2017, New Orleans, France. ⟨10.1109/ICDM.2017.118⟩. ⟨hal-01687722⟩
532 View
262 Download



Gmail Facebook Twitter LinkedIn More