The contagion number: How fast can a disease spread?
DOI:
https://doi.org/10.31181/dmame060128022023bKeywords:
Disease spread, graph theory, burning number, contagion number, COVID-19.Abstract
The burning number of a graph models the rate at which a disease, information, or other externality can propagate across a network. The burning number is known to be NP-hard even for a tree. Herein, we define a relative of the burning number that we coin the contagion number (CN). We aver that the CN is a better metric to model disease spread than the burning number as it only counts first time infections (i.e., constrains a node from getting the same disease/same variant/same alarm more than once). This is important because the Centers for Disease Control and Prevention report that COVID-19 reinfections are rare. This paper delineates a method to solve for the contagion number of any tree, in polynomial time, which addresses how fast a disease could spread (i.e., a worst-cast analysis) and then employs simulation to determine the average contagion number (ACN) (i.e., a most-likely analysis) of how fast a disease would spread. The latter is analyzed on scale-free graphs, which are used to model human social networks generated through a preferential attachment mechanism. With CN differing across network structures and almost identical to ACN, our findings advance disease spread understanding and reveal the importance of network structure. In a borderless world without replete resources, understanding disease spread can do much to inform public policy and managerial decision makers’ allocation decisions. Furthermore, our direct interactions with supply chain executives at two COVID-19 vaccine developers provided practical grounding on what the results suggest for achieving social welfare objectives.
Downloads
References
Adbi, A., Chatterjee, C., Drev, M., & Mishra, A. (2019). When the Big One Came: A Natural Experiment on Demand Shock and Market Structure in India’s Influenza Vaccine Markets. Production and Operations Management, 28(4). https://doi.org/10.1111/poms.12948
Barabási, A. L. (2013). Network science. In Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences (Vol. 371, Issue 1987). https://doi.org/10.1098/rsta.2012.0375
Barabási, A. L., & Albert, R. (1999). Emergence of scaling in random networks. Science, 286(5439). https://doi.org/10.1126/science.286.5439.509
Bessy, S., Bonato, A., Janssen, J., Rautenbach, D., & Roshanbin, E. (2017). Burning a graph is hard. Discrete Applied Mathematics, 232. https://doi.org/10.1016/j.dam.2017.07.016
Bessy, S., Bonato, A., Janssen, J., Rautenbach, D., & Roshanbin, E. (2018). Bounds on the burning number. Discrete Applied Mathematics, 235. https://doi.org/10.1016/j.dam.2017.09.012
Bonato, A., English, S., Kay, B., & Moghbel, D. (2021). Improved Bounds for Burning Fence Graphs. Graphs and Combinatorics, 37(6). https://doi.org/10.1007/s00373-021-02390-x
Bonato, A., Janssen, J., & Roshanbin, E. (2016). How to burn a graph. Internet Mathematics, 12(1–2). https://doi.org/10.1080/15427951.2015.1103339
Bourla, A. (2022). Moonshot: Inside Pfizer’s Nine-Month Race to Make the Impossible Possible. New York, NY: HarperCollins Publishers.
Brandeau, M. L., & Chiu, S. S. (1989). An Overview of Representative Problems in Location Research. Management Science, 35(6). https://doi.org/10.1287/mnsc.35.6.645
Carter, J. (2022) Foreword to Moonshot. In Bourla, A. (2022). Moonshot: Inside Pfizer’s Nine-Month Race to Make the Impossible Possible. New York, NY: HarperCollins Publishers.
Center for Disease Control and Prevention (2021a). CDC Influenza SARS-CoV-2 (Flu SC2) Multiplex Assay (Report No.: LB-135).
Center for Disease Control and Prevention (2021b). Reinfection with COVID-19, accessed November 11, 2021, available at https://www.cdc.gov/coronavirus/2019-ncov/your-health/reinfection.html
Centers for Disease Control and Prevention (2021c). COVID-19-Forecasts: Cases, accessed February 9, 2021, available at https://www.cdc.gov/coronavirus/2019-ncov/cases-updates/forecasts-cases.html
Centers for Disease Control and Prevention (2021d). COVID-19-Forecasts: Deaths, accessed February 9, 2021, available at https://www.cdc.gov/coronavirus/2019-ncov/covid-data/forecasting-us.html
Chen, J., Fu, M. C., Zhang, W., & Zheng, J. (2020). Predictive Modeling for Epidemic Outbreaks: A New Approach and COVID-19 Case Study. Asia-Pacific Journal of Operational Research, 37(3). https://doi.org/10.1142/S0217595920500281
Drezner, Z., & Hamacher, H. W. (2002). Facility location: applications and theory. In Facility Location Application and Theory.
Duijzer, L. E., van Jaarsveld, W. L., Wallinga, J., & Dekker, R. (2018). Dose-Optimal Vaccine Allocation over Multiple Populations. Production and Operations Management, 27(1). https://doi.org/10.1111/poms.12788
Erdos, P., & Rényi, A. (1960; reprinted 2011). On the evolution of random graphs. In The Structure and Dynamics of Networks (Vol. 9781400841356). https://doi.org/10.1515/9781400841356.38
Garey, M. R. and Johnson, D. S. (1979), Computers and intractability: A guide to the theory of NP-completeness. San Francisco, CA: W. H. Freeman and Co.
Git Hub. (2021). COVID-19 Forecasting Model Descriptions, accessed February 9, 2021, available at https://github.com/cdcepi/COVID-19-Forecasts/blob/master/COVID-19_Forecast_Model_Descriptions.md
Hale, T. S., & Moberg, C. R. (2003). Location Science Research: A Review. In Annals of Operations Research (Vol. 123, Issues 1–4). https://doi.org/10.1023/A:1026110926707
Hutson, M. (2020). Why modeling the spread of COVID-19 is so damn hard. IEEE Spectrum, accessed June 4, 2022, available at https://spectrum.ieee.org/artificial-intelligence/medical-ai/why-modeling-the-spread-of-covid19-is-so-damn-hard
Keskinocak, P. (2021). Infectious Disease Modeling and Informing Decisions. Production and Operations Management Society Annual Conference Plenary Session on May 2, 2021.
Lancichinetti, A., Fortunato, S., & Radicchi, F. (2008). Benchmark graphs for testing community detection algorithms. Physical Review E - Statistical, Nonlinear, and Soft Matter Physics, 78(4). https://doi.org/10.1103/PhysRevE.78.046110
Laporte, G., Nickel, S., & Saldanha-da-Gama, F. (2019). Introduction to Location Science. In Location Science. https://doi.org/10.1007/978-3-030-32177-2_1
Liu, H., Zhang, R., & Hu, X. (2019). Burning number of theta graphs. Applied Mathematics and Computation, 361. https://doi.org/10.1016/j.amc.2019.05.031
Nickel, S., & Albandoz, J. P. (2005). Location theory: A unified approach. In Location Theory: A Unified Approach. https://doi.org/10.1007/3-540-27640-8
ReVelle, C., Toregas, C., & Falkson, L. (1976). Applications of the Location Set‐covering Problem. Geographical Analysis, 8(1). https://doi.org/10.1111/j.1538-4632.1976.tb00529.x
Schilling, D. A., Jayaraman, V., & Barkhi, R. (1993). A review of covering problems in facility location. Location Science, 1(1).
Šimon, M., Huraj, L., Luptáková, I. D., & Pospíchal, J. (2019). Heuristics for spreading alarm throughout a network. Applied Sciences (Switzerland), 9(16). https://doi.org/10.3390/app9163269
Snyder, L. V. (2011). Covering problems. In H. A. Eiselt and V. Marianov (Eds.), Foundations of Location Analysis. Berlin, Germany: Springer-Verlag, 109-135.
Weisstein, E. W. (2022). Graph Eccentricity, accessed June 4, 2022, available at https://mathworld.wolfram.com/GraphEccentricity.html
West, D. B. (2001). Introduction to Graph Theory (2nd ed.) Englewood Cliffs, New Jersey: Prentice-Hall.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2023 Decision Making: Applications in Management and Engineering
This work is licensed under a Creative Commons Attribution 4.0 International License.
