基于最小点覆盖和反馈点集的社交网络影响最大化算法

摘要：

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

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

所属期刊栏目：38

分类号：TP393(计算技术、计算机技术)

资助基金：国家自然科学基金61370193@@@@The National Natural Science Foundation of China 61370193

在线出版日期：2016-05-30（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：795-802