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

Minimum Vertex Covering and Feedback Vertex Set-based Algorithm for Influence Maximization in Social Network

作　　者：许宇光[1] 潘惊治 谢惠扬[2] 

机构地区：[1]北京大学信息科学技术学院,北京100871 [2]北京林业大学理学院,北京100083

出　　处：《电子与信息学报》2016年第4期795-802,共8页Journal of Electronics & Information Technology

基　　金：国家自然科学基金(61370193)~~

摘　　要：社交网络中的影响最大化问题是指在特定的传播模型下,如何寻找k个最具影响力的节点使得在该模型下社交网络中被影响的节点最多,信息传播的范围最广。该问题是一个优化问题,并且已经被证明是NP-难的。考虑到图的最小点覆盖和反馈点集中的顶点对图的连通性影响较大,该文提出一种基于最小点覆盖和反馈点集的社交网络影响最大化算法(Minimum Vertex Covering and Feedback Vertex Set,MVCFVS),并给出了具体的仿真实验和分析。实验结果表明,与最新的算法比较,该算法得到的节点集在多种模型下都具有优异的传播效果,例如在独立级联模型和加权级联模型中超过当前最好的算法,并且还具有更快的收敛速度。Influence maximization is an optimization issue of finding a subset of nodes under a given diffusion model, which can maximize the spread of influence. This optimization issue has been proved to be NP-hard. Leveraging the fact that vertices in minimum vertex covering and feedback vertex set are of great importance for the connectivity of a graph, a heuristic algorithm for influence maximization based on Minimum Vertex Covering and Feedback Vertex Set（MVCFVS）. Extensive experiments on various diffusion models against state of the art algorithms are carried out. Specifically, the proposed algorithm performs excellent on Independent Cascade Model（ICM） and Weighted Cascade Model（WCM）, which exhibits its great advantages in terms of influence range and convergent speed.

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

分 类 号：TP393[自动化与计算机技术—计算机应用技术]