Online Model-Free Influence Maximization with Persistence

Abstract : Influence maximization is the problem of finding influent 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 the problem of sequentially selecting seeds in the network under the hypothesis that previously activated nodes can still transfer information, but do not yield further rewards. Furthermore, we make no assumption on the underlying diffusion model. We refer to this problem as online influence maximization with persistence. We first discuss scenarios motivating the problem and present our approach to solve it. We then analyze a novel algorithm relying on upper confidence bound on the so-called missing mass, that is, the expected number of nodes that can still be reached from a given seed. From a computational standpoint, the proposed approach is several orders faster than state-of-the-art methods, making it possible to tackle very large graphs. In addition, it displays high-quality spreads on both simulated and real datasets.
Document type :
Preprints, Working Papers, ...
Complete list of metadatas

Cited literature [34 references]  Display  Hide  Download

https://hal.inria.fr/hal-01478788
Contributor : Paul Lagrée <>
Submitted on : Tuesday, February 28, 2017 - 1:25:38 PM
Last modification on : Saturday, May 4, 2019 - 1:20:26 AM
Long-term archiving on : Monday, May 29, 2017 - 2:05:13 PM

File

paperarxiv.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01478788, version 1

Citation

Paul Lagrée, Olivier Cappé, Bogdan Cautis, Silviu Maniu. Online Model-Free Influence Maximization with Persistence. 2017. ⟨hal-01478788v1⟩

Share

Metrics

Record views

700

Files downloads

117