随着过去十几年在线社会媒体迅猛发展，人们越来越趋向于利用社交平台交流想法、分享信息甚至接受一些创新和新产品，从而加速了信息、产品等传播。此外，在很多其他网络化系统中我们也可以观察到类似传播现象，例如，人类或者动物真实社会网络中的疾病传播、工业网络中的级联失效传播以及计算机网络中的病毒传播。学者们针对如何用数学模型刻画这些复杂的个体行为来帮助人们更好地理解传播现象机制以及如何控制传播过程进行了大量的科学研究，其中被广泛研究的一个核心问题就是影响力最大化问题。影响力最大化问题是指，在指定的传播模型下如何选取初始传播者集合(也称为种子点集合)，使得这些节点可以最大程度影响社会网络中的其他节点，从而使信息或者产品在社会网络中可以获得最大程度的扩散。此类研究具有广泛的实际应用及商业价值，例如市场营销中广告投放、控制谣言传播、意见形成以及预测信息传播等。
　　影响力最大化问题通常考虑积极正面的信息或者创新的传播。而一些不良或负面的东西，如失效、谣言、疾病等会以相似的方式在网络中传播，从而给社会带来不安定或者重大经济损失。因此，研究如何控制和抑制不良信息等传播具有重要意义。本文致力于社会网络谣言抑制与影响力最小化问题研究，主要研究成果分为三部分。
　　在第一部分，本文在线性阈值模型(LTM)下定义了两种不同的影响力最小化问题以形式化及广泛化一些实际社会现象，分别是具有中断情况的损失最小化问题(LMD)与确保传播目标的传播最小化问题(DMGT)。针对LMD问题，首先证明了解决此问题等价于解决一个整数线性规划问题从而求得最优解，同时提出了两个启发式算法以求得近似解；针对DMGT问题，在某些特定情况下提出了求最优解的方法以及一种普遍适用的启发式算法以求得次优解。
　　在第二和第三部分，通过采用不同的谣言抑制策略，我们重点研究和分析谣言抑制问题。首先采用抵消策略，其核心思想是通过传播正确信息与谣言相竞争以抵消掉谣言的影响。基于LTM模型提出了一种竞争型传播模型，称之为具有单向状态转移的线性阈值模型(LT1DT)。LT1DT模型很好地刻画了在同一网络中谣言和真相竞相传播的实际情况，同时克服了现已有竞争型模型中的一些缺陷。在LT1DT模型下，本文主要研究谣言传播最小化问题(MRS)，MRS问题被证明是NP-hard问题。由于其理论困难性，为解决此问题本文提出了三种不同的启发式算法，分别是PageRank，MinGreedy，ContrId。同时为了突出临近效应在抑制谣言传播中的效果，本文提出了它们的约束类型，分别是ProxPageRank，ProxMinGreedy，ProxContrId。其中新提出的启发式算法ContrId和ProxContrId可以保证MRS问题的目标函数在LT1DT模型下单调递减，此特性使得控制谣言的有限预算可以得到合理正确地应用。为了验证各个方法的效率，我们在四种不同的网络中做了仿真实验。仿真结果显示，基于传播动态的方法(ContrId)要优于基于中心性的方法(PageRank)。ContrId与PageRank具有相同计算复杂度，也就是与网络中节点个数呈线性关系，从而可以应用于大规模网络。通过引入临近效应，ContrId抑制谣言的效果与MinGreedy一样好，而其计算速度比MinGreedy要快两到三个数量级。
　　为了控制谣言传播，本文继而采用了网络干扰策略，其核心思想是通过封锁网络中的一些节点来抑制传播。首先，识别最有效k个封锁节点问题的目标函数在LTM模型下被证明是单调但是非次模与非超模的。其次，在LTM模型下基于内聚力的概念我们将识别最有效k个封锁节点问题形式化为一个非线性规划问题。通过引入一些数学技术，本文对非线性问题进行了线性化操作，从而解决识别最有效k个封锁节点问题等价于求解一个整数线性规划。最后，本文证明了在给定的种子集合下，原网络中的传播过程等价于它的激活子网络中的传播过程。这一结论可以有效地削弱整数线性规划的复杂度。为了验证利用整数线性规划解决识别最有效k个封锁节点问题的有效性，我们将此方法与基于贪婪算法的方法以及两个不同的基于中心性的方法做了对比仿真测试。仿真结果显示，整数线性规划解决方法要优于其他三种方法，而且由于其合理的计算时间，此方法可以应用于大规模网络。