  Online social networks have been one of the most effective platforms for
marketing and advertising. Through "word of mouth" effects, information or
product adoption could spread from some influential individuals to millions of
users in social networks. Given a social network $G$ and a constant $k$, the
influence maximization problem seeks for $k$ nodes in $G$ that can influence
the largest number of nodes. This problem has found important applications, and
a large amount of works have been devoted to identifying the few most
influential users. But most of existing works only focus on the diffusion of a
single idea or product in social networks. However, in reality, one company may
produce multiple kinds of products and one user may also have multiple
adoptions.
  Given multiple kinds of different products with different activation costs
and profits, it is crucial for the company to distribute the limited budget
among multiple products in order to achieve profit maximization. Profit
Maximization with Multiple Adoptions (PM$^{2}$A) problem aims to seek for a
seed set within the budget to maximize the overall profit. In this paper, a
Randomized Modified Greedy (RMG) algorithm based on the Reverse Influence
Sampling (RIS) technique is presented for the PM$^{2}$A problem, which could
achieve a $(1-1/e-\varepsilon)$-approximate solution with high probability.
Compared with the algorithm proposed in [16] that achieves a
$\frac{1}{2}(1-1/e^{2})$-approximate solution, our algorithm provides a better
performance ratio which is also the best performance ratio of the PM$^{2}$A
problem. Comprehensive experiments on three real-world social networks are
conducted, and the results demonstrate that our RMG algorithm outperforms the
algorithm proposed in [16] and other heuristics in terms of profit
maximization, and could better allocate the budget.

Social and Information Networks