Geodemographic Influence Maximization

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review


  • 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.

Original languageEnglish
Title of host publicationKDD '20 : Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining
Number of pages11
PublisherAssociation for Computing Machinery
Publication yearAug 2020
ISBN (Electronic)9781450379984
Publication statusPublished - Aug 2020
Event26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2020 - Virtual, Online, United States
Duration: 23 Aug 202027 Aug 2020


Conference26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2020
LandUnited States
ByVirtual, Online

    Research areas

  • approximation algorithm, geodemographic influence, influence maximization, neural network, outdoor advertising, submodular optimization

See relations at Aarhus University Citationformats

ID: 196722364