ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2022, Vol. 59 ›› Issue (2): 294-309.doi: 10.7544/issn1000-1239.20210891

Special Issue: 2022空间数据智能专题

Previous Articles     Next Articles

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

Jin Pengfei1, Chang Xueqin1, Fang Ziquan1, Li Miao2   

  1. 1(College of Computer Science and Technology, Zhejiang University, Hangzhou 310027);2(Huawei Cloud Business Unit, Huawei Technologies CO., LTD, Shenzhen, Guangdong 518129)
  • Online:2022-02-01
  • Supported by: 
    This work was supported by the National Natural Science Foundation of China (62025206, 61972338, 62102351) and the Fundamental Research Funds for the Central Universities.

Abstract: 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.

Key words: influence maximization, information dissemination, location-based advertising, geo-social network, combinational optimization

CLC Number: