病毒式营销被认为是最有效的营销方式之一，借助人与人之间的影响作用实现营销信息在消费者之间自发的扩散。随着信息技术的迅猛发展，大量在线社交网站和社会媒体网站涌现并成为人们交流和分享信息的重要平台，给病毒式营销的发展带来重大机遇，因此这种营销方式变得日益流行。病毒式营销的一个关键问题是种子用户选择，即定位一组种子用户作为营销的初始投放对象，以期获得最大的影响范围——社会网络中被影响的用户数量，该问题通常被称为影响最大化问题。作为社会网络分析的一个重要问题，影响最大化问题近些年随着在线社会网络的兴起得到学术界和工业界的广泛关注。在线社会网络规模大、拓扑结构复杂等特点给求解其上的影响最大化问题带来很大困难，体现在对影响最大化算法的可扩展性、鲁棒性和求解精度上的挑战。因此，研究在线社会网络上的影响最大化问题具有重要的理论意义和应用价值。　　本文对在线社会网络上的影响最大化问题展开研究，针对在线社会网络规模大、拓扑结构复杂多样的特点，分别研究了具有高可扩展性的影响最大化近似算法和鲁棒性良好的启发式影响最大化算法。进一步的，本文从在线社会网络上营销场景的特点入手，研究了精准的影响最大化方式。本文的主要贡献及创新之处如下:　　本文首先针对求解影响最大化问题的经典贪婪算法面临的可扩展性与精度保障两难的问题，提出了一种非常有效的解决方法。本文指出该问题的根源在于，现有贪婪近似算法执行过程中影响范围函数的子模性和单调性存在被破坏的风险。为降低这一风险，这些算法每次估计影响范围时需要采用大量蒙特卡罗模拟，导致可扩展性差。基于上述认识，本文提出了一种快速的贪婪近似算法StaticGreedy，通过重复使用一组蒙特卡罗模拟结果估计影响范围，严格保证了影响范围函数的子模性和单调性。这使得StaticGreedy只需要采用少量蒙特卡罗模拟就能收敛至一个理想的解集，与现有贪婪近似算法求解精度一致但运行速度快了1000倍以上。本文还根据StaticGreedy的特点设计了一种加速策略，使其运行速度进一步提高了10倍左右。　　本文随后针对当前影响最大化算法在不同网络上性能表现不稳定的问题，提出了一种高效的启发式影响最大化算法框架IMRank并给出其具体实现。本文从贪婪算法的解集性质出发定义了一种特殊的节点排列——“自洽排列”，其中节点按其基于该排列的边际影响范围降序排列。IMRank通过迭代调整初始排列以获得在影响最大化问题上性能表现良好的自洽排列。其迭代方式非常高效且收敛性具有理论保证。一些简单的初始排列就能使其收敛至与贪婪算法解集性能接近的自洽排列。在IMRank的具体实现中，本文针对独立级联模型设计了一种高效的由后至前分配策略，能高效地计算所有节点基于给定排列的边际影响范围。大量实验表明，IMRank在运行速度和求解精度上的表现都优于现有的启发式影响最大化算法，具有更好的鲁棒性。　　本文最后探讨了现有影响最大化算法求解精度有限的问题，设计了一种面向在线营销场景的动态影响最大化，有效提高了影响最大化算法能获得的影响范围。其核心是分批动态选点方式，这是指允许在一次实际扩散的多个时刻分批地选择和投放种子节点，并在此过程中利用在线营销下可收集的实时扩散信息指导后续种子节点选择，从而提高单次扩散的影响范围。为更好地应用这种方式，本文提出了一个动态影响最大化问题，该问题是寻找一组最优时刻集合，使得依据该组时刻选择种子节点下，在给定截止时刻获得的影响范围最大。本文提出了两种有效的启发式算法求解该问题，并从理论和实验两方面证实了，优化种子节点选择时刻有助于算法获得更好的影响范围。在一些情形下，利用分批动态选点方式，基于度的简单种子节点选择策略就能得到比传统贪婪近似算法更大的影响范围，并且时间开销显著更低。