Geodesic
S̲tochastic S̲imulation A̲lgorithm For Effective Spreading Dynamics On T̲ime-Evolving A̲daptive N̲etworX̲ (SSATAN-X)
Nadezhda Malysheva1, 2, 3 ; Junyu Wang3 ; Max von Kleist2, 3
1 International Max-Planck Research School for Biology and Computing (BAC), Berlin, Germany
2 Department of Mathematics and Computer Science, Freie Universität Berlin, Berlin, Germany
3 P5 Systems Medicine of Infectious Disease, Robert Koch-Institute, Berlin, Germany
Mathematical modelling of natural phenomena, Tome 17 (2022), article no. 35.

Voir la notice de l'article provenant de la source EDP Sciences

Modelling and simulating of pathogen spreading has been proven crucial to inform containment strategies, as well as cost-effectiveness calculations. Pathogen spreading is often modelled as a stochastic process that is driven by pathogen exposure on time-evolving contact networks. In adaptive networks, the spreading process depends not only on the dynamics of a contact network, but vice versa, infection dynamics may alter risk behavior and thus feed back onto contact dynamics, leading to emergent complex dynamics. However, numerically exact stochastic simulation of such processes via the Gillespie algorithm is currently computationally prohibitive. On the other hand, frequently used ‘parallel updating schemes’ may be computationally fast, but can lead to incorrect simulation results. To overcome this computational bottleneck, we propose SSATAN-X. The key idea of this algorithm is to only capture contact dynamics at time-points relevant to the spreading process. We demonstrate that the statistics of the contact- and spreading process are accurate, while achieving ~100 fold speed-up over exact stochastic simulation. SSATAN-X’s performance increases further when contact dynamics are fast in relation to the spreading process, as applicable to most infectious diseases. We envision that SSATAN-X may extend the scope of analysis of pathogen spreading on adaptive networks. Moreover, it may serve to create benchmark data sets to validate novel numerical approaches for simulation, or for the data-driven analysis of the spreading dynamics on adaptive networks.
DOI : 10.1051/mmnp/2022035

Nadezhda Malysheva 1, 2, 3 ; Junyu Wang 3 ; Max von Kleist 2, 3

1 International Max-Planck Research School for Biology and Computing (BAC), Berlin, Germany
2 Department of Mathematics and Computer Science, Freie Universität Berlin, Berlin, Germany
3 P5 Systems Medicine of Infectious Disease, Robert Koch-Institute, Berlin, Germany 
@article{MMNP_2022_17_a16,
     author = {Nadezhda Malysheva and Junyu Wang and Max von Kleist},
     title = {S̲tochastic {S̲imulation} {A̲lgorithm} {For} {Effective} {Spreading} {Dynamics} {On} {T̲ime-Evolving} {A̲daptive} {N̲etworX̲} {(SSATAN-X)}},
     journal = {Mathematical modelling of natural phenomena},
     eid = {35},
     publisher = {mathdoc},
     volume = {17},
     year = {2022},
     doi = {10.1051/mmnp/2022035},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/mmnp/2022035/}
}
TY  - JOUR
AU  - Nadezhda Malysheva
AU  - Junyu Wang
AU  - Max von Kleist
TI  - S̲tochastic S̲imulation A̲lgorithm For Effective Spreading Dynamics On T̲ime-Evolving A̲daptive N̲etworX̲ (SSATAN-X)
JO  - Mathematical modelling of natural phenomena
PY  - 2022
VL  - 17
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.1051/mmnp/2022035/
DO  - 10.1051/mmnp/2022035
LA  - en
ID  - MMNP_2022_17_a16
ER  - 
%0 Journal Article
%A Nadezhda Malysheva
%A Junyu Wang
%A Max von Kleist
%T S̲tochastic S̲imulation A̲lgorithm For Effective Spreading Dynamics On T̲ime-Evolving A̲daptive N̲etworX̲ (SSATAN-X)
%J Mathematical modelling of natural phenomena
%D 2022
%V 17
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.1051/mmnp/2022035/
%R 10.1051/mmnp/2022035
%G en
%F MMNP_2022_17_a16
Nadezhda Malysheva; Junyu Wang; Max von Kleist. S̲tochastic S̲imulation A̲lgorithm For Effective Spreading Dynamics On T̲ime-Evolving A̲daptive N̲etworX̲ (SSATAN-X). Mathematical modelling of natural phenomena, Tome 17 (2022), article  no. 35. doi : 10.1051/mmnp/2022035. http://geodesic.mathdoc.fr/articles/10.1051/mmnp/2022035/

[1] D.F. Anderson A modified next reaction method for simulating chemical systems with time dependent propensities and delays J. Chew,. Phys 2007 214107

