Abstract
The dynamics of disease transmission strongly depends on the properties of the population contact network. Pair-approximation models and individual-based network simulation have been used extensively to model contact networks with non-trivial properties. In this paper, using a continuous time Markov chain, we start from the exact formulation of a simple epidemic model on an arbitrary contact network and rigorously derive and prove some known results that were previously mainly justified based on some biological hypotheses. The main result of the paper is the illustration of the link between graph automorphisms and the process of lumping whereby the number of equations in a system of linear differential equations can be significantly reduced. The main advantage of lumping is that the simplified lumped system is not an approximation of the original system but rather an exact version of this. For a special class of graphs, we show how the lumped system can be obtained by using graph automorphisms. Finally, we discuss the advantages and possible applications of exact epidemic models and lumping.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Anderson RM, May RM (1991) Infectious diseases of humans: dynamics and control. Oxford University Press
Andersson H, Djehich B (1997) A threshold limit theorem for the stochastic logistic epidemic. J Appl Prob 35: 662–670
Ball F, Mollison D, Salia-Tomba G (1997) Epidemics with two levels of mixing. Ann Appl Prob 7: 46–89
Brandes U, Erlebach T (2005) Network analysis: methodological foundations. Springer-Verlag, Berlin
Brauer F, van den Driessche P, Wu J (2008) In: (eds) Mathematical epidemiology. In: Lecture notes in mathematics. Springer-Verlag, Berlin
Broom M, Rychtář J (2008) An analysis of the fixation probability of a mutant on special classes of non-directed graphs. Proc R Soc A 464: 2609–2627
Daley DJ, Gani J (1999) Epidemic modelling: an intoduction. Cambridge University Press
Dent JE, Kao RR, Kiss IZ, Hyder K, Arnold M (2008) Contact structures in the poultry industry in Great Britain: exploring transmission routes for a potential avian influenza virus epidemic. BMC Vet Res 4: 27
Diekmann O, Heesterbeek JAP (2000) Mathematical epidemiology of infectious diseases: model building, analysis and interpretation. Wiley, Chichester
Diekmann O, De Jong MCM, Metz JAJ (1998) A deterministic epidemic model taking account of repeated contacts between the same individuals. J Appl Prob 35: 448–462
Ferguson NM, Donnelly CA, Anderson RM (2001) The foot-and mouth epidemic in Great Britain: pattern of spread and impact of interventions. Science 292: 1155–1160
Filliger L, Hongler M-O (2008) Lumping complex networks. Madeira Math Encounters XXXV. http://ccm.uma.pt/mme35/files/LumpingNetworks-Filliger.pdf
Green DM, Kiss IZ, Kao RR (2006) Modelling the initial spread of foot-and-mouth disease through animal movements. Proc R Soc B 273: 2729–2735
Gross JL, Yellen J (2003) Handbook of graph theory. CRC Press, Boca Raton
House T, Davies G, Danon L, Keeling MJ (2009) A motif-based approach to network epidemics. Bull Math Biol 71: 1693–1706
Hufnagel L, Brockmann D, Geisel T (2004) Forecast and control of epidemics in a globalized world. Proc Natl Acad Sci USA 101: 15124–15129
Hundsdorfer W, Verwer JG (2003) Numerical solution of time-dependent advection-diffusion-reactions equations. Springer, New York
Jacobi MN, Görnerup O (2009) A spectral method for aggregating variables in linear dynamical systems with application to cellular automata renormalization. Adv Complex Syst 12: 1–25
Kao RR, Danon L, Green DM, Kiss IZ (2006) Demographic structure and pathogen dynamics on the network of livestock movements in Great Britain. Proc R Soc B 273: 1999–2007
Keeling MJ (1999) The effects of local spatial structure on epidemiological invasions. Proc R Soc Lond B 266: 859–867
Keeling MJ (2005) The implications of network structure for epidemic dynamics. Theor Popul Biol 67: 1–8
Keeling MJ, Eames KTD (2005) Networks and epidemic models. J R Soc Interface 2: 295–307
Keeling MJ, Ross JV (2008) On methods for studying stochastic disease dynamics. J R Soc Interface 5: 171–181
Keeling MJ, Rand DA, Morris AJ (1997) Correlation models for childhood epidemics. Proc R Soc B 264: 1149–1156
Kemeny JG, Snell JL (1976) Finite Markov chains, 2nd edn. Springer, New York
Kenah E, Robins JM (2007) Network-based analysis of stochastic SIR epidemic models with random and proportionate mixing. J Theor Biol 249: 706–722
Kermack WO, McKendrick AG (1927) A contribution to the mathematical study of epidemics. Proc R Soc Lond Ser A 115: 700–721
Kiss IZ, Green DM, Kao RR (2005) Disease contact tracing in random and clustered networks. Proc R Soc B 272: 1407–1414
Kiss IZ, Green DM, Kao RR (2006a) The network of sheep movements within Great Britain: network properties and their implications for infectious disease spread. J R Soc Interface 3: 669–677
Kiss IZ, Green DM, Kao RR (2006b) The effect of network heterogeneity and multiple routes of transmission on final epidemic size. Math Biosci 203: 124–136
Kiss IZ, Green DM, Kao RR (2008) The effect of network mixing patterns on epidemic dynamics and the efficacy of disease contact tracing. J R Soc Interface 5: 791–799
Kurtz TG (1970) Solutions of ordinary differential equations as limits of pure jump Markov processes. J Appl Prob 7: 49–58
Kurtz TG (1971) Limit theorems for sequences of jump Markov processes approximating ordinary differential processes. J Appl Prob 8: 344–356
Lipsitch M et al (2003) Transmission dynamics and control of severe acute respiratory syndrome. Science 300: 1966–1970
May RM, Lloyd AL (2001) Infection dynamics on scale-free networks. Phys Rev E 64: 066112
Meyers LA, Pourbohloul B, Newman MEJ, Skowronski DM, Brunham RC (2005) Network theory and SARS: predicting outbreak diversity. J Theor Biol 232: 71–81
Nåsell I (1996) The quasi-stationary distribution of the closed endemic SIS model. Adv Appl Probab 28: 895–932
Newman MEJ (2002) The spread of epidemic disease on networks. Phys Rev E 66: 016128
Picard P (1965) Sur les modèles stochastique logistiques en démographie. Ann Inst Henri Poincaré B II: 151–172
Rand DA (1999) Correlation equations for spatial ecologies. In: McGlade J (eds) Advanced ecological theory. Blackwell, Oxford, pp 100–142
Sato K, Matsuda H, Sasaki A (1994) Pathogen invasion and host extinction in lattice structured populations. J Math Biol 32: 251–268
Sharkey KJ (2008) Deterministic epidemiological models at the individual level. J Math Biol 57: 311–331
Smith GJ et al (2009) Origins and evolutionary genomics of the 2009 swine-origin H1N1 influenza A epidemic. Nature 459: 1122–1125
van Baalen M (2000) Pair approximations for different spatial geometries. In: Dieckmann U, Law R, Metz JAJ (eds) The geometry of ecological interactions: simplifying complexity. Cambridge University Press, pp 359–387
Yap HP (1986) Some topics in graph theory. In: London Mathematical Society, Lecture notes series 108. Cambridge University Press, Cambridge
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Simon, P.L., Taylor, M. & Kiss, I.Z. Exact epidemic models on graphs using graph-automorphism driven lumping. J. Math. Biol. 62, 479–508 (2011). https://doi.org/10.1007/s00285-010-0344-x
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00285-010-0344-x