Strategic distribution of seeds to support diffusion in complex networks

EasyChair Preprint 1051

Abstract

Usually, the launch of the diffusion process is triggered by a few early adopters–i.e., seeds of diffusion. Many studies have assumed that all seeds are activated once to initiate the diffusion process in social networks and therefore are focused on finding optimal ways of choosing these nodes according to a limited budget. Despite the advances in identifying influencing spreaders, the strategy of activating all seeds at the beginning might not be sufficient in accelerating and maximising the coverage of diffusion. Also, it does not capture real scenarios in which marketing campaigns continuously monitor and support the diffusion process by seeding more nodes. More recent studies investigate the possibility of activating additional seeds as the diffusion process goes forward. In this work, we further examine this approach and search for optimal ways of distributing seeds during the diffusion process according to a pre-allocated seeding budget. Theoretically, we show that a universally best solution does not exist, and we prove that finding an optimal distribution of supporting seeds over time for a particular network is an NP-hard problem. Numerically, we evaluate several seeding strategies on different networks regarding maximising the coverage and minimising the spreading time. We find that each network topology has a best strategy given some spreading parameters. Our findings can be crucial in identifying the best strategies for budget allocation in different scenarios such as marketing or political campaigns.

Keyphrases: Spreading process, diffusion process, primary seeding, seeds distribution, sequential seeding, supporting seed, supporting seeding, total coverage

@booklet{EasyChair:1051,
  author    = {Jaroslaw Jankowski and Marcin Waniek and Aamena Alshamsi and Piotr Bródka and Radosław Michalski},
  title     = {Strategic distribution of seeds to support diffusion in complex networks},
  howpublished = {EasyChair Preprint 1051},
  year      = {EasyChair, 2019}}