The development of online social networks such as Facebook and Twitter provides opportunities for large-scale online viral marketing. Under this circumstance, influence maximization becomes a very popular research direction, which could be described as the problem of finding a small set of most influential nodes in a social network so that the spread of influence in the network is maximizeds. A large amount of efforts have been made on this research topic since Kempe et al. [1]} first defined the problem and obtained plentiful results in many ways[2]}, [3]}, [4]}.
Those studies are based on the assumption that the number of influenced users determines the profit of product [5]}, [1]}, [7]}, [8]}, [9]}.
The influence maximization (IM) problem and the problems extended from IM adopt the cadinality or knapsack constraint, which represents the seeding budget in a product promotion activity. Under such setting, the solution, which is a set of the most influential seed nodes, should maximizes the expected influenced nodes with the constraint of seeds number. Since the influence spread is a non-decreasing function of the seeds set[1]}, the solution seeds set is always of the limit size. In this paper, we study the overall profit maximization, our goal is to obtain the optimal investment to achieve the maximum net profit, which take into account the varying cost of seeding that is proportional to the number of seeds. In this problem, the objective function is not monotone and there is no cardinality or knapsack constraint.
