影响力最大化和传播抑制等问题在复杂社会网络分析领域有着重要的研究和应用价值。在影响力最大化中和传播抑制等问题中,成本的限制已经引起了很多很多研究者越来越多的关注。近年来,成本限制下的影响力最大化和传播抑制最大化问题引起了很多学者的关注。限制下的影响力传播不仅要考虑影响力在最大范围的传播,还要考虑选取种子的成本。成本限制下的负影响力的传播抑制最大化是在固定成本的限制下,抑制尽可能多的负影响力传播。由于影响力的传播是一个随机过程,大多数的影响力最大化以及抑制算法都是基于概率模型,通过Monte-Carlo方法来模拟影响力扩散的过程,而这一个过程需要大量的计算时间。为了提高算法的效率,我们在影响力最大化以及抑制算法中都使用了抽样图的方法,用节点在抽样图中的可达节点去代替影响力扩散这一动态过程,节省了计算时间。针对成本限制下的最小影响力最大化和传播抑制等问题,本文的主要工作以及研究成果有:(1)针对基于线性阈值模型的成本限制下的影响力最大化的问题,提出了基于抽样的影响力最大化算法。在目前的算法中,耗时最长的就是对于度量影响力扩散使用的Monte-carlo 模拟,这个过程是一个动态的过程,而且对于每一批不同的种子都需要进行模拟。为了提高算法的效率,我们使用抽样图来固定这一个模拟。我们介绍了不确定图的可能世界概念,然后在图中进行路径抽样,并使用Chernoff界去估计需要计算的抽样图的数量。实验结果证明,我们的算法精度高且提高了算法效率。(2)定义了基于概率覆盖的影响力传播的成本最小化问题,我们将该问题规约为带权集合覆盖问题(WCS),从而证明了该问题是NP-hard的。我们还证明了该问题的影响力的期望值函数是单调、次模的。提出了基于抽样的贪心算法,并估计了算法的误差。实验结果证明,我们的算法具有较高的精度。(3)介绍了成本限制下的影响力传播抑制问题,定义了各个顶点的抑制集合和被抑制集合,通过在多个抽样图上的抽样来估算正种子集合的抑制范围的期望值。提出了相应的贪心法逐个选取正种子集合的元素,并给出了在选取了一个顶点加入正种子集合以后,相应顶点在抽样图上的抑制集和和被抑制集合的更新规则。我们对提出的算法进行了实验,实验验证了我们算法的可行性。