成本控制下的快速影响最大化算法
来源：计算机应用杂志2017年第2期北京时间：
作者：刘院英, 郭景峰, 魏立东, 胡心专
单位：1. 燕山大学 信息科学与工程学院, 河北 秦皇岛 066004;2. 河北经贸大学 信息技术学院, 石家庄 050061
摘要：针对成本控制下影响最大化时间复杂度高的问题，提出一种快速的最大化算法BCIM。首先提出对初始节点进行多次传播的传播模型；其次选择高影响力节点作为备用种子，并基于近距离影响减少计算节点影响范围的工作量；最后利用动态规划方法在每组备用种子中最多选择一个种子。仿真实验表明，与随机算法Random、每轮取影响力增量最大的节点的贪心算法Greedy_MII、每轮取影响力增量与成本比值最大的节点的贪心算法Greedy_MICR相比，在影响范围上，BICM接近或优于Greedy_MICR及Greedy_MII，远次于Random；在种子集合的质量上，BCIM、Greedy_MICR、Greedy_MII三者差距较小，但都远远好于Random；在运行时间上，BCIM是Random的几倍，而两个贪心算法都是BCIM的几百倍。BCIM算法能在较短时间内找到更有效的种子集合。
关键词：影响最大化,在线社会网络,成本控制,动态规划,多次传播模型
基金资助：国家自然科学基金资助项目（61472340）；河北省科技计划项目（15210913）。
