Cost-Efficient Influence Maximization in Online Social Networks

Influence maximization is a classic problem in Online Social Networks (OSNs) especially for viral markets. It has been proposed to help a company to select a set of seed users for promotion given a predefined budget (e.g., the set size k). The budget-making is of challenging due to the difficulty in trade off between profit and expense. Moreover, the current studies on influence maximization focus on the independent product promotion without considering the impacts of other products that users already have. In this paper, we define a general influence maximization problem in a practical context of coexistence of multiple products. To capture the impacts of existing products, we present a new measurement of influence between users. Besides, the objective of our general problem is to maximize the profit/cost ratio which can reflects maximization effects better and meanwhile avoids the difficulty of budget-making. We propose an approximate algorithm for ratio maximization. Evaluations with two real world datasets validate the efficiency of our proposed solution.