Research Article: Strategic distribution of seeds to support diffusion in complex networks

Date Published: October 16, 2018

Publisher: Public Library of Science

Author(s): Jarosław Jankowski, Marcin Waniek, Aamena Alshamsi, Piotr Bródka, Radosław Michalski, Ming Tang.


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.

Partial Text

The increasing number of people who use social media has presented a new channel for marketing campaigns. Viral marketing targets potentially influential nodes in social networks to spread the word about certain products or services. However, the optimisation problem of selecting influential nodes as seeds is NP-hard [1]. Due to the computational complexity of the problem, seed selection methods are often based on heuristics. In simple approaches, nodes are selected according to network metrics such as degree or betweenness. In other lines of research, seed selection is based on a greedy approach, [1] which offers reasonable results compared to the exact solution, but unfortunately still has high computational requirements. This is why proposed modifications of the greedy approach are focused on the reduction of the time needed to obtain the seed set [2]. More recent approaches like VoteRank [3] or the community-based selection [4] focus on the information-spreading potential of individual seeds as well as their location in the network in order to select seeds in regions that would not be naturally activated by the spreading process.

The increasingly important role of social media in marketing strategies requires new analytical and decision supported solutions. Most of the earlier studies related to viral marketing are focused on seed selection and initialisation of the information diffusion process, without considering additional support. At the same time, real-life marketing campaigns are based on continuous monitoring of performance, using an additional budget to boost campaign dynamics and coverage. However, the budget assigned to supporting campaigns can be allocated according to different strategies. One possible strategy is to assign the same number of supporting seeds at each stage, while another strategy can add more supporting seeds at the beginning or close to the end of a campaign. Spending the additional budget at the beginning of the campaign may result in activating nodes that would be reached anyway by the natural diffusion processes, while postponing supporting seeding to the end of the process enables activating nodes which are difficult to reach with the natural processes, but it might be too late to fully exploit the potential of activating these nodes in initiating new information cascades.




0 0 vote
Article Rating
Notify of
Inline Feedbacks
View all comments