近年来,迅速兴起的在线社交网络不仅成为人们传播信息的重要途径,而且也成为众多应用实施的流行平台。其中最典型应用是口碑影响(或病毒式营销)——通过网络用户之间口耳相传,实现营销信息传播。该应用实施的一个关键问题是影响力最大化问题:给定一个网络和参数k,找出网络中k个用户;从这些用户发起信息传播,使得最终受影响用户数最大化。传统影响力最大化算法大多数忽略用户节点选择的成本代价,且运行效率较低。本文考虑选择节点的成本因素,研究基于代价的影响力最大化问题,主要工作内容如下:(1)研究如何在网络中找出k个影响力最大化、代价最小化的用户。本文采用基于跳步的独立级联模型,提出了针对最小代价IM问题的惰性前进(简称HCLF)算法。该算法利用影响力最大化的子模性特点,快速地计算出本轮非种子节点的“收益率”增益上限,若大于或等于上一轮的增益上限,则此节点为种子集。实验结果表明,在不同的数据集和不同的代价下,HCLF比传统的影响力最大化算法CELF的运行时间快千倍以上;收益率也比CELF高5至8倍,验证了所提出算法的有效性。(2)研究给定预算下,如何快速地找出带来高收益的种子用户群。本文利用基于跳步的独立级联模型,设计了针对给定预算下IM问题的惰性前进算法(BHLF)。该方法通过基于跳步的方法找出对应预算下的候选集,然后使用BHLF算法快速地在候选集中挑选出对应预算下的种子集。在真实数据集Nethept和GR-QC上的进行了实验,对算法在运行时间和效果上进行了比较;实验结果表明,BHLF算法的运行时间缩短了1000多倍,同时“性价比”提高了20%。(3)研究给定的影响力覆盖范围下,如何找到激活成本最小的目标集。针对线性阈值模型,提出了一种基于跳步的具有近似保证的算法。该算法在有限跳步局部范围内评估节点影响力和成本,度量节点对整个网络的影响。在数据集Net HEPT和Email上进行了实验;结果表明,在给定影响力覆盖范围下,所提出算法比折扣度算法、随机算法能够节约15%-80%成本。