Design of viral marketing strategies for product cross-sell through social networks

摘要: In this paper, we introduce a novel and generalized version of the influence maximization problem in social networks, which call as Budgeted Influence Maximization with Cross-sell Products (B-IMCP), it considers simultaneously following three practical aspects: (i) Often cross-sell among products is possible, (ii) Product-specific costs (and benefits) for promoting have to be considered, (iii) Since company often has budget constraints, initial seeds chosen within given budget. particular, consider that relationships single are by an arbitrary bipartite graph. We explore two variants cross-sell, one weak strong, also assume product-specific benefits. This leads different versions B-IMCP problem. Given fixed budget, key issues associated each choose not only individual products, but phenomenon these products. The specific contributions paper: propose propagation model capture both costs---benefits products; For problem, note turns out NP-hard, then, present simple greedy approximation algorithm same. derive ratio drawing upon certain results from theory matroids; then outline heuristics based on well-known concepts sociology literature; (iv) Finally, experimentally compare contrast proposed algorithms using network data sets such WikiVote trust network, Epinions, Telco detail records data. Based experiments, consistently found stronger relationship between larger overlap lesser distances corresponding non-overlapping seeds.