Least Cost Problem For Target Users In Social Networks

With the booming development of online social networks,it is increasingly valuable for precision marketing and personalized recommendation for target user by analyzing users’ behaviors and attributes.This paper mainly focuses on the research of the Least Cost problem for target users.We use the user profile to distinguish whether are the target user.First,we research the Least Cost problem for target users in Non-competitive social networks(NLC-TU)problem.Its objective is to minimize the cost to choose initial seeds while at least J target users described by certain user profile are influenced.Considering that users have different propagation capabilities in social networks,a novel propagation model named Limited Diffusion Independent Cascade model(LD-IC model)is presented.It is proved that the NLC-TU problem in LD-IC model is NP-hard and the influence propagation function is submodular and monotonous.Therefore,a greedy algorithm with error guarantees is developed for the problem.However,the greedy algorithm is too time consuming to be scalable to large networks,so the Target User Local Influence Heuristic algorithm(TU-LIH)is proposed by utilizing local influences of each node to approximate the influence propagation in LD-IC model.Extensive experiments on datasets from four real social networks demonstrate the effectiveness and efficiency of proposed algorithms.Then,the Least Cost problem for target users in Competitive social networks(CLC-TU)problem based on the NLC-TU problem is proposed considering the complexity of information propagation in the network.Assuming that users in competitive network can receive and propagate many information but will only be influenced by one kind of information in the end,we propose a Competitive Limited Diffusion Independent Cascade model(CLD-IC model).It is proved that the CLC-TU problem in CLD-IC model is NP-hard and the influence propagation function is submodular and monotonous.Therefore,this paper designs a developed greedy algorithm with error guarantees and Target User Competitive Influence Heuristic algorithm(TU-CIH)to solve the problem.Finally,the feasibility and high efficiency of the algorithm are demonstrated by experiments on different datasets.