Effectiveness of Diffusing Information through a Social Network in Multiple Phases

We study the effectiveness of using multiple phases for maximizing the extent of information diffusion through a social network, and present insights while considering various aspects. In particular, we focus on the well-studied independent cascade model with the possibility of adaptively selecting seed nodes in multiple phases based on the observed diffusion in preceding phases, and conduct a detailed simulation study on real-world network datasets. We first present a negative result that more phases do not guarantee a better spread, however the adaptability advantage of using more phases generally leads to a better spread on real-world datasets. We study how diffusing in multiple phases affects the mean and standard deviation of the extent of diffusion, and explain how using multiple phases reduces uncertainty in diffusion. We then study how the number of phases impacts the effectiveness of diffusion, how the diffusion progresses phase-by-phase, and how to optimally split the total seeding budget across phases. Our experiments show a significant gain when we move from single phase to two phases, however, the marginal gain of having an additional phase decreases as we increase the number of phases. Our main conclusion is that, given the number of phases, an optimal way to split the budget across phases is such that the expected number of influenced nodes in each phase is almost the same.