Information Diffusion in Social Networks in Two Phases

Abstract

The problem of maximizing information diffusion, given a certain budget expressed in terms of the number of seed nodes, is an important topic in social networks research. Existing literature focuses on single phase diffusion where all seed nodes are selected at the beginning of diffusion and all the selected nodes are activated simultaneously. This paper undertakes a detailed investigation of the effect of selecting and activating seed nodes in multiple phases. Specifically, we study diffusion in two phases assuming the well-studied independent cascade model. First, we formulate an objective function for two-phase diffusion, investigate its properties, and propose efficient algorithms for finding seed nodes in the two phases. Next, we study two associated problems: (1) budget splitting which seeks to optimally split the total budget between the two phases and (2) scheduling which seeks to determine an optimal delay after which to commence the second phase. Our main conclusions include: (a) under strict temporal constraints, use single phase diffusion, (b) under moderate temporal constraints, use two-phase diffusion with a short delay while allocating most of the budget to the first phase, and (c) when there are no temporal constraints, use two-phase diffusion with a long delay while allocating roughly one-third of the budget to the first phase.