Efficient Algorithms for Budgeted Influence Maximization on Massive Social Networks

Given a social network G, a cost associated with each node, and a budget B, the budgeted influence maximization (BIM) problem aims to find a set S of nodes, denoted as the seed set, that maximizes the expected number of influenced users under the constraint that the total cost of the users in S is no larger than B. The current state-of-the-art practical solution for BIM problem provides a (1-1/e/2 --- ε)-approximate (≈ 0.316 --- ε) result and is still inefficient on large networks. We first show that we can improve the approximation guarantee to 1 --- 1/eβ --- ε where 1 --- 1/eβ = (1 --- β) (1 --- 1/e), achieving a better approximation guarantee (≈ 0.355 --- ε). Next, we apply the reverse sampling based technique, a popular technique for classic influence maximization, to our studied BIM problem. However, it is non-trivial to design efficient solutions for large scale networks even the reverse sampling based technique is applied. On one hand, it is unclear how to derive tight bounds for the nodes selected by the greedy algorithm under the budgeted scenario, where each time it selects the seed node with the highest benefit-cost ratio. With tighter bounds, the algorithm can terminate as soon as the approximation ratio is satisfied, thus saving the running cost. On the other hand, the number of nodes selected under BIM problem may be quite large since it may greedily select many nodes with large benefit-cost ratio but with low costs. The time complexity of existing influence maximization algorithms heavily depends on the size of the seed set. To tackle such challenging issues, we first present new bound estimation techniques for the BIM problem. Next, we present new node selection strategies to alleviate the dependency to the size of the seed set. Extensive experiments show that our proposed solution is far more efficient than alternatives.