  We consider the problem of maximizing the spread of influence in a social
network by choosing a fixed number of initial seeds --- a central problem in
the study of network cascades. The majority of existing work on this problem,
formally referred to as the influence maximization problem, is designed for
submodular cascades. Despite the empirical evidence that many cascades are
non-submodular, little work has been done focusing on non-submodular influence
maximization.
  We propose a new heuristic for solving the influence maximization problem and
show via simulations on real-world and synthetic networks that our algorithm
outputs more influential seed sets than the state-of-the-art greedy algorithm
in many natural cases, with average improvements of 7% for submodular cascades,
and 55% for non-submodular cascades. Our heuristic uses a dynamic programming
approach on a hierarchical decomposition of the social network to leverage the
relation between the spread of cascades and the community structure of social
networks. We verify the importance of network structure by showing the quality
of the hierarchical decomposition impacts the quality of seed set output by our
algorithm. We also present "worst-case" theoretical results proving that in
certain settings our algorithm outputs seed sets that are a factor of
$\Theta(\sqrt{n})$ more influential than those of the greedy algorithm, where
$n$ is the number of nodes in the network. Finally, we generalize our algorithm
to a message passing version that can be used to find seed sets that have at
least as much influence as the dynamic programming algorithms.