[2] D.F. Anderson Incorporating postleap checks in tau-leaping J. Chew,. Phys 2008 054103

[3] D.F. Anderson, A. Ganguly, T.G. Kurtz Error analysis of tau-leap simulation methods Ann. Appl. Probab 2011 2226 2262

[4] S. Bansal, B.T. Grenfell, L.A. Meyers When individual behaviour matters: homogeneous and network models in epidemiology J.R. Soc. Interface 2007 879 91

[5] M. Boguîiâ, L.F. Lafuerza, R. Toral, M.A. Serrano Simulating non-Markovian stochastic processes Phys. Rev. E 2014 042108

[6] M.-C. Boily, R.F. Baggaley, L. Wang, B. Masse, R.G. White, R.J. Hayes, M. Alary Heterosexual risk of HIV-1 infection per sexual act: systematic review and meta-analysis of observational studies Lancet Infect Dis 2009 118 29

[7] F. Brauer Mathematical epidemiology: past, present, and future Infect Dis. Model 2017 113 127

[8] J. Butcher , Numerical Methods for Ordinary Differential Equations, Second Edition, Wiley (2008).

[9] Y. Cao, D.T. Gillespie, L.R. Petzold Efficient step size selection for the tau-leaping simulation method J. Chem. Phys 2006 044109

[10] M.S. Cohen, Y.Q. Chen, M. Mccauley, T. Gamble, M.C. Hosseinipour, N. Kumarasamy, J.G. Hakim, J. Kumwenda, B. Grinsztejn, J.H.S. Pilotto, S.V. Godbole, S. Mehendale, S. Chariyalertsak, B.R. Santos, K.H. Mayer, I.F. Hoffman, S.H. Eshleman, E. Piwowar-Manning, L. Wang, J. Makhema, L.A. Mills, G. De Bruyn, I. Sanne, J. Eron, J. Gallant, D. Havlir, S. Swindells, H. Ribaudo, V. Elharrar, D. Burns, T.E. Taha, K. Nielsen-Saines, D. Celentano, M. Essex, T.R. Fleming Prevention of HIV-1 infection with early antiretroviral therapy N. Engl. J. Med 2011 493 505

[11] C.E. Dangerfield, J.V. Ross, M.J. Keeling Integrating stochasticity and network structure into an epidemic model J. R. Soc. Interface 2009 761 74

[12] J.T. Davis, M. Chinazzi, N. Perra, K. Mu, A. Pastore, Y. Piontti, M. Ajelli, N.E. Dean, C. Gioannini, M. Litvinova, S. Merler, L. Rossi, K. Sun, X. Xiong, I.M. Longini, M.E. Halloran, C. Viboud, A. Vespignani Cryptic transmission of SARS-CoV-2 and the first COVID-19 wave Nature 2021 127 132

[13] R. Dunbar , Grooming, gossip, and the evolution of language. Harvard University Press (1998).

[14] R.I.M. Dunbar Neocortex size as a constraint on group size in primates J. Human Evolut 1992 469 493

[15] S. Duwal, L. Dickinson, S. Khoo, M. Von Kleist Hybrid stochastic framework predicts efficacy of prophylaxis against HIV PLoS Comput. Biol 2018 e1006155

[16] S. Duwal, D. Seeler, L. Dickinson, S. Khoo, M. Von Kleist The Utility of Efavirenz-based prophylaxis against hiv infection. A systems pharmacological analysis Front. Pharmacol 2019 199

[17] S. Duwal, V. Sunkara, M. Von Kleist Multiscale systems-pharmacology pipeline to assess the prophylactic efficacy of NRTIs Against HIV-1 CPT Pharmacometr. Syst. Pharmacol 2016 377 87

[18] S. Duwal, S. Winkelmann, C. Schütte, M. Von Kleist Optimal treatment strategies in the context of 'treatment for prevention' against HIV-1 PLoS Comput. Biol 2015 e1004200

[19] J. Enright, R.R. Kao Epidemics on dynamic networks Epidemics 2018 88 97

[20] E. Fehlberg , Classical fifth-, sixth-, seventh-, and eighth-order Runge-Kutta formulas with stepsize control. NASA Technical Report (TR) (1968).

[21] S.C. Ferreira, C. Castellano, R. Pastor-Satorras Epidemic thresholds of the susceptible-infected-susceptible model on networks: a comparison of numerical and theoretical results Phys. Rev. E 2012 041125

[22] S. Funk, M. Salathe, V.A.A. Jansen Modelling the influence of human behaviour on the spread of infectious diseases: a review J.R. Soc. Interface 2010 1247 1256

