【博士论文】影响力最大化及其变种的高效近似算法

在现代社会中，社交网络已经成为传播信息和沟通的基本渠道。诸如Facebook、Twitter、Instagram 和LinkedIn 这样的平台彻底改变了我们如何连接、分享和互动。除了个人使用之外，许多公司现在也将这些网络作为主要的广告媒介来推广他们的产品。这一趋势在影响力最大化（IM）领域催生了大量的研究。然而，在大数据时代，这些网络的不断增长使得影响力最大化算法的效率变得越来越重要。为了应对这一挑战，我们提出了一系列针对影响力最大化问题及其变体的高效算法。 给定一个具有𝑛 个节点和𝑚 条边的社交网络𝐺 和一个正整数𝑘，影响力最大化问题要求找到𝐺 中的𝑘 个节点，使得这𝑘 个节点影响的节点的期望数量最大化。现有算法的一个关键阶段是随机反向可达集（RR-set）的生成，这一阶段显著影响了现有算法的效率和可扩展性。我们对这一关键阶段进行了研究，并在独立级联（IC）模型下提出了一种高效的随机反向可达集的生成算法。通过这个新的生成方法，现有算法在独立级联模型下的期望复杂度最大可以提高图的平均度这样的级别。对于非均匀权重的独立级联模型，我们提出了一种无索引采样算法来提高采样效率。此外，现有的影响力最大化算法在大影响力的网络中存在扩展性差的问题，因为在这种情况下，随机反向可达集的大小通常相当大。我们通过减少可达集的平均大小来解决这一棘手问题，而且不牺牲近似保证。实验结果证明了所提算法的有效性。

然后，我们考虑了预算受限下的自适应影响力最大化（BAIM）问题。给定一个社交网络𝐺、每个节点的成本和预算𝐵，预算受限下影响力最大化（BIM）旨在找到一个节点集合𝑆 ⊆ 𝑉 ，使得𝑆 的总成本不超过𝐵, 并有最大的期望影响力。在自适应设置下，种子节点在观察到前一个种子的扩散结果后逐步选择。对于这个问题，我们设计了第一个可实用的算法，通过以概率方式选择成本感知的贪婪策略或单个有影响力的节点。该算法实现了期望近似保证。此外，自适应影响力最大化相关问题的可扩展性仍然是一个困难的问题。这是因为它们通常涉及多轮（例如，轮次等于种子数量），并且在每一轮中，它们必须重新构建足够多的反向可达集，以便达到所想要的近似保证，这导致过高的计算成本。为了解决这个困境，我们提出了一种增量更新方法。具体来说，它在构建反向可达集时保留额外的信息，在复用这些反向可达集时可以从第一次受影响的地方开始快速纠正偏差，从而节约了计算成本。最后，实验展示了我们的算法在影响力和运行时间方面相对于其他算法的优越性。 最后，我们探讨了符合边际效用递减定律（DMU）且预算受限的利润最大化（BPM）问题。给定一个社交网络𝐺，预算不受限的利润最大化问题旨在确定一个子集𝑆 ⊆ 𝑉 ，以最大化净利润。净利润可以由预期效用Γ(𝑆) 减去相关成本𝑐 (𝑆) 计算得到。然而，这样的设置存在两个显著的局限性：（i）它假设预算没有限制，然而实际情况中预算通常受限，比如市场营销，因此是不现实的；（ii）它使用期望影响力作为效用度量，忽视了经济学中一个广为人知的概念——边际效用递减效应。因此，我们引入了符合边际效用递减定律的效用函数，它采用了斜率递减的分段线性函数，接着我们构建了一个新的优化问题，称为符合边际效用递减定律且预算受限的利润最大化。我们首先设计了一个新的算法，它可以返回具有近似保证的集合𝑆，用于解决上述优化问题。然后，我们进一步介绍如何利用混合多根反向可达集的组合来高效计算期望效用Γ¹𝑆º。我们还引入了一个优化版本，从而改进了时间复杂度。实验表明了我们提出的算法的有效性。