Model-free algorithms for influence estimation and influence maximization
University of Paris-Sud, Orsay
11 Jul 2018 Wednesday, 10:30 AM to 12:00 PM
COM2 Level 4
Executive Classroom, COM2-04-02
Word-of-mouth effects and influence are nowadays crucial ingredients for successful recommendation campaigns in social networks. I will discuss in this talk some of our recent research on understanding influence patterns and using them when running spread campaigns in social networks. First, we revisit the problem of inferring a diffusion network from adoption traces (so called cascades). Importantly, in our study, we make no assumptions on the underlying diffusion model, in this way obtaining a generic method with broader practical applicability. Our approach exploits the pairwise adoption-time intervals from cascades, with the observation that different kinds of information spread differently. Experiments on both synthetic data and real-world datasets from Twitter and Flixster show that our method significantly outperforms the state-of-the-art, in terms of precision and recall. Second, we consider influence maximization (IM), the problem of finding influent users (nodes in a graph) so as to maximize the spread of information. We study a version of IM in which we maximize influence campaigns by adaptively selecting "spread seeds" from a set of candidates, a small subset of the node population. Influencer marketing is one straightforward application of this kind. According to our main motivation, we make the hypothesis that, in a given campaign, previously activated nodes remain "persistently" active throughout, and thus, do not yield further rewards. Once again, we make no assumptions on the underlying diffusion model and we work in a setting where neither a diffusion network nor historical activation data are available. We call this problem online influence maximization with persistence (OIMP). We address it using an original approach based on multi-armed bandit techniques for adaptive learning and show that it leads to high-quality spreads on both simulated and real datasets while being orders of magnitude faster than state-of-the-art IM methods.
Bogdan Cautis is a Professor in the Department of Computer Science of University of Paris-Sud, Orsay. He received engineering and Master diplomas from Ecole Polytechnique, and his PhD diploma from University of Paris-Sud. He was recently on extended leave of absence from the university, as a senior researcher in Huawei Noah's Ark Lab, Hong Kong. His current research interests lie in the broad area of Web data management and information retrieval, including social data management and database theory.