在线社交网络是信息传播的基本媒介,社交网络中用户的决策易受到其邻居顶点的影响,并且这种影响能够在网络中传播。深入理解社交网络中的信息传播模式和规律,具有重要的社会价值和经济价值。本文主要针对信息转发问题和收益最大化问题展开研究。信息转发问题是研究一个用户是否转发来自社交网络上邻居的一条信息,而收益最大化问题是通过社交网络影响力的传播,制定优化策略使得商品营销收益最大化。对于信息转发问题,本文提出了三种建模方法,分别是信息传播进化博弈模型(EGT模型),基于用户及信息交互的信息传播模型(IAD模型),以及基于异质网络低维表示生成的信息传播模型(HUCE模型)。对于社交网络收益最大化问题,本文提出了基于计算的随机算法(CR算法)和基于计算的最大堆更新贪心算法(CHG算法)。以往相关研究工作大多专注于单个信息在社交网络上的传播,而很少考虑多个信息同时传播时的信息交互影响。由于在线社交网络中的信息数量非常之多,每天都有大量的信息暴露于个人用户,但是个人用户的注意力是有限的,用户可能只关注少部分的暴露信息,所以一段时间内发生的多条新闻或信息需要通过竞争用户的注意力而传播。除了信息竞争关系之外,还存在一些信息通过相互作用进而促进传播的情况。所以信息在传播过程中存在竞争或合作的交互关系。对于信息转发问题,本文的第一个工作提出了信息传播进化博弈模型EGT,对多个信息之间的交互关系建模。该模型的基本思想是将社交网络中多条信息类比为生物群体中的多个生物体,传播过程类似生物体间的相互作用,从一个状态演变成另一个状态。模型用统计学习的方法量化传播中信息之间的交互关系。由于社交网络中信息数量巨大,量化拟合出每两个信息之间的交互是不可能的。为了应对这一挑战,本工作提出了一个信息聚类的方法,对类别-类别的交互进行建模,而不对全部信息-信息的交互进行建模,这显著减少了需要学习的参数数量,使其具备更好的可扩展性。在DIGG网络中的实验结果表明,EGT模型有助于更好的理解信息的交互关系,并且能够更准确的预测用户的转发行为。基于信息进化动力学和进化稳定策略的深入分析揭示了信息在传播的过程中是否可以被其他信息促进或抑制。由于信息的传播会受到网络结构的影响,而用户在网络中的角色依其在网络中的结构而立,所以用户的社会角色及其交互关系也对信息传播至关重要。因此在模型建模时,自然的可将用户的结构特征以及他们的交互关系考虑进来。此外,每个用户都有自己对信息的偏好,这种偏好可视为用户与信息的交互关系,同样也会对信息传播造成影响。因此,对于信息转发的研究,如何集成用户以及信息之间的多种交互关系到一个统一的模型中,是一个挑战。本文的第二、第三个工作分别用不同的方法解决了这个问题:第二个工作提出了信息转发的概率模型,即基于用户及信息交互的信息传播模型IAD;第三个工作提出了信息转发的特征提取模型,即基于异质网络低维表示生成的信息传播模型HUCE。除了对用户以及信息之间的多种交互影响建模外,本文的第二个工作IAD模型还能够挖掘显式的信息类别之间的相互作用。相对于隐式的类别,更有意义的是显式类别之间的相互作用,即属于一个类别的信息是否会对属于另一类别的信息的传播产生影响。要深入研究显式类别之间的相互作用,首先需信息的类别。鉴于信息量巨大,对所有信息的类别进行人工标注是不可能的,如何找到一种高效的方法来对信息分类是一个重要挑战。本工作首先应用混合高斯模型来解释用户网络特征的生成过程,使用EM算法来提取每个用户的社会角色分布,然后基于Co-training的思想,使用少量的标记类别的信息,对大量未标记类别的信息进行分类。通过这些方法,可以得出每个信息的类别和每个用户的社会角色。IAD模型统计学习了用户以及信息的交互关系,有助于更好的理解信息传播,并为信息转发问题提供更准确的预测。在大规模微博数据集的实验表明,IAD模型在预测信息转发的准确性以及算法的学习时间方面都取得了很好的效果。此外,通过模型拟合,学习到的用户及信息间的交互关系揭示了有趣的发现,例如,食品类别的信息传播最容易抑制其他类别信息的传播,而广告类别信息的传播对其他信息的传播的抑制能力最弱。异质网络的低维表示学习,是本文的第三个工作HUCE模型的核心思想。为了研究用户以及信息之间的多种交互关系,用户的低维表示和信息的低维表示应该以一致的方式,在同一向量空间中生成。HUCE模型引入异质网络的思想,构建以用户和信息为顶点对象的异质网络,通过在异质网络中的统一学习,用户顶点和信息顶点的低维表示可以在同一个向量空间中生成。HUCE模型首先根据用户的网络关注关系,用户转发信息的行为历史,以及信息的文本内容,构建异质网络。而后提出了一个在异质网络上的随机游走算法HWalk,该算法基于元路径的相似性来指导随机游走的过程。基于HWalk生成的随机游走路径,模型将异质网络中不同类型的顶点学习到一个低维的连续向量空间中,得到顶点的低维表示。基于这些表示,所有用户和信息顶点的不同种类的相互作用关系可以构造出来,作为信息转发问题的输入特征。该模型能够帮助更好的理解信息传播中信息转发的决策行为。此外,模型生成的顶点的低维表示也能够应用到其它的任务中,例如信息的分类任务。在大规模的微博数据集上的实验结果表明,HUCE模型对于预测信息转发具有更好的效果,能够更准确的预测用户的转发行为,同时该模型在异质网络中生成的低维表示在信息分类任务中也取得了较好的效果。对于网络收益最大化问题的研究,是本文的第四个工作。近年来社交网络已成为市场营销的重要平台,很多公司在社交网络上通过口碑宣传推动其产品和服务,这促进了网络收益最大化问题的研究。在网络中,一个用户对商品的估值往往受到他的邻居用户的影响,如果该用户的邻居购买了某商品,则该用户对商品的估值会产生变化,更倾向于购买该商品。收益最大化问题是在社交网络影响力传播下,如何制定策略获得最优收益的问题。更具体的说,该问题为如何制定商品的价格,以及如何选择网络上的一些顶点,免费赠送商品给这些顶点,通过这些顶点的影响力,使得在网络上的整体收益最大化。随着社交网络的发展,当前的网络规模越来越庞大,导致了在解决商品收益最大化问题中的效率低,运行时间长。随着各种现实应用对于算法执行时间的要求越来越严格,需要研究大规模社交网络中商品收益最大化问题的高效处理技术。鉴于此,本工作提出了高效且有效的算法来解决商品无限供应情形和有限供应情形的收益最大化问题。首先,提出了基于局部无环图的收益近似计算的方法。相对于耗时的传播级联模拟方法,本方法执行速度非常快,其主要思想是将传播到一个顶点的影响力限制于一个局部的无环图中,该顶点的激活概率可以在该局部无环图中近似计算。对于商品无限供应情形,本工作提出了一个高效算法CR,基于局部无环图,商品的收益可以近似计算。对于商品有限供应情形,本工作提出了一个高效算法CHG,该算法的主要思想包含两个关键部分:(1)基于局部无环图的收益近似计算;(2)基于收益最大化问题的目标函数的子模特性,设计最大堆更新模式。在合成网络和大规模现实世界网络上的实验结果表明了 CR算法和CHG算法的有效性和高效性,相较于以往算法,本工作提出的算法能够在保持几乎同样的最大收益的同时,运行速度要快出若干数量级。