Location-Aware Joint Influence Maximizaton in Geo-Social Networks Using Multi-Target Combinational Optimization

Influence maximization aims to identify a number of influential nodes (seeds) in social networks, in order to trigger a largest information dissemination. Most of the existing studies equal the importance of users in social networks. In location-based advertising, the targets for promotion are spatial objects with geographical tags. Due to users’ mobility limitations in the world, the spatial object can only attract potential users in its local range. Hence, to fully improve the market potential, merchants often have multiple targets at the same time (e.g., managers of chain stores prefer to jointly promote several chains), where both the content of promotion targets as well as the seeds will actually affect the marketing performance. In view of this, this paper focuses on the joint optimization towards both merchant locations and seed selection policies, to best facilitate the location-aware joint influence promotion (LA-JIP) in geo-social networks. We first analyze the complexity of this problem, claim its difference from the conventional influence maximization problem. To efficiently and accurately solve this problem, we extend the reverse influence sampling (reverse influence sampling, RIS) techniques by considering users’ weights, and derive tightened upper and lower bounds to evaluate the solution with theoretical guarantees. Based on the bounds, we further develop an iterative algorithm to find the suboptimal result optimized by several rounds with high confidence. Finally, extensive experiments on real datasets demonstrate the effectiveness of LA-JIP in location-aware influence promotion, and also validate the good performance of the proposed methods.