Profit Maximization for Competitive Influence Spread in Social Networks

Influence maximization is a classic problem in social networks and has been extensively studied in recent years. Viral marketing is an important application for influence maximization. Most of existing related research focus on influence maximization of a single product, but in reality, a marketer may promote multiple products in the social network at the same time. This paper studies the profit maximization problem for multiple kinds of products in viral marketing. We formulate it as the Profit Maximization Problem for Competitive Influence Spread (PMPCIS), which aims at selecting a set of seed users within the total budget B and the total number of seeds K to maximize the overall profit of k kinds of products. The objective problem is proved to be a monotone k-submodular maximization problem under the knapsack and cardinality constraint. We present a Singleton+Greedy-Local-Search Algorithm in four steps, and prove the approximation performance guarantee of the proposed algorithm.