2025-11-23T02:01:16.750653

Multi-product Influence Maximization in Billboard Advertisement

Ali, Islam, Banerjee

Billboard Advertisement has emerged as an effective out-of-home advertisement technique where the goal is to select a limited number of slots and play advertisement content over there with the hope that this will be observed by many people, and effectively, a significant number of them will be influenced towards the brand. Given a trajectory and a billboard database and a positive integer $k$, how can we select $k$ highly influential slots to maximize influence? In this paper, we study a variant of this problem where a commercial house wants to make a promotion of multiple products, and there is an influence demand for each product. We have studied two variants of the problem. In the first variant, our goal is to select $k$ slots such that the respective influence demand of each product is satisfied. In the other variant of the problem, we are given with $\ell$ integers $k_1,k_2, \ldots, k_{\ell}$, the goal here is to search for $\ell$ many set of slots $S_1, S_2, \ldots, S_{\ell}$ such that for all $i \in [\ell]$, $|S_{i}| \leq k_i$ and for all $i \neq j$, $S_i \cap S_j=\emptyset$ and the influence demand of each of the products gets satisfied. We model the first variant of the problem as a multi-submodular cover problem and the second variant as its generalization. For solving the first variant, we adopt the bi-criteria approximation algorithm, and for the other variant, we propose a sampling-based approximation algorithm. Extensive experiments with real-world trajectory and billboard datasets highlight the effectiveness and efficiency of the proposed solution approach.

academic

빌보드 광고에서의 다중 제품 영향력 최대화

기본 정보

논문 ID: 2510.09050
제목: Multi-product Influence Maximization in Billboard Advertisement
저자: Dildar Ali (IIT Jammu), Rajibul Islam (Gandhi Institute for Technological Advancement), Suman Banerjee (IIT Jammu)
분류: cs.DS (데이터 구조 및 알고리즘), cs.DB (데이터베이스)
발표 시간: 2025년 10월 10일 (arXiv 사전인쇄본)
논문 링크: https://arxiv.org/abs/2510.09050

초록

옥외 광고판은 제한된 수의 시간대를 선택하여 광고 콘텐츠를 방송하고 많은 사람들에게 관찰되어 브랜드에 대한 태도에 효과적으로 영향을 미치는 것을 목표로 하는 효과적인 옥외 광고 기술이 되었습니다. 본 논문은 변형 문제를 연구합니다: 상업 회사가 여러 제품을 홍보하고자 하며, 각 제품은 영향력 요구사항을 가집니다. 두 가지 문제 변형을 연구했습니다: 첫 번째 변형의 목표는 k개의 시간대를 선택하여 각 제품의 해당 영향력 요구사항을 충족시키는 것입니다; 두 번째 변형에서는 ℓ개의 정수 k₁,k₂,...,k_ℓ이 주어졌을 때, ℓ개의 시간대 집합 S₁,S₂,...,S_ℓ을 찾는 것이 목표이며, 이는 서로 겹치지 않고 각 제품의 영향력 요구사항을 모두 충족해야 합니다.

연구 배경 및 동기

문제 배경

옥외 광고의 중요성: 상업 회사는 일반적으로 총 수익의 7-10%를 광고에 사용하며, 옥외 광고판은 투자 수익 보장 및 사용 용이성으로 인해 효과적인 방법이 됩니다
기존 문제의 한계: 기존 연구는 주로 단일 광고주의 영향력 최대화 또는 여러 광고주 간의 후회 최소화에 초점을 맞춥니다
실제 요구사항: 상업 회사는 일반적으로 서로 다른 고객 그룹을 대상으로 하는 여러 이질적 제품을 동시에 홍보해야 합니다

연구 동기

실무 요구사항: 현실에서 광고주는 통일된 예산 내에서 여러 제품의 서로 다른 영향력 요구사항을 충족해야 합니다
이론적 공백: 기존 문헌에는 다중 제품 광고판 시간대 선택 문제에 대한 연구가 부족합니다
기술적 과제: 각 제품의 영향력 제약을 충족하면서 총 비용을 최소화해야 합니다

핵심 기여

