Evolving Influence Maximization in Evolving Networks

Abstract

Influence Maximization (IM) aims to maximize the number of people that become aware of a product by finding the `best' set of `seed' users to initiate the product advertisement. Unlike prior arts on static social networks containing fixed number of users, we undertake the first study of IM in more realistic evolving networks with temporally growing topology. The task of evolving IM ({\bfseries EIM}), however, is far more challenging over static cases in the sense that seed selection should consider its impact on future users and the probabilities that users influence one another also evolve over time. We address the challenges through $\mathbb{EIM}$, a newly proposed bandit-based framework that alternates between seed nodes selection and knowledge (i.e., nodes' growing speed and evolving influences) learning during network evolution. Remarkably, $\mathbb{EIM}$ involves three novel components to handle the uncertainties brought by evolution:

References in corpus (9)

• Emergence of scaling in random networks
• A High-Resolution Human Contact Network for Infectious Disease Transmission
• Information diffusion epidemics in social networks
• Sketch-based Influence Maximization and Computation: Scaling up with Guarantees
• Adaptive Influence Maximization in Dynamic Social Networks
• Online Influence Maximization (Extended Version)
• Seed Selection for Spread of Influence in Social Networks: Temporal vs. Static Approach
• Online Influence Maximization under Independent Cascade Model with Semi-Bandit Feedback
• Time is What Prevents Everything from Happening at Once: Propagation Time-conscious Influence Maximization