摘要：社交网络中的影响最大化问题是指在特定的传播模型下,如何寻找k个最具影响力的节点使得在该模型下社交网络中被影响的节点最多,信息传播的范围最广。该问题是一个优化问题,并且已经被证明是NP-难的。考虑到图的最小点覆盖和反馈点集中的顶点对图的连通性影响较大,该文提出一种基于最小点覆盖和反馈点集的社交网络影响最大化算法（Minimum Vertex Covering and Feedback Vertex Set,MVCFVS）,并给出了具体的仿真实验和分析。实验结果表明,与最新的算法比较,该算法得到的节点集在多种模型下都具有优异的传播效果,例如在独立级联模型和加权级联模型中超过当前最好的算法,并且还具有更快的收敛速度。

关键词：社交网络 影响最大化 传播模型 最小点覆盖 反馈点集 

单位：北京大学信息科学技术学院 北京100871 北京林业大学理学院 北京100083