Faculty of Computer Science and Information Technology, West Pomeranian University of Technology, 70-310, Szczecin, Poland.
Social and Cognitive Networks Academic Research Center and Department of Computer Science, Rensselaer Polytechnic Institute, Troy, NY, 12180, USA.
Sci Rep. 2018 Sep 18;8(1):13996. doi: 10.1038/s41598-018-32081-2.
We consider here information spread which propagates with certain probability from nodes just activated to their not yet 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 seeding 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 to be the best heuristic.
我们在这里考虑以一定概率从刚刚激活的节点传播到尚未激活的邻居的信息。扩散级联可以由一小部分节点的激活触发。这里分析了一种基于顺序播种的新方法，得出了三个基本贡献。首先，我们提出了一种随机选择的协调执行方法，以能够在一般情况下精确比较不同的算法。我们在传播的每个阶段，当新激活的节点试图激活其邻居时，应用它。然后，我们给出了一个正式的证明，即顺序播种至少可以提供与单阶段播种一样好的传播覆盖率。此外，我们还表明，在适度的假设下，使用相同数量的种子和节点排序，顺序播种比使用相同数量的种子和节点排序的单阶段播种表现更好。最后，我们在有向图和无向图上比较了单阶段和顺序方法与著名的贪婪方法的实验结果，以提供顺序播种好处的客观衡量标准。令人惊讶的是，将顺序播种应用于简单的基于度的选择会导致比目前被认为是最佳启发式方法的计算成本高昂的贪婪方法更高的覆盖率。
