论文标题
RCELF：一种基于残留的影响最大化问题的方法
RCELF: A Residual-based Approach for Influence Maximization Problem
论文作者
论文摘要
影响最大化问题（IMP）正在选择社交网络中的一组种子节点，以尽可能广泛地传播影响。它在多个领域中具有许多应用程序，例如，病毒营销经常用于新产品或活动广告。不幸的是，尽管这是计算机科学中经典且研究的问题，但所有这些提出的技术都在时间效率，记忆消耗和结果质量中妥协。在本文中，我们对最先进的方法进行了全面的实验研究，以揭示基本的权衡策略。有趣的是，我们发现，当已经考虑了网络的传播概率时，即使是最先进的方法也是不切实际的。有了现有方法的发现，我们提出了一种针对IMP的新型基于残差的方法（即RCELF），i）克服了现有近似方法的缺陷，ii）ii）在时间和空间的角度方面提供了高效率的理论保证结果。我们通过对实际数据集进行了广泛的实验评估来证明我们的提案的优势。
Influence Maximization Problem (IMP) is selecting a seed set of nodes in the social network to spread the influence as widely as possible. It has many applications in multiple domains, e.g., viral marketing is frequently used for new products or activities advertisements. While it is a classic and well-studied problem in computer science, unfortunately, all those proposed techniques are compromising among time efficiency, memory consumption, and result quality. In this paper, we conduct comprehensive experimental studies on the state-of-the-art IMP approximate approaches to reveal the underlying trade-off strategies. Interestingly, we find that even the state-of-the-art approaches are impractical when the propagation probability of the network have been taken into consideration. With the findings of existing approaches, we propose a novel residual-based approach (i.e., RCELF) for IMP, which i) overcomes the deficiencies of existing approximate approaches, and ii) provides theoretical guaranteed results with high efficiency in both time- and space- perspectives. We demonstrate the superiority of our proposal by extensive experimental evaluation on real datasets.
