随着互联网的普及和在线社会网络的发展,研究者可以获取丰富的历史数据,并对社会网络中的信息传播进行分析、预测和利用。作为一种新型的媒介,社会网络中的信息可以像“病毒”一样迅速地在人与人之间传播,因此受到了普遍的关注：一方面,相比于电台、报纸、电视等大众传媒广播的方式,社会网络中的信息传播具有“口口相传”的效应,更容易被人们所信任；另一方面,信息的传播还可能具有级联效应,造成广泛的影响。然而,社会网络中难以预测的个体行为和复杂的拓扑结构,为信息传播的分析和利用带来了极大的挑战。因此,如何通过历史数据挖掘,对信息传播进行分析预测,并进一步利用信息传播达到影响力最大化,为企业宣传、广告营销、舆情监控等提供决策辅助,已成为当前社会网络研究的一个热点问题。针对上述问题,本文首先对信息级联的结构进行挖掘,识别出社会网络信息级联几种典型结构模式,并利用结构模式对信息传播进行预测；然后基于信息传播的模式,分析了多种信息同时传播的交互模型,用信息回溯的方法找到最有影响力的节点；最后研究了在给定预算的情况下,如何通过预算分配来激励这些最有影响力的节点,从而使得影响力的扩散可以达到最大。论文的主要贡献可概括如下：(1)分析信息传播的级联结构,并通过级联结构预测信息未来的传播模式。在社会网络中,信息级联的结构往往和信息传播互相影响。首先,不同机制所驱动的信息传播会导致结构不同的级联,同质性主导的级联往往会发展为宽而浅的结构,而社会影响力主导的级联则会变得深而复杂；其次,不同结构的信息级联会传播到不同的范围和社群,从而影响信息的传播过程。本文采用数据驱动的方法,分析了大量信息级联的传播结构,通过对信息级联的结构进行降维嵌入(embedding)和谱聚类(spectral clustering)，识别出社会网络中的信息级联五种典型的结构模式,并且发现不同结构模式的信息级联之间具有明显差异的特征。根据以上观察,本文引入级联结构来预测信息未来的传播模式,实验结果表明,该方法可以显著提升预测的准确率。(2)研究了多种信息同时传播的交互模型,并识别其中有影响力的节点。社会网络中往往有多种信息在同时传播,而且信息之间可能存在竞争、互利等交互关系。针对这种情况,本文设计了交互信息级联模型来刻画多种信息之间的传播,可以同时考虑信息之间的交互关系和用户对交互信息的选择偏好。在这个模型下,本文首先证明了该问题是NP难的,并提出了一种基于回溯的马尔科夫随机游走(markov random walk)算法：假设信息传播可以达到所有节点,然后通过传播模型进行回溯,找出信息最有可能的来源,即为影响力最大的节点。模拟实验表明,相比于其它常用的算法,本文提出的算法可以在绝大多数情况下取得最好的效果。同时,该算法还可以快速地收敛,因此有很高的运行效率。(3)提出了一个基于预算分配的策略,通过激励社会网络中的初始用户实现影响力最大化。为了激励初始用户实现影响力最大化,以往的工作一般理想地假设用户具有确定的估值,只有分配的预算高于该估值,用户才会成为初始用户；而在实际情况中,在不同的预算下,用户都有可能成为初始用户。本文使用效用函数(utility function)来刻画用户的满意度,假定用户的估值满足一定的概率分布函数。在这个模型下,通过归约证明了该问题的难度。同时,提出了一个离散贪心的算法来找出预算分配的方案：首先将预算均匀地离散化,然后采用迭代的方式将预算依次分配给具有边际增益最大的用户。该方法可以在离散的设置中取得近似最优的结果。进一步,本文还证明了当合理地选择一个离散的粒度后,该算法可以在预算连续的设置下取得1-1/e-o(1)的性能保证。最后,本文还通过更新边际增益的计算和估算传播概率的方法来提升算法的执行效率。实验结果表明,相比于其它已有的方法,离散贪心的算法能显著提高信息覆盖的范围,同时还有非常好的可扩展性。