ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2022, Vol. 59 ›› Issue (2): 294-309.doi: 10.7544/issn1000-1239.20210891

所属专题: 2022空间数据智能专题

• 人工智能 • 上一篇    下一篇

地理社交网络中基于多目标组合优化的空间感知影响力联合最大化

金鹏飞1,常雪芹1,房子荃1,李淼2   

  1. 1(浙江大学计算机科学与技术学院 杭州 310027);2(华为技术有限公司华为云架构业务部 广东深圳 518129) (jinpf@zju.edu.cn)
  • 出版日期: 2022-02-01
  • 基金资助: 
    国家自然科学基金项目(62025206,61972338,62102351);中央高校基本科研业务费专项资金

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.

摘要: 影响力最大化问题旨在从社交网络中寻找若干具有高影响力的用户节点(种子),以触发最大化的信息传播规模.目前绝大多数工作认为社交网络中所有用户都拥有相同的影响力推广价值.然而,在基于位置的营销活动中,影响力推广的主体通常为带有位置标签的空间对象,考虑到用户在物理世界中的移动受限问题,空间对象仅能吸引其邻近范围内的潜在用户.因此,为了最大化市场营销潜力,商家通常需要同时拥有多个营销目标,譬如,连锁店企业对旗下的多家门店进行联合推广.不同的推广内容以及不同的影响力种子选择都将对营销推广的效益产生切实的影响.鉴于此,综合考虑商家在营销过程中对推广门店位置的选择以及在线上部署影响力传播种子的策略,在地理社交网络中研究基于多目标组合优化的空间感知影响力联合推广问题.首先分析了问题的理论难度,阐明了其与传统影响力最大化问题的区别.为支持高效且准确的问题求解,根据用户推广权重的差异,拓展了现有反向影响力采样(reverse influence sampling, RIS)技术,对不同位置和种子组合下的影响力传播收益进行理论保证下的上下界评估,并基于此提出了迭代处理算法框架,在多个轮次下实现高置信度保障的近似最优求解.最后,通过多组真实数据集上的实验,证明了所研究问题能在多目标组合下有效地提升空间感知的影响力推广效果,并验证了所提出算法的良好性能.

关键词: 影响力最大化, 信息传播, 基于位置的营销, 地理社交网络, 组合优化

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

中图分类号: