A paper titled “Probing Limits of Information Spread with Sequential Seeding” by Jaroslaw Jankowski, Boleslaw K. Szymanski, Przemyslaw Kazienko, Radoslaw Michalski, and Piotr Brodka has been accepted by Scientific Reports on August 26, 2018

A paper titled “Probing Limits of Information Spread with Sequential Seeding” by Jaroslaw Jankowski, Boleslaw K. Szymanski, Przemyslaw Kazienko, Radoslaw Michalski, and Piotr Brodka has been accepted by Scientific Reports on August 26, 2018. The paper studies information spread which propagates with certain probability from nodes just activated to their no activated neighbors. Diffusion cascades can be triggered by activation of even a small set of nodes. Such activation is commonly performed in a single stage. A novel approach based on sequential seeding is analyzed here resulting in three fundamental contributions. First, we propose a coordinated execution of randomized choices to enable precise comparison of different algorithms in general. We apply it here when the newly activated nodes at each stage of spreading attempt to activate their neighbors. Then, we present a formal proof that sequential seeding delivers at least as good spread coverage as the single stage seeding does. Moreover, we also show that, under modest assumptions, sequential seeding performs provably better than the single stage based approach using the same number of seeds and node ranking. Finally, we present experimental results comparing single stage and sequential approaches on directed and undirected graphs to the well-known greedy approach to provide the objective measure of the sequential seeding benefits. Surprisingly, applying sequential seeding to a simple degree-based selection leads to higher coverage than achieved by the computationally expensive greedy approach currently considered the best heuristic. The paper is available at the link below.