ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2019, Vol. 56 ›› Issue (6): 1302-1311.doi: 10.7544/issn1000-1239.2019.20180068

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



  1. (东北大学计算机科学与工程学院 沈阳 110169) (
  • 出版日期: 2019-06-01
  • 基金资助: 

An Advertising Game Theory Decision-Making Mechanism for Overlapping Seeds in Geo-Social Network

Yu Yaxin, Wang Lei   

  1. (College of Computer Science and Engineering, Northeastern University, Shenyang 110169)
  • Online: 2019-06-01
  • Supported by: 
    This work was supported by the National Key Research and Development Plan of China (2016YFC0101500) and the National Natural Science Foundation of China (61871106).

摘要: 作为社交影响最大化问题的重要应用之一,社交广告(或社交营销)已成为一个热门行业.其目标就是寻找k个最具影响力的种子节点,使产品公司利用成员间推介的“级联”效应推销产品.然而,由于所用数据集的限制,大多数现有影响力最大化问题的研究成果只能用于分析用户在虚拟世界中的行为,忽略了位置信息所起的作用.在信息传播过程中,用户间的距离也会对传播概率造成影响.因此,对地理社交网络中的位置敏感的影响力最大化(location-aware influence maximization, LAIM)问题进行了定义,并提出一种贪婪框架下考虑位置的影响力最大化算法,该算法将营销位置信息引入现有影响力最大化(influence maximization, IM)问题定义中,解决了传统IM中由于缺少位置信息所导致的传播范围与实际需求不符问题.此外,鉴于同一领域不可避免的竞争会引发种子重叠现象,从而导致种子个体不能实现预期传播范围,立足重叠种子角度,旨在对公司选择进行决策博弈并找到纳什均衡点,从而降低了种子集合的重叠率与影响力损失.实验结果验证了贪婪框架下考虑位置的影响力最大化算法和重叠种子下决策博弈策略的有效性.

关键词: 地理社交网络, 位置敏感的影响力最大化问题, 重叠种子, 博弈论, 纳什均衡

Abstract: Social advertising (or social promotion), one of the most important application for influence maximization (IM), has become a hot industry. The purpose of social advertising is to identify a seed set of k nodes for maximizing the expected influence spread to make businesses promote products by utilizing the cascade effect. However, most existing works concerning influence maximization problem were confined to behaviors that were observed mostly in the virtual world and neglected the location information. In fact, the distance between users can also affect propagation probability during information propagation. Thus, a problem of location-aware influence maximization (LAIM) in geo-social network is formally defined in this paper. Further, a location-aware influence maximization algorithm based on greedy frame is proposed, which introduces the promotion location information into the existing IM definition and solves the problem that influence spread is not in line with actual demand in traditional IM. Due to the overlapping seeds problem caused by inevitable competition, some of the selected nodes may not work well in practice. Thus we first conduct a decision-making game from overlapping seed’s perspective to obtain Nash equilibrium by analyzing the payoff matrix of overlapping seeds and their neighbors so that the overlapping ratio of seed set and influence loss will be reduced. Finally, comprehensive experiments demonstrate the effectiveness of our algorithm and strategy.

Key words: geo-social network, location-aware influence maximization (LAIM), overlapping seeds, game theory, Nash equilibrium