[23] D.T. Gillespie Exact stochastic simulation of coupled chemical-reactions J. Phys. Chem 1977 2340 2361

[24] D.T. Gillespie Approximate accelerated stochastic simulation of chemically reacting systems J. Chem. Phys 2001 1716 1733

[25] S.M. Goodreau, S. Cassels, D. Kasprzyk, D.E. Montano, A. Greek, M. Morris Concurrent partnerships, acute infection and HIV epidemic dynamics among young adults in Zimbabwe AIDS Behav 2012 312 322

[26] R.M. Grant, J.R. Lama, P.L. Anderson, V. Mcmahan, A.Y. Liu, L. Vargas, P. Goicochea, M. Casapia, J.V. Guanira-Carranza, M.E. Ramirez-Cardich, O. Montoya-Herrera, T. Fernandez, V.G. Veloso, S.P. Buchbinder, S. Chariyalertsak, M. Schechter, L.-G. Bekker, K.H. Mayer, E.G. Kallas, K.R. Amico, K. Mulligan, L.R. Bushman, R.J. Hance, C. Ganoza, P. Defechereux, B. Postle, F. Wang, J.J. Mcconnell, J.-H. Zheng, J. Lee, J.F. Rooney, H.S. Jaffe, A.I. Martinez, D.N. Burns, D.V. Glidden Preexposure chemoprophylaxis for HIV prevention in men who have sex with men N. Engl. J. Med 2010 2587 2599

[27] T. Gross, B. Blasius Adaptive coevolutionary networks: a review J.R. Soc. Interface 2008 259 271

[28] T. Gross and H. Sayama , Adaptive Networks: Theory, Models and Applications. Springer (2009).

[29] S.L. Hakimi On realizability of a set of integers as degrees of the vertices of a linear graph. I J. Soc. Indust. Appl. Math 1962 496 506

[30] R. Hinch, W.J.M. Probert, A. Nurtay, M. Kendall, C. Wymant, M. Hall, K. Lythgoe, A. Bulas Cruz, L. Zhao, A. Stewart, L. Ferretti, D. Montero, J. Warren, N. Mather, M. Abueg, N. Wu, O. Legat, K. Bentley, T. Mead, K. Van-Vuuren, D. Feldner-Busztin, T. Ristori, A. Finkelstein, D.G. Bonsall, L. Abeler-Doürner, C. Fraser OpenABM-Covid19-An agent-based model for non-pharmaceutical interventions against COVID-19 including contact tracing PLoS Comput. Biol 2021 e1009146

[31] T. Hladish, E. Melamud, L.A. Barrera, A. Galvani, L.A. Meyers EpiFire: An open source CH-+ library and application for contact network epidemiology BMC Bioinform 2012 76

[32] P. Holme Epidemiologically optimal static networks from temporal network data PLoS Comput. Biol 2013 e1003142

[33] P. Holme and J. Saramüaki , Temporal Networks. Springer (2013).

[34] R. Huerta, L.S. Tsimring Contact tracing and epidemics control in social networks Phys. Rev. E 2002 056115

[35] S.M. Jenness, S.M. Goodreau, M. Morris EpiModel: an R package for mathematical modeling of infectious disease over networks J. Stat. Software 2018

[36] M.J. Keeling, K.T.D. Eames Networks and epidemic models J.R. Soc. Interface 2005 295 307

[37] M.J. Keeling, T. House, A.J. Cooper, L. Pellis Systematic approximations to susceptible-infectious-susceptible dynamics on networks PLoS Comput. Biol 2016 e1005296

[38] W. Kermack, A. Mckendrick A contribution to the mathematical theory of epidemics Proc. Roy. Soc. A 1927 700 721

[39] C.C. Kerr, R.M. Stuart, D. Mistry, R.G. Abeysuriya, K. Rosenfeld, G.R. Hart, R.C. Nünez, J.A. Cohen, P. Selvaraj, B. Hagedorn, L. George, M. Jastrzebski, A.S. Izzo, G. Fowler, A. Palmer, D. Delport, N. Scott, S.L. Kelly, C.S. Bennette, B.G. Wagner, S.T. Chang, A.P. Oron, E.A. Wenger, J. Panovska-Griffiths, M. Famulare, D.J. Klein Covasim: an agent-based model of COVID-19 dynamics and interventions PLOS Comput. Biol 2021 1 32

[40] M. Kretzschmar, M. Morris Measures of concurrency in networks and the spread of infectious disease Math. Biosci 1996 165 195

[41] T. Leng, M.J. Keeling Concurrency of partnerships, consistency with data, and control of sexually transmitted infections Epidemics 2018 35 46

