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.
Type de document :
Pré-publication, Document de travail
Liste complète des métadonnées

Littérature citée [34 références]  Voir  Masquer  Télécharger
Contributeur : Paul Lagrée <>
Soumis le : mardi 28 février 2017 - 13:25:38
Dernière modification le : mardi 20 novembre 2018 - 14:04:02
Document(s) archivé(s) le : lundi 29 mai 2017 - 14:05:13


Fichiers produits par l'(les) auteur(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-01478788〉



Consultations de la notice


Téléchargements de fichiers