成本约束下影响力最大化问题研究

摘要

Enterprise excepts to influence more user in the spreading process of social network information so that they can achieve marketing goals under the constraint of limited cost.Based on this background,de-fine a new social network influence maximization problem:the influence maximization problem under cost constraint that is select a initial node set under the condition of limited cost to spread information so that the influenced range in the whole network can be maximized at the final state.This paper bases on the net-work topological structure of user and user interaction information in the network to measure the user acti-vation cost,solve the above problems by genetic algorithm in the Independent Cascade Model and use the experiments of different data set to verify that the genetic algorithm has good effect on the final influenced range and operating time at last.%企业希望在社交网络信息传播过程中影响到更多的用户，以便其在有限成本约束下达到营销目标。依据此背景，定义了一个新的社交网络影响力最大化问题：成本约束下的影响力最大化问题，即在有限成本条件下选择一个初始节点集传播信息使得最终状态下全网被影响到的范围最大化。基于网络中用户的网络拓扑结构和用户交互信息衡量用户激活成本，并在独立级联模型下使用遗传算法求解上述问题，最后通过不同数据集上的实验验证遗传算法在最终影响范围和运行时间上都获得较好的效果。