RAISE:一种高效的社交网络影响成本最小化算法

在市场营销、政治选举等领域,说服个体接受新产品或新思想需要耗费一定的成本。将影响成本最小化问题定义为如何选择不同个体,使影响最终扩散到社交网络中给定数量的个体,且耗费的成本最小。运用现有方法解决该问题,解的质量和时间效率都面临一定的瓶颈。为了解决该问题,提出了一种高效的算法——RAISE算法。在理论上,当期望达到的影响与网络规模可比拟时,该算法具备常数近似比和线性时间复杂度。实践表明,该算法在解的质量和时间效率两方面都显著优于现有方法。