IDEAS home Printed from https://ideas.repec.org/a/plo/pone00/0090303.html
   My bibliography  Save this article

Finding Near-Optimal Groups of Epidemic Spreaders in a Complex Network

Author

Listed:
  • Geoffrey Moores
  • Paulo Shakarian
  • Brian Macdonald
  • Nicholas Howard

Abstract

In this paper, we present algorithms to find near-optimal sets of epidemic spreaders in complex networks. We extend the notion of local-centrality, a centrality measure previously shown to correspond with a node's ability to spread an epidemic, to sets of nodes by introducing combinatorial local centrality. Though we prove that finding a set of nodes that maximizes this new measure is NP-hard, good approximations are available. We show that a strictly greedy approach obtains the best approximation ratio unless P = NP and then formulate a modified version of this approach that leverages qualities of the network to achieve a faster runtime while maintaining this theoretical guarantee. We perform an experimental evaluation on samples from several different network structures which demonstrate that our algorithm maximizes combinatorial local centrality and consistently chooses the most effective set of nodes to spread infection under the SIR model, relative to selecting the top nodes using many common centrality measures. We also demonstrate that the optimized algorithm we develop scales effectively.

Suggested Citation

  • Geoffrey Moores & Paulo Shakarian & Brian Macdonald & Nicholas Howard, 2014. "Finding Near-Optimal Groups of Epidemic Spreaders in a Complex Network," PLOS ONE, Public Library of Science, vol. 9(4), pages 1-10, April.
    • Handle: RePEc:plo:pone00:0090303
    DOI: 10.1371/journal.pone.0090303
    as

    Download full text from publisher

    File URL: https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0090303
    Download Restriction: no
    File URL: https://journals.plos.org/plosone/article/file?id=10.1371/journal.pone.0090303&type=printable
    Download Restriction: no
    File URL: https://libkey.io/10.1371/journal.pone.0090303?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Stephen P. Borgatti, 2006. "Identifying sets of key players in a social network," Computational and Mathematical Organization Theory, Springer, vol. 12(1), pages 21-34, April.
    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. Mark J. O. Bagley, 2019. "Networks, geography and the survival of the firm," Journal of Evolutionary Economics, Springer, vol. 29(4), pages 1173-1209, September.
    2. Hosseinali Salemi & Austin Buchanan, 2022. "Solving the Distance-Based Critical Node Problem," INFORMS Journal on Computing, INFORMS, vol. 34(3), pages 1309-1326, May.
    3. Raddant, Matthias & Takahashi, Hiroshi, 2019. "The Japanese corporate board network," Kiel Working Papers 2130, Kiel Institute for the World Economy (IfW Kiel).
    4. Marco Di Summa & Syed Md Omar Faruk, 2023. "Critical node/edge detection problems on trees," 4OR, Springer, vol. 21(3), pages 439-455, September.
    5. Heetae Kim & Petter Holme, 2015. "Network Theory Integrated Life Cycle Assessment for an Electric Power System," Sustainability, MDPI, vol. 7(8), pages 1-15, August.
    6. Alexander Veremyev & Oleg A. Prokopyev & Eduardo L. Pasiliao, 2014. "An integer programming framework for critical elements detection in graphs," Journal of Combinatorial Optimization, Springer, vol. 28(1), pages 233-273, July.
    7. Lindquist, Matthew J. & Zenou, Yves, 2019. "Crime and Networks: 10 Policy Lessons," IZA Discussion Papers 12534, Institute of Labor Economics (IZA).
    8. Caterina Liberati & Massimiliano Marzo & Paolo Zagaglia & Paola Zappa, 2015. "Drivers of demand and supply in the Euro interbank market: the role of “Key Players” during the recent turmoil," Financial Markets and Portfolio Management, Springer;Swiss Society for Financial Market Research, vol. 29(3), pages 207-250, August.
    9. Mishael Milaković & Simone Alfarano & Thomas Lux, 2010. "The small core of the German corporate board network," Computational and Mathematical Organization Theory, Springer, vol. 16(2), pages 201-215, June.
    10. Deb Verhoeven & Katarzyna Musial & Stuart Palmer & Sarah Taylor & Shaukat Abidi & Vejune Zemaityte & Lachlan Simpson, 2020. "Controlling for openness in the male-dominated collaborative networks of the global film industry," PLOS ONE, Public Library of Science, vol. 15(6), pages 1-23, June.
    11. César Yajure & Darihelen Montilla & Jose Emmanuel Ramirez-Marquez & Claudio M Rocco S, 2013. "Network vulnerability assessment via bi-objective optimization with a fragmentation approach as proxy," Journal of Risk and Reliability, , vol. 227(6), pages 576-585, December.
    12. Matjaž Krnc & Riste Škrekovski, 2020. "Group Degree Centrality and Centralization in Networks," Mathematics, MDPI, vol. 8(10), pages 1-11, October.
    13. repec:hal:pseose:halshs-00977005 is not listed on IDEAS
    14. Caterina Liberati & Massimiliano Marzo & Paolo Zagaglia & Paola Zappa, 2012. "Structural Distortions in the Euro Interbank Market: The Role of 'Key Players' during the Recent Market Turmoil," Working Paper series 57_12, Rimini Centre for Economic Analysis.
    15. Shu-Hao Chang, 2017. "The evolutionary growth estimation model of international cooperative patent networks," Scientometrics, Springer;Akadémiai Kiadó, vol. 112(2), pages 711-729, August.
    16. Reini Schrama & Dorte Sindbjerg Martinsen & Ellen Mastenbroek, 2020. "Going Nordic in European Administrative Networks?," Politics and Governance, Cogitatio Press, vol. 8(4), pages 65-77.
    17. Adam R. Cocco & Matthew Katz & Marion E. Hambrick, 2021. "Co-Attendance Communities: A Multilevel Egocentric Network Analysis of American Soccer Supporters’ Groups," IJERPH, MDPI, vol. 18(14), pages 1-18, July.
    18. Zacharie Ales & Céline Engelbeen & Rosa Figueiredo, 2024. "Correlation Clustering Problem Under Mediation," INFORMS Journal on Computing, INFORMS, vol. 36(2), pages 672-689, March.
    19. Stefano Breschi & Camilla Lenzi, 2015. "The Role of External Linkages and Gatekeepers for the Renewal and Expansion of US Cities' Knowledge Base, 1990-2004," Regional Studies, Taylor & Francis Journals, vol. 49(5), pages 782-797, May.
    20. Dufhues, Thomas & Buchenrieder, Gertrud & Fischer, Isabel, 2006. "Social capital and rural development: literature review and current state of the art [Sozialkapital und ländliche Entwicklung: Literaturüberblick und gegenwärtiger Stand der Forschung]," IAMO Discussion Papers 96, Leibniz Institute of Agricultural Development in Transition Economies (IAMO).
    21. Dell’Apa, Andrea & Fullerton, Adam & Schwing, Franklin & Brady, Margaret M., 2015. "The status of marine and coastal ecosystem-based management among the network of U.S. federal programs," Marine Policy, Elsevier, vol. 60(C), pages 249-258.

    More about this item

    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:plo:pone00:0090303. 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: plosone (email available below). General contact details of provider: https://journals.plos.org/plosone/ .

    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.