Minimal contagious sets: Degree distributional bounds

• 成果类型: Article
• 署名作者: Arieli, Itai; Ashkenazi-Golan, Galit; Peretz, Ron; Tsodikovich, Yevgeny
• 署名单位: Technion Israel Institute of Technology; University of London; London School Economics & Political Science; Bar Ilan University; Ben-Gurion University of the Negev
• 刊物名称: JOURNAL OF ECONOMIC THEORY
• ISSN/ISSBN: 0022-0531
• DOI: 10.1016/j.jet.2025.106009
• 发表日期: 2025
• 关键词: innovation; diffusion; Word-of-mouth; Contagious; attachment

摘要

Agents in a network adopt an innovation if a certain fraction of their neighbors has already done so. We study the minimal contagious set size required for a successful innovation adoption by the entire population, and provide upper and lower bounds on it. Since detailed information about the network structure is often unavailable, we study bounds that depend only on the degree distribution of the network-a simple statistic of the network topology. Moreover, as our bounds are robust to small changes in the degree distribution, they also apply to large networks for which the degree distribution can only be approximated. Applying our bounds to growing networks shows that the minimal contagious set size is linear in the number of nodes. Consequently, for outside of knife-edge cases (such as the star-shaped network), contagion cannot be achieved without seeding a significant fraction of the population. This finding highlights the resilience of networks and demonstrates a high penetration cost in the corresponding markets.