Geodemographic Influence Maximization

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

Standard

Geodemographic Influence Maximization. / Zhang, Kaichen; Zhou, Jingbo; Tao, Donglai; Karras, Panagiotis; Li, Qing; Xiong, Hui.

KDD '20: Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. Association for Computing Machinery, 2020. s. 2764-2774.

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

Harvard

Zhang, K, Zhou, J, Tao, D, Karras, P, Li, Q & Xiong, H 2020, Geodemographic Influence Maximization. i KDD '20: Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. Association for Computing Machinery, s. 2764-2774, 26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2020, Virtual, Online, USA, 23/08/2020. https://doi.org/10.1145/3394486.3403327

APA

Zhang, K., Zhou, J., Tao, D., Karras, P., Li, Q., & Xiong, H. (2020). Geodemographic Influence Maximization. I KDD '20: Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (s. 2764-2774). Association for Computing Machinery. https://doi.org/10.1145/3394486.3403327

CBE

Zhang K, Zhou J, Tao D, Karras P, Li Q, Xiong H. 2020. Geodemographic Influence Maximization. I KDD '20: Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. Association for Computing Machinery. s. 2764-2774. https://doi.org/10.1145/3394486.3403327

MLA

Zhang, Kaichen o.a.. "Geodemographic Influence Maximization". KDD '20: Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. Association for Computing Machinery. 2020, 2764-2774. https://doi.org/10.1145/3394486.3403327

Vancouver

Zhang K, Zhou J, Tao D, Karras P, Li Q, Xiong H. Geodemographic Influence Maximization. I KDD '20: Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. Association for Computing Machinery. 2020. s. 2764-2774 https://doi.org/10.1145/3394486.3403327

Author

Zhang, Kaichen ; Zhou, Jingbo ; Tao, Donglai ; Karras, Panagiotis ; Li, Qing ; Xiong, Hui. / Geodemographic Influence Maximization. KDD '20: Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. Association for Computing Machinery, 2020. s. 2764-2774

Bibtex

@inproceedings{fa04ecabdbcf4d838018b9cef3bbe867,
title = "Geodemographic Influence Maximization",
abstract = "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.",
keywords = "approximation algorithm, geodemographic influence, influence maximization, neural network, outdoor advertising, submodular optimization",
author = "Kaichen Zhang and Jingbo Zhou and Donglai Tao and Panagiotis Karras and Qing Li and Hui Xiong",
year = "2020",
month = aug,
doi = "10.1145/3394486.3403327",
language = "English",
pages = "2764--2774",
booktitle = "KDD '20",
publisher = "Association for Computing Machinery",
note = "26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2020 ; Conference date: 23-08-2020 Through 27-08-2020",

}

RIS

TY - GEN

T1 - Geodemographic Influence Maximization

AU - Zhang, Kaichen

AU - Zhou, Jingbo

AU - Tao, Donglai

AU - Karras, Panagiotis

AU - Li, Qing

AU - Xiong, Hui

PY - 2020/8

Y1 - 2020/8

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

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

KW - approximation algorithm

KW - geodemographic influence

KW - influence maximization

KW - neural network

KW - outdoor advertising

KW - submodular optimization

UR - http://www.scopus.com/inward/record.url?scp=85090424376&partnerID=8YFLogxK

U2 - 10.1145/3394486.3403327

DO - 10.1145/3394486.3403327

M3 - Article in proceedings

AN - SCOPUS:85090424376

SP - 2764

EP - 2774

BT - KDD '20

PB - Association for Computing Machinery

T2 - 26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2020

Y2 - 23 August 2020 through 27 August 2020

ER -