移动广告用户传播能力评价与覆盖优化算法

doi:10.3969/j.issn.0253-2778.2017.07.004

中国科学技术大学学报 ›› 2017, Vol. 47 ›› Issue (7): 569-574.DOI: 10.3969/j.issn.0253-2778.2017.07.004

移动广告用户传播能力评价与覆盖优化算法

徐婉茹，杨盘隆

解放军理工大学通信工程学院,江苏南京 210007

收稿日期:2016-08-28 修回日期:2016-12-08 出版日期:2017-07-31 发布日期:2017-07-31
通讯作者: 杨盘隆
作者简介:徐婉茹，女，1992年生，硕士生. 研究方向：数据挖掘. E-mail: xwr88023@gmail.com
基金资助:
国家自然科学基金重点项目（61232018），江苏省自然科学基金杰出青年基金（BK20150030）资助.

Mobile user propagation capability evaluation and coverage optimization algorithm

XU Wanru, YANG Panlong

School of Communications Engineering, PLA University of Science and Technology, Nanjing 210007, China

Received:2016-08-28 Revised:2016-12-08 Online:2017-07-31 Published:2017-07-31

摘要/Abstract

摘要： 移动广告的分发效果对于广告商和用户来说都是相当重要的事情.目前对于高效率的广告分发特别是对用户的轨迹和预算的研究较为匮乏.为了获得有效可行的移动广告分发策略，提出了以位置为中心的移动众包网络的概念，代替传统的以用户为中心的网络和平台，其中，位置信息对于广告分发起到至关重要的作用.为此重点研究考虑有兴趣区域的覆盖（interested area coverage, IAC）策略下的移动广告用户选择问题.对于以位置为中心的研究需要考虑每个用户的时空特性，并需要有效地计算有兴趣的覆盖区域，资金预算的约束使这一问题更加难以解决.为应对上述挑战，首先，考虑到对位置敏感的移动广告应用程序时，提出了被证明是NP-hard的有预算约束的用

关键词: 移动广告, 用户位置, 区域覆盖, 时空特性, 用户选择, 子模问题

Abstract: The distribution efficiency of mobile advertising is extremely important for both advertisers and users. Few studies have been conducted on efficient ad delivery, especially user tracing and the budget. In order to obtain a feasible and effective mobile advertising distribution policy, the concept of location-centric mobile crowd sourcing network was presented to replace the traditional user-centric networks and platforms, in which the location information for advertizing distribution plays a crucial role. Therefore, the user selection under the interested area coverage(interested area coverage， IAC) region was mainly focused upon. However, research centering on location information we need requires the consideration of the temporal characteristics of each user， and effective calculation of the ICA. The problem will be more difficult to solve when considering the budget constraint. To address these challenges, considering the location sensitive mobile advertising applications, and a user selection solution was proposed， which was proved to be an NP-hard budget-constrained problem. Then, the submodularity problem was explored and a simple and effective heuristic was presented whose approximate ratio is(1－

Key words: mobile advertisement, user location, area coverage, spatial-temporal feature, user selection, submodularity

中图分类号:

TP311

徐婉茹，杨盘隆. 移动广告用户传播能力评价与覆盖优化算法[J]. 中国科学技术大学学报, 2017, 47(7): 569-574.

XU Wanru, YANG Panlong. Mobile user propagation capability evaluation and coverage optimization algorithm[J]. Journal of University of Science and Technology of China, 2017, 47(7): 569-574.

参考文献

［1］
BORGS C, CHAYES J, IMMORLICA N, et al. Dynamics of bid optimization in online advertisement auctions[C]// Proceedings of the 16th International Conference on World Wide Web. Banff, Canada: ACM Press, 2007: 531-540.
[2] MAHDIAN M, NAZERZADEH H, SABERI A. Allocating online advertisement space with unreliable estimates[C]// Proceedings of the 8th ACM Conference on Electronic Commerce. San Diego: ACM Press, 2007: 288-294.
[3] KLMEL B, ALEXAKIS S. Location based target advertising[C]// Proceedings of the First International Conference on Mobile Business. Athens, Greece: Springer, 2002: 1-7.
[4] BANERJEE S, DHOLAKIA R R. Mobile advertising: Does location based advertising work?[J]. International Journal of Mobile Marketing, 2008, 3(2): 68-74.
[5] NATH S, LIN F X Z, RAVINDRANATH L, et al. SmartAds: Bringing contextual ads to mobile apps[C]// Proceeding of the 11th Annual International Conference on Mobile Systems, Applications, and Services. Taipei, China: ACM Press, 2013: 111-124.
[6] NATH S. Madscope: Characterizing mobile in-app targeted ads[C]// Proceedings of the 13th Annual International Conference on Mobile Systems, Applications, and Services. Florence, Italy: ACM Press, 2015: 59-73.
[7] KRAUSE A, GUESTRIN C. Near-optimal observation selection using submodular functions[C]// Proceedings of the 22nd National Conference on Artificial Intelligence. Vancouver, Canada: AAAI Press, 2007, 2: 1650-1654.
[8] KEMPE D, KLEINBERG J, TARDOS . Maximizing the spread of influence through a social network[C]// Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Washington: ACM Press, 2003: 137-146.
[9] KRAUSE A, GOLOVIN D. Submodular function maximization[M]// Tractability: Practical Approaches to Hard Problems. Cambridge: Cambridge University Press, 2014: 71-104.
[10] KHULLER S, MOSS A, NAOR J S. The budgeted maximum coverage problem[J]. Information Processing Letters, 1999, 70(1): 39-45.
[11] Kuo T W, Lin K C J, Tsai M J. Maximizing submodular set function with connectivity constraint: Theory and application to networks[J]. IEEE/ACM Transactions on Networking (TON), 2015, 23(2): 533-546.
[12] Nemhauser G L, Wolsey L A, Fisher M L. An analysis of approximations for maximizing submodular set functions—I[J]. Mathematical Programming, 1978, 14(1): 265-294.

[1]	吴加禹，李永坤，许胤龙. 一种读写均衡的高性能键值存储系统[J]. 中国科学技术大学学报, 2020, 50(6): 825-831.
[2]	蔡勇，陈红梅，. MapReduce环境下基于概念分层的概念格并行构造算法[J]. 中国科学技术大学学报, 2018, 48(4): 275-283.
[3]	王勇，黄志球，韦良芬，卢桂馥. 基于故障森林的组合测试故障定位研究[J]. 中国科学技术大学学报, 2018, 48(1): 28-34.

移动广告用户传播能力评价与覆盖优化算法

Mobile user propagation capability evaluation and coverage optimization algorithm

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 3

编辑推荐

Metrics

本文评价