[42] N.H.L. Leung, D.K.W. Chu, E.Y.C. Shiu, K.-H. Chan, J.J. Mcdevitt, B.J.P. Hau, H.-L. Yen, Y. Li, D.K.M. Ip, J.S.M. Peiris, W.-H. Seto, G.M. Leung, D.K. Milton, B.J. Cowling Respiratory virus shedding in exhaled breath and efficacy of face masks Nat. Med 2020 676 680

[43] P. Lindenfors, A. Wartel, J. Lind 'Dunbar's number' deconstructed Biol. Lett 2021 20210158

[44] I.M. Longini, M.E. Halloran, A. Nizam, Y. Yang Containing pandemic influenza with antiviral agents Am,. J. Epidemiol 2004 623 633

[45] L. Marchetti , C. Priami and V.H. Thanh , Simulation Algorithms for Computational Systems Biology. Springer (2017).

[46] F. Morone, H. Makse Influence maximization in complex networks through optimal percolation Nature 2015 65 68

[47] M. Nadini, L. Zino, A. Rizzo, M. Porfiri A multi-agent model to study epidemic spreading and vaccination strategies in an urban-like environment Appl. Netw. Sci 2020 68

[48] D.-Y. Oh, S. Buda, B. Biere, J. Reiche, F. Schlosser, S. Duwe, M. Wedde, M. Von Kleist, M. Mielke, T. Wolffand, R. Dürrwald Trends in respiratory virus circulation following COVID-19-targeted nonpharmaceutical interventions in Germany, January-September 2020: analysis of national surveillance data Lancet Reg. Health Eur 2021 100112

[49] S. Osat, A. Faqeeh, F. Radicchi Optimal percolation on multiplex networks Nat. Commun 2017 1540

[50] R. Pastor-Satorras, C. Castellano, P.V. Mieghem, A. Vespignani Epidemic processes in complex networks Rev. Mod. Phys 2015 925 979

[51] F.P. Polack, S.J. Thomas, N. Kitchin, J. Absalon, A. Gurtman, S. Lockhart, J.L. Perez, G. Perez Marc, E.D. Moreira, C. Zerbini, R. Bailey, K.A. Swanson, S. Roychoudhury, K. Koury, P. Li, W.V. Kalina, D. Cooper, R.W. Frenck, L.L. Hammitt, O. Türeci, H. Nell, A. Schaefer, S. Ünal, D.B. Tresnan, S. Mather, P.R. Dormitzer, U. Sahin, K.U. Jansen, W.C. Gruber Safety and Efficacy of the BNT162b2 mRNA Covid-19 Vaccine N. Engl. J. Med 2020 2603 2615

[52] R.A. Royce, A. Sena, W. Cates, M.S. Cohen Sexual transmission of HIV N. Engl. J. Med 1997 1072 1078

[53] P. Rue, J. Villa-Freixa, K. Burrage Simulation methods with extended stability for stiff biochemical Kinetics BMC Syst. Biol 2010 110

[54] E. Silverman, Ü. Gostoli, S. Picascia, J. Almagor, M. Mccann, R. Shaw, C. Angione Situating agent-based modelling in population health research Emerg. Themes Epidemiol 2021 10

[55] W. Van Der Toorn, D.-Y. Oh, D. Bourquain, J. Michel, E. Krause, A. Nitsche, M. Von Kleist An intra-host SARS-CoV-2 dynamics model to assess testing and quarantine strategies for incoming travelers, contact management, and de-isolation Patterns (N Y) 2021 100262

[56] W. Van Der Toorn, D.-Y. Oh, M. Von Kleist COVIDStrategyCal-culator: a software to assess testing and quarantine strategies for incoming travelers, contact management, and de-isolation Patterns (N Y) 2021 100264

[57] C.L. Vestergaard, M. Genois Temporal gillespie algorithm: fast simulation of contagion processes on time-varying networks PLoS Comput. Biol 2015 e1004579

[58] M. Voliotis, P. Thomas, R. Grima, C. Bowsher Stochastic simulation of biomolecular networks in dynamic environments PLoS Comput. Biol 2016 e1004923

[59] S. Weller, K. Davis Condom effectiveness in reducing heterosexual HIV transmission Cochrane Database Syst. Rev 2002 CD003255

[60] L. Zhang, J. Wang, M. Von Kleist Numerical approaches for the rapid analysis of prophylactic efficacy against HIV with arbitrary drug-dosing schemes PLoS Comput. Biol 2021 1009295

[61] G. Zschaler, T. Gross Largenet2: an object-oriented programming library for simulating large adaptive networks Bioinformatics 2013 277 278

Cité par Sources :