随着近二十年信息科学的发展,社交网络迅速普及,信息传播带来的影响深入人们的日常生活中,它为大规模的在线病毒营销提供了有效的平台。病毒营销是指将免费产品提供给特定人群后,人们会因社交网络中的影响力将产品推荐给朋友、朋友的朋友,最后产生大规模的营销效果。随着在线社交网络的快速发展,关于病毒式营销做了大量的研究工作,但是多数研究工作都基于一个假设,最终的产品收益与被影响的用户的个数相关。然而在某些情形下,被影响的用户的个数不能反映一个产品营销的成功,某些产品的收益依赖于被影响用户之间的互动活动。在线游戏就是一个很好的例子,游戏公司的收益主要得益于游戏玩家的参与和互动。在论文中,我们主要研究与被影响的用户之间互动活动相关的收益最大化问题的优化方法,主要工作和研究成果可以归纳为以下几个方面:(1)以在线游戏产品的营销为例,我们分析了在线游戏产品收益的来源,游戏的收益与游戏玩家的交互活动紧密相关,提出了收益最大化问题(PMP),即在社交网络中,选择一个种子集合,通过社交网络中的影响力传播,使得最终被影响的用户之间产生的收益最大。分析了问题的复杂性,证明了问题是NP-hard的。对于传统的影响力最大化问题,由于问题本身具有次模性,贪婪算法可以获得1-1/e近似保证。但是,我们证明了收益最大化问题既不是次模的也不是超模的,所以经典的贪婪算法不能直接用于收益最大化问题来获得一个近似解。为了解决收益最大化问题,从非次模优化的角度出发,我们提出了基于DS(Difference of Submodular)分解的解决策略,把原问题分解成两个次模函数的差。基于分解得到的两个次模函数的模上界和模下界,我们提出了四个模函数来近似原函数,并设计了四种对应的启发式算法来解决收益最大化问题。为了处理计算目标函数的复杂性,我们设计了基于反向可达集的采样方法,这种方法可以代替蒙特卡洛采样方法,具有更强的可扩展性。通过实际的数据集,我们验证了算法的有效性。(2)由于社交网络本身的特点,很难得到每条边传播概率的精确值,通常能够获得的是一个传播概率区间,即边上真实的传播概率会在这个区间内。以上观察驱使我们研究以下问题,在社交网络中,选择一个种子集合,在传播概率不确定的情形下,使得最终的与用户交互活动相关的收益在最坏情形下达到最好,我们称之为鲁棒的收益最大化问题(RPMP),为了解决这个问题,我们设计了基于双三明治算法的解决方案。基本思路如下,首先在最小的概率空间向量下和最大的概率空间向量下,求解收益最大化问题,然后选择在最小概率空间向量下,获得较大收益的那个解,作为算法的解。给定传播概率空间的一个概率传播向量,求解收益最大化问题是一个非次模问题。为了解决这个非次模的子问题,我们找到该问题的次模上界和次模下界,然后应用三明治算法,分别求解次模上界,次模下界,原问题,将对原问题来说最好的解输出,作为这个子问题的解。通过理论分析,证明了双三明治算法可以得到一个与数据相关的近似解。为了进一步提高算法的鲁棒性,我们提出了采样的方法,来缩小边的传播概率空间,即降低每条边的传播概率的不确定性,然后我们将双三明治算法与统一的采样方法结合,来解决鲁棒的收益最大化问题。对于一个给定的鲁棒率,我们给出了统一采样的复杂性,实验结果表明,我们的算法可以提高问题的鲁棒性。(3)最后,为了处理影响力传播的随机性,即选择种子以后,该种子实际的影响力传播过程和能够影响的节点集合是不确定的,为此我们提出了自适应的策略来解决社交网络中收益最大化问题,定义了自适应的收益最大化问题(APMP),分析它的复杂性,证明了该问题是自适应的非次模的,因此自适应的贪婪策略无法直接应用到该问题从而获得有保证的近似解。为了解决这个问题,我们找到了目标函数的上界函数和下界函数,并证明它们都是自适应次模的。然后我们将三明治策略应用于自适应的收益最大化问题中,设计了自适应的三明治策略,证明了该策略可以获得数据相关的近似解。据我们所知,本论文第一次将三明治策略应用于随机优化中,用来解决适应的非次模函数优化问题,我们提出的自适应三明治策略可以作为适应的非次模随机优化问题的一般解决框架。