Download PDFOpen PDF in browser

Strategic distribution of seeds to support diffusion in complex networks

EasyChair Preprint 1051

16 pagesDate: May 28, 2019

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

BibTeX entry
BibTeX does not have the right entry for preprints. This is a hack for producing the correct reference:
@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}}
Download PDFOpen PDF in browser