成本控制下的快速影响最大化算法

• 作者: 刘院英 胡心专 郭景峰 魏立东
• 来源期刊: 计算机应用
• 学科: 工学
• 关键词: 影响最大化 在线社会网络 成本控制 动态规划 多次传播模型
• 年，卷（期）: 2017,（2）
• 所属期刊栏目: 第33届中国数据库学术会议(NDBC 2016)
• 页码范围: 367-372
• 页数: 6页
• 分类号: TP312
• 字数: 6906字
• 语种: 中文
• DOI: 10.11772/j.issn.1001-9081.2017.02.0367

摘要

针对成本控制下影响最大化时间复杂度高的问题,提出一种快速的最大化算法BCIM.首先提出对初始节点进行多次传播的传播模型;其次选择高影响力节点作为备用种子,并基于近距离影响减少计算节点影响范围的工作量;最后利用动态规划方法在每组备用种子中最多选择一个种子.仿真实验表明,与随机算法Random、每轮取影响力增量最大的节点的贪心算法Greedy_MII、每轮取影响力增量与成本比值最大的节点的贪心算法Greedy_MICR相比,在影响范围上,BICM接近或优于Greedy_MICR及Greedy_MII,远次于Random;在种子集合的质量上,BCIM、Greedy_MICR、Greedy_MII三者差距较小,但都远远好于Random;在运行时间上,BCIM是Random的几倍,而两个贪心算法都是BCIM的几百倍.BCIM算法能在较短时间内找到更有效的种子集合.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	胡心专	燕山大学信息科学与工程学院	13	59	6.0	6.0
2	郭景峰	燕山大学信息科学与工程学院	105	1001	17.0	28.0
3	刘院英	燕山大学信息科学与工程学院	14	25	3.0	4.0
7	魏立东	河北经贸大学信息技术学院	1	6	1.0	1.0