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 <inline formula> <tex math notation="LaTeX"$A$ /tex math>/inline formula> and <inline formula> <tex math notation="LaTeX"$B$ /tex math>/inline formula> at the same time, it is possible for him to adopt product <inline formula> <tex math notation="LaTeX"$C$ /tex math>/inline formula> 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 <inline formula> <tex math notation="LaTeX"{1}{2}(1 {1}{e} /tex math>/inline formula> 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.
IEEE Transactions on Computational Social Systems