2016/06/02 by Mehrdad Moharrami, Moharrami, Mehrdad, Vijay Subramanian +5
Decision Sciences · Physics and Astronomy · #05C80 #Complex Network Analysis Techniques #FOS: Mathematics #Game Theory and Applications #Opinion Dynamics and Social Influence #Probability (math.PR)
paper · pdf · doi:10.48550/arxiv.1606.00858
openalex publication_date 2016/06/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.