%A 孙永樾, 李红燕, 张金波 %T RAISE:一种高效的社交网络影响成本最小化算法 %0 Journal Article %D 2019 %J 计算机科学 %R 10.11896/j.issn.1002-137X.2019.09.007 %P 59-65 %V 46 %N 9 %U {https://www.jsjkx.com/CN/abstract/article_18499.shtml} %8 2019-09-15 %X 在市场营销、政治选举等领域,说服个体接受新产品或新思想需要耗费一定的成本。将影响成本最小化问题定义为如何选择不同个体,使影响最终扩散到社交网络中给定数量的个体,且耗费的成本最小。运用现有方法解决该问题,解的质量和时间效率都面临一定的瓶颈。为了解决该问题,提出了一种高效的算法——RAISE算法。在理论上,当期望达到的影响与网络规模可比拟时,该算法具备常数近似比和线性时间复杂度。实践表明,该算法在解的质量和时间效率两方面都显著优于现有方法。