Maximizing Influence Diffusion over Evolving Social Networks

Influence diffusion in social networks has been intensively studied over last two decades. Most prior arts assume that the underlying network structure is static, remaining fixed during the influence diffusion process. However, many real networks are growing over time in terms of both the number of users and the relations in between. This motivates us to make the first study on influence diffusion over such evolving networks, where we extend the classical Influence Maximization (IM) problem to accomodate network evolution, i.e., a fairly general joining in behavior of new users. The goal of evolving IM problem studied in this paper is to select, at a given time, a few influential nodes (seeds) to initiate a diffusion with maximum spread over the network evolved after a certain time period. To tackle the both unknown network topology and influence probability arisen from the network evolution, our solution is to propose an Uppber Confidence Bound (UCB) based learning method to learn, on a multi-round basis, the unknown influence probabilities from previous diffusion feedbacks, and perform seed selection for diffusion maximization accordingly in each round. Our influence learning method provably returns a sub-linear regret bound of influence diffusion size to time. Meanwhile, empirical results performed under real evolving network datasets unravel the effect of network evolution on the influence diffusion, and demonstrate that the proposed solution significantly outperforms the non-evolving counterparts on maximizing the influence diffusion size over evolving social networks.