陈 彬，帅天平,宋新月

(北京邮电大学 理学院， 北京 100876)

随着网络社交的迅速发展和演进，在线社交网络吸引了大量研究人员的兴趣.研究人员能够在大规模的社交网络和海量交互信息中提取、研究并分析社交用户之间的关系.影响力最大化问题是社交网络研究中最热点问题之一，其广泛的应用于推荐系统、病毒式营销和突发事件检测等领域.

然而由于社交网络用户群体的不断扩大，形成了结构复杂的社交网络.如何准确刻画结构复杂的社交网络，如何模拟计算信息在社交网络中的传播，如何设计高效的算法寻找高影响力的用户等是社交网络中亟待解决的核心问题.

1 国内外研究现状

Kempe[1]等人通过有向图去刻画社交网络，首次将影响力最大化问题建模成一个组合优化问题.证明了在独立级联模型下影响力最大化问题是NP-hard的，并给出一个近似比为1-1/e的贪婪算法.目前，对社交网络中影响力最大化问题的研究大都是在Kempe等研究的基础上进行探索，主要包括如下几个方面：

1)针对Kempe等提出的模型，进行算法优化.Leskovec[2]等将偷懒估值的方法运用到贪婪算法中，提出CELF算法.CELF算法既能达到1-1/e近似比，又能在实际计算中比贪婪算法效率更高.Borgs[3]等优化采样过程，提出基于反向影响力采样的近线性算法.Tang[4-5]在反向影响力采样的算法基础上,分别提出了TIM/TIM+[4]和IMM[5]算法.两种算法都能达到1-1/e-ε近似比，但是IMM算法减少了反向可达集的数目，算法运行时间更短.在IMM算法……