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

• 作者: 潘惊治 许宇光 谢惠扬
• 来源期刊: 电子与信息学报
• 学科: 工学
• 关键词: 社交网络 影响最大化 传播模型 最小点覆盖 反馈点集
• 年，卷（期）: 2016,（4）
• 所属期刊栏目: 论文
• 页码范围: 795-802
• 页数: 8页
• 分类号: TP393
• 字数: 7732字
• 语种: 中文
• DOI: 10.11999/JEIT160019

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	谢惠扬	北京林业大学理学院	12	51	4.0	7.0
2	许宇光	北京大学信息科学技术学院	3	15	2.0	3.0
3	潘惊治	北京大学信息科学技术学院	2	14	2.0	2.0