Tensor product approach to modelling epidemics on networks. (English) Zbl 07748302
Summary: To improve mathematical models of epidemics it is essential to move beyond the traditional assumption of homogeneous well-mixed population and involve more precise information on the network of contacts and transport links by which a stochastic process of the epidemics spreads. In general, the number of states of the network grows exponentially with its size, and a master equation description suffers from the curse of dimensionality. Almost all methods widely used in practice are versions of the stochastic simulation algorithm (SSA), which is notoriously known for its slow convergence. In this paper we numerically solve the chemical master equation for an SIR model on a general network using recently proposed tensor product algorithms. In numerical experiments we show that tensor product algorithms converge much faster than SSA and deliver more accurate results, which becomes particularly important for uncovering the probabilities of rare events, e.g. for number of infected people to exceed a (high) threshold.
MSC:
| 92D30 | Epidemiology |
| 15A69 | Multilinear algebra, tensor calculus |
| 37N25 | Dynamical systems in biology |
| 60J28 | Applications of continuous-time Markov processes on discrete state spaces |
| 65F55 | Numerical methods for low-rank matrix approximation; matrix compression |
| 90B15 | Stochastic network models in operations research |
Keywords:
epidemiological modelling; networks; chemical master equation; tensor train; stochastic simulation algorithm; Monte Carlo simulation; rare events; high precisionSoftware:
MatlabReferences:
| [1] | Kermack, W. O.; McKendrick, A. G., A contribution to the mathematical theory of epidemics, Proc. R. Soc. Lond. A, 115, 772, 700-721 (1927) · JFM 53.0517.01 |
| [2] | Chen, W.-Y.; Bokka, S., Stochastic modeling of nonlinear epidemiology, J. Theor. Biol., 234, 4, 455-470 (2005) · Zbl 1445.92267 |
| [3] | Youssef, M.; Scoglio, C., An individual-based approach to SIR epidemics in contact networks, J. Theor. Biol., 283, 1, 136-144 (2011) · Zbl 1397.92697 |
| [4] | Gillespie, D. T., Approximate accelerated stochastic simulation of chemically reacting systems, J. Chem. Phys., 115, 4, 1716-1733 (2001) |
| [5] | Keeling, M. J., The effects of local spatial structure on epidemiological invasions, Proc. Biol. Sci., 266, 1421, 859-867 (1999) |
| [6] | Rand, D. A., Correlation equations and pair approximations for spatial ecologies, (Advanced Ecological Theory: Principles and Applications (1999), Blackwell Science: Blackwell Science Oxford), 100-142, Ch. 4 · Zbl 1001.92552 |
| [7] | Gleeson, J. P., High-accuracy approximation of binary-state dynamics on networks, Phys. Rev. Lett., 107, Article 068701 pp. (2011) |
| [8] | Lindquist, J.; Ma, J.; van den Driessche, P.; Willeboordse, F. H., Effective degree network disease models, J. Math. Biol., 62, 143-164 (2011) · Zbl 1232.92066 |
| [9] | Taylor, M.; Taylor, T. J.; Kiss, I. Z., Epidemic threshold and control in a dynamic network, Phys. Rev. E, 85, Article 016103 pp. (2012) |
| [10] | Miller, J. C.; Slim, A. C.; Volz, E. M., Edge-based compartmental modelling for infectious disease spread, J. R. Soc. Interface, 9, 890-906 (2012) |
| [11] | Griebel, M.; Harbrecht, H., Analysis of tensor approximation schemes for continuous functions, Found. Comput. Math., 23, 219-240 (2023) · Zbl 1531.41026 |
| [12] | Oseledets, I. V., Tensor-train decomposition, SIAM J. Sci. Comput., 33, 5, 2295-2317 (2011) · Zbl 1232.15018 |
| [13] | Hackbusch, W.; Kühn, S., A new scheme for the tensor representation, J. Fourier Anal. Appl., 15, 5, 706-722 (2009) · Zbl 1188.15022 |
| [14] | Dolgov, S. V., TT-GMRES: solution to a linear system in the structured tensor format, Russ. J. Numer. Anal. Math. Model., 28, 2, 149-172 (2013) · Zbl 1266.65050 |
| [15] | Dolgov, S. V.; Savostyanov, D. V., Alternating minimal energy methods for linear systems in higher dimensions, SIAM J. Sci. Comput., 36, 5, A2248-A2271 (2014) · Zbl 1307.65035 |
| [16] | Dolgov, S. V.; Khoromskij, B. N.; Oseledets, I. V.; Savostyanov, D. V., Computation of extreme eigenvalues in higher dimensions using block tensor train format, Comput. Phys. Commun., 185, 4, 1207-1216 (2014) · Zbl 1344.65043 |
| [17] | Dolgov, S. V.; Savostyanov, D. V., Corrected one-site density matrix renormalization group and alternating minimal energy algorithm, (Numerical Mathematics and Advanced Applications — ENUMATH 2013, vol. 103 (2015)), 335-343 · Zbl 1328.65087 |
| [18] | Rakhuba, M.; Novikov, A.; Oseledets, I., Low-rank Riemannian eigensolver for high-dimensional Hamiltonians, J. Comput. Phys., 396, 1, 718-737 (2019) · Zbl 1452.65070 |
| [19] | Dolgov, S. V., A tensor decomposition algorithm for large ODEs with conservation laws, Comput. Methods Appl. Math., 19, 23-38 (2019) · Zbl 1420.65030 |
| [20] | White, S. R., Density-matrix algorithms for quantum renormalization groups, Phys. Rev. B, 48, 14, 10345-10356 (1993) |
| [21] | Klümper, A.; Schadschneider, A.; Zittartz, J., Matrix product ground states for one-dimensional spin-1 quantum antiferromagnets, Europhys. Lett., 24, 4, 293-297 (1993) |
| [22] | Schollwöck, U., The density-matrix renormalization group in the age of matrix product states, Ann. Phys., 326, 1, 96-192 (2011) · Zbl 1213.81178 |
| [23] | Kolda, T. G.; Bader, B. W., Tensor decompositions and applications, SIAM Rev., 51, 3, 455-500 (2009) · Zbl 1173.65029 |
| [24] | Hackbusch, W., Tensor Spaces and Numerical Tensor Calculus (2012), Springer-Verlag: Springer-Verlag Berlin · Zbl 1244.65061 |
| [25] | Khoromskij, B. N., Tensor numerical methods for multidimensional PDEs: theoretical analysis and initial applications, ESAIM Proc., 48, 1-28 (2015) · Zbl 1382.65461 |
| [26] | Ballani, J.; Grasedyck, L.; Kluge, M., A review on adaptive low-rank approximation techniques in the hierarchical tensor format, (Extraction of Quantifiable Information from Complex Systems. Extraction of Quantifiable Information from Complex Systems, Lecture Notes in Computational Science and Engineering, vol. 102 (2014), Springer), 195-210 · Zbl 1317.65106 |
| [27] | van Kampen, N. G., Stochastic Processes in Physics and Chemistry (1981), North Holland: North Holland Amsterdam · Zbl 0511.60038 |
| [28] | Hemberg, M.; Barahona, M., Perfect sampling of the master equation for gene regulatory networks, Biophys. J., 93, 2, 401-410 (2007) |
| [29] | Anderson, D. F.; Higham, D. J., Multilevel Monte Carlo for continuous time Markov chains, with applications in biochemical kinetics, Multiscale Model. Simul., 10, 1, 146-179 (2012) · Zbl 1262.60072 |
| [30] | Lester, C.; Baker, R. E.; Giles, M. B.; Yates, C. A., Extending the multi-level method for the simulation of stochastic biological systems, Bull. Math. Biol., 78, 8, 1640-1677 (2016) · Zbl 1352.92062 |
| [31] | Munsky, B.; Khammash, M., The finite state projection algorithm for the solution of the chemical master equation, J. Chem. Phys., 124, Article 044104 pp. (2006) |
| [32] | Jahnke, T., An adaptive wavelet method for the chemical master equation, SIAM J. Sci. Comput., 31, 6, 4373 (2010) · Zbl 1205.65022 |
| [33] | Cao, Y.; Terebus, A.; Liang, J., State space truncation with quantified errors for accurate solutions to discrete chemical master equation, Bull. Math. Biol., 78, 4, 617-661 (2016) · Zbl 1341.92086 |
| [34] | Hegland, M.; Burden, C.; Santoso, L.; MacNamara, S.; Booth, H., A solver for the stochastic master equation applied to gene regulatory networks, J. Comput. Appl. Math., 205, 2, 708-724 (2007) · Zbl 1121.65009 |
| [35] | Kryven, I.; Röblitz, S.; Schütte, C., Solution of the chemical master equation by radial basis functions approximation with interface tracking, BMC Syst. Biol., 9, 1, 67 (2015) |
| [36] | Gupta, A.; Schwab, C.; Khammash, M., DeepCME: a deep learning framework for computing solution statistics of the chemical master equation, PLoS Comput. Biol., 17, 12, 1-23 (2021) |
| [37] | Sukys, A.; Öcal, K.; Grima, R., Approximating solutions of the chemical master equation using neural networks (2022), bioRxiv |
| [38] | Jahnke, T.; Huisinga, W., A dynamical low-rank approach to the chemical master equation, Bull. Math. Biol., 70, 2283-2302 (2008) · Zbl 1169.92021 |
| [39] | Ammar, A.; Cueto, E.; Chinesta, F., Reduction of the chemical master equation for gene regulatory networks using proper generalized decompositions, Int. J. Numer. Methods Biomed. Eng., 28, 9, 960-973 (2012) |
| [40] | Hegland, M.; Garcke, J., On the numerical solution of the chemical master equation with sums of rank one tensors, ANZIAM J., 52, C628-C643 (2011) · Zbl 1386.65050 |
| [41] | Kazeev, V.; Khammash, M.; Nip, M.; Schwab, C., Direct solution of the chemical master equation using quantized tensor trains, PLoS Comput. Biol., 10, 3, Article e100359 pp. (2014) |
| [42] | Dolgov, S.; Khoromskij, B., Simultaneous state-time approximation of the chemical master equation using tensor product formats, Numer. Linear Algebra Appl., 22, 2, 197-219 (2015) · Zbl 1363.65117 |
| [43] | Vo, H. D.; Sidje, R. B., An adaptive solution to the chemical master equation using tensors, J. Chem. Phys., 147, 4, Article 044102 pp. (2017) |
| [44] | Dinh, T.; Sidje, R. B., An adaptive solution to the chemical master equation using quantized tensor trains with sliding windows, Phys. Biol., 17, 6, Article 065014 pp. (2020) |
| [45] | Ion, I. G.; Wildner, C.; Loukrezis, D.; Koeppl, H.; De Gersem, H., Tensor-train approximation of the chemical master equation and its application for parameter inference, J. Chem. Phys., 155, 3, Article 034102 pp. (2021) |
| [46] | Gelß, P.; Matera, S.; Schütte, C., Solving the master equation without kinetic Monte Carlo: tensor train approximations for a CO oxidation model, J. Comput. Phys., 314, 489-502 (2016) · Zbl 1349.80031 |
| [47] | Botev, Z. I.; Kroese, D. P., An efficient algorithm for rare-event probability estimation, combinatorial optimization, and counting, Methodol. Comput. Appl. Probab., 10, 4, 471-505 (2008) · Zbl 1293.65004 |
| [48] | Peherstorfer, B.; Kramer, B.; Willcox, K., Multifidelity preconditioning of the cross-entropy method for rare event simulation and failure probability estimation, SIAM/ASA J. Uncertain. Quantificat., 6, 2, 737-761 (2018) · Zbl 1394.35493 |
| [49] | Wagner, F.; Latz, J.; Papaioannou, I.; Ullmann, E., Multilevel sequential importance sampling for rare event estimation, SIAM J. Sci. Comput., 42, 4, A2062-A2087 (2020) · Zbl 1442.35569 |
| [50] | Kemeny, J. G.; Snell, J. L., Finite Markov Chains (1976), Springer · Zbl 0328.60035 |
| [51] | Rogers, L. C.G.; Pitman, J. W., Markov functions, Ann. Probab., 9, 4, 573-582 (1981) · Zbl 0466.60070 |
| [52] | Gillespie, D. T., Exact stochastic simulation of coupled chemical reactions, J. Phys. Chem., 81, 25, 2340-2361 (1977) |
| [53] | Anderson, D. F.; Ganguly, A.; Kurtz, T. G., Error analysis of Tau-Leap simulation methods, Ann. Appl. Probab., 21, 6, 2226-2262 (2011) · Zbl 1234.60066 |
| [54] | Hitchcock, F. L., The expression of a tensor or a polyadic as a sum of products, J. Math. Phys., 6, 1, 164-189 (1927) · JFM 53.0095.01 |
| [55] | de Silva, V.; Lim, L.-H., Tensor rank and the ill-posedness of the best low-rank approximation problem, SIAM J. Matrix Anal. Appl., 30, 3, 1084-1127 (2008) · Zbl 1167.14038 |
| [56] | Golub, G.; Kahan, W., Calculating the singular values and pseudo-inverse of a matrix, SIAM J. Numer. Anal., 2, 2, 205-224 (1965) · Zbl 0194.18201 |
| [57] | Holtz, S.; Rohwedder, T.; Schneider, R., The alternating linear scheme for tensor optimization in the tensor train format, SIAM J. Sci. Comput., 34, 2, A683-A713 (2012) · Zbl 1252.15031 |
| [58] | Fannes, M.; Nachtergaele, B.; Werner, R., Finitely correlated states on quantum spin chains, Commun. Math. Phys., 144, 3, 443-490 (1992) · Zbl 0755.46039 |
| [59] | Rohrbach, P. B.; Dolgov, S.; Grasedyck, L.; Scheichl, R., Rank bounds for approximating Gaussian densities in the Tensor-Train format, SIAM/ASA J. Uncertain. Quantificat., 10, 3, 1191-1224 (2022) · Zbl 1505.65195 |
| [60] | Kazeev, V.; Schwab, C., Tensor approximation of stationary distributions of chemical reaction networks, SIAM J. Matrix Anal. Appl., 36, 3, 1221-1247 (2015) · Zbl 1322.60155 |
| [61] | Byrne, G. D.; Hindmarsh, A. C., A polyalgorithm for the numerical solution of ordinary differential equations, ACM Trans. Math. Softw., 1, 1, 71-96 (1975) · Zbl 0311.65049 |
| [62] | Trefethen, L. N., Spectral Methods in MATLAB (2000), SIAM: SIAM Philadelphia · Zbl 0953.68643 |
| [63] | Kazeev, V. A.; Khoromskij, B. N., Low-rank explicit QTT representation of the Laplace operator and its inverse, SIAM J. Matrix Anal. Appl., 33, 3, 742-758 (2012) · Zbl 1268.15025 |
| [64] | Kazeev, V.; Reichmann, O.; Schwab, C., Low-rank tensor structure of linear diffusion operators in the TT and QTT formats, Linear Algebra Appl., 438, 11, 4204-4221 (2013) · Zbl 1281.15024 |
| [65] | Dolgov, S. V.; Khoromskij, B. N.; Savostyanov, D. V., Superfast Fourier transform using QTT approximation, J. Fourier Anal. Appl., 18, 5, 915-953 (2012) · Zbl 1260.65114 |
| [66] | Savostyanov, D. V., QTT-rank-one vectors with QTT-rank-one and full-rank Fourier images, Linear Algebra Appl., 436, 9, 3215-3224 (2012) · Zbl 1244.65253 |
| [67] | Oseledets, I. V.; Savostyanov, D. V.; Tyrtyshnikov, E. E., Linear algebra for tensor problems, Computing, 85, 3, 169-188 (2009) · Zbl 1172.65018 |
| [68] | Oseledets, I. V.; Tyrtyshnikov, E. E., TT-cross approximation for multidimensional arrays, Linear Algebra Appl., 432, 1, 70-88 (2010) · Zbl 1183.65040 |
| [69] | Savostyanov, D. V.; Oseledets, I. V., Fast adaptive interpolation of multi-dimensional arrays in tensor train format, (Proceedings of 7th International Workshop on Multidimensional Systems (nDS) (2011), IEEE) |
| [70] | Savostyanov, D. V., Quasioptimality of maximum-volume cross interpolation of tensors, Linear Algebra Appl., 458, 217-244 (2014) · Zbl 1294.65017 |
| [71] | Dolgov, S.; Savostyanov, D., Parallel cross interpolation for high-precision calculation of high-dimensional integrals, Comput. Phys. Commun., 246, Article 106869 pp. (2020) · Zbl 07678425 |
| [72] | Barcza, G.; Legeza, O.; Marti, K. H.; Reiher, M., Quantum-information analysis of electronic states of different molecular structures, Phys. Rev. A, 83, Article 012508 pp. (2011) |
| [73] | Ballani, J.; Grasedyck, L., Tree adaptive approximation in the hierarchical tensor format, SIAM J. Sci. Comput., 36, 4, A1415-A1431 (2014) · Zbl 1303.65026 |
| [74] | Bebendorf, M.; Kuske, C., Separation of variables for function generated high-order tensors, J. Sci. Comput., 61, 1, 145-165 (2014) · Zbl 1307.65052 |
| [75] | Solomonik, E.; Matthews, D.; Hammond, J. R.; Stanton, J. F.; Demmel, J., A massively parallel tensor contraction framework for coupled-cluster computations, J. Parallel Distrib. Comput., 74, 12, 3176-3190 (2014) |
| [76] | Grasedyck, L.; Kriemann, R.; Löbbert, C.; Nägel, A.; Wittum, G.; Xylouris, K., Parallel tensor sampling in the hierarchical Tucker format, Comput. Vis. Sci., 17, 2, 67-78 (2015) · Zbl 1360.65042 |
| [77] | Secular, P.; Gourianov, N.; Lubasch, M.; Dolgov, S.; Clark, S. R.; Jaksch, D., Parallel time-dependent variational principle algorithm for matrix product states, Phys. Rev. B, 101, Article 235123 pp. (2020) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
