Skip to Main content Skip to Navigation
Conference papers

Effective Large-Scale Online Influence Maximization

Abstract : 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.
Complete list of metadata

Cited literature [19 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-01687722
Contributor : Bogdan Cautis Connect in order to contact the contributor
Submitted on : Thursday, January 18, 2018 - 4:47:27 PM
Last modification on : Tuesday, November 16, 2021 - 5:11:27 AM
Long-term archiving on: : Wednesday, May 23, 2018 - 11:18:20 PM

File

lagree2017effective.pdf
Files produced by the author(s)

Identifiers

Citation

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⟩

Share

Metrics

Record views

817

Files downloads

712