OPEN SUBJECT AREAS: COMPLEX NETWORKS PHASE TRANSITIONS AND CRITICAL PHENOMENA Localized attacks on spatially embedded networks with dependencies Yehiel Berezin1, Amir Bashan2, Michael M. Danziger1, Daqing Li3,4 & Shlomo Havlin1 1 Received 10 November 2014 Accepted 3 February 2015 Published 11 March 2015 Department of Physics, Bar Ilan University, Ramat Gan 52900, Israel, 2Channing Division of Network Medicine, Brigham and Women’s Hospital and Harvard Medical School, Boston, MA, USA, 3School of Reliability and Systems Engineering, Beihang University - Beijing 100191, China, 4Science and Technology on Reliability and Environmental Engineering Laboratory - Beijing 100191, China. Correspondence and requests for materials should be addressed to Y.B. (bereziny@gmail. com) Many real world complex systems such as critical infrastructure networks are embedded in space and their components may depend on one another to function. They are also susceptible to geographically localized damage caused by malicious attacks or natural disasters. Here, we study a general model of spatially embedded networks with dependencies under localized attacks. We develop a theoretical and numerical approach to describe and predict the effects of localized attacks on spatially embedded systems with dependencies. Surprisingly, we find that a localized attack can cause substantially more damage than an equivalent random attack. Furthermore, we find that for a broad range of parameters, systems which appear stable are in fact metastable. Though robust to random failures—even of finite fraction—if subjected to a localized attack larger than a critical size which is independent of the system size (i.e., a zero fraction), a cascading failure emerges which leads to complete system collapse. Our results demonstrate the potential high risk of localized attacks on spatially embedded network systems with dependencies and may be useful for designing more resilient systems. any modern critical infrastructures are embedded in two dimensional space1–5. Examples include ground transportation systems like road and railway networks, electrical power networks, gas and oil pipelines, water supply, the internet and communication lines. The main feature of these spatial networks is that their links represent real physical connections (connectivity links), where link length is relatively short compared to the system size. With the ongoing technological development, these systems have become more and more integrated and interdependent (via dependency links) upon each other. These dependencies lead to substantially increased vulnerability of spatial as well as non-spatial networks to random failures and even first order transitions which are characterized by the emergence of cascading failures6–21. However, failures in spatially embedded systems are often not random but geographically localized. These ‘‘localized attacks’’ can be caused by natural disasters (e.g., the 2011 Tohoku earthquake and tsunami) or malicious attacks (e.g., weapons of mass ¯ destruction). The resilience of a complex system with dependencies under attack of this sort, which we call ‘‘localized attack,’’ has not been addressed before. Even though different infrastructure systems have their own specific function and dynamics, they share a 2D spatial embedding that implies a fundamental restriction on their structure due the length limitation of connectivity and dependency links. Therefore we study here the general vulnerability of spatially embedded systems under localized attacks. We find here that localized attacks on spatially embedded systems with dependencies are significantly more damaging than random failures (see Fig. 1a), in marked contrast to single networks. Furthermore, we discover a metastable phase which spans a broad range of parameters and is qualitatively different from the stable and unstable phases known to percolation theory. In metastable systems, there exists a c critical damage size with radius rh , above which localized damage will spread and destroy the entire system and below which the damage will remain in place (see Fig. 1a and 1c). This critical size is determined solely by intensive system quantities and thus, in marked contrast to random failures, it does not scale with system size and constitutes a zero-fraction of the system in the limit of large systems (N R ‘) (Fig. 1d). To our knowledge, this is the first study to consider geographically localized attacks from the perspective of percolation theory. Previous research using percolation theory has studied the effects of attacks targeting nodes with special topological properties such as degree but not geographically correlated attacks22–25. Geographic localized attacks have been utilized to identify the most vulnerable parts of specific infrastructure networks26–28 but have not been studied in a general percolation framework. Cascading failures have been studied as the outcome of specific dynamic models: load-shedding29, binary decisions with fractional M SCIENTIFIC REPORTS | 5 : 8934 | DOI: 10.1038/srep08934 1 www.nature.com/scientificreports Figure 1 | The effect of a localized attack on a system with dependencies. (a), Propagation of local damage in a system of two interdependent diluted c lattices with spatially constrained dependency links between the lattices (only one lattice shown here). The hole on the right is above the critical size rh and c spreads throughout the system while the hole on the left is below rh and remains essentially the same size. (b), A localized circular failure of radius rh in a lattice with dependency links of length up to r. Outside the hole, the survival probability of a node increases with the distance r from the edge. The parameter rc denotes the distance from the edge of the hole at which the occupation probability is equal to the percolation threshold of a lattice without dependencies pc < 0.592736. (c), Phase diagram of a lattice with dependencies or two interdependent lattices. Depending on the average degree Ækæ and c dependency length r, the system is either stable, unstable or metastable. The circles illustrate the increase (when Ækæ increases) of the critical attack size (rh ) that leads to system collapse in the metastable region. (d), As the system size grows, the minimal number of nodes which cause the system to collapse increases linearly for random attacks but stays constant (<300) for localized attacks. This figure was obtained for a system of interdependent lattices diluted to Ækæ < 2.9 and r 5 15 (in the metastable phase-see c), with 1000 runs for each data point. thresholds30, and betweenness-based loads31,32. Recently, it was shown that a new kind of cascading failure emerges from percolation on interdependent networks12–19,33. However, these studies considered random attacks only. The unique cascading failures that we describe here have not been observed before. Indeed, they can only arise when the more realistic features of spatial embedding, dependencies and localized attacks are considered together. Though many of the models for complex systems with dependencies assume dependencies between networks, it has been shown that similar effects are present in a single network composed of connectivity and dependency links34–37. Here, we treat dependency as a general property and examine cascading failures triggered by localized attacks within a single network as well as between networks. When considering spatially embedded networks, the dimension of a network is a fundamental quantity to characterize its structure and basic physical properties39. On the basis of universality principles, all single network models with links of a characteristic length, embedded in a space of the same dimension, have the same percolation behavior38. Therefore, any 2D network with a characteristic link length belongs to the same universality class as regular lattices. When dependency links are introduced, the critical behavior is additionally determined by the length of the dependency link17. For tractability, the theory presented in this work is based on 2D lattices. However, the effects of localized attacks on systems with dependencies are expected to be the same for any system embedded in 2D SCIENTIFIC REPORTS | 5 : 8934 | DOI: 10.1038/srep08934 space as illustrated with the European power grid40 in Sup. Fig. 2 and synthetic power grids41,42 in Supplementary Figs. 1–4. We model spatially embedded systems via square lattices diluted to degree 2.5 # Ækæ # 4. The dependencies between nodes are constrained to be less than a distance r (in lattice units) and can be taken across networks or within a single network. See Methods for details of system construction. The localized geographical attack is modeled by the removal of all nodes within a distance rh from a random location in the system (see Fig. 1a–b). This triggers a cascade in which the nodes that depend on the removed nodes fail, triggering further losses as more nodes get cut off from the largest connected component. This percolative damage triggers further damage due to the dependencies between the nodes. This process is continued iteratively until no more nodes fail. At the end of this cascade, the system is categorized as functional or non-functional depending on whether a largest connected component of the order of the system size N remains or not. Results We discover that the k–r plane can be divided into three distinct phases as shown in Fig. 1c. In the stable phase, no matter how large rh is (as long as it is finite) the damage will remain localized and the system will stay intact. In the unstable phase, the system spontaneously collapses even with rh 5 0 (no localized attack). In this phase, low Ækæ and dependencies lead to the spontaneous emergence of holes which overwhelm the system. Between these phases, the system is 2 www.nature.com/scientificreports c metastable. If a hole smaller than rh is removed, the system remains c intact. However, if a hole of size §rh is removed, it will trigger a cascade which destroys the entire system. This cascade is characterized by the spread of damage from the initial localized attack throughout the system (Fig. 1a, b). This metastability is analogous to the well known supercooling property of water in which water can be cooled well below its freezing point and remain in the liquid state until a disturbance triggers crystallization of a critical size and it turns to ice44. For a system in the metastable phase under random attack, the number of nodes required to trigger system collapse increases linearly with the system size (See Fig. 1d). Therefore, as N R ‘, metastable systems are robust to the removal of O(N) nodes, as long as they are removed randomly. However, if the attack is localized, the number of nodes required remains constant (Fig. 1d) and even a zero fraction removed can trigger a cascading failure which destroys the system. Thus increasing the size of the system does not increase its resilience with respect to localized attacks. We find similar results for both interdependent networks and single networks composed of connectivity and dependency links. The results presented in the main text were obtained from interdependent networks and comparison to single networks with connectivity and dependency links is shown in Supplementary Fig. 1. c Predicting the value of rh for a given system is an important question which is treated below theoretically and numerically, with good agreement. c Simulations. We find that rh is entirely determined by the average degree Ækæ and the maximal dependency link length r. These are c intensive system quantities and therefore rh does not grow with system size (Fig. 1d). Figs. 2c and 2d show how the critical damage c size rh changes with respect to Ækæ and r for a system of size L 3 L 5 1000 3 1000. In Fig. 2c we can see that the metastable region covers a wider range of Ækæ values when r increases. In the metastable phase, c for every r, rh increases with Ækæ and jumps up dramatically at a certain Ækæ value which represents the end of the metastable phase and the beginning of the stable phase. Furthermore, we see that this jump occurs at larger Ækæ values for larger r values (Fig. 2c). In Fig. 2d, c we see that above a certain minimum value, rh has an approximately linear dependence on r in the metastable region. This is due to the fact that a larger r means that a given node’s dependency link can be located farther away. Thus the secondary damage from the localized attack is more dispersed and a larger attack size is required to initiate c a cascade. Furthermore, we find that the critical damage size rh takes a minimal value and the system is most susceptible to small local attacks when r is near the stable phase. Extensive numerical c simulations of rh over a high resolution grid of parameters Ækæ and r is shown in Fig. 2a and the theoretical prediction which is in good agreement is given in Fig. 2b. The theoretical description of the effect c of Ækæ and r on rh is presented below. dependence (with radius r and center i). Taking r as the distance from the edge of the hole, the gradient of occupation probability following an attack can be evaluated as pðr,r,rh ,hkiÞ~ps ðhkiÞ I ðrh ,r,rÞ pr2 ð1Þ where ps(Ækæ) is the occupation concentration before the attack and I(rh, r, r) is the standard formula for the area of intersection of two circles of radius r and rh with centers located a distance r 1 rh from each other. This probability describes a lattice concentration gradient in the form of an annulus of width r surrounding the removed hole, see Fig. 1b. For a given set of system parameters (r, rh, Ækæ) we can set p(r) on the LHS of Eq. (1) to pc of the lattice and solve for r. If a solution in the region of interest (0 , r , r) exists, it corresponds to a distance rc at which the lattice concentration will be equal to its critical value. The existence of such a point is a necessary but not sufficient condition for the hole to propagate. Below pc, the network forms clusters with a characteristic size j,(p), which diverges at pc, where j,(p) is the connectedness correlation length for p , pc38,45. Hence the sufficient condition for damage propagation is that the critical region 0 , r , rc be wide enough for clusters of size j,(p) to form and break away. The value of j,(p) is determined by the underlying topology and can thus be calculated from the percolation problem on a lattice without dependencies using an appropriate estimation for p in the 0 , r , rc region. From Eq. (1), p(r) increases monotonically over this region and an accurate evaluation solution for j, would require treating the full gradient percolation problem46. In this work, for simplicity we assume p~ which is the average of p(r) over the p region of interest. Additionally, the removal of the hole causes secondary damage due to dependencies in the annulus and the concentration of the gradient is decreased by a factor of g(r) which we calculate numerically and find to vary monotonically from 0.85 to ð rc 0.89 as a function of r. We can thereby estimate