Geodemographic Influence Maximization

Publikation: Bidrag til bog/antologi/rapport/proceedingKonferencebidrag i proceedingsForskningpeer review

DOI

  • Kaichen Zhang, Beijing University of Posts and Telecommunications, Baidu Researh, Beijing
  • ,
  • Jingbo Zhou, Baidu Researh, Beijing, National Engineering Laboratory of Deep Learning Technology and Applications, Beijing
  • ,
  • Donglai Tao, Tsinghua University
  • ,
  • Panagiotis Karras
  • Qing Li
  • Hui Xiong, Rutgers University–New Brunswick

Given a set of locations in a city, on which ones should we place ads on so as to reach as many people as possible within a limited budget? Past research has addressed this question under the assumption that dense trajectory data are available to determine the reach of each ad. However, the data that are available in most industrial settings do not consist of dense, long-range trajectories; instead, they consist of statistics on people's short-range point-to-point movements. In this paper, we address the natural problem that arises such data: given a distribution of population and point-to-point movement statistics over a network, find a set of locations within a budget that achieves maximum expected reach. We call this problem geodemographic influence maximization (GIM). We show that the problem is NP-hard, but its objective function is monotone and submodular, thus admits a greedy algorithm with a 1 over 2 (1-1 over e) approximation ratio. Still, this algorithm is inapplicable on large-scale data for high-frequency digital signage ads. We develop an efficient deterministic algorithm, Lazy-Sower, exploiting a novel, tight double-bounding scheme of marginal influence gain as well as the locality proprieties of the problem; a learning-based variant, NN-Sower, utilizes randomization and deep learning to further improve efficiency, with a slight loss of quality. Our exhaustive experimental study on two real-world urban datasets demonstrates the efficacy and efficiency of our solutions compared to baselines.

OriginalsprogEngelsk
TitelKDD '20 : Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining
Antal sider11
ForlagAssociation for Computing Machinery
Udgivelsesåraug. 2020
Sider2764-2774
ISBN (Elektronisk)9781450379984
DOI
StatusUdgivet - aug. 2020
Begivenhed26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2020 - Virtual, Online, USA
Varighed: 23 aug. 202027 aug. 2020

Konference

Konference26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2020
LandUSA
ByVirtual, Online
Periode23/08/202027/08/2020
SponsorACM SIGKDD, ACM SIGMOD

Se relationer på Aarhus Universitet Citationsformater

ID: 196722364