MDd.llng and Simulation In Se/.ne., Englnllrlng and T.ehnology S"IIB Editor Nicola Bellomo Politecnico Torino Italy Advisory Edltor/al Board K.J. Bathe P.Degond Massachusetts Institute of Technology Universit6 P. Sabatier Toulouse 3 USA France W. Kliemann P. Le Tallec Iowa State University INRIA USA France S. Nikitin K.R. Rajagopal Arizona State University Texas A&M University USA USA V. Protopopescu Y. Sone CSMD Kyoto University Oak Ridge National Laboratory Japan USA E.S. Subuhi Istanbul Technical University Turkey Gilbert G. Walter Martha Contreras Compartmental Modeling with Networks Springer Science+Business Media, LLC Gilbert G. Walter Martha Contreras Department of Mathematical Sciences Department of Biometry University of Wisconsin-Milwaukee Cornell University P.O. Box 413 434 Warren Hall Milwaukee, WI 53201-0413 Ithaca, NY 14853-7801 USA USA Library of Congress Cataloging-in-PubIication Data Walter, Gilbert G. Compartmental modeling with networks / Gilbert Walter, Martha Contreras. p. cm. - (Modeling and simulat ion in science, engineering and technology) Includes bibliographical references and index. ISBN 978-1-4612-7207-6 ISBN 978-1-4612-1590-5 (eBook) DOI 10.1007/978-1-4612-1590-5 1. Mathematical models. 2. Computer simulation. 1. Contreras, Martha. II. Title. III. Series. TA342.W35 1999 511'.8--dc21 98-44616 CIP AMS Subject Classifications: 05, 60, 92 Printed on acid-free paper. © 1999 Springer Science+Business Media New York Originally published by Birkhăuser Boston in 1999 Softcover reprint of the hardcover lst edition 1999 AII rights reserved. This work may not be translated or copied in whole or in part without the written permission of the publisher, Springer Science+Business Media, LLC except for brief excerpts in connection with reviews or scholarly analysis. Use in connection with any form of information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed is forbidden. The use of general descriptive names, trade names, trademarks, etc., in this publicat ion, even if the former are not especially identified, is not to be taken as a sign that such names, as understood by the Trade Marks and Merchandise Marks Act, may accordingly be used freely byanyone. ISBN 978-1-4612-7207-6 Formatted from the authors' TeX files. 9 8 7 6 5 4 321 Contents Preface ix List of Figures xviii 1 Introduction and Simple Examples 1 1.1 Mathematical Models 1 1.2 Examples of Models ........ 2 Part I. Structure of Models: Directed Graphs 9 2 Digraphs and Graphs: Definitions and Examples 11 2.1 Definitions. 11 2.2 Examples 12 2.3 Problems . 15 3 A Little Simple Graph Theory 17 3.1 Isomorphic Graphs and Digraphs 17 3.2 Connected Graphs and Digraphs 19 4 Orientation of Graphs and Related Properties 25 4.1 Vertex Basis. . . . . . 25 4.2 Multigraphs...... 27 4.3 Orientation of Graphs 31 4.4 Spanning Trees . . . . 33 4.5 Minimum Connector Problem 37 5 Tournaments 41 5.1 Definitions and Basic Results 41 5.2 Transitive Tournaments 44 6 Planar Graphs 47 6.1 Bipartite Graphs . . . . . . . . . . . . . . . . . . 48 6.2 A Necessary Condition for a Graph to Be Planar 49 v VI Contents 7 Graphs and Matrices 53 7.1 Adjacency and Reachability Matrices. 53 7.2 Eigenvalues of Adjacency Matrices 56 7.3 Using Maple with Graphs ...... . 59 Part II. Digraphs and Probabilities: Markov Chains 63 8 Introduction to Markov Chains 65 8.1 Relation to Digraphs ..... . 65 8.2 More Definitions and Examples 66 9 Classification of Markov Chains 71 9.1 Definitions............ 71 9.2 Condensation of a Stochastic Digraph 76 10 Regular Markov Chains 81 10.1 Theory of Regular Chains 81 10.2 Fixed-Point Probability Vector 84 10.3 Influence Digraph ..... 86 11 Absorbing Markov Chains 89 11.1 An Example. . . . . . . . . . . . . . . . . . . . . . . . .. 89 11.2 Some General Results .................... 92 11.3 Population Genetics: An Example of an Absorbing Chain 95 11.4 Small Group Decision Making: An Absorbing Markov Chain 97 12 From Markov Chains to Compartmental Models 101 12.1 Comparison of Quantities 101 12.2 Two Examples ................ . 104 Part III. Compartmental Models: Applications 109 13 Introduction to Compartmental Models 111 13.1 Basic Concepts ......... . 111 13.2 One-Compartment Applications. 114 13.2.1 Linear Case ... 115 13.2.2 Logistic Growth 116 13.3 Other Examples ... . 118 13.4 Matrix Forms ..... . 120 13.5 Two-Compartment Models 121 14 Models for the Spread of Epidemics 125 14.1 The SIR Model ...... . 125 14.2 Other Models of Epidemics ..... 128 Contents Vll 15 Three Traditional Examples as Compartmental Models 131 15.1 Predator-Prey or Host-Parasite Equations. 131 15.2 The Leslie Matrix ........ . 135 15.3 Leontief Input-Output Analysis. 137 16 Ecosystem Models 141 16.1 Dissolved Oxygen. 141 16.2 Forest Ecosystem 143 16.3 Food Webs . . 146 17 Fisheries Models 149 17.1 Logistic Equation Approach 150 17.2 Nonequilibrium Yield ... . 152 17.3 A Multispecies Model .. . 156 17.4 An Ecosystem Fisheries Model 159 18 Drug Kinetics 163 18.1 Bilirubin Metabolism (Simple) 163 18.2 Bilirubin Metabolism (Complex) 165 18.3 Lead Kinetics . 166 18.4 HIV Dynamics . . . . . . . . . . 167 Part IV. Compartmental Models Theory 173 19 Basic Properties of Linear Models 175 19.1 Compartmental Matrices. 176 19.2 Eigenvalues ... . 178 19.3 Analytic Solution .... . 180 20 Structure and Dynamical Properties 183 20.1 Positivity of Solutions .... 183 20.2 Condensation of the Digraph 185 20.3 Eigenvalues and Structure 189 20.4 Some Special Cases ..... . 192 21 Identifiability of a Compartmental System 197 21.1 General Input and Output ......... . 197 21.2 An Example of an Identifiable System . . . 199 21.3 Another Example Which Is Not Identifiable 200 21.4 Another Approach: Using Laplace Transforms. 201 21.5 The General Case. . . . . . . . . . . . . . . . 203 21.6 Size Identifiability of Compartmental Models 204 21.6.1 Example ....... . 206 21.6.2 Some More Examples 207 21.6.3 Main Result ..... . 209 viii Contents 22 Parameter Estimation 211 22.1 Estimation Problem 211 22.2 Statistical Estimation 215 23 Complexity and Stability 218 23.1 Complexity ..... 218 23.2 The Shannon Index. 221 23.3 Other Indices . . . . 223 23.4 Relation to Stability 226 A Mathematical Prerequisites 228 Appendix 228 A.l Matrix Operations .......... . 228 A.2 Finding Eigenvalues and Eigenvectors 233 A.3 Systems of Differential Equations 235 A.4 Matrices with Maple . . . . . . . . . . 238 Bibliography 242 Index 247 Preface The subject of mathematical modeling has expanded considerably in the past twenty years. This is in part due to the appearance of the text by Kemeny and Snell, "Mathematical Models in the Social Sciences," as well as the one by Maki and Thompson, "Mathematical Models and Applica tions." Courses in the subject became a widespread if not standard part of the undergraduate mathematics curriculum. These courses included var ious mathematical topics such as Markov chains, differential equations, linear programming, optimization, and probability. However, if our own experience is any guide, they failed to teach mathematical modeling; that is, few students who completed the course were able to carry out the mod eling paradigm in all but the simplest cases. They could be taught to solve differential equations or find the equilibrium distribution of a regular Markov chain, but could not, in general, make the transition from "real world" statements to their mathematical formulation. The reason is that this process is very difficult, much more difficult than doing the mathemat ical analysis. After all, that is exactly what engineers spend a great deal of time learning to do. But they concentrate on very specific problems and rely on previous formulations of similar problems. It is unreasonable to expect students to learn to convert a large variety of real-world problems to mathematical statements, but this is what these courses require. Fortunately, there is a large class of problems for which the transition step is not as difficult. These are problems for which the appropriate model is a flow model. They are used when there is a flow of something such as a fluid or money or energy between the components of a system. They are widely used in biomedicine for tracer experiments, but have applications in other areas of biology such as the study of ecosystems, as well as in input-output analysis in economics, arms races, and the study of epidemics. What's more is that the transition step from the problem statement to the mathematical formulation is very intuitive and easily learned. Most of our students chose such models for their course projects even though they formerly constituted a small portion of the course. These flow models are usually called compartmental models to distinguish IX x Preface them from diffusion models. To construct them, a system is divided up into homogeneous compartments and the flows of material between the various compartments and to and from the outside are traced. This leads immediately to a directed graph, which can be used as a simple model and may be adequate for an initial analysis of the system. If information on flow rates is known, the model becomes a system of differential or difference equations. These can be solved by traditional means, but because of the special nature of these models, properties of the solutions can be inferred without knowing the solutions explicitly. In this work, we shall concentrate on these models and their applica tions. This will involve consideration of some properties of digraphs (di rected graphs), their relations to the systems of differential equations, and their conversion to Markov chains. The applications will be to ecosystem models, to fluid transfer, to competition models, to predator-prey systems, to fisheries management, to regular and absorbing Markov chain models, to Leontief input-output models, to Leslie matrices, to tracer experiments, to epidemic models, and to network flows in engineering. The book will be organized in four parts as follows: The first part will be devoted to the theory of digraphs; it will be at a level accessible to most students who have had any college mathematics course. The second part deals with Markov chains. Although the terminology involves concepts from probability theory, the mathematics is pure matrix theory. It requires only the material found in a first course in matrix theory or finite mathematics. The third part will introduce the differential equations associated with compartmental models and develop their theory to some extent. This part will require a knowledge of calculus and matrices, but not necessarily dif ferential equations. The final part will go into the theory of compartmental models somewhat more deeply. The relations between the dynamics of the solution and the structure of the model will be studied. The required level of sophistication is higher but still requires only calculus and matrix theory. Although these compartmental models are not designed to be computer models, they lend themselves very well to computer simulation and approx imation. The code for implementation of an approximation scheme comes directly out of the differential equation formats. Previous versions of this book have been used for a course in mathe matical modeling at the University of Wisconsin-Milwaukee for about a dozen years. This is a third-year course requiring a semester of calculus and a semester of matrix theory. The students have come from a number of different disciplines: about one-half from mathematics and others from biology, economics, sociology, and even architecture. Typically, about half the material in this book was covered in a semester