Discount allocation for cost minimization in online social networks
- PDF / 1,555,036 Bytes
- 21 Pages / 439.37 x 666.142 pts Page_size
- 102 Downloads / 217 Views
Discount allocation for cost minimization in online social networks Qiufen Ni1,2 · Smita Ghosh3 · Chuanhe Huang1,2 · Weili Wu3 · Rong Jin3 Accepted: 7 November 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract We introduce the discount allocation problem to a new online social networks (OSNs) scenario where the nodes and the relationships between nodes are determined but the states of edges between nodes are unknown. We can know the states of all the edges centered on a node only when it becomes active. Different from most previous work on influence maximization discount allocation problem in OSNs, our goal is to minimize the discount cost that the marketer spends while ensuring at least Q customers who adopt the target product in the end in OSNs. We propose an online discount allocation policy to select seed users to spread the product information. The marketer initially selects one seed user to offer him a discount and observes whether he accepts the discount. If he accepts the discount, the marketer needs to observe how well this seed user contributes to the diffusion of product adoptions and how much discount he accepts. The remaining seeds are chosen based on the feedback of diffusion results obtained by all previous selected seeds. We propose two online discount allocation greedy algorithms under two different situations: uniform and non-uniform discounts allocation. We offer selected users discounts changing from the lowest to highest in the discount rate set until the users receive the discount and become seed users in nonuniform discount allocation situation, which saves the cost of firms comparing with the previous method that providing product to users for free. We present a theoretical analysis with bounded approximation ratios for the algorithms. Extensive experiments are conducted to evaluate the performance of the proposed online discount allocation algorithms on real-world online social networks datasets and the results demonstrate the effectiveness and efficiency of our methods. Keywords Discount allocation · Seed selection · Minimum cost · Online social networks
B
Chuanhe Huang [email protected]
Extended author information available on the last page of the article
123
Journal of Combinatorial Optimization
1 Introduction In recent years, online social networks (OSNs) have gained popularity at a rapid pace and become an important part in our daily lives. People use OSN sites such as Twitter, Microblog, Facebook, and LinkedIn not only to stay in touch with friends but also to generate, spread and share various social contents. OSNs enable government agencies to post news and events as well as ordinary people to post contents from their own perspectives and experience. As an important application of OSNs, viral marketing has become a focus of attention by many firms. It is an effective marketing strategy based on person-to-person recommendation within an OSN (Jurvetson 2000). More and more firms promote their products through OSNs. We consider a problem that a
Data Loading...
