Microsoft Word - 476hernandez.docx CHEMICAL ENGINEERING TRANSACTIONS VOL. 43, 2015 A publication of The Italian Association of Chemical Engineering Online at www.aidic.it/cet Chief Editors: Sauro Pierucci, Jiří J. Klemeš Copyright © 2015, AIDIC Servizi S.r.l., ISBN 978-88-95608-34-1; ISSN 2283-9216 Complex Network Statistics to the Design of Fire Breaks for the Control of Fire Spreading Lucia Russoa*, Paola Russob, Ioannis N. Evaggelidisc ,Constantinos Siettosc aIstituto di Ricerche sulla Combustione, Consiglio Nazionale delle Ricerche,80125, Napoli, Italia bDepartment of Chemical Engineering Materials Environment, Sapienza Univerisy of Rome, Rome, Italy dSchool of Applied Mathematics and Physical Sciences, National Technical University of Athens, Athens,Greece lucia.russo@irc.cnr.it A computational approach for identifying efficient fuel breaks partitions for the containment of fire incidents in forests is proposed. The approach is based on the complex networks statistics, namely the centrality measures and cellular automata modeling. The efficiency of various centrality statistics, such as betweenness, closeness, Bonacich and eigenvalue centrality to select fuel breaks partitions vs. the random-based distribution is demonstrated. Two examples of increasing complexity are considered: (a) an artificial forest of randomly distributed density of vegetation, and (b) a patch from the area of Vesuvio, National Park of Campania, Italy. Both cases assume flat terrain and single type of vegetation. Simulation results over an ensemble of lattice realizations and runs show that the proposed approach appears very promising as it produces statistically significant better outcomes when compared to the random distribution approach. 1. Introduction The design of risk-management measures for the control and/or prevention of wildland fire outbreaks is of outmost importance and one of the most challenging problems in ecological modeling with serious social and economic implications (see e.g.Heymes et al, 2013). Fuel management treatments have been extensively applied at local scale, but they have a limited influence on the evolution of wildfires at large landscape scale (Finney 2001, 2003). One of the main open-problems in the area is related to the efficient spatially distribution of fire breaks that can serve as barriers in the fire spread. At large scale level, experimental work is prohibitory, and the majority of previous studies on the spatial distribution of fuel management activities have been mostly theoretical. Several studies have also evidenced that the wildland fire growth as well as the spread is strongly affected by the systematic fragmentation or fuel break partitions of the forest (Jones & Chew, 1999). For this reason, organizations like the USDA Forest Service devoted significant resources in their management plan (Loehle, 2004). The key problem is how to spatially distribute, across the landscape, the fuel management activities. Mathematical models and simulations can be thus very helpful towards this direction. Yet, due to the complexity in the phenomenon of fire spread, there is still a lack of techniques that can tackle the problem in a systematic way and with a low computational cost. Hence, most studies have been mostly empirical and/or relying to simplified models. Factors such as weather/climate conditions (wind field, air humidity and temperature), characteristics of the distributed local fuel (type and structure of the vegetation, moisture and density), landscape/earth characteristics (slope, fragmentation and natural barriers) as well as fire-suppression tactics are key elements toward this effort (Ager et al., 2010). At a small scale, previous theoretical studies on the spatial distribution of fuel managements activities have shown that a random distribution of fuel management activities reduce the spread rate of the fire when treating large portions of the landscape under study (Loehle, 2004). On the other hand, regular patterns like parallel stripes work effectively just if the fire moves perpendicular to the stripes (Ager et al., 2010). Although these approaches are very promising, just a few studies have faced the problem at the large-scale level (Alexandridis et al., 2008, 2011a,b; Russo et al., 2013, 2014). Within this context, methods coming from mathematical modeling, simulation and analysis of complex systems can thus enhance our efficiency in DOI: 10.3303/CET1543393 Please cite this article as: Russo L., Russo P., Evaggelidis I.N., Siettos C., 2015, Complex network statistics to the design of fire breaks for the control of fire spreading, Chemical Engineering Transactions, 43, 2353-2358 DOI: 10.3303/CET1543393 DOI: 10.3303/CET1543393 Please cite this article as: Russo L., Russo P., Evaggelidis I.N., Siettos C., 2015, Complex network statistics to the design of fire breaks for the control of fire spreading, Chemical Engineering Transactions, 43, 2353-2358 DOI: 10.3303/CET1543393 2353 designing better control policies, especially for disaster spread situations (Hu and Sheng, 2015). Clearly, the key element is the development of reliable models. Towards this direction, we propose a computational methodology based on complex networks and cellular automata modelling (see e.g. Alexandridis et al., 2008; Baetens et al., 2013; Lauret et al., 2014) which allow an efficient spatially distribution of fire breaks that can serve as barriers in the fire spread. The spread of the fire is considered to propagate through the links of a lattice network in a probabilistic way. The approach involves the construction of the adjacency matrix of the network whose elements are the strengths (weights) of the fire propagation. The weights of the links are computed on the basis of the underlying characteristics of the forest (e.g. density, kind of vegetation etc.). In this work, we illustrate our proposed approach through (a) a simplistic lattice configuration with randomly distributed vegetation density and a single type of vegetation, and, (b) a patch of land from the area of Vesuvio, National Park, Campania, Italy. In particular, we compare the efficiency of the so-called Bonacich (Bonacich, 1987) eigen-centrality statistic approach, which is correlated with the flow information through a network, with the random distribution benchmark approach. 2. Methodology Let us consider an area that is represented by a two dimensional grid of cells of small land patches. The shape and size of patches depend on the available precision of the underlying spatial heterogeneity. The containment of spread makes use of vegetation cutting in a percentage, say ep , of the total number of cells with vegetation. Motivated by the complex network theory, we address a systematic approach for the spatial distribution of fire breaks. Under this approach the evolution of the fire is modeled by Cellular Automata on a lattice network, say ( ), G V Ε , where { } , 1, 2, ..., kV v k N= = represents the set of vertices (or nodes) corresponding to the N grid cells and Ε = { } k lv v e is the set of edges between cells. An edge k lv v e is defined by { , }k lv v . The network is directed and weighted with i jv v be p→ = , where bp is the probability that the fire spreads from cell kv to cell .lv In this way the adjacency matrix A ,whose structure governs the underlying evolution dynamics, is constructed. The elements, klA ,are indeed the weights of the links i jv ve → whose values are provided to the Cellular Automata computations. Let us assume that the vegetation density varies in a continuous manner from 0 (corresponding to very dense vegetation) to 1 (corresponding to empty/burned cells) (in an analogy to the grayscale image representation assuming 0 for black and 1 for white). Let us denote the state of a cell { }, i j at time t as ( ) [ ]0 1ija t ∈ and also define another state, say, ( ) 1ija t = − , reflecting the burning state at time t . Then, the simulation advances from time t to time t+1 for all cells simultaneously according to the following rules: Rule 1: IF ( )ija t = -1THEN ( )1 1ija t + = This rule implies that a burning cell at the current time step t will be burned down at the next time step t+1. Rule 2: IF ( ) [ ]0 1ija t ∈ THEN: IF the state of a neighbor cell of { }, i j is -1, THEN ( )1 1ija t + = − with probability ( )1b ijp a t= − . For a von-Neumann lattice, the neighbourhood of each cell {i, j} is defined by a set of 8 cells: { } { } { } { } { } { } { } { } { }{ }, 1, , 1, , , 1 , , 1 , 1, 1 , 1, 1 , 1, 1 , 1, 1i jN i j i j i j i j i j i j i j i j= − + + + + − + − − +- - . Under this view, fire spread can be now regarded as a problem of information flow through the underlying (lattice) network. Hence, one can compute the corresponding network statistics that identify nodes that are important for the information flow in a network. In other words, it identifies those nodes that if removed from the network, then the fire spread will slow down. For the identification such “central” nodes, several measures have been proposed. The most-common used ones are the betweenness centrality (BC), the closeness centrality (CC), the degree centrality (DC), and the eigen-centrality (EC).The BC of node kv is defined as: 2354 k l m k l m v v v v l k m v v s BC s≠ ≠ =  . (1) k l m v v vs is the number of shortest paths between nodes lv and mv passing from kv , and l mv vs is the number of the shortest paths between lv and mv . The CC of node kv is defined as the inverse of the sum of geodesic distances (i.e. the shortest paths) from node kv to all other nodes in the network: 1 1 − ≠=         =  N mkm vvv mkk dCC , , (2) where mk vv d is the geodesic distance from lv to mv . The EC of node kv corresponds to the k-th component of the eigenvector related to the largest eigenvalue of the adjacency matrix A . For very large scale directed weighted networks where A is asymmetric, one can employ Arnoldi’s iterative method for extracting a low dimensional upper Hessenberg matrix whose eigenvalues provide approximations of the outermost spectrum of the full matrix. However for directed graphs, EC may not produce meaningful results. An extension of EC to directed weighted graphs comes from the Bonacich measure defined as the k-th component of (Bonacich, 1987): eIx max 1−       −= Α λ β , (3) where e is a vector of ones and maxλ is the largest eigenvalue of A (that can be computed through the Arnoldi eigensolver). Note that for 0=β , the above expression reduces to the degree centrality, while for 1=β it reduces to the standard EC. 3. Simulation Results Here we exploited the Bonacich measure for the distribution of fire breaks. In order to demonstrate the efficiency of the proposed approach two examples are considered: (a) a simplistic artificial forest on a square lattice of 50x50 cells with periodic boundary conditions, where the density of the forest is distributed randomly on the lattice using a uniform distribution in (0 1), (b) a patch of forest from the Vesuvio, National Park of Campania, Italy, processed under the assumption of flat terrain. For the simplistic artificial forest case, 100rN = realizations (ensembles) of randomly generated forests were considered and for each one of the realizations we created a corresponding distribution of fire breaks (randomly or centrality measure-based) and, finally, we run the CA model until there were no burning cells. For the case of Vesuvio area, simulations were also repeated with the same initial conditions, 100 times. The initial condition for both cases was a fire (i.e. a burning cell) at the centre of the lattice. Fire spread hazard is evaluated as a function of the density of fire breaks: ( ) ( ) = = rN i v b r f N iN N dR 1 1 , (4) where v e f N N d = is the ratio of fire breaks nodes in the lattice, that is the number of empty nodes ( eN ) respect to the total number of nodes (cells) vN that contain vegetation within the area of interest. rN denotes the number of simulations for a given initial condition, bN denotes the total number of burned cells. Significant differences for a given fd was computed by implementing the non-parametric Wilcoxon test on the rN outcomes of the simulations with a threshold set at =a 0.01. 2355 (a) (b) Figure 1. (a) A realization of the artificial forest with 50x50 cells and density created with uniform random distribution in (0 1). (b) A comparison of the risk intensity ratio ( )fR d as obtained using the proposed approach for distributing fire breaks based on the Bonacich EC criterion for β=0.2, 0.5, 0.8 vs. the random distribution tactic. The shaded area marks the region of significant differences between the EC-based and the random distribution-based outcomes (from 100 lattice realization and runs). Figure 1a shows a realization of the “artificial” forest with density distributed on 50X50 cells in a uniform random manner. Figure 1b depicts the diagram ( )fR d as obtained using the Bonacich EC with various choices of β and the one obtained by implementing the random distribution approach. For any practical means, the Bonacich EC-obtained outcomes are independent of β indicating the robustness of the criterion. As it is shown, the proposed approach performs significantly better than the random-based distribution of fire breaks. Indeed, for the centrality-based approach there is a phase transition from high to very low R s around fd ~ 0.22 while for the random-based distribution the phase transition occurs around fd ~0.36. This implicates that in order to obtain the same fire spread hazard risk of e.g. ~5%, ~25% (respectively~40%) of the vegetation has to be cut when fire breaks are distributed according to the EC measure ( for random approach). Our next example is a more realistic one. A patch of land from the area of Vesuvio National Park in Campania, Italy has been extracted from Google Earth (see Figure 2a). The image has been transformed into a grayscale image relating the levels of gray to density levels (Figure 2b). Here the probability of transmission appearing in Eq.(2) is multiplied by a factor, say, g , reflecting other parameters that influence the propagation rate. For example in an area with relatively high level of moisture in the vegetation, the fire transmission probability will be reduced ( 1g < ). For our illustrations we used 0 45.g = . Figure 3 shows the derived diagram of ( )fR d as obtained using the Bonacich EC criterion with β=0.5 vs. the random distribution way. As it is shown, the proposed approach results to a phase transition to low hazard risks at fd =0.11. For fd =0.13 only the 2.3% of the forestry on average is burned. For the same value of fd , the random distribution way results to a much higher risk (~51.6%). In order to reduce the hazard risk at the levels of 2.3%, 17% of the forestry has to be cut when this is done randomly. 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 2356 (a) (b) Figure 2. (a) A satellite image of the area in the National Park of Vesuvio, Campania, Italy. (b) The gray-scaled transformed image as processed with a size of 162x261 pixels (cells). 4. Conclusions Motivated by the arsenal that complex theory of networks offers, we propose a computational approach for the design of the spatial distribution of fire breaks for hazard management of wildland fires. The proposed approach is a two tier framework where the fire spread is considered to evolve through a (lattice) weighted network. The basis of simulations is a cellular automata model which is also used to construct the adjacency matrix of the network. The approach is demonstrated considering as examples two kind of vegetation distributions: a random one and a more realistic which is extracted by a Google map of a patch from the Vesuvio National Park, Campania, Italy. In both cases, the risk intensity factor obtained with randomly distributions of fuel breaks over the domain is significantly superior respect to the fuel breaks partitions obtained with all the centrality measures considered. 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 2357 Figure 3. Simulation results for the Vesuvio area, Campania, Italy. Comparison of the risk intensity ratio ( )fR d obtained distributing fire breaks using the proposed approach based on the Bonacich EC criterion for β=0.5 vs. the random distribution tactic. The shaded areas mark the regions of significant differences between the EC-based and the random distribution-based outcomes (from 100 lattice realization and runs). References Ager A.A., Vaillant N.M., Finney M.A., 2010, A comparison of landscape fuel treatment strategies to mitigate wildland fire risk in the urban interface and preserve old forest structure, Forest Ecology and Management, 259, 8, 1556 – 1570. Alexandridis A, Vakalis D., Siettos C.I., Bafas G. V., 2008, A Cellular Automata Model for Forest Fire Spread Prediction: The case of the Wildfire that Swept through Spetses Island in 1990, Applied Mathematics & Computation, 204, 191-201. Alexandridis A., Russo L., Vakalis D., Siettos, C.I., 2011, Simulation of wildland fires in large-scale eterogeneous environements, Chemical EngineeringTransactions, 24 , 433-438. Alexandridis A., Russo L., Vakalis D., Bafas G.V., Siettos C.I., 2011, Wildland fire spread modelling using cellular automata: Evolution in large-scale spatially heterogeneous environments under fire suppression tactics, International Journal of Wildland Fire, 20 (5) ,633-647. Baetens J.M., De Loof K., De Baets B., 2013, Influence of the topology of a cellular automaton on its dynamical properties, Communications in Nonlinear Science and Numerical Simulation, 18 (3), 651-668. Bonacich, P., 1987, Power and Centrality: A Family of Measures, American Journal of Sociology, 92, 1170–1182. Finney M.A., 2003, Calculation of fire spread rates across random landscapes, International Journal of Wildland Fire, 12, 167–174. Finney M.A., 2001, Design of regular landscape fuel treatment patterns for modifying fire growth and behaviour, Forest Sci., 47, 219–228. Heymes F., Aprin L., Ayral P.A., Slangen P., Dusserre G., 2013, Impact of wildfires on LPG tanks, Chemical Engineering Transactions, 31, 637-642. Hu Z.-H., Sheng Z.-H., 2015, Disaster spread simulation and rescue time optimization in a resource network, Information Sciences, 298, 118-135. Jones J.G., Chew J.D., 1999, Applying simulation and optimization to evaluate the effectiveness of fuel treatments for different fuel conditions at landscape scales, Proceedings of Joint Fire Science Conference and Workshop, 89–95. Lauret P., Heymes F., Aprin L., Lapébie E., Osmont A., 2014, Atmospheric turbulent dispersion modeling methods using machine learning tools, Chemical Engineering Transactions, 36, 517-522. Loehle C., 2004, Applying landscape principles to fire hazard reduction, Forest Ecology and Management, 198, 261–267. Newman, M.E.J., 2010, Networks: An Introduction. Oxford, UK: Oxford University Press. Russo L., Vakalis D., Siettos C.I., 2013, Simulating the wildfire in Rhodes in 2008 with a cellular automata model, Chemical Engineering Transactions, 35, 1399-1405. Russo L., Russo P., Vakalis D., Siettos C.I., 2014, Detecting weak points of wildland fire spread: A cellular automata model risk assessment simulation approach, Chemical Engineering Transactions, 36, 253-257. 2358