문제 확장: 영향력 시간대 선택 문제를 다중 제품 광고 시나리오로 확장하여 두 가지 관련 문제 변형을 연구합니다
이론적 모델링: 첫 번째 변형을 다중 부분모듈 커버 문제로, 두 번째 변형을 그 일반화 버전으로 모델링합니다
알고리즘 설계:
- 첫 번째 변형에 대해 이중 기준 근사 알고리즘 채택
- 두 번째 변형에 대해 샘플링 기반 근사 알고리즘 제안
효율성 최적화: 확장성 문제를 해결하기 위한 효율적인 휴리스틱 솔루션 개발
실험 검증: 실제 궤적 및 광고판 데이터셋에서 광범위한 실험 수행

방법론 상세 설명

작업 정의

입력:

궤적 데이터베이스 D: 사용자 위치-시간 정보 및 제품 관심도 포함
광고판 데이터베이스 B: 광고판 위치, 시간대 및 비용 정보 포함
비용 함수 c: BS → R⁺
제품 집합 P = {1,2,...,ℓ}

두 가지 문제 변형:

공통 다중 제품 시간대 선택 문제:
- 단일 시간대 집합 S ⊆ BS 선택
- 총 비용 최소화: ∑_{s∈S} c(s)
- 제약 조건: ∀j ∈ ℓ, I_j(S) ≥ k_j
분리된 다중 제품 시간대 선택 문제:
- ℓ개의 겹치지 않는 시간대 집합 S₁,S₂,...,S_ℓ 선택
- 만족: |S_j| ≤ k_j, S_i ∩ S_j = ∅ (i≠j), I_j(S_j) ≥ σ_j

핵심 기술

1. 영향력 함수 모델링

제품 j의 영향력 함수는 다음과 같이 정의됩니다:

I_j(S) = ∑_{u_i∈U_j} [1 - ∏_{s_j∈S} (1 - Pr(s_j, u_i))]

여기서 U_j는 제품 j에 관심 있는 사용자 집합이고, Pr(s_j, u_i)는 시간대 s_j가 사용자 u_i에 미치는 영향 확률입니다.

2. 부분모듈성 속성

영향력 함수는 부분모듈성 속성을 가지며, 한계 감소 효과를 만족합니다:

f(A ∪ {e}) - f(A) ≥ f(B ∪ {e}) - f(B), ∀A ⊆ B

알고리즘 아키텍처

알고리즘 1: 공통 시간대 선택을 위한 이중 기준 근사 알고리즘

정규화: 각 제품의 영향력 함수를 정규화하여 I_j(BS) = 1이 되도록 합니다
연속 탐욕법: 다중선형 확장을 사용하여 매트로이드 다면체에서 분수 해를 구합니다
무작위 반올림: ℓ = ⌈log_{1/(1-ε)}(r)⌉개의 무작위 부분집합을 샘플링합니다
복구 단계: 제약 조건을 충족하지 않는 제품에 대해 탐욕적으로 시간대를 추가합니다

알고리즘 2: 분리된 시간대 선택을 위한 샘플링 알고리즘

순열 샘플링: 제품-시간대 할당의 순열을 무작위로 샘플링합니다
탐욕적 할당: 순열 순서에 따라 각 제품에 대해 탐욕적으로 시간대를 선택합니다
가능성 검사: 모든 제약 조건을 충족하는지 확인합니다
최적 선택: 비용이 최소인 가능한 해를 반환합니다

기술적 혁신점

다중선형 확장 적용: 부분모듈 함수의 연속 확장 기술을 다중 제품 시나리오에 적용합니다
샘플링 복잡도 분석: Hoeffding 부등식을 사용하여 샘플링 알고리즘의 샘플 복잡도를 분석합니다
이중 기준 근사: 영향력 제약을 충족하면서 비용 근사 보장을 제공합니다

실험 설정

데이터셋

뉴욕시 (NYC):
- 227,428개의 체크인 기록 (2012년 4월-2013년 2월)
- 1,083명의 고유 사용자
- 716개의 광고판, 1,031,040개의 시간대
로스앤젤레스 (LA):
- 74,170개의 체크인 기록, 15개 거리 포함
- 2,000명의 고유 사용자
- 1,483개의 광고판, 2,135,520개의 시간대