VLDB2024_Host Profit Maximization：Leveraging Performance Incentives and User Flexibility_华为.pdf
免费下载
Host Profit Maximization: Leveraging Performance Incentives
and User Flexibility
Xueqin Chang
Zhejiang University
changxq@zju.edu.cn
Xiangyu Ke
Zhejiang University
xiangyu.ke@zju.edu.cn
Lu Chen
Zhejiang University
luchen@zju.edu.cn
Congcong Ge
Huawei Cloud Computing
Technologies Co., Ltd
gecongcong1@huawei.com
Ziheng Wei
Huawei Cloud Computing
Technologies Co., Ltd
ziheng.wei@huawei.com
Yunjun Gao
Zhejiang University
gaoyj@zju.edu.cn
ABSTRACT
The social network host has knowledge of the network structure
and user characteristics and can earn a prot by providing mer-
chants with viral marketing campaigns. We investigate the problem
of host prot maximization by leveraging performance incentives
and user exibility. To incentivize the host’s performance, we pro-
pose setting a desired inuence threshold that would allow the host
to receive full payment, with the possibility of a small bonus for
exceeding the threshold. Unlike existing works that assume a user’s
choice is frozen once they are activated, we introduce the Dynamic
State Switching model to capture “comparative shopping” behavior
from an economic perspective, in which users have the exibilities
to change their minds about which product to adopt based on the
accumulated inuence and propaganda strength of each product.
In addition, the incentivized cost of a user serving as an inuence
source is treated as a negative part of the host’s prot.
The host prot maximization problem is NP-hard, submodu-
lar, and non-monotone. To address this challenge, we propose an
ecient greedy algorithm and devise a scalable version with an ap-
proximation guarantee to select the seed sets. As a side contribution,
we develop two seed allocation algorithms to balance the distri-
bution of adoptions among merchants with small prot sacrice.
Through extensive experiments on four real-world social networks,
we demonstrate that our methods are eective and scalable.
PVLDB Reference Format:
Xueqin Chang, Xiangyu Ke, Lu Chen, Congcong Ge, Ziheng Wei, Yunjun
Gao. Host Prot Maximization: Leveraging Performance Incentives and
User Flexibility. PVLDB, 17(1): 51 - 64, 2023.
doi:10.14778/3617838.3617843
PVLDB Artifact Availability:
The source code, data, and/or other artifacts have been made available at
https://github.com/ZJU-DAILY/HPM.
This work is licensed under the Creative Commons BY-NC-ND 4.0 International
License. Visit https://creativecommons.org/licenses/by-nc-nd/4.0/ to view a copy of
this license. For any use beyond those covered by this license, obtain permission by
emailing info@vldb.org. Copyright is held by the owner/author(s). Publication rights
licensed to the VLDB Endowment.
Proceedings of the VLDB Endowment, Vol. 17, No. 1 ISSN 2150-8097.
doi:10.14778/3617838.3617843
1 INTRODUCTION
Inuence maximization (IM) [
28
] is a crucial task in the analysis
of social networks with signicant commercial value in viral mar-
keting [
16
], network monitoring [
30
], social recommendation [
58
],
and so on. Given a social graph and an integer
𝑘
, the objective of
IM is to identify a set of
𝑘
seed nodes as the source of information
propagation such that the expected number of inuenced nodes
is maximized under a specied diusion model. The study of IM
has attracted signicant attention in the elds of data management,
leading to the focuses on (1) designing practical objectives accord-
ing to real-world application demands [
5
,
20
,
27
]; (2) modeling
information diusion process based on users’ behaviors and inher-
ent properties [
7
,
35
,
54
]; and (3) devising eective and ecient
solutions with quality guarantees [18, 41, 48].
Traditional IM assumes that merchants can access the social
network and determine optimal seed users to initially adopt their
product
1
. However, in reality, social networks are often owned by
third-party hosts like Facebook or TikTok, which keep the network
structure secret for their own benet and privacy legislation [
35
,
60
].
Merchants typically lack direct access to the network and are de-
pendent on the host’s permission to run their marketing campaigns.
Motivated by this observation, there has been an increasing focus on
studying the IM problem from the perspective of the host [
5
,
6
,
20
].
Additionally, multiple competing merchants may launch similar
products around the same time in the marketplace [
6
,
29
,
32
]. For
instance, in 2022, iPhone 14 series, Huawei Mate 50 series and Sam-
sung Galaxy series were launched around September [
1
,
23
,
42
].
Therefore, in this work, we consider a scenario where the social
platform host conducts the seed selection for multiple competing mer-
chants, each oering a budget as the quoted price for their desired level
of inuence. We dene a practical host prot maximization prob-
lem under a novel diusion model that incorporates the economic
perspective of “comparative shopping” behavior [12, 46, 55].
Host Prot Maximization. The host of a social network plat-
form, who has knowledge about the social graph structure and
user characteristics, has the opportunity to generate prot by pro-
viding merchants with inuence in marketing campaigns on the
platform
2
[
20
,
43
,
59
]. The host’s prot is calculated by subtracting
the incentivizing cost from the revenue. The revenue represents
1
The term product may also refer to opinions, technologies, innovations, etc.
2
Inuencer marketing has grown from a $1.7 billion in 2016 to a projected $16.4 billion
in 2022, reported in https://sproutsocial.com/insights/pr-and-inuencer-marketing/.
51
the amount paid by each merchant to the host for a desired number
of user adoptions, while the cost refers to the payment made by
the host to incentivize the seed users. The host can evaluate the
user adoptions through user actions, i.e. retweet and like. Unlike
previous research [
3
,
4
,
20
], we introduce a novel revenue computa-
tion approach that incorporates a “retail goal or threshold” dened
by each merchant’s desired level of inuence spread. In complex
market environments, achieving the requested inuence level may
not always be feasible [
43
,
59
]. Hence, we formalize that the host
earns partial or even no payment if they are unable to meet the
merchant’s requirement, and a small extra reward if they exceed the
merchant’s demand. Host can estimate Furthermore, in contrast to
prior studies [
3
,
20
,
60
], we assume that the cost of incentivizing
seed users is a negative part of the host’s prot, as only the host
can evaluate a user’s inuence ability.
Dynamic State Switching Model. The traditional single-merchant
Independent Cascade (IC) and Linear Threshold (LT) models [
28
],
as well as their extended multi-merchant versions [
29
,
35
,
36
,
54
]
all assume that users’ adoptions are frozen upon one-time acti-
vation, regardless of the arrival of other even-matched products,
which contradicts Kalish’s famous characterization of new product
adoption
3
[
26
]. In economic and marketing contexts, users usually
engage in “comparative shopping” behavior [12, 46, 55] where con-
sumers search for and compare various similar competing products
based on factors such as price, warranty policy, and quality reviews
before making a purchase decision
4
. To capture this nature, we pro-
pose the Dynamic State Switching (DSS) model where users change
their minds from product A to B i (1) the inuence strength from
friends for B is greater than that of A, and (2) the host’s propaganda
strength for B is stronger than that of A. The model converges
when no more user is activated and no user changes her mind.
Applicability. Competitive Electric Vehicle (EV) merchants may
utilize social platforms for promotion. Merchants like Tesla, Rivian,
and NIO submit campaign proposals to a host, including a mini-
mum sales target (desired number of adoptions) and budget, and
incentive and penalty measures [
4
,
59
]. The host in turn selects
inuential users for each merchant accordingly. During the cam-
paign, an activated user (e.g., inuenced by friends’ EV purchases)
refrains from making an immediate decision based solely on the
popularity of a choice, such as Tesla among her friends. Instead, she
tends to gather and compare information about other comparable
EVs. The decision-making process considers various factors, like
price or online quality reviews. Users make the nal purchase deci-
sions either when their adoption converges or at a predetermined
timestamp, such as before the end of the marketing campaign.
Theoretical Analyses and Solutions. We demonstrate that un-
der the DSS model, the Host Prot Maximization problem is not
monotone and submodular, and NP-hard. Moreover, it is also NP-
hard to approximate with any constant factor. These results imply
that our problem is not tractable in general. However, we develop
an eective greedy algorithm with approximation guarantee to
allocate seed users for multiple merchants extended from the ROI-
Greedy [
25
]. Solving the multi-merchant scenario is non-trivial
3
Products awareness is propagated through word-of-mouth eects, after an individual
becomes aware, she would decide which item to adopt based on other considerations.
4
2 in 3 UK online shoppers compare before they buy [12].
due to the need for a meticulous seed allocation strategy and con-
sideration of dynamic changes in user’s product adoption while
maintaining theoretical guarantees. We also propose a scalable
version of our method with performance bounds by leveraging Re-
verse Inuence Sampling method to estimate the expected inuence
spread, while a novel unbiased estimation method is specically
tailored for our DSS model. As a side contribution, we consider the
practical case where the host aims to maintain long-term business
relationships with all merchants. We investigate how to allocate
seeds fairly with minimal prot sacrice (i.e., up to 10% as shown in
§ 5) to ensure a balanced distribution of adoptions among merchants
and propose two heuristic solutions.
Contributions and Roadmap.
•
We study the host prot maximization problem where a
merchant will make the full payment if a desired inuence
spread is achieved, while the incentivized cost of a user is
treated as a negative part of the host’s prot (§ 2.2).
•
We design the Dynamic State Switching propagation model
to capture the “comparative shopping” behavior from an
economic perspective (§ 2.1).
•
We characterize the hardness of solving our problem (§ 2.3),
and develop an eective greedy seed selection method to
maximize the host’s prot with an approximation guaran-
tee (§ 3.1). Moreover, we devise a scalable version of our
approximation algorithm (§ 3.2).
•
We present a practical scenario, and propose two heuristic
methods to balance the distribution of adoptions among
products while sacricing little prot of host (§ 4).
•
We conduct thorough experimental evaluations using four
real-world social network datasets, and validate that our
algorithms are eective and scalable (§ 5).
•
We present a thorough literature review about other social
advertising variants (§ 6) and conclude our paper (§ 7).
2 PRELIMINARIES
A social network platform, referred to as the host, owns a social
graph
𝐺 = (𝑉, 𝐸)
, where
𝑉
is the set of
𝑛
users and
𝐸 ⊆ 𝑉 × 𝑉
represents the set of
𝑚
social connections. Each edge
𝑒 = (𝑢, 𝑣)
is associated with a weight
𝑤
𝑢,𝑣
, depicting the inuence strength
from user
𝑢
to
𝑣
.
H = {ℎ
1
, ℎ
2
, ..., ℎ
| H |
}
is a set of
|H |
merchants
who would like to promote their products on a social network.
Each merchant
ℎ
𝑖
submits a campaign proposal to the host, which
includes a minimum desired inuence spread
𝐼
𝑖
(i.e., a threshold)
and the corresponding budget
𝐵
𝑖
that the merchant is willing to pay.
The host evaluates the inuence diusion on her social network
and selects a set of seed users
𝑆
𝑖
for merchant
ℎ
𝑖
,
𝑆
𝑖
∩ 𝑆
𝑗
= ∅
,
𝑖 ≠ 𝑗
.
In the following, we present the novel Dynamic State Switching
(DSS) information diusion model (§ 2.1) to capture “comparative
shopping” behavior and facilitate the inuence spread estimation.
After that, we formally dene our host prot maximization problem
(§ 2.2) and provide the theoretical characteristics (§ 2.3).
2.1 The DSS Propagation Model
In the classical single-merchant LT model [
28
], each node is assigned
an activation threshold randomly from the range [0, 1]. The sum of
the weights of all incoming edges for each node is normalized to be
52
of 14
免费下载
【版权声明】本文为墨天轮用户原创内容，转载时必须标注文档的来源（墨天轮），文档链接，文档作者等基本信息，否则作者和墨天轮有权追究责任。如果您发现墨天轮中有涉嫌抄袭或者侵权的内容，欢迎发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。
下载排行榜
文档被以下合辑收录
评论