Abstract: Concerning the high time complexity in influence maximization under budget control, a fast influence maximization algorithm, namely BCIM, was proposed. Firstly, a new information dissemination model which propagates the initial nodes for many times was proposed. Secondly, the nodes with high influence ranking value were selected as candidate seeds, and the calculation of node's influence scope was decreased based on the short distance influence. Lastly, only one seed was selected at most in each set of candidate seeds by using the dynamic programming method. The experimental results show that, compared with Random (random algorithm), Greedy_MII (greedy algorithm based on the maximum influence increment) and Greedy_MICR (greedy algorithm based on the maximum of influence increment over cost ratio), the influence scope of BCIM is near to or a bit better than that of Greedy_MICR and Greedy_MII, but much worse than that of Random; the quality of seeds set of BCIM, Greedy_MICR and Greedy_MII is similar, but much better than that of Random; the running time of BCIM is several times of Random, while the running time of the both greedy algorithms are hundreds times of BCIM. In summary, BCIM algorithm can find a more effective seeds set in a short time.

Key words: influence maximization, online social network, budget control, dynamic programming, multi-propagation model

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

关键词: 影响最大化, 在线社会网络, 成本控制, 动态规划, 多次传播模型