key: cord-0010879-4rpzt4dv
authors: Estrada, Ernesto; Meloni, Sandro; Sheerin, Matthew; Moreno, Yamir
title: Epidemic spreading in random rectangular networks
date: 2016-11-28
journal: Phys Rev E
DOI: 10.1103/physreve.94.052316
sha: 539a38db27a297c3c20edafd7c7788cfd0987ecf
doc_id: 10879
cord_uid: 4rpzt4dv

The use of network theory to model disease propagation on populations introduces important elements of reality to the classical epidemiological models. The use of random geometric graphs (RGGs) is one of such network models that allows for the consideration of spatial properties on disease propagation. In certain real-world scenarios—like in the analysis of a disease propagating through plants—the shape of the plots and fields where the host of the disease is located may play a fundamental role in the propagation dynamics. Here we consider a generalization of the RGG to account for the variation of the shape of the plots or fields where the hosts of a disease are allocated. We consider a disease propagation taking place on the nodes of a random rectangular graph and we consider a lower bound for the epidemic threshold of a susceptible-infected-susceptible model or a susceptible-infected-recovered model on these networks. Using extensive numerical simulations and based on our analytical results we conclude that (ceteris paribus) the elongation of the plot or field in which the nodes are distributed makes the network more resilient to the propagation of a disease due to the fact that the epidemic threshold increases with the elongation of the rectangle. These results agree with accumulated empirical evidence and simulation results about the propagation of diseases on plants in plots or fields of the same area and different shapes.

The use of network theory to model disease propagation on populations introduces important elements of reality to the classical epidemiological models. The use of random geometric graphs (RGGs) is one of such network models that allows for the consideration of spatial properties on disease propagation. In certain real-world scenarios-like in the analysis of a disease propagating through plants-the shape of the plots and fields where the host of the disease is located may play a fundamental role in the propagation dynamics. Here we consider a generalization of the RGG to account for the variation of the shape of the plots or fields where the hosts of a disease are allocated. We consider a disease propagation taking place on the nodes of a random rectangular graph and we consider a lower bound for the epidemic threshold of a susceptible-infected-susceptible model or a susceptible-infected-recovered model on these networks. Using extensive numerical simulations and based on our analytical results we conclude that (ceteris paribus) the elongation of the plot or field in which the nodes are distributed makes the network more resilient to the propagation of a disease due to the fact that the epidemic threshold increases with the elongation of the rectangle. These results agree with accumulated empirical evidence and simulation results about the propagation of diseases on plants in plots or fields of the same area and different shapes.

DOI: 10.1103/PhysRevE.94.052316

The study of epidemiological models on networks is one of the areas that has observed a major development in the application of network theory to real-world problems [1] . The discovery of the fact that networks with fat-tailed degree distributions do not display an epidemic threshold in the asymptotic limit is a relevant example of how the connectivity pattern of interacting agents can dramatically change the course of an epidemic [2, 3] . The use of network theory in epidemiological models provides a way to incorporate the individual-level heterogeneity necessary for the mechanistic understanding of the spread of infectious disease. These characteristics are very attractive for the application of network epidemiological models in ecology on the different spatial and temporal scales.

Although there have been many successful applications of network theory to human and animal epidemiology, the situation is a little less developed for epidemics on plants. Ten years ago Jeger et al. [4] recognized the relatively low use of network theory for studying plant diseases. Since then, more theoretical developments have been presented in the literature. These models include the important description of the geometric constraints in which the pathogen is spreading as well as stochasticity and several sources of heterogeneity in the transmission of infection [5] [6] [7] [8] .

In order to consider spatial effects in the transmission of diseases it is possible to consider spatial networks that treat interactions as a continuous variable that decays with increasing distance or by distributing randomly and independently a set of vertices on the Euclidean plane to represent the relative spatial location of individual hosts or habitat patches. The second kind of model is based on random geometric graphs (RGGs) [9] [10] [11] [12] , in which each node is randomly assigned geometric coordinates and then two nodes are connected if the (Euclidean) distance between them is smaller than or equal to a certain threshold r. Random geometric graphs have found applications to model populations which are geographically constrained in a certain region [13] [14] [15] [16] [17] [18] , which offer many valuable features over other types of random graphs [19, 20] . Brooks et al. [21] have used RGGs to model the interactions between the anther smut fungus and fire pink using temporal data that spans 7 years of field studies. They have concluded that the use of spatially explicit network models can yield important insights into how heterogeneous structure promotes the persistence of species in natural landscapes.

When studying the propagation of diseases in plants there is an important factor that needs to be taken into account. It is obvious that plants are not as mobile as humans and animals; thus they reach lower levels of mixing in a given population due to mobility. The immediate consequence of this lack of mobility is the fact that the shape of the plot or field in which the plants are distributed may significantly affect disease dynamics. In fact, there is both empirical and theoretical evidence that supports this hypothesis [22] [23] [24] [25] [26] [27] [28] [29] [30] . In general, it has been suggested that square plots and fields favored higher spreading of plant diseases than elongated ones of the same area [22] [23] [24] [25] . We should make here some remarks about the shape of plots in different scenarios. First, we should mention the experimental plots for different crops. In those cases, the size and shape of the plots are controlled typically to estimate crop yields. Thus, they are typically of almost perfect square or rectangular shapes (see, for instance, Ref. [24] ). The second scenario is when crops are cultivated in country fields. In these cases the sizes and shapes of the fields depends on the geographical conditions of the region. However, in general these fields can be grossly approximated as rectanglelike or squarelike on the basis that they are more or less elongated. Such shapes are also thought to facilitate the mechanized work on the fields more than irregular shapes. Finally, there is a third scenario in which plants are growing naturally in a given environment. In these cases it is obvious that the distribution could be quite irregular and acquiring many different shapes. However, when studying the influence of the shape of these natural fields on the propagation of an epidemic it is typical to approximate their shapes to rectangular or square ones, as it is well illustrated for the case study of the spatial and spatiotemporal pattern analysis of coconut lethal yellowing in Mozambique [26] .

It is important to remark that the area of the field also plays a fundamental role, with larger plots and fields favoring more the spreading of diseases [27, 29, 30] . Also, the orientation of elongated fields may affect the disease propagation with orientations perpendicular to prevalent winds suppressing epidemic progression [23, 25] . All in all, for plots and fields of the same area and orientation there is empirical and theoretical evidence that elongated shapes decrease the impact of epidemics on plant populations. It is worth noting that the theoretical models [28] [29] [30] used in the previously mentioned studies do not use network theory as a tool for the study of epidemic spreading.

In this work we consider a generalization of the RGG known as the random rectangular graph (RRG) model which has been recently introduced [31] . In this case, the nodes are uniformly and independently distributed on a unit rectangle of given side lengths. Thus, we simulate plots and fields of the same size in which we can analyze the effect of elongation on epidemic spreading on plants. When both sides are of the same length we recover the RGG which accounts for squared shapes. It is worth mentioning that previous models have considered the variation of the shape for the region where the nodes are distributed in the RGG. In some of these works more general boundaries, such as right prisms and fractal regions have been considered in particular for analyzing the connectivity of the resulting RGGs [32] [33] [34] . In this work we consider a susceptible-infected-susceptible (SIS) model on the RRGs to describe the propagation of a disease on a plant population on a field of varied rectangular shapes. We obtain analytical and simulation results that support the empirical observations and theoretical evidence about the fact that (ceteris paribus) elongated plots and fields decrease significantly the propagation of diseases on plants. In particular, our results show that the epidemic threshold is significantly displaced to the right with the elongation of the rectangle, which indicates that the number of infected plants necessary to produce an epidemic grows with the rectangle elongation. Finally, we stress that in classical, noninteracting systems-either homogeneous or heterogeneous-the resemblance of SIS and susceptible-infected-recovered (SIR) epidemiological models translates into a strong mathematical symmetry between them that leads to identical expressions for the epidemic thresholds under mean-field approaches (i.e., when neglecting the effects of dynamical correlations). We therefore anticipate that our results will be also valid in a SIR framework, which as a matter of fact could be more relevant for plant diseases.

Here we consider a population, e.g., plants, represented by the nodes of a graph for which the edges represent the interaction between the individuals in the population. Then, our representation consists of simple graphs G = (V ,E) defined by a set of n nodes V and a set of m edges E = {(u,v)|u,v ∈ V } between the nodes. These graphs are unweighted and undirected, with no self-loops (edges from a node to itself) and no multiple edges. The matrix A = (A ij ), called the adjacency matrix of the graph, has the following entries:

Once the structure of a network is defined, the adjacency matrix is not changed during the process of disease propagation to be modeled on the nodes and edges of that network. That is, the network topology is static and not changing with time. The degree k i of the node i is the number of edges incident to it, equivalently k i = j A ij . Let G = (V ,E) be a simple connected graph and let λ 1 > λ 2 · · · λ n be the eigenvalues of its adjacency matrix. The eigenvalue λ 1 is known as the principal eigenvalue of the adjacency matrix, also as the Perron-Frobenius eigenvalue. Below we show that λ 1 is key to determining the conditions of invasion.

When modeling epidemic disease propagation on plants, Brooks et al. [21] have considered the plants as the nodes of an RGG, in which the n nodes are points uniformly and independently distributed in the unit square [0,1] 2 [9] . Then, two points are connected by an edge if their Euclidean distance is at most r, which is a given fixed number known as the connection radius. This connection radius indicates the maximum distance at which a disease can be transmitted from one plant to its nearest neighbors (see Ref. [21] ).

Here we use an extension of the RGG to consider a rectangle, [0,a] × [0,b], where a,b ∈ R and a b. Due to the accumulated evidence that reveals the importance of the plot or field size on disease propagation, we keep the area of the rectangle fixed in order to analyze only the influence of the rectangle elongation on the disease spreading. Consequently, we consider unit rectangles of the form [0,a] × [0,a −1 ]. The rest of the construction of an RRG is similar to that of an RGG. That is, we distribute uniformly and independently n points in the unit rectangle [0,a] × [0,a −1 ] and then connect two points by an edge if their Euclidean distance is at most r. Obviously, when a = 1 the rectangle [0,a] × [0,a −1 ] is simply the unit square [0,1] 2 , which means that the RRG becomes the classical RGG [31] .

In Fig. 1 we illustrate two RRGs with different values of the rectangle side length a and the same number of nodes and edges. In the first case when a = 1 the graph corresponds to the classical random geometric graph in which the nodes are embedded into a unit square. The second case corresponds to a = 2 and it represents a slightly elongated rectangle.

An important question when studying RGGs in general is related to the connectivity of the resulting graphs. That is, for which values of the connection radius is an RGG with n nodes connected with high probability? In the case of the square, Penrose [35] proved that for the two-dimensional case

where P [· · · ] represents the probability that [· · · ] takes place andk is the average degree.

This means that for α → +∞ the RGG is almost surely connected when n → ∞ and almost surely disconnected when α → −∞.

In the case of the RRG where the value ofk depends on the relation between the two sides of the rectangle we can write Eq. (1) for the unit rectangle as [31] lim

where f is given by

The significance of the function f is clearer when we consider [31] that the expected average degree in an RRG is given byk

Because the parameter α is unknown and it depends on the specific RRG considered, we have obtained a lower bound for increase of the connection radius in a similar way as in the case of the RGGs. However, as the elongation of the rectangle increases (increase of a) it is more difficult for the graph to be connected, and the critical radius guaranteeing that the graph is connected increases significantly with a. In Fig. 2(b) we illustrate the way in which we determine these critical radii. For a given value of a we find the minimum value of r for which P (connected) = 1. Although we use in all cases the values obtained from the simulations, we can see that the theoretical bound for P (connected) (5) produces very similar results.

We then plot the values of the connectivity radius versus the elongation of the rectangles [see Fig. 2(c) ]. The curve joining the points of this plot makes a separation between the RRGs which are connected (upper triangular part) from those which are disconnected (lower triangular part). That is, the curve represents the critical radii versus critical elongation, and it gives the critical region indicating the connectivity of the RRGs. It can be read in two different ways. You can fix a value of a and then determine which is the critical radius for which the network will be disconnected. For instance, for a rectangle with longer side a = 15 it is necessary to use a radius larger than 0.17 to make the RRGs connected. More interesting for this work is the other way around. That is, we have a fixed radius of connection, which may represent the radius of spreading of a disease among plants. Then, you can find what elongation of the rectangle disconnects the network. For instance, if the connection radius is fixed to r = 0.35 every RRG is connected for a < 30. Then, we emphasize here that we always work in the region of connected RRGs in this work. That is, any analysis carried out in this paper is based on graphs for which the connectivity of the graph is 100% guaranteed as we work in the upper triangular part of this plot. In addition, we check computationally that every RRG generated in this work is connected.

The spreading of an infectious disease on networks can be modeled representing individuals as nodes and the contacts between them as edges. In this context individuals are categorized in different compartments according to their health state [36] : susceptible (S) for individuals that can be infected by the disease, infected (I) for infectious individuals that can spread the pathogen, or recovered (R) for individuals that have already passed the disease and are immune to it.

Two fundamental models for disease spreading are the so-called SIS and SIR models [36, 37] . The SIS model is intended to model recurrent diseases that do not provide immunity, i.e., most sexually transmitted diseases, where individuals can get the infection multiple times during their lifetime. Instead, in the SIR model, once an individual gets cured of the disease she enters the recovered compartment and cannot be infected again, that is, she acquires immunity. Both SIS and SIR dynamics are governed by two parameters, namely, the per contact infection rate β and the recovery rate μ. Let, s i , x i , and r i be the probabilities that the node i is susceptible, infected, or has recovered from infection, respectively. The equations governing a SIS process are the following:ṡ

while those governing a SIR one arė

In these models, β represents the rate for a susceptible individual to catch the disease once in contact with an infected one through a link of the network, whereas the recovery rate μ characterizes the rate at which an infected individual recovers from the disease. Note that the spreading of the disease depends on the network of contacts (an isolated individual cannot catch the disease), while the recovery phase is independent of the substrate network (an isolated infected individual will recover after some time).

The ratio β/μ drives the spreading of the disease. Depending on its infectious power two distinct phases are possible: an absorbing one where the spreading is not efficient enough to reach a large fraction of the system and the disease is absorbed and an active phase where the epidemic reaches a macroscopic fraction of the network. The transition from the absorbing to the active phase strictly resembles a nonequilibrium secondorder phase transition in statistical physics [38, 39] . The critical value of this transition ( β μ ) c = τ is defined as the epidemic threshold. This term is also known as the basic reproduction number and it represents a threshold in the sense that when τ < 1 the infection dies out and if τ > 1 the disease becomes an epidemic. In those cases where τ = 1, the disease remains in the population becoming endemic. The value of this threshold strongly depends on the topology of the network. In particular, for a given graph G = (V ,E) , it has been shown that [40] [41] [42] 

where λ 1 (G) is the largest eigenvalue of the adjacency matrix of the network. In the case of RGGs, Preciado and Jadbabaie [43] have made an exhaustive spectral analysis of virus spreading using the spectral moments of the adjacency matrix. They have found that for the RGG in a d-dimensional cube, the spectral radius is bounded as λ 1 (G) < c d nr d , where c d is a constant characteristic of the RGG in the d-dimensional cube. In two-dimensional space this means that λ 1 (G) < c 2 nr 2 . Then, because in these graphs the average degree is nr 2 , the previous expression basically tells us that the spectral radius is bounded by the average degree of the RGG.

In this section we concentrate more on the phenomenology of the process than on deriving analytical results about the dependence of the epidemic threshold with the topological parameters of the RRGs. Thus, we obtain some sort of mean-field approach that captures the behavior of the disease parameters with the topological ones. We start by considering the following well-known bounds for the largest eigenvalue of the adjacency matrix of a simple graph λ 1 (G) = λ 1 ,

where k max andk are the maximum and the average degree, respectively. Then, it is straightforward to realize that

Then, by substituting Eq. (4) in Eq. (13) we have the following bound for the epidemic threshold of an RRG:

This result generalizes the one obtained by Preciado and Jadbabaie [43] for the RGG to the case where we have a rectangle of any elongation and where we consider explicitly the border effects of the rectangle (respectively, the square in RGG).

Let us now consider what happens to the epidemic threshold when we elongate the rectangle without disconnecting the RRG. That is, what is the behavior of the epidemic threshold when a → a c . In the following we prove that, when a → a c , f decreases. Consequently, the spectral radius of the adjacency matrix λ 1 also decreases when a → a c , which implies that the epidemic threshold grows monotonically. Our strategy here is to prove that the increase of the rectangle elongation produces a decay of the average degree of the RRGs. Strictly speaking, proving that the average degree decreases with the elongation of the rectangle is not proof that the spectral radius also decreases. Although such proof is analytically possible, it is out of our intention of working more on the phenomenology of the process in this work. However, it is possible to indirectly infer such a relation between the elongation and the spectral radius as follows. First, it is well known in spectral graph theory that the average degree is a tight bound to the spectral radius of graphs in general. In particular, we are interested here in showing whether the average degree and the spectral radius of RRGs show the same behavior when the rectangle is elongated. In Fig. 3 we illustrate the plot of the spectral radius versus the average degree for RRGs with a = 1 [panel (a)], a = 30 [panel (b)], and a = 1, 2.5, 5, 7.7, 15, 20, 25, and 30 [panel (c) ] for different values of the connection radius. As can be seen in all cases, and particularly in the last one, the trends of the spectral radius and the average degree are exactly the same and indeed they are very highly linearly correlated. Thus, our conclusion here is that proving that the average degree has a certain behavior when the rectangle is elongated can be directly extrapolated to the behavior of the spectral radius with the elongation of the rectangle.

Then, in order to prove this result we first consider what happens to the function f when a → a c . Let 0 < r a −1 . Then, the first derivative of f 1 = f (0 r a −1 ) is given by

and since

(1 − a −2 ) 0, this is bounded by

Let a −1 r a. Then, the first derivative of f 2 = f (a −1 r a) is given by

which is bounded as

where

Let a r √ a 2 + a −2 . Then, the first derivative of

which is bounded as

where

and t = √ a 2 + a −2 . Then, because all the derivatives are negative, we have proven the result. Strictly speaking the fact that 1/(n − 1)f increases with increasing a does not necessarily imply that τ will exhibit a similar trend for every a. However, as we see in the next section there is a very good linear correlation between the values of τ obtained from the simulations and the lower bound 1/(n − 1)f , which indicates that both quantities follow the same trend and consequently that the previous assertion relating the behavior of the epidemic threshold when a → a c is general. We discuss this in more detail in the next section.

In Fig. 4 we illustrate the plot of the spectral radius of the adjacency matrix of RRGs as a function of both the rectangle size length a and the connection radius r. As expected the lower triangular part of the plot corresponds to the disconnected RRGs, which are never used in this work. However, in the upper triangular part of the plot we observe a large variation of the spectral radius λ 1 of an RRG with both parameters 

In this section we conduct extensive numerical simulations of the SIS dynamics for different values of the elongation a and a fixed radius r with the goal of checking the goodness of the bound defined in Eq. (13) and to illustrate how the elongation of the rectangle in the RRG model changes the epidemic dynamics. In the simulations we start seeding the infection in a small fraction, ρ 0 = 0.01, of the nodes and let the SIS dynamics evolve for 5 × 10 4 time steps. At this point, we let the simulations run for an additional 10 3 time steps and calculate the fraction of infected nodes ρ as the average of ρ(t) over this period. For each selection of the parameters we performed 250 independent runs with different initial conditions. The final value of ρ is obtained as the average over all the runs. Figure 5 shows the fraction of infected nodes in the stationary state against the infection rate β for different values of a = 1, 10, 20, and 30. The values shown by arrows are the analytical ones obtained using Eq. (14) .

To have a more detailed picture of the behavior of the epidemic threshold, in Fig. 6(a) we compare the theoretical bound with the epidemic threshold obtained via the numerical simulations. As we have stressed in the previous section this comparison is very important for understanding whether the (14) is very tight, and more importantly the bound and the "observed" epidemic threshold display the same behavior when the rectangle elongation changes. Indeed, our analysis of the difference between the observed value of the epidemic threshold and the lower bound obtained by Eq. (13) shows that for all the RRGs having 1 a 35 such relative difference is 2.93% and in no case it is larger than 10%. Also we observe no trend in the relative difference related to the elongation of the rectangle. That is, the relative difference is neither increasing nor decreasing with the elongation of the rectangle.

Finally, in Fig. 6 (b) we also tested the third case of Eq. (3), a r √ a 2 + a −2 for a = 3 and r = 3.01. In all cases, as expected, the theoretical and the simulation results show that the increase of the elongation of the rectangle produces an increase of the epidemic threshold. In other words, the elongation of the rectangle retards the disease progression through the nodes embedded in the rectangle.

In the case of disease propagating on plants, these resultsboth analytical and simulations-coincide with the field observations and simulations using stochastic models [22] [23] [24] [25] [26] [27] [28] [29] [30] which suggest that square plots and fields favored higher spreading of plant diseases than elongated ones of the same area [22] [23] [24] [25] .

Our analytical and simulation results point to the fact that, under the same conditions, the propagation of an epidemic on a rectangular plot or field is much harder than on a square one because a larger number of infected individuals is needed for the disease to become epidemic. Here we have kept the size of the plot or field constant by considering unit rectangles in our analysis. However, it is important to consider that other factors, such as the orientation of the plot or field, play fundamental roles in the propagation of a disease on plants. For instance, if the rectangular plots are placed perpendicular to the direction of the prevalent winds the disease will not propagate as a consequence of this factor.

We have studied the propagation of diseases on a recently proposed RRG model, deriving analytically a lower bound of the epidemic threshold for a SIS or SIR model running on these networks. This model is appropriate for the simulation of disease spreading on plants allocated on plots and field of varied shapes. RRGs account for the spatial distribution of nodes allowing the variation of the shape of the unit square commonly used in RGGs. We have shown here by using analytical results and extensive numerical simulations of the SIS dynamics for different values of the elongation a and a fixed radius r that the elongation of the plots or fields in which the nodes (plants) are distributed makes the network more resilient to the propagation of epidemics. This is due to the fact that the epidemic threshold increases with the elongation of the rectangle. These results agree with a large accumulation of empirical evidence about the role of elongation of plots and fields on the propagation of diseases on plants. This model represents a new way to analyze disease propagation on plants or similar scenarios, by combining the heterogeneities introduced at individual levels by networks with the influence produced by the shape variation of the plots and fields where the plants are growing.

Complex networks: Structure and dynamics

Absence of Epidemic Threshold in Scale-Free Networks with Degree Correlations

Thresholds for Epidemic Spreading in Networks

Modelling disease spread and control in networks: Implications for plant sciences

Epidemics in networks of spatially correlated three-dimensional root-branching structures

The effect of heterogeneity on invasion in spatial epidemics: From theory to experimental evidence in a model system

Heterogeneity in susceptible-infected-removed (SIR) epidemics on lattices

Complexity and anisotropy in host morphology make populations less susceptible to epidemic outbreaks

Random Geometric Graphs

Random geometric graphs

Random Graphs (Academic

Random graphs

Understanding spatial connectivity of individuals with non-uniform population density

Synchronization in random geometric graphs

Worm epidemics in wireless ad hoc networks

Spread of information and infection on finite random networks

Proximity networks and epidemics

A study on analyzing the grid road network: Patterns using relative neighborhood graph

Five challenges for spatial epidemic models

Opinion dynamics and influencing on random geometric graphs, Sci. Rep

Spatial and temporal heterogeneity explain disease dynamics in a spatially explicit network model

Interplot interference: A model for planning field experiments with aerially disseminated pathogens

Weather, space, time, and chance of infection

Size and shape of plots for estimating yield losses from cereal foliage diseases

Effect of field geometry on the spread of crop disease

Spatial and spatiotemporal pattern analysis of coconut lethal yellowing in Mozambique

Effect of genotype unit number and spatial arrangement on severity of yellow rust in wheat cultivar mixtures

Influence of number of host genotype units on the effectiveness of host mixtures for disease control: A modeling approach

Effects of quadrat size and shape, initial epidemic conditions, and spore dispersal gradient on spatial statistics of plant disease epidemics

The explicit dependence of quadrat variance on the ratio of clump size to quadrat size

Random rectangular graphs

Full connectivity: corners, edges and faces

12th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt)

More is less: Connectivity in fractal regions

The longest edge of the random minimal spanning tree

The Mathematical Theory of Infectious Diseases and Its Applications

Infectious Diseases of Humans: Dynamics and Control

Nonequilibrium Phase Transitions in Lattice Models

Nonequilibrium Phase Transitions

Epidemic thresholds in real networks

Discrete-time Markov chain approach to contact-based disease spreading in complex networks

Virus spread in networks

Spectral analysis of virus spreading in random geometric networks