随着社交网络在人们的日常生活中扮演着越来越重要的角色,如何在社交网络上最大范围的传播某一信息,这一问题受到越来越多的人的关注。为了在社交网络上传播一个消息,我们可以选择一些个体作为初始群体(称为种子集合),说服该群体接受这个消息,然后通过他们的影响力,将这个消息传播给他们身边的人,而这些接受了消息的人又将接着影响到他们身边的人,通过这样的口口相传使消息得以在社交网络中传播。那么如何选择这个种子集合,使最终消息影响到的范围最大,这就是影响最大化问题要解决的。人们已经对社交网络上影响最大化问题做了大量的研究,主要包括两方面:建立合理的信息传播的模型以及提出合适的种子搜索方法来确定最终的种子集合,本文在这两方面分别做了研究,主要工作如下:1、由于现有的一些传播模型忽略了现实网络的一些不确定性,例如一般传播模型中,考虑到了信息的传播概率,但是没有考虑到节点的接受概率。因此,本文考虑到这些不确定性并且提出了一种现实独立级联模型,即Realistic Independent Cascade(RIC)模型。2、基于提出的RIC模型,提出节点的活跃度这一概念,以节点的活跃度来衡量节点的影响力,据此提出greedy-degree种子搜索算法,在合成网络及现实网络上进行对比实验,结果可以表明greedy-degree算法的优越性。3、基于提出的RIC模型,提出分三步完成的R-greedy种子搜索算法,以蒙特卡洛仿真对影响力函数进行近似计算,接着进一步提出M-greedy来优化R-greedy的时间复杂度。在合成网络及现实网络上进行对比实验,结果表明M-greedy和R-greedy算法具有近似的效果,优于已有的对比算法,且M-greedy相较于R-greedy时间开销将近为一半。4、基于提出的RIC模型,提出基于略图的D-greedy种子搜索算法,从略图的角度计算影响力函数,直接保证影响力函数子模特性的成立且节省时间开销。在真实网络及合成网络上的实验表明,D-greedy算法优势明显。