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

Kemeny-based testing for COVID-19

Author

Listed:
  • Serife Yilmaz
  • Ekaterina Dudkina
  • Michelangelo Bin
  • Emanuele Crisostomi
  • Pietro Ferraro
  • Roderick Murray-Smith
  • Thomas Parisini
  • Lewi Stone
  • Robert Shorten

Abstract

Testing, tracking and tracing abilities have been identified as pivotal in helping countries to safely reopen activities after the first wave of the COVID-19 virus. Contact tracing apps give the unprecedented possibility to reconstruct graphs of daily contacts, so the question is: who should be tested? As human contact networks are known to exhibit community structure, in this paper we show that the Kemeny constant of a graph can be used to identify and analyze bridges between communities in a graph. Our ‘Kemeny indicator’ is the value of the Kemeny constant in the new graph that is obtained when a node is removed from the original graph. We show that testing individuals who are associated with large values of the Kemeny indicator can help in efficiently intercepting new virus outbreaks, when they are still in their early stage. Extensive simulations provide promising results in early identification and in blocking the possible ‘super-spreaders’ links that transmit disease between different communities.

Suggested Citation

  • Serife Yilmaz & Ekaterina Dudkina & Michelangelo Bin & Emanuele Crisostomi & Pietro Ferraro & Roderick Murray-Smith & Thomas Parisini & Lewi Stone & Robert Shorten, 2020. "Kemeny-based testing for COVID-19," PLOS ONE, Public Library of Science, vol. 15(11), pages 1-19, November.
    • Handle: RePEc:plo:pone00:0242401
    DOI: 10.1371/journal.pone.0242401
    as

    Download full text from publisher

    File URL: https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0242401
    Download Restriction: no
    File URL: https://journals.plos.org/plosone/article/file?id=10.1371/journal.pone.0242401&type=printable
    Download Restriction: no
    File URL: https://libkey.io/10.1371/journal.pone.0242401?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. Yaesoubi, Reza & Cohen, Ted, 2011. "Generalized Markov models of infectious disease spread: A novel framework for developing dynamic health policies," European Journal of Operational Research, Elsevier, vol. 215(3), pages 679-687, December.
    2. Marcel Salathé & James H Jones, 2010. "Dynamics and Control of Diseases in Networks with Community Structure," PLOS Computational Biology, Public Library of Science, vol. 6(4), pages 1-11, April.
    3. Joost Berkhout & Bernd F. Heidergott, 2019. "Analysis of Markov Influence Graphs," Operations Research, INFORMS, vol. 67(3), pages 892-904, May.
    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. Gregory, Steve, 2012. "Ordered community structure in networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 391(8), pages 2752-2763.
    2. Wei Zhong, 2017. "Simulating influenza pandemic dynamics with public risk communication and individual responsive behavior," Computational and Mathematical Organization Theory, Springer, vol. 23(4), pages 475-495, December.
    3. Christoph Zimmer & Reza Yaesoubi & Ted Cohen, 2017. "A Likelihood Approach for Real-Time Calibration of Stochastic Compartmental Epidemic Models," PLOS Computational Biology, Public Library of Science, vol. 13(1), pages 1-21, January.
    4. Chen, Dandan & Zheng, Muhua & Zhao, Ming & Zhang, Yu, 2018. "A dynamic vaccination strategy to suppress the recurrent epidemic outbreaks," Chaos, Solitons & Fractals, Elsevier, vol. 113(C), pages 108-114.
    5. Xie, Xiaoxiao & Huo, Liang'an, 2024. "Co-evolution dynamics between information and epidemic with asymmetric activity levels and community structure in time-varying multiplex networks," Chaos, Solitons & Fractals, Elsevier, vol. 181(C).
    6. Das, Saikat & Bose, Indranil & Sarkar, Uttam Kumar, 2023. "Predicting the outbreak of epidemics using a network-based approach," European Journal of Operational Research, Elsevier, vol. 309(2), pages 819-831.
    7. Yunhan Huang & Quanyan Zhu, 2022. "Game-Theoretic Frameworks for Epidemic Spreading and Human Decision-Making: A Review," Dynamic Games and Applications, Springer, vol. 12(1), pages 7-48, March.
    8. Bowen Yan & Steve Gregory, 2013. "Identifying Communities and Key Vertices by Reconstructing Networks from Samples," PLOS ONE, Public Library of Science, vol. 8(4), pages 1-14, April.
    9. Topuz, Kazim & Urban, Timothy L. & Yildirim, Mehmet B., 2024. "A Markovian score model for evaluating provider performance for continuity of care—An explainable analytics approach," European Journal of Operational Research, Elsevier, vol. 317(2), pages 341-351.
    10. Zhou, Bin & Yan, Xiao-Yong & Xu, Xiao-Ke & Xu, Xiao-Ting & Wang, Nianxin, 2018. "Evolutionary of online social networks driven by pareto wealth distribution and bidirectional preferential attachment," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 507(C), pages 427-434.
    11. Eugenio Valdano & Chiara Poletto & Armando Giovannini & Diana Palma & Lara Savini & Vittoria Colizza, 2015. "Predicting Epidemic Risk from Past Temporal Contact Data," PLOS Computational Biology, Public Library of Science, vol. 11(3), pages 1-19, March.
    12. Saxena, Chandni & Doja, M.N. & Ahmad, Tanvir, 2018. "Group based centrality for immunization of complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 508(C), pages 35-47.
    13. Stephen J Gilmore, 2011. "Control Strategies for Endemic Childhood Scabies," PLOS ONE, Public Library of Science, vol. 6(1), pages 1-14, January.
    14. Kotnis, Bhushan & Kuri, Joy, 2016. "Cost effective campaigning in social networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 450(C), pages 670-681.
    15. Kathrin Büttner & Joachim Krieter & Arne Traulsen & Imke Traulsen, 2013. "Efficient Interruption of Infection Chains by Targeted Removal of Central Holdings in an Animal Trade Network," PLOS ONE, Public Library of Science, vol. 8(9), pages 1-12, September.
    16. De Angelis, Luca & Dias, José G., 2014. "Mining categorical sequences from data using a hybrid clustering method," European Journal of Operational Research, Elsevier, vol. 234(3), pages 720-730.
    17. Jose L Herrera & Ravi Srinivasan & John S Brownstein & Alison P Galvani & Lauren Ancel Meyers, 2016. "Disease Surveillance on Complex Social Networks," PLOS Computational Biology, Public Library of Science, vol. 12(7), pages 1-16, July.
    18. Shams, Bita & Khansari, Mohammad, 2015. "On the impact of epidemic severity on network immunization algorithms," Theoretical Population Biology, Elsevier, vol. 106(C), pages 83-93.
    19. Karikalan Nagarajan & Bharathidasan Palani & Javeed Basha & Lavanya Jayabal & Malaisamy Muniyandi, 2022. "A social networks-driven approach to understand the unique alcohol mixing patterns of tuberculosis patients: reporting methods and findings from a high TB-burden setting," Palgrave Communications, Palgrave Macmillan, vol. 9(1), pages 1-8, December.
    20. Gong Kai & Kang Li, 2018. "A New K-Shell Decomposition Method for Identifying Influential Spreaders of Epidemics on Community Networks," Journal of Systems Science and Information, De Gruyter, vol. 6(4), pages 366-375, August.

    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:0242401. 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.