In social networks, the problem of revenue maximization aims at maximizing the overall revenue from the purchasing behaviors of users under the influence propagations. Previous studies use a number of simulations on influence cascades to obtain the maximum revenue. However, these simulation-based methods are time-consuming and can't be applied to large-scale networks. Instead, we propose calculation-based algorithms for revenue maximization, which gains the maximum revenue through fast approximate calculations within local acyclic graphs instead of the slow simulations across the global network. Furthermore, a max-Heap updating scheme is proposed to prune unnecessary calculations. These algorithms are designed for both the scenarios of unlimited and constrained commodity supply. Experiments on both the synthetic and real-world datasets demonstrate the efficiency and effectiveness of our proposals, that is, our algorithms run in orders of magnitude faster than the state-of-art baselines, and meanwhile, the maximum revenue achieved is nearly not affected.
展开▼
