Minimal Contagious Sets: Degree Distributional Bounds

We study the minimum seed size necessary for successful innovation adoption in networks of growing size, such as scale-free networks, widely used to model real-world social networks. We employ reply dynamics in a 2×2 coordination game, where one action represents innovation, and the other represents the status quo. Agents adopt the innovation if a certain fraction of their neighbors have already adopted it. Our main contribution is to provide upper and lower bounds on the seed set's size and to demonstrate that in growing networks, the minimum seed required to reach the entire network cannot be sub-linear in the network size. Our results establish a theoretical foundation for the optimal seeding strategies within more complex network structures and dynamics.

Joint with Itai Arieli, Galit Ashkenazi-Golan & Ron Peretz.