  The majority of influence maximization (IM) studies focus on targeting
influential seeders to trigger substantial information spread in social
networks. In this paper, we consider a new and complementary problem of how to
further increase the influence spread of given seeders. Our study is motivated
by the observation that direct incentives could "boost" users so that they are
more likely to be influenced by friends. We study the $k$-boosting problem
which aims to find $k$ users to boost so that the final "boosted" influence
spread is maximized. The $k$-boosting problem is different from the IM problem
because boosted users behave differently from seeders: boosted users are
initially uninfluenced and we only increase their probability to be influenced.
Our work also complements the IM studies because we focus on triggering larger
influence spread on the basis of given seeders. Both the NP-hardness of the
problem and the non-submodularity of the objective function pose challenges to
the $k$-boosting problem. To tackle the problem on general graphs, we devise
two efficient algorithms with the data-dependent approximation ratio. For the
$k$-boosting problem on bidirected trees, we present an efficient greedy
algorithm and a rounded dynamic programming that is a fully polynomial-time
approximation scheme. We conduct extensive experiments using real social
networks and synthetic bidirected trees. We show that boosting solutions
returned by our algorithms achieves boosts of influence that are up to several
times higher than those achieved by boosting solutions returned by intuitive
baselines, which have no guarantee of solution quality. We also explore the
"budget allocation" problem in our experiments. Compared with targeting seeders
with all budget, larger influence spread is achieved when we allocation the
budget to both seeders and boosted users.
