快速发展的社交网络为信息交流分享提供了新途径。随着各类在线社交网络应用的兴起,社交用户交互行为与信息传播呈现爆发性增长。基于影响力(influence)的传播模型也因此成为了近年的研究热点并在推荐系统、电子商务中得到广泛应用。典型应用包括基于口碑效应的病毒式营销(viral-marketing),为社交网络上的产品推广选择若干个具有较大影响力的用户,通过激励(比如提供免费适用产品),促进他们在好友圈中推广产品,达成提升销售的目的。这个过程对应着影响力最大化问题,即从n个社交用户中找到达成最佳影响力扩散的k个用户(种子节点集合)。在过去的十多年中,独立级联与线性阈值模型在影响力最大化问题中得到广泛应用,对应的模型最优解近似比以及算法时间复杂度也得到了充分论证。当前该领域的主要研究工作是结合实际应用场景研究影响力最大化,并设计相应的高效求解算法。本文的主要工作就是研究三个典型应用场景的影响力传播问题:1.基于地理位置信息驱动的影响力最大化问题:现有的影响力最大化的工作选择社交网络中极具影响力的节点作为种子节点,来触发广泛的在线影响力传播。然而,这种用户驱动的影响力传播模式将影响力最大化问题的应用局限在了纯线上的场景。随着虚拟世界与现实世界之间的互动越来越频繁,用户的线上社交行为也越来越受到他们线下行为的影响。当需要在线下活动举办中考虑如何引起线上的影响力传播时,现有这些工作就无法提供有效的参考。本文从线下线上交互的角度考虑,定义了一个由地理位置驱动的影响力最大化问题(LDIM:location-driven influence maximization):给定一笔预算来举办线下活动,如线下营销活动或是为选举而进行的街头演说,怎样决定最优的举办位置以及举办的时长,从而获得最大的线上影响力传播。2.全局性预算敏感的影响力最大化问题:大部分现有的影响力最大化问题的研究通常都采用一个共同的假设:选择任何一个用户节点作为种子节点都产生相同的花费。然而,在现实中这个假设很少成立。因为通常来说,往往会需要付出更昂贵的价格才能让一个巨有更大影响力的人来作为种子节点来发帖。相反,说服他转发一个帖子很可能只需要较小的花费。基于这种现象,本文考虑同时选择种子节点(发帖)与推动节点(转发),并定义了全局性预算敏感的影响力最大化问题(HBIM:holistic budgeted influence maximization)。给定每个节点的发帖与转发报价,HBIM问题致力于用给定的预算来更加灵活地求得一个种子节点(发帖)与推动节点(转发)的配置从而使得影响力传播得以最大化。3.动态的负面影响力阻断问题:在一个网络化的系统之中,不可避免的会出现负面影响力的传播。这些恶意的负面影响力传播如果不加以控制,必然会带来严重的个人生命财产安全问题乃至造成社会动荡。因此,学界与业界开始关注与影响力最大化相反的一个问题:影响力阻断。当前关于影响力阻断(IB:influence blocking)问题的研究通常都采用单次选择的形式:一旦观察到负面影响力的传播,就立刻用完所有的预算来选择免疫节点。这种形式有两个缺陷。首先,没有针对紧急状况的出现预留措施因而很可能导致产生极大的损失。其次,可以不用继续免疫那些不会带来更多遏制负面影响力贡献的点,以避免产生不必要的花费。考虑到以上两点,本文提出了动态的影响力阻断(AIB:Adaptive Influence Blocking)问题。AIB问题旨在通过动态的选择免疫节点来最小化负面影响力的传播。每一次在当前时间戳对免疫节点的选择都依赖于对过去所有时间戳里负面影响力传播结果的观测。对于以上三个问题,本文给出了它们对应的精确数学形式描述,并在分析其求解难解性的基础上,分别对应的设计了高效可靠的近似求解方法,构建合理的数据结构来设计高效的实现算法。通过大量的理论分析,本文证明了所有提出方法可以取得的理论近似效果保证,误差边界以及理论上的平均时间复杂度。对于以上三个工作,本文都在真实数据集上进行了大量的模拟实验,实验的结果分析验证了本文提出算法的有效性与高效性。本文工作结合社交影响力传播实际场景,提出并解决三个典型实际应用问题。基于本文所提出的研究框架,有望解决更多的影响力传播应用问题,并对相关的学界与业界研究工作带来更多的启发,引出进一步探索方向。