Geodemographic Influence Maximization
Aug 13, 20207 views
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-topoint movements,. In this paper, we address the natural problem,that arises on 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,2,(,1,−,1,𝑒,),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.