Influence maximization is the task of selecting a small number of seed nodes in a social network to maximize the influence spread from these seeds. It has been widely investigated in the past two decades. In the canonical setting, the social network and its diffusion parameters are given as input. In this paper, we consider the more realistic sampling setting where the network is unknown and we only have a set of passively observed cascades that record the sets of activated nodes at each diffusion step. We study the task of influence maximization from these cascade samples (IMS) and present constant approximation algorithms for it under mild conditions on the seed set distribution. To achieve the optimization goal, we also provide a novel solution to the network inference problem, that is, learning diffusion parameters and the network structure from the cascade data. Compared with prior solutions, our network inference algorithms require weaker assumptions and do not rely on maximum-likelihood estimation and convex programming. Our IMS algorithms enhance the learning-and-then-optimization approach by allowing a constant approximation ratio even when the diffusion parameters are hard to learn, and we do not need any assumption related to the network structure or diffusion parameters.
翻译:影响最大化的任务是在社会网络中选择少量种子节点,以最大限度地扩大这些种子的传播影响。 在过去20年中,已经对此进行了广泛调查。 在卡纳基环境下,社会网络及其传播参数被作为投入。在本文中,我们考虑的是网络未知的更现实的抽样环境,我们只有一套被动观察的级联,记录每个扩散步骤的一组激活节点。我们研究的是从这些级联样本(IMS)中最大限度地发挥影响的任务,并在种子集分布的温和条件下为它提出恒定的近似算法。为了实现优化目标,我们还为网络推断问题提供了新的解决方案,即学习传播参数和从级联数据中获取网络结构。与先前的解决方案相比,我们的网络推断算法需要较弱的假设,而不需要依靠最大似估计和配置。我们的IMS算法通过允许持续近似比率,即使传播参数难以学习,也不需要与网络结构或扩散参数有关的任何假设。