  We consider the problem of Influence Maximization (IM), the task of selecting
$k$ seed nodes in a social network such that the expected number of nodes
influenced is maximized. We propose a community-aware divide-and-conquer
framework that involves (i) learning the inherent community structure of the
social network, (ii) generating candidate solutions by solving the influence
maximization problem for each community, and (iii) selecting the final set of
seed nodes using a novel progressive budgeting scheme. Our experiments on
real-world social networks show that the proposed framework outperforms the
standard methods in terms of run-time and the heuristic methods in terms of
influence. We also study the effect of the community structure on the
performance of the proposed framework. Our experiments show that the community
structures with higher modularity lead the proposed framework to perform better
in terms of run-time and influence.
