Abstract
Determining design principles that boost the robustness of interdependent networks is a fundamental question of engineering, economics, and biology. It is known that maximizing the degree correlation between replicas of the same node leads to optimal robustness. Here we show that increased robustness might also come at the expense of introducing multiple phase transitions. These results reveal yet another possible source of fragility of multiplex networks that has to be taken into the account during network optimization and design.
| Original language | English |
|---|---|
| Article number | 020301(R) |
| Pages (from-to) | 1-7 |
| Journal | Physical Review E |
| Volume | 100 |
| Issue number | 2 |
| DOIs | |
| Publication status | Published - 15 Aug 2019 |
Funding
https://orcid.org/0000-0002-3964-2196 Kryven Ivan * Mathematical Institute, Utrecht University , P.O. Box 80010, 3508 TA Utrecht, The Netherlands Bianconi Ginestra School of Mathematical Sciences, Queen Mary University of London , London, E1 4NS, United Kingdom The Alan Turing Institute , the British Library, London NW1 2DB, United Kingdom * Corresponding author: [email protected] 15 August 2019 August 2019 100 2 020301 1 March 2019 17 July 2019 ©2019 American Physical Society 2019 American Physical Society Determining design principles that boost the robustness of interdependent networks is a fundamental question of engineering, economics, and biology. It is known that maximizing the degree correlation between replicas of the same node leads to optimal robustness. Here we show that increased robustness might also come at the expense of introducing multiple phase transitions. These results reveal yet another possible source of fragility of multiplex networks that has to be taken into the account during network optimization and design. Nederlandse Organisatie voor Wetenschappelijk Onderzoek 10.13039/501100003246 639.071.511 Multilayer networks [1–3] formed by several interacting layers have emerged as a powerful framework to analyze a variety of complex systems, including such classical examples as global infrastructures, economic networks, temporal networks, and the multilevel structure of the brain. Other disciplines, such as material science and chemical synthesis, are on the way to adopt the network science toolbox, less for analysis purposes, than for its potential for optimization and rational design [4–8] . Therefore, predicting the robustness of multilayer networks [9–11] , assessing the risk of large avalanches of failures [9–15] , and designing robust multilayer architectures [16–18] are the key theoretical questions entailing implications for engineering, economics, and biology. Recent works on percolation in multilayer networks revealed that the correlation between intralayer degrees of replica nodes [16,17] and link overlap [19–21] have profound consequences in determining the response of a multiplex network to random damage. The case of positive interlayer degree correlation [1,16] , when a hub node in one layer is likely to be interdependent on a hub node in another layer, is known to increase the robustness of interdependent multiplex networks. It is widely believed that maximizing the interlayer degree correlation is a good design principle for building robust infrastructures. The network optimization is used not only for engineered networks and infrastructures [22–27] but also for economic [28] and biological networks [29,30] . Therefore, it is of fundamental importance to understand how maximizing the interlayer degree correlation may affect the properties of multiplex networks. In this Rapid Communication we demonstrate that such an optimization strategy might come at a cost: unexpectedly, multiplex networks with strong intralayer degree correlations may be prone to multiple percolation transitions. Several works already showed that percolation processes on interdependent networks may be associated with multiple phase transitions [31–35] . For instance, when an interdependent multilayer network is drawn from the configuration model, percolation may lead to multiple discontinuous and hybrid transitions due to a successive deactivation of different layers at different values of the percolation parameter [31] . A similar effect is also seen in classical percolation as it can display multiple phase transitions corresponding to deactivation of one or several layers at a time [32,35] . Nevertheless, these phase transitions are continuous and second order. Here we show that interdependent multiplex networks may be decomposed during percolation by multiple discontinuous phase transitions into submultiplexes that, contrary to previous observations, span across all layers. Let P ( k , B ) be the joint probability that a randomly chosen node has degree k in every layer and activity B , i.e., it is dependent on B − 1 replicas in other layers. We identify three classes of such multiplex networks: (1) multiplex networks with multimodal degree distribution and a node's replicas having identical degrees in all layers, therefore featuring pairwise degree correlation one, (2) regular multiplex networks with all nodes having identical degrees and multimodal activity distribution, and (3) multiplex networks with a multimodal joint degree-activity distribution and identical degrees of a node's replicas. In this Rapid Communication multiplex networks are modeled by the maximum-entropy ensemble preserving the degree-activity distribution P ( k , B ) , and therefore, as explained in Appendix A , size S of the MCGC is found by solving the following equations: (1) S = p ∑ k , B > 0 P ( k , B ) [ 1 − ( 1 − s ) k ] B , where p is the probability that the edge is present and s is the fixed point of s = p ∑ k , B > 0 k 〈 k 〉 P ( k , B ) [ 1 − ( 1 − s ) k − 1 ] [ 1 − ( 1 − s ) k ] B − 1 . Interdependent percolation can also be interpreted as the steady state of an interdependent epidemic spreading process [1,11,36,37] in which each node must have at least one infected neighbor in each layer to become infected. Under this interpretation, the discontinuous phase transitions can be interpreted as a successive abrupt invasion of different submultiplexes by an epidemic. Constant activity and multimodal degree distribution. Consider a multiplex network in which all nodes have the same activity B = M and the intralayer degrees are distributed according to the degree distribution P ̂ ( k ) . The degree-activity distribution is then given by (2) P ( k , B ) = δ B , M P ̂ ( k ) , where δ a , b is the Kronecker's delta. Let the intralayer degree distribution be multimodal, as defined by (3) P ̂ ( k ) = c 1 δ k , k 1 + c 2 δ k , k 2 + c 3 δ k , k 3 , where the normalization condition imposes the constraint c 1 + c 2 + c 3 = 1 . We refer to all combinations of c 1 , c 2 , c 3 ∈ [ 0 , 1 ] that satisfy the above-mentioned normalization condition as the phase space of the model (2) . Note that even though we have three parameters to choose, there are only two degrees of freedom. Networks satisfying Eq. (2) arise as a result of top-down design [23–27] and appear in temporal network frameworks [38] . In what follows, we report the existence of peculiar domains in the phase space, Ω i , j ⊂ { ( c 1 , c 2 , c 3 ) : c 1 , c 2 , c 3 ∈ [ 0 , 1 ] } , at which, generally speaking, the percolation process features i continuous and j discontinuous phase transitions. When the multiplex network is defined by Eq. (3) , and as long as the degrees k 1 , k 2 , and k 3 are sufficiently distant and the number of layers M is sufficiently large, one observes up to three discontinuous phase transitions, that is, i = 0 and j = 1 , 2 , 3 . The phase diagram of such model can be represented by using the barycentric coordinate system in which each point has coordinates ( c 1 , c 2 , c 3 ) . By studying the critical behavior of Eq. (1) for this choice of the degree distribution, we identify three distinct domains in the phase diagram as indicated by Ω 01 , Ω 02 , and Ω 03 (see Fig. 1 ). Each of the discontinuous phase transitions corresponds to progressive deactivation of distinct submultiplexes. Both theoretical predictions and simulations of the percolation process [see Figs. 2(a) – 2(c) ] show that these phase transitions correspond to the deactivation of the nodes in the order of their increasing intralayer degrees. The nodes that are damaged first are the nodes with the lowest intralayer degree, then the nodes with the second-lowest value of the intralayer degree are damaged, and finally, also the nodes with the largest intralayer degree fail. Conversely, in the epidemic spreading interpretation of the interdependent percolation, these transitions correspond to an abrupt successive invasion of the epidemics into different submultiplexes. Therefore, these three transitions can be revealed by monitoring the order parameters σ k indicating the fraction of nodes that have intralayer degree k and that belong to the MCGC as a function of p [see Figs. 2(a) – 2(c) ]. 10.1103/PhysRevE.100.020301.f1 1 FIG. 1. The phase diagram for interdependent percolation in multiplex networks with degree-activity distribution P ( k , B ) = δ B , 20 P ̂ ( k ) , and P ̂ ( k ) = c 1 δ k , 3 + c 2 δ k , 9 + c 3 δ k , 30 is depicted with a barycentric plot featuring domains Ω i j with i continuous and j discontinuous phase transitions. Panels: The fraction S of nodes in the Mutually connected giant component (MCGC) for the points A , B , C , D , of barycentric coordinates ( c 1 , c 2 , c 3 ): A = ( 0.095 , 0.095 , 0.810 ) ; B = ( 0.87 , 0.04 , 0.09 ) ; C = ( 0.75 , 0.2 , 0.05 ) , and D = ( 0.73 , 0.20 , 0.065 ) . The dashed lines indicate the unstable branch and the vertical guidelines indicate the predicted positions of the discontinuous phase transitions. 10.1103/PhysRevE.100.020301.f2 2 FIG. 2. Evolution of the size and structure of MCGC during interdependent percolation. (a)–(c) Theoretical predictions (solid lines) and simulation results (dots) for size S of MCGC and the fraction σ k of nodes that have intralayer degree k are plotted at different points of the phase diagram from Fig. 1 : C , panel (a); B , panel (b); and A , panel (c). (d)–(f) The fractions S of nodes in the MCGC (solid lines) are compared against the randomized network in which replica degrees are independent random variables (RVs) (dashed lines) and shown at different points from the phase diagram: C , panel (d); B , panel (e); and A , panel (f). The simulations in panels (a)–(c) are averaged over 20 realizations of networks with 10 5 nodes and M = 20 layers. In order to investigate the effect of the interlayer degree correlations, we have considered a multiplex network in the region Ω 03 that features three discontinuous phase transitions and compared the robustness of this network with the robustness of a null model, which is formed by a multiplex network having independent degrees of replica nodes, as explained in Appendix B . As can be seen in Figs. 2(d) – 2(f) , the multiplex networks with identical replica degrees are more robust than the null model, i.e., for every value of p they have a larger MCGC, which was also reported in Ref. [16] . However, such an optimization induces two additional discontinuous phase transitions that are not observable in the null model. Therefore, we conclude that optimization of network robustness by maximizing the interlayer degree correlations might come at the expense of inducing additional discontinuous phase transitions. The decomposition of the studied multiplex networks into submultiplexes indicates that having multiple modes in the degree distribution is necessary to maintain multiple phase transitions. The presence of multiple phase transitions is strongly favored by the multimodality of the degree distribution. Figure 3 applies a series of the Gaussian window filters (i.e., discrete convolution with a Gaussian function) with progressively increasing standard deviation to reduce the segregation between the peaks in the case from Ω 03 and shows that, as the peaks merge, the corresponding discontinuous phase transitions disappear. Overall, the investigations presented in this Rapid Communication suggest that a large number of layers, segregated multimodal degree distribution, and identical degrees of nodes' replicas jointly provide sufficient conditions for the presence of multiple discontinuous phase transitions in percolation of interdependent multiplex networks. Variable activity and constant intralayer degree. In the previous paragraphs we showed that a multimodal degree distribution can lead to multiple percolation transitions in multiplex networks with identical intralayer degrees of nodes' replicas and the identical activity B = M of each node of the multiplex networks, in which case, the distribution P ( k , B ) is given by Eq. (2) . Here we consider the other extreme case in which P ( k , B ) corresponds to a multiplex network in which all nodes have the same intralayer degree k 0 , and the multimodal activity distribution P ̃ ( B ) : (4) P ( k , B ) = δ k , k 0 P ̃ ( B ) , where (5) P ̃ ( B ) = c 1 δ B , B 1 + c 2 δ B , B 2 + c 3 δ B , B 3 , and c 1 + c 2 + c 3 = 1 . Also in this scenario, we observe that if the modes of the activity distribution P ̃ ( B ) are well separated, the interdependent percolation may again result in multiple phase transitions. These phase transitions correspond to the decomposition of the multiplex network into submultiplexes having nodes with activity lower or equal to a given threshold. If all activities are greater than one, B n > 1 for n = 1 , 2 , 3 , the interdependent percolation features up to three discontinuous phase transitions. In this case the phase diagram contains three regions denoted as Ω 01 , Ω 02 , and Ω 03 indicating that there are zero continuous and one, two, or three discontinuous transitions, respectively. However, if we set B 1 = 1 the network may also display one continuous and up to two discontinuous phase transitions. Therefore, in this case, as shown in Fig. 4 , we have four possible domains. 10.1103/PhysRevE.100.020301.f3 3 FIG. 3. The influence of multimodality of degree distributions on the number of phase transitions. Three examples of degree distributions given by P ( k , B ) = δ B , 20 P ̂ ′ ( k ) are shown together with the analytically obtained fraction S of nodes in the MCGC. Distributions P ̂ ′ ( k ) are obtained by applying Gaussian filters to P ̂ ( k ) = c 1 δ k , 3 + c 2 δ k , 9 + c 3 δ k , 30 with ( c 1 , c 2 , c 3 ) = ( 0.75 , 0.2 , 0.05 ) . Case (a) depicts the unmodified P ̂ ( k ) distribution; cases (b) and (c) are obtained by applying the Gaussian window filter with standard deviation σ = 0.55 and σ = 1.1 , respectively. 10.1103/PhysRevE.100.020301.f4 4 FIG. 4. The phase diagram for interdependent percolation in a regular multiplex network defined by degree distribution P ( k , B ) = δ k , 3 P ̃ ( B ) , P ̃ ( k ) = c 1 δ B , 1 + c 2 δ B , 2 + c 3 δ B , 30 . The barycentric plot features domains Ω i j with i continuous and j discontinuous phase transitions. Panels: The fraction S of nodes in the MCGC for points A , B , C , D , and E having the barycentric coordinates ( c 1 , c 2 , c 3 ) : A = ( 0.85 , 0.06 , 0.09 ) , B = ( 0.33 , 0.33 , 0.33 ) , C = ( 0.68 , 0.04 , 0.28 ) , D = ( 0.6 , 0.16 , 0.24 ) , and the shared accumulation point E = ( 0.70 , 0.11 , 0.18 ) . Correlated intralayer degree and activity. Consider a scenario in which a node's degree and activity correlate: (6) P ( k , B ) = c 1 δ k , k 1 δ B , B 1 + c 2 δ k , k 2 δ B , B 2 + c 3 δ k , k 3 δ B , B 3 , and thus neither B 1 , B 2 , B 3 nor k 1 , k 2 , k 3 are triplets of identical numbers. As shown in Fig. 5 , also in this case we see a rich phase diagram including phases Ω 10 , Ω 01 , Ω 11 , and Ω 02 having the same definition as above. To assess the effect of anticorrelations between activity and intralayer degree, the robustness of multiplex networks can be compared against the null model presented in Appendix B , in which the intralayer degrees and activity are independent. The intuition is that anticorrelations between activity and degree will enhance the robustness of the network as the hubs of each layer are less prone to failure than in the null model due to the fact that they are interdependent with a smaller number of layers; we call these nodes superrobust nodes (SRNs). Indeed, in these networks p c is typically lower than in the null model. However anticorrelations also reduce the fragility of low degree nodes by associating to them high activity values; we call these nodes superfragile nodes (SFNs). Therefore intralayer degree-activity correlation may lead to both increased and reduced robustness of the multiplex network monitored by measuring the fraction of nodes S in the MCGC depending on the region of the phase diagram and the exact value of percolation parameter p (see Fig. 5 ). For large values of p the percolation process on a multiplex network with degree-activity anticorrelation efficiently dismantles the submultiplex formed by the SFN leading to a reduced value of S with respect to the null model. At small p either the network is totally dismantled (see, for instance, point C in Fig. 5 ) or the anticorrelated multiplex network is formed by a large percentage SRN leading to an increased value of S and a smaller value of p c . 10.1103/PhysRevE.100.020301.f5 5 FIG. 5. Barycentric plot: The phase diagram for interdependent percolation in the multiplex network with the degree-activity distribution given by P ( k , B ) = c 1 δ k , 5 δ B , 1 + c 2 δ k , 4 δ B , 2 + c 3 δ k , 3 δ B , 30 . Panels: Comparison of the MCGC size S versus the randomized null model at the points A , B , C , D , and E having coordinates ( c 1 , c 2 , c 3 ) : A = ( 0.62 , 0.10 , 0.28 ) , B = ( 0.36 , 0.08 , 0.56 ) , C = ( 0.1 , 0.2 , 0.7 ) , D = ( 0.32 , 0.48 , 0.2 ) , and E = ( 0.22 , 0.30 , 0.48 ) . The effect of number of layers. The above-mentioned examples consider only degree-activity distributions with three modes; however, other modes may also lead to more numerous discontinuous phase transitions reminiscent of cascades in the Barkhausen effect [39] . Figures 6(a) and 6(b) show that when multiple phase transitions are present, these phase transitions can be removed by reducing the number of layers. In which case the jump discontinuity that corresponds to the largest value of p c is first to vanish, and eventually, all discontinuous transitions disappear. Our results show that interdependent percolation and thus the corresponding interdependent epidemic spreading process defined on multiplex networks with many layers cannot always be effectively approximated with just a few layers. For instance, Figs. 6(a) and 6(b) provide examples of a qualitative change of the percolation properties that are associated to a small change in the number of layers (i.e., increment or decrement by one) even if the total number of layers is large. 10.1103/PhysRevE.100.020301.f6 6 FIG. 6. The effect of the number of layers on network robustness. The size of MCGC S in a network with joint degree-activity distributions given by (a) P ( k , B ) = δ B , M P ̂ ( k ) , P ̂ ( k ) = c 1 δ k , 3 + c 2 δ k , 9 + c 3 δ k , 30 with ( c 1 , c 2 , c 3 ) = ( 0.75 , 0.2 , 0.05 ) , and (b) P ( k , B ) = δ B , M ( c 1 δ k , 3 1 + c 2 δ k , 3 2 + c 3 δ k , 3 3 + c 4 δ k , 3 4 + c 5 δ k , 3 5 + c 6 δ k , 3 6 where ( c 1 , c 2 , c 3 , c 4 , c 5 , c 6 ) = ( 0.5718 , 0.3049 , 0.0953 , 0.0210 , 0.0057 , 0.0013 ) . The numbers of layers M are indicated in the legends. In this work we have shown evidence of an unexpected outcome of interdependent percolation on multiplex networks. We showed that multiplex networks with maximum interlayer degree correlations that were designed to minimize p c can also display multiple discontinuous phase transitions corresponding to the successive dismantling of submultiplexes that span across all the layers of the network. Therefore, although setting all degrees of a node's replicas to be identical does yield optimally robust multilayer networks (as this operation minimizes p c ), such an increased robustness might come at the expense of introducing a series of discontinuous phase transitions. This result shows that in the large variety of contexts, when this type of optimization principle might be at work, including engineering, economics, and biological networks, constrained or multiobjective optimization [40,41] should be adopted to avoid multiple discontinuous phase transitions. Another aspect of this study is the demonstration that even in multiplex networks with a large number of layers, removing even one layer may lead to a qualitative change in the percolation behavior as the number of phase transitions may change. Many real networks do naturally admit a multilayer representation in which the number of layers is large or even tends to infinity. Examples include airport networks [42,43] , trade networks [44] , social networks [43] , and temporal networks [38,45,46] wherein layers represent time. This study shows that it is not always possible to approximate such networks with multiplexes having a smaller number of layers while still preserving the qualitative structure of the phase space. Acknowledgments. I.K. acknowledges the kind hospitality of the School of Mathematical Sciences at QMUL and the funding from Netherlands Organisation for Scientific Research through the Veni scheme, Project No. 639.071.511. APPENDIX A: