key: cord-017590-w5copp1z authors: Fresnadillo, María J.; García, Enrique; García, José E.; Martín, Ángel; Rodríguez, Gerardo title: A SIS Epidemiological Model Based on Cellular Automata on Graphs date: 2009 journal: Distributed Computing, Artificial Intelligence, Bioinformatics, Soft Computing, and Ambient Assisted Living DOI: 10.1007/978-3-642-02481-8_160 sha: doc_id: 17590 cord_uid: w5copp1z The main goal of this work is to introduce a new SIS epidemic model based on a particular type of finite state machines called cellular automata on graphs. The state of each cell stands for the fraction of the susceptible and infected individuals of the cell at a particular time step and the evolution of these classes is given in terms of a local transition function. The public health issues have a lot of importance in our society, particularly viral spread through populated areas. Epidemics refer to a disease that spreads rapidly and extensively by infection and affecting many individuals in an area at the same time. In this way, the most recent worrying epidemic was the Severe Acute Respiratoy Syndrome (SARS) outbreak in Asia. Infectious disease accounts for 29 of 96 major causes of human morbidity and mortality listed by the World Health Organization and the World Bank, and 25% of global deaths (over 14 million deaths annually). Consequently, since the publication of the first modern mathematical epidemic models in the first years of XX century (see [6, 9] ), several mathematical models to study the dynamics of epidemics have been appeared in the literature. Traditionally, mathematical models are based on differential equations. Nevertheless, this approach has some drawbacks since they do not take into account spatial factors such as population density, they neglect the local character of the spreading process, they do not include variable susceptibility of individuals, etc. As a consequence, this can lead to very unrealistic results, such as, for example, endemic patterns relaying on very small densities of individuals, which are called "atto-foxes" or "nano-hawks" (see [8] ). Other mathematical models are based on a particular type of discrete dynamical systems called cellular automata (see, for example [2, 5, 7, 10, 11] ). These simple models of computation eliminate the last mentioned shortcomings, and are specially suitable for computer simulations. Roughly speaking, cellular automata (CA for short) are a special type of finite state machines capable to simulate physical, biological or environmental complex phenomena. Consequently, several models based on such mathematical objects have been proposed to simulate growth processes, reaction-diffusion systems, selfreproduction models, epidemic models, forest fire spreading, image processing algorithms, cryptographic protocols, etc. (see, for example, [12, 13] ). Specifically, a two-dimensional CA is formed by a two-dimensional array of identical objects called cells which can be disposed in a rectangular, triangular or an hexagonal lattice (called cellular space). These cells are endowed with a state that changes in discrete steps of time according to a specific rule. As the CA evolves, the updated function (whose variables are the states of the neighbor cells) determines how local interactions can influence the global behaviour of the system. Usually, mathematical models to study epidemic spreading are divided into three types: SIS models, SIR models and SEIR models, depending on the classes in which the population can be classified. The model introduced in this paper deals with SIS epidemic diseases (for example the group of those responsible for the common cold), that is, the population is divided into susceptible individuals (S) and infected individuals (I). The susceptible individuals are those capable to contracting the disease whereas the infected individuals are those capable of spreading the disease. For a SIS model, infected individuals return to the susceptible class on recovery because the disease confers no immunity against reinfection. Moreover, some assumptions will be common to all models: (1) The disease is transmitted by contact between an infected individual and a susceptible individual; (2) There is no latent period for the disease, hence the disease is transmitted instantaneously upon contact; (3) All susceptible individuals are equally susceptible and all infected individuals are equally infectious; (4) The population under consideration is fixed in size. This means that no births or migration occurs, and no deaths are taken into account. The main goal of this work is to introduce a new SIS model to simulate the spread of a general epidemic based on cellular automata on graph. Specifically, in the proposed model, the state of each cell stands for the fraction of the susceptible and infected individuals of the cell at a particular time step. The local transition function is a function involving the states of the neighbor cells and other parameters such as the virulence of the epidemic, the rate of recovered infected individuals, etc. Moreover, as is mentioned above, the standard paradigm for cellular automata states that the topology of the cellular space is given in terms of a regular rectangular or hexagonal lattices. Nevertheless, in this paper we will consider a more efficient topology to model an epidemic disease, which is given by an undirected graph where its nodes stand for the cells of the cellular automata. There are several CA-based algorithms to simulate a SIS epidemic model (see, for example [1, 3, 4] ). The standard paradigm of these models states that each cell stands for an only one individual. Unfortunately, there are few models considering more than one invidual in each cell (see for example [5] ). We think that this new paradigm is more accurate than the other one in order to obtain more realistic simulations. The main advantage of the model presented in this paper over the model introduced in [5] is the use of graph tology and a more realistic transition function involving new parameters as the portion of susceptible individuals that moves from one cell to another one. The rest of the paper is organized as follows: In Section 2 the basic theory about cellular automata on graphs is provided; the proposed model is introduced in Section 3; the analysis of the model is shown in Section 4; and, finally, the conclusions and the future work are presented in Section 5. . . , v n } is a ordered non-empty finite set of elements called nodes (or vertices), and E is a finite family of pairs of elements of V called edges. Two nodes of the graph, v i , v j ∈ V , are said to be adjacent (or neighbors) if there exists an edge in E of the form (v i , v j ). We consider undirected graphs, that is, is not two edges of G with the same ends and no loops exist, i.e. edges whose start and end is located at the same node. The neighborhood of a node v ∈ V , N v , is the set of all nodes of G which are adjacent to v, that is: The degree of a node v, d v , is the number of its neighbors. A cellular automaton on an undirected graph G = (V, E) is a 4-uple A = (V, S, N, f ) where: The set V defines the cellular space of the CA such that each node stands for a cell the cellular automaton. S is the finite set of states that can be assumed by the nodes at each step of time. The state of the node v at time step t is denoted by s t v ∈ S. These states change accordingly to the local transition function f . N is the neighborhood function which assigns to each node its neighborhood, that is: Note that the neighborhoods of the nodes are, in general, different from others. The local transition function f calculates the state of every node at a particular time step t + 1 from the states of the its neighbors at the previous time step t, that is, In the mathematical epidemiological model introduced in this paper, the population is divided into two classes: those who are susceptible to the disease and those who are infected to the disease. Moreover, the population is located at city centres which stand for the nodes of a graph G. If there is some type of transport connection (by car, train, airplane, etc.) between two of these cities, the associated nodes are connected by an edge. The following assumptions are also made: 1. The population of each node remains constant over time, that is, no births or deaths are taking into account (it is a SIS model without vital dynamics). Moreover, the population distribution is inhomogeneous: Let P u be the number of individuals of the node u ∈ V , and set P = max {P u , u ∈ V }. 2. The transmission of the disease (that is, the passing of the disease from an infected individual to a susceptible individual) is through direct physical contact: touching an infected person, including sexual contact. 3. The population (susceptible and infected people) are able to move from its node to another one and return to the origin node at every step of time. Since the model introduced in this work is a SIS model, then the state of the node u ∈ V at time step t is: s t u = (S t u , I t u ) ∈ Q × Q = S, where S t u ∈ [0, 1] stands for the fraction of susceptible individuals of the node u at time t, and I t u ∈ [0, 1] stands for the fraction of infected individuals of the node u at time t. Consequently, the transition function of the CA is as follows: where d is a suitable discretization function. The ground where the epidemic is spreading is modeled as a weighted graph where each node stands for a city or a town, and the arc between two nodes represents the connection between the corresponding cities. In this sense, the connection factor between the nodes u and v is the weight associated to the arc (u, v) ∈ E and it is denoted by w uv . It depends on the transportation capacity of the public and non-public transport. Consequently where h uv is the total amount of population wich move from u to v during a time step. The evolution of the number of infected individuals of the node u ∈ V is as follows: The infected individuals of u at time step t is given by the sum of: 1. The infected individuals at the previous time step which have not been recovered from the disease. 2. The susceptible individuals which have been infected during the time step. In this case we have to take into account the recovery rate r ∈ [0, 1]. These new sick individuals of u can be infected both by the infected individuals of u or by the infected individuals of the neighbor nodes of u which have moved to u during the time step. In the first case, only the rate of transmission, p ∈ [0, 1], is involved, whereas in the second case we have to consider the connection factors between the nodes, and the population and movement factor of each node. Moreover we also consider the susceptible individuals of u moved to a neightbor node during the step of time and infected in this neighbor node by its corresponding infected individuals; in this case η u ∈ [0, 1] yields the portion of moved susceptible individuals from u to its neighbor nodes. Then, the mean-field equation for infected individuals is the following: On the other hand, the susceptible individuals of each node is given by the difference of the susceptible individuals of the node at the previous time step and the susceptible individuals which have been infected as is mentioned above. Note that, as a simple calculus shows: then a discretization function d : [0, 1] → Q must be used in order to get a finite state set. In our case, the discretization function used is the following: 100 where [m] stands for the nearest integer to m. As a consequence, Q ={0, 0.01, . . . , 1}. Then, the system of equations governing the evolution of the two classes of population is: One of the most important question in a mathematical epidemiological model is the study of the possibility of the eradication of disease. In relation with every mathematical epidemiological model, it is very important to determine under what circumstances the epidemic occurs. Taking into account the intrinsic characteristics of our model, we will demand two conditions: (1) The epidemic disease must spread among the nodes of the graph; and (2) The infected population grows. The initial conditions in the study are the following: At time step t = 0, we will consider only one node, for example u ∈ V , with infected individuals: First of all we will show the necessary condition for epidemic spreading from the node u to its neighbor v ∈ N u , at the next step of time t = 1. Thus, it As the unique node with infected population at time t = 0 is u, then taking into account (1), it yields: As a consequence: . This equation must hold for every neighbor nodes of u, then the following result holds: Theorem. The epidemic disease spreads from node u to its neighbor nodes if the following condition holds: Now we will study what conditions that must be held to get a growth of the infected population in a node u. We have to distinguish two cases: (1) There not exist infected individuals from neighbor nodes to u; (2) There exist such infected individuals. 1. In the first case it is I t+1 u > I t u , that is: As a consequence the growth occurs if: 2. In the second case, the inequality I t+1 u > I t u gives: In this example, for the sake of simplicity we will suppose that the epidemic is spreading over n = 10 cities, v 1 , . . . , v 10 , forming a complete graph K 10 . In this example, we will consider the following initial configuration: That is, there is only one node at time t = 0 with infected population. Moreover, the parameters used are p = 0.25, r = 0.8, η ui = 0.2, 1 ≤ i ≤ 6. Moreover, let us suppose that the population of each node is the same: P ui = 100 with 1 ≤ i ≤ 6, and also the transport capacity between two nodes is the same: w uiuj = 1 for 1 ≤ i, j ≤ 6. Note that this example deals with an homogeneous-symmetric case. In Figure 1 the evolution of the total number of infected and susceptible individuals is shown. If we set p = 0.15 instead of p = 0.25, the number of infected and susceptible individuals also remains constant with time, but in this case the number of susceptible is greater than the number of infected individuals. In this work a new mathematical model to simulate the spreading of an epidemic is introduced. It is based on the use of cellular automata on graphs endowed with Fig. 1 . Evolution of the total number of infected and susceptible individuals a suitable local transition function. The state of each cell is considered to be the portion of its population which is infected at each time step. The analysis of the model proposed in this paper seems to be in agreement with the results obtained for other mathematical models not based on discrete event systems, such as ODEs or PDEs. Future work aimed at designing a more complete CA-based epidemic model involving additional effects such as the population movement, virus mutation, etc. Furthermore, it is also interesting to consider non-constant connections factors and also the effect of migration between the cells must be considered. On some applications of cellular automata A simple cellular automaton model for influenza A viral infections Critical behaviour of a probablistic automata network SIS model for the spread of an infectious disease in a population of moving individuals Cellular automata and epidemiological models with spatial dependence A model based on cellular automata to simulate epidemic diseases Contributions to the mathematical theory of epidemics, part I A cellular automata model for citrus variegated chlorosis The dependence of epidemic and population velocities on basic parameters The prevention of malaria Extending the SIR epidemic model A cellular automaton model for the effects of population movement and vaccination on epidemic propagation Cellular Automata Machines: A New Environment for Modeling A New Kind of Science Acknowledgments. This work has been partially supported by Consejería de Sanidad, Junta de Castilla y León (Spain).