A New Strategy in Boosting Information Spread

Finding a seed set to propagate more information within a specific budget is defined as the influence maximization (IM) problem. The traditional IM model contains two cardinal aspects: (i) the influence propagation model and (ii) effective/efficient seed-seeking algorithms. However, most of models only consider one kind of node (i.e., influential nodes), ignoring the role of other nodes (e.g., boosting nodes) in the spreading process, which are irrational. Specifically, in the real-world propagation scenario, the boosting nodes always improve the spread of influence from the initial activated seeds, which is an efficient and cost-economic measure. In this paper, we consider the realistic budgeted influence maximization (RBIM) problem, which contains two kind of nodes to improve the diffusion of influence. Facing the newly modified objective function, we propose a novel B-degree discount algorithm to solve it. The novel B-degree discount algorithm which adopts the cost-economic boosting nodes to retweet the influence from the predecessor nodes can greatly reduce the cost, and performs better than other state-of-the-art algorithms in both effect and efficiency on RBIM problem solving.