Location-based Influence Maximization In Social Networks

Influence maximization(IM)problem,which selects a set of users in a social network and these users diffuse information through friendships to maximize the expected number of users influenced by the selected users.IM problem has important signification in product marketing,and service promotion.The problem has quickly became a hot research area in the field of social network when influence maximization problem is raised.Scholars put forward a lot of information diffusion model to simulate the process of information dissemination in social networks,and further proposed algorithms to solve this problem.Typical information diffusion models are the Linear Threshold model and Independent Cascade model proposed by Kempe.For proposed information diffusion models,Kempe et al proposed the greedy algorithm to solve the problem of maximizing the impact.The greedy algorithm can obtain the /11-? approximate optimal effect,but the time complexity is very large.Then there are many improved algorithms based on greedy algorithm and heuristic algorithms to reduce the time complexity.The most common heuristic algorithm is the Max Degree algorithm which selects users with the most degree as the initial nodes set.Most of research only consider the friendly relationship when solve the Influence Maximization problem.However,with the development of the network,the relationship between nodes in the social network is not only a friendly relationship but also a hostile relationship.Therefore,it is also important to consider the adversarial relationship between nodes when considering Influence Maximization problem.At the meantime,with the explosion of smart phones and social network services,location-based social networks(LBSNs)are becoming more and more important.The historical check-ins information in LBSN can reflect the mobility behavior and consumption preference of users.The general information diffusion models cannot describe the diffusion process of influence in social networks when the promotion is related to a geographical location since the location will affect the users' acceptance.Focusing on these issues,the IPR algorithm based on Page Rank is first proposed to solve the influence maximization problem in signed network,and experiments are carried out in a real dataset to verify the effectiveness of the IPR algorithm.Then this paper proposes an improved influence diffusion model to describe the information diffusion process in social networks when promotion product or service related to a specific geographical location.At the same time,the influence discount algorithm is proposed to solve the Influence Maximization problem.Then we conduct experiments on two large-scale real data sets,and experimental results show the influence discount algorithm achieves high performance with other classic heuristic influence maximization algorithms.