Profit maximization for multiple products in online social networks

Abstract

Information propagation in online social networks (OSNs), which helps shaping consumers' purchasing decisions, has received a lot of attention. The ultimate goal of marketing and advertising in OSNs is to massively influence audiences and enlarge the number of product adoptions. Most of existing works focus on maximizing the influence of a single product or promoting the adoption of one product in competing campaigns. However, in reality, the majority of companies produce various products for supplying customers with different needs. Therefore, it is truly significant and also challenging to wisely distribute limited budget across multiple products in viral marketing. In this paper, we investigate a Profit Maximization with Multiple Adoptions (PM2A) problem, which aims at maximizing the overall profit across all products. The natural greedy fails to provide a bounded result. In order to select high quality seeds for information propagation, we first proposed the PMCE algorithm, which has a ratio 1/2 (1 - 1/e2). Moreover, we further improve this ratio to (1-1/e) by proposing the PMIS algorithm. Comprehensive experiments on three real social networks are conducted. And results show that our algorithms outperform other heuristics, and better distribute the budget in terms of profit maximization.