IDEAS home Printed from https://ideas.repec.org/p/ehl/lserod/127954.html

Minimal contagious sets: degree distributional bounds

Author

Listed:
  • Arieli, Itai
  • Ashkenazi-Golan, Galit
  • Peretz, Ron
  • Tsodikovich, Yevgeny

Abstract

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.

Suggested Citation

  • Arieli, Itai & Ashkenazi-Golan, Galit & Peretz, Ron & Tsodikovich, Yevgeny, 2025. "Minimal contagious sets: degree distributional bounds," LSE Research Online Documents on Economics 127954, London School of Economics and Political Science, LSE Library.
    • Handle: RePEc:ehl:lserod:127954
    as

    Download full text from publisher

    File URL: https://researchonline.lse.ac.uk/id/eprint/127954/
    File Function: Open access version.
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Ellison, Glenn, 1993. "Learning, Local Interaction, and Coordination," Econometrica, Econometric Society, vol. 61(5), pages 1047-1071, September.
    2. Rosenberg, Dinah & Solan, Eilon & Vieille, Nicolas, 2009. "Informational externalities and emergence of consensus," Games and Economic Behavior, Elsevier, vol. 66(2), pages 979-994, July.
    3. Erol, Selman & Parise, Francesca & Teytelboym, Alexander, 2023. "Contagion in graphons," Journal of Economic Theory, Elsevier, vol. 211(C).
    4. Blume Lawrence E., 1995. "The Statistical Mechanics of Best-Response Strategy Revision," Games and Economic Behavior, Elsevier, vol. 11(2), pages 111-145, November.
    5. Ozan Candogan, 2022. "Persuasion in Networks: Public Signals and Cores," Operations Research, INFORMS, vol. 70(4), pages 2264-2298, July.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Arieli, Itai & Ashkenazi-Golan, Galit & Peretz, Ron & Tsodikovich, Yevgeny, 2025. "Minimal contagious sets: Degree distributional bounds," Journal of Economic Theory, Elsevier, vol. 226(C).
    2. H Peyton Young, 2014. "The Evolution of Social Norms," Economics Series Working Papers 726, University of Oxford, Department of Economics.
    3. Michael Kosfeld, 2002. "Stochastic strategy adjustment in coordination games," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 20(2), pages 321-339.
    4. Kreindler, Gabriel E. & Young, H. Peyton, 2013. "Fast convergence in evolutionary equilibrium selection," Games and Economic Behavior, Elsevier, vol. 80(C), pages 39-67.
    5. Azomahou, T. & Opolot, D., 2014. "Stability and strategic diffusion in networks," MERIT Working Papers 2014-035, United Nations University - Maastricht Economic and Social Research Institute on Innovation and Technology (MERIT).
    6. Alós-Ferrer, Carlos & Weidenholzer, Simon, 2008. "Contagion and efficiency," Journal of Economic Theory, Elsevier, vol. 143(1), pages 251-274, November.
    7. Hsiao-Chi Chen & Yunshyong Chow & Li-Chau Wu, 2013. "Imitation, local interaction, and coordination," International Journal of Game Theory, Springer;Game Theory Society, vol. 42(4), pages 1041-1057, November.
    8. Fagiolo, Giorgio, 2005. "Endogenous neighborhood formation in a local coordination model with negative network externalities," Journal of Economic Dynamics and Control, Elsevier, vol. 29(1-2), pages 297-319, January.
    9. Ge Jiang & Simon Weidenholzer, 2017. "Local interactions under switching costs," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 64(3), pages 571-588, October.
    10. Suren Basov, 2002. "Evolution of Social Behavior in the Global Economy: The Replicator Dynamics with Migration," Department of Economics - Working Papers Series 847, The University of Melbourne.
    11. López-Pintado, Dunia, 2008. "Diffusion in complex social networks," Games and Economic Behavior, Elsevier, vol. 62(2), pages 573-590, March.
    12. Stephen Morris & Hyun Song Shin, 2003. "Heterogeneity and Uniqueness in Interaction Games," Cowles Foundation Discussion Papers 1402, Cowles Foundation for Research in Economics, Yale University.
    13. Wallace, Chris & Young, H. Peyton, 2015. "Stochastic Evolutionary Game Dynamics," Handbook of Game Theory with Economic Applications,, Elsevier.
    14. Cowan, Robin, 2004. "Network models of innovation and knowledge diffusion," Research Memorandum 016, Maastricht University, Maastricht Economic Research Institute on Innovation and Technology (MERIT).
    15. Carlos Alós-Ferrer & Georg Kirchsteiger & Markus Walzl, 2010. "On the Evolution of Market Institutions: The Platform Design Paradox," Economic Journal, Royal Economic Society, vol. 120(543), pages 215-243, March.
    16. Oyama, Daisuke & Takahashi, Satoru, 2015. "Contagion and uninvadability in local interaction games: The bilingual game and general supermodular games," Journal of Economic Theory, Elsevier, vol. 157(C), pages 100-127.
    17. Giorgio Fagiolo, 2025. "Equilibrium selection in generalized Polya-urn coordination games with partial information on population shares," Economics Bulletin, AccessEcon, vol. 45(4), pages 1658-1665.
    18. Staudigl, Mathias & Weidenholzer, Simon, 2014. "Constrained interactions and social coordination," Journal of Economic Theory, Elsevier, vol. 152(C), pages 41-63.
    19. Côme Billard, 2020. "Technology Contagion in Networks," Working Papers 2020.01, FAERE - French Association of Environmental and Resource Economists.
    20. Cartwright, Edward, "undated". "Learning to play approximate Nash equilibria in games with many players," Economic Research Papers 269484, University of Warwick - Department of Economics.

    More about this item

    Keywords

    ;
    ;
    ;
    ;
    ;

    JEL classification:

    • O33 - Economic Development, Innovation, Technological Change, and Growth - - Innovation; Research and Development; Technological Change; Intellectual Property Rights - - - Technological Change: Choices and Consequences; Diffusion Processes
    • M30 - Business Administration and Business Economics; Marketing; Accounting; Personnel Economics - - Marketing and Advertising - - - General

    NEP fields

    This paper has been announced in the following NEP Reports:

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:ehl:lserod:127954. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: LSERO Manager (email available below). General contact details of provider: https://edirc.repec.org/data/lsepsuk.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.