Journal
IEEE TRANSACTIONS ON COMPUTATIONAL SOCIAL SYSTEMS
Volume 6, Issue 4, Pages 797-808Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TCSS.2019.2926112
Keywords
Composite complementary products (CCP); influence maximization (IM); knapsack; sandwich approximation; social network; viral marketing
Funding
- National Science Foundation [1747818]
- Div Of Information & Intelligent Systems
- Direct For Computer & Info Scie & Enginr [1747818] Funding Source: National Science Foundation
Ask authors/readers for more resources
Viral marketing, the method of using a small set of users in social networks to propagate products through cascades, is a well-known and extreme research problem in recent years. Then, influence maximization (IM) is formulated, which aims to select the most influential seeds to maximize the expected total adoption eventually. IM expresses viral marketing perfectly. However, almost all prior work focused on cardinality constraint or considers only simple comparative products model. They neglected that composite complementary products (CCP) are widespread. In other words, when a customer adopts products A and B at the same time, it is possible for him to adopt product C. Therefore, we design a multi-layer network model under independent cascade (IC) model to adapt to multiple complementary products and define the seed selection problem for complementary products model [IM for complementary products (IMCP)] and CCP model (IMCCP) under knapsack constraint. Here, the seed for different products has a different cost. In this paper, we propose two efficient techniques to solve IMCP problem, called Greedy and general-TIM. The Greedy uses simple Greedy Hill-Climbing algorithm under knapsack constraint and obtain (1/2)(1 - (1/e))-approximation, but the time complexity is hard to accept. The second algorithm, general-TIM, forms a weighted set cover problem by means of randomized sampling (close to Greedy in practice), which reduces the time-consuming significantly. For IMCCP problem, it is difficult to handle because no ready-made algorithms exist to optimize a function that is nonsubmodular and nonsupermodular. Then, we need to get help from sandwich method by finding an upper and lower bound. Finally, our algorithms are evaluated on several real data sets, which prove the correctness of our algorithms.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available