  We study cascades under the threshold model on sparse random graphs with
community structure. In this model, individuals adopt the new behavior based on
how many neighbors have already chosen it. Specifically, we consider the
permanent adoption model wherein individuals that have adopted the new behavior
(or opinion) cannot change their state. We present a
differential-equation-based tight approximation to the stochastic process of
adoption and prove the validity of the mean-field equations. In addition, we
characterize both necessary and sufficient conditions for contagion to happen
no matter how small the set of initial adopters is. Finally, we study the
problem of optimum seeding given budget constraints and propose a
gradient-based heuristic seeding strategy. Our algorithm, numerically, dispels
commonly held beliefs in the literature that suggest the best seeding strategy
is to seed over the vertices with the highest number of neighbors.
