A Novel Scene of Viral Marketing for Complementary Products

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.