论文标题
影响最大化的溶液分布：对三种算法方法的高级实验研究
The Solution Distribution of Influence Maximization: A High-level Experimental Study on Three Algorithmic Approaches
论文作者
论文摘要
影响最大化是社会影响分析中最基本的算法问题之一。在过去的十年中，一项巨大的努力致力于开发有效的影响最大化算法，以便确定``最佳''算法已成为一项艰巨的任务。在Sigmod'17中，Arora，Galhotra和Ranu在现有的11种算法上报告了基准结果，并证明没有单一的最先进可以在计算效率和解决方案质量之间提供最佳的权衡。 在本文中，我们报告了一项高级实验研究，以实现影响最大化的三种完善的算法方法，即被称为Onehot，快照和反向影响采样（RIS）。与Arora等人不同，我们的实验方法是如此设计，以至于我们检查了随机解决方案的分布，表征了样本数和实际溶液质量之间的关系，并避免实施依赖性。我们的主要发现如下：1。对于足够大的样本编号，无论算法如何，我们都会获得独特的解决方案。 2。Onehot，快照和RIS的平均解决方案质量以相同的速率提高到样本编号的缩放。 3。Oneshot需要的样本比快照需要更多，而快照比RIS所需的样本更少但更大。我们讨论了将Onehot，快照和RIS的时间效率相同的准确性。我们的结论是，只有在可用内存的大小有限的情况下，Onehot才适合使用，并且RIS比大型网络的快照更有效。快照比小型低概率网络更可取。
Influence maximization is among the most fundamental algorithmic problems in social influence analysis. Over the last decade, a great effort has been devoted to developing efficient algorithms for influence maximization, so that identifying the ``best'' algorithm has become a demanding task. In SIGMOD'17, Arora, Galhotra, and Ranu reported benchmark results on eleven existing algorithms and demonstrated that there is no single state-of-the-art offering the best trade-off between computational efficiency and solution quality. In this paper, we report a high-level experimental study on three well-established algorithmic approaches for influence maximization, referred to as Oneshot, Snapshot, and Reverse Influence Sampling (RIS). Different from Arora et al., our experimental methodology is so designed that we examine the distribution of random solutions, characterize the relation between the sample number and the actual solution quality, and avoid implementation dependencies. Our main findings are as follows: 1. For a sufficiently large sample number, we obtain a unique solution regardless of algorithms. 2. The average solution quality of Oneshot, Snapshot, and RIS improves at the same rate up to scaling of sample number. 3. Oneshot requires more samples than Snapshot, and Snapshot requires fewer but larger samples than RIS. We discuss the time efficiency when conditioning Oneshot, Snapshot, and RIS to be of identical accuracy. Our conclusion is that Oneshot is suitable only if the size of available memory is limited, and RIS is more efficient than Snapshot for large networks; Snapshot is preferable for small, low-probability networks.
