Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

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
Contributor : Paul Lagrée <>
Submitted on : Tuesday, February 28, 2017 - 1:25:38 PM
Last modification on : Wednesday, June 24, 2020 - 2:30:05 PM
Document(s) archivé(s) le : Monday, May 29, 2017 - 2:05:13 PM


Files produced by the author(s)


  • HAL Id : hal-01478788, version 1



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



Record views


Files downloads