随着网络以及社交网站的快速发展,例如Facebook和Twitter,社交网络已经成为人们获取信息和扩散信息的主要平台之一。在社交网络中,利用社交网络的信息扩散的特性(如快捷,范围广,影响力大等),可以有效的帮助企业进行产品推销,帮助政府进行谣言阻塞等等。在企业的产品宣传中,选择尽量少的关键性用户去扩散消息,不仅可以有效快捷的宣传产品,还能降低企业成本,提高产品最终带来的利润。基于此点,本文综合考虑消息扩散所需要的代价以及消息扩散范围问题。本文主要考虑解决两个问题:影响力最大化问题和最小代价的信息传播问题。其中最小代价的信息传播问题是在影响力最大化问题的基础上结合现实情况进行调研后提出的。在最小代价的信息传播问题中,本文提出代价函数的概念,代价具体包含以下两个方面的内涵:一方面代价指种子结点集合中结点的个数,即给定相同的信息扩散范围,选择作为种子结点的结点个数最少;另一方面代价指种子结点集合所需要的花费成本,即给定相同的消息扩散范围的前提下,总的代价最小,即种子结点集合需要花费的成本最少。针对代价的不同内涵,本文中考虑了两种不同代价函数的情况。针对影响力最大化问题,本文归纳总结了现有的影响力最大化算法,提出基于HISS方法的影响力最大化算法(HISS-IM),其特征在于种子结点集合中的每个结点与其他结点的最短距离至少是h+1跳,这样可以避免种子结点间的影响力重叠,从而使得在相同的信息扩散范围下,需要的种子结点个数更少。针对最小代价的信息传播问题,本文首先提出基于HISS的最小代价的结点选择算法(HISS-MCID),结合结点的权重和代价信息选取出候选种子结点集合,然后提出一个评估函数预估种子结点集合的影响范围选取出种子结点集合。本文接着设计基于信息传播模型的结点选择算法(IPMA),在选取结点的过程中,考虑结点的代价,并且基于信息传播模型来选取种子结点。本文还利用社交网络中的中心性指标思想,提出性价比的概念,设计基于性价比排序的结点选择算法(HRA),即在选取结点的过程中,优先选择性价比高的结点。最后,本文利用现实中的公开数据集,分别在数据集上采用独立级联模型和权重级联模型来模拟整个信息传播过程,对本文提出的算法进行实验分析和论证。针对影响力最大化问题,在结点相互影响概率不同时,在同样数目的种子结点的情况下,本文提出的HISS-IM方法其影响的结点数目比经典算法要更多,尤其是在要求影响范围越大的情况下,效果更加明显。针对最小代价的信息传播问题,采用线性代价函数的情况下,三种算法的效果相差不是很明显,在同等影响范围的要求下,IPMA算法需要花费的代价最小,但其运行时间长。采用常数代价函数并且结点相互影响概率不同的情况下,HISS-MCID方法在达到相同的影响范围时相比于另外两种算法,其需要的种子结点个数更少。