1
|
Meng Y, Lai YC, Grebogi C. The fundamental benefits of multiplexity in ecological networks. J R Soc Interface 2022; 19:20220438. [PMID: 36167085 PMCID: PMC9514891 DOI: 10.1098/rsif.2022.0438] [Citation(s) in RCA: 2] [Impact Index Per Article: 1.0] [Reference Citation Analysis] [Abstract] [Key Words] [MESH Headings] [Grants] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 06/13/2022] [Accepted: 09/01/2022] [Indexed: 11/12/2022] Open
Abstract
A tipping point presents perhaps the single most significant threat to an ecological system as it can lead to abrupt species extinction on a massive scale. Climate changes leading to the species decay parameter drifts can drive various ecological systems towards a tipping point. We investigate the tipping-point dynamics in multi-layer ecological networks supported by mutualism. We unveil a natural mechanism by which the occurrence of tipping points can be delayed by multiplexity that broadly describes the diversity of the species abundances, the complexity of the interspecific relationships, and the topology of linkages in ecological networks. For a double-layer system of pollinators and plants, coupling between the network layers occurs when there is dispersal of pollinator species. Multiplexity emerges as the dispersing species establish their presence in the destination layer and have a simultaneous presence in both. We demonstrate that the new mutualistic links induced by the dispersing species with the residence species have fundamental benefits to the well-being of the ecosystem in delaying the tipping point and facilitating species recovery. Articulating and implementing control mechanisms to induce multiplexity can thus help sustain certain types of ecosystems that are in danger of extinction as the result of environmental changes.
Collapse
Affiliation(s)
- Yu Meng
- Institute for Complex Systems and Mathematical Biology, School of Natural and Computing Sciences, King’s College, University of Aberdeen, AB24 3UE, UK
- Max Planck Institute for the Physics of Complex Systems, Nöthnitzer Straße 38, Dresden 01187, Germany
- Center for Systems Biology Dresden, Pfotenhauerstraße 108, Dresden 01307, Germany
| | - Ying-Cheng Lai
- School of Electrical, Computer and Energy Engineering, Arizona State University, Tempe, AZ 85287, USA
- Department of Physics, Arizona State University, Tempe, AZ 85287, USA
| | - Celso Grebogi
- Institute for Complex Systems and Mathematical Biology, School of Natural and Computing Sciences, King’s College, University of Aberdeen, AB24 3UE, UK
| |
Collapse
|
2
|
Kim JH, Goh KI. K-selective percolation: A simple model leading to a rich repertoire of phase transitions. CHAOS (WOODBURY, N.Y.) 2022; 32:023115. [PMID: 35232055 DOI: 10.1063/5.0081253] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 12/08/2021] [Accepted: 01/19/2022] [Indexed: 06/14/2023]
Abstract
We propose a K-selective percolation process as a model for iterative removals of nodes with a specific intermediate degree in complex networks. In the model, a random node with degree K is deactivated one by one until no more nodes with degree K remain. The non-monotonic response of the giant component size on various synthetic and real-world networks implies a conclusion that a network can be more robust against such a selective attack by removing further edges. From a theoretical perspective, the K-selective percolation process exhibits a rich repertoire of phase transitions, including double transitions of hybrid and continuous, as well as reentrant transitions. Notably, we observe a tricritical-like point on Erdős-Rényi networks. We also examine a discontinuous transition with unusual order parameter fluctuation and distribution on simple cubic lattices, which does not appear in other percolation models with cascade processes. Finally, we perform finite-size scaling analysis to obtain critical exponents on various transition points, including those exotic ones.
Collapse
Affiliation(s)
- Jung-Ho Kim
- Department of Physics, Korea University, Seoul 02841, South Korea
| | - K-I Goh
- Department of Physics, Korea University, Seoul 02841, South Korea
| |
Collapse
|
3
|
Dong S, Wang H, Mostafavi A, Gao J. Robust component: a robustness measure that incorporates access to critical facilities under disruptions. J R Soc Interface 2019; 16:20190149. [PMID: 31387488 PMCID: PMC6731514 DOI: 10.1098/rsif.2019.0149] [Citation(s) in RCA: 27] [Impact Index Per Article: 5.4] [Reference Citation Analysis] [Abstract] [Key Words] [MESH Headings] [Grants] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 03/05/2019] [Accepted: 06/27/2019] [Indexed: 11/12/2022] Open
Abstract
The objective of this paper is to integrate the post-disaster network access to critical facilities into the network robustness assessment, considering the geographical exposure of infrastructure to natural hazards. Conventional percolation modelling that uses generating function to measure network robustness fails to characterize spatial networks due to the degree correlation. In addition, the giant component alone is not sufficient to represent the performance of transportation networks in the post-disaster setting, especially in terms of the access to critical facilities (i.e. emergency services). Furthermore, the failure probability of various links in the face of different hazards needs to be encapsulated in simulation. To bridge this gap, this paper proposed the metric robust component and a probabilistic link-removal strategy to assess network robustness through a percolation-based simulation framework. A case study has been conducted on the Portland Metro road network during an M9.0 earthquake scenario. The results revealed how the number of critical facilities severely impacts network robustness. Besides, earthquake-induced failures led to a two-phase percolation transition in robustness performance. The proposed robust component metric and simulation scheme can be generalized into a wide range of scenarios, thus enabling engineers to pinpoint the impact of disastrous disruption on network robustness. This research can also be generalized to identify critical facilities and sites for future development.
Collapse
Affiliation(s)
- Shangjia Dong
- School of Civil and Construction Engineering, Oregon State University, Corvallis, OR 97331, USA
| | - Haizhong Wang
- School of Civil and Construction Engineering, Oregon State University, Corvallis, OR 97331, USA
| | - Ali Mostafavi
- Zachry Department of Civil Engineering, Texas A&M University, College Station, TX 77840, USA
| | - Jianxi Gao
- Department of Computer Science, Rensselaer Polytechnic Institute, Lally Hall 207, Troy, NY 12180, USA
| |
Collapse
|
4
|
Kryven I. Bond percolation in coloured and multiplex networks. Nat Commun 2019; 10:404. [PMID: 30679430 PMCID: PMC6345799 DOI: 10.1038/s41467-018-08009-9] [Citation(s) in RCA: 20] [Impact Index Per Article: 4.0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 06/27/2018] [Accepted: 12/10/2018] [Indexed: 11/09/2022] Open
Abstract
Percolation in complex networks is a process that mimics network degradation and a tool that reveals peculiarities of the network structure. During the course of percolation, the emergent properties of networks undergo non-trivial transformations, which include a phase transition in the connectivity, and in some special cases, multiple phase transitions. Such global transformations are caused by only subtle changes in the degree distribution, which locally describe the network. Here we establish a generic analytic theory that describes how structure and sizes of all connected components in the network are affected by simple and colour-dependent bond percolations. This theory predicts locations of the phase transitions, existence of wide critical regimes that do not vanish in the thermodynamic limit, and a phenomenon of colour switching in small components. These results may be used to design percolation-like processes, optimise network response to percolation, and detect subtle signals preceding network collapse. Percolation is a tool used to investigate a network’s response as random links are removed. Here the author presents a generic analytic theory to describe how percolation properties are affected in coloured networks, where the colour can represent a network feature such as multiplexity or the belonging to a community.
Collapse
Affiliation(s)
- Ivan Kryven
- Van't Hoff Institute for Molecular Sciences, University of Amsterdam, PO Box 94157, 1090 GD, Amsterdam, The Netherlands.
| |
Collapse
|
5
|
Shu P, Liu QH, Wang S, Wang W. Social contagions on interconnected networks of heterogeneous populations. CHAOS (WOODBURY, N.Y.) 2018; 28:113114. [PMID: 30501222 DOI: 10.1063/1.5042677] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 06/03/2018] [Accepted: 10/26/2018] [Indexed: 06/09/2023]
Abstract
Recently, the dynamics of social contagions ranging from the adoption of a new product to the diffusion of a rumor have attracted more and more attention from researchers. However, the combined effects of individual's heterogenous adoption behavior and the interconnected structure on the social contagions processes have yet to be understood deeply. In this paper, we study theoretically and numerically the social contagions with heterogeneous adoption threshold in interconnected networks. We first develop a generalized edge-based compartmental approach to predict the evolution of social contagion dynamics on interconnected networks. Both the theoretical predictions and numerical results show that the growth of the final recovered fraction with the intralayer propagation rate displays double transitions. When increasing the initial adopted proportion or the adopted threshold, the first transition remains continuous within different dynamic parameters, but the second transition gradually vanishes. When decreasing the interlayer propagation rate, the change in the double transitions mentioned above is also observed. The heterogeneity of degree distribution does not affect the type of first transition, but increasing the heterogeneity of degree distribution results in the type change of the second transition from discontinuous to continuous. The consistency between the theoretical predictions and numerical results confirms the validity of our proposed analytical approach.
Collapse
Affiliation(s)
- Panpan Shu
- Xi'an University of Technology, Xi'an 710054, China
| | - Quan-Hui Liu
- Big Data Research Center,University of Electronic Science and Technology of China, Chengdu 610054, China
| | | | - Wei Wang
- Cybersecurity Research Institute, Sichuan University, Chengdu 610065, China
| |
Collapse
|
6
|
Choi W, Lee D, Kertész J, Kahng B. Two golden times in two-step contagion models: A nonlinear map approach. Phys Rev E 2018; 98:012311. [PMID: 30110730 PMCID: PMC7217535 DOI: 10.1103/physreve.98.012311] [Citation(s) in RCA: 7] [Impact Index Per Article: 1.2] [Reference Citation Analysis] [Abstract] [MESH Headings] [Grants] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 06/27/2017] [Indexed: 11/07/2022]
Abstract
The two-step contagion model is a simple toy model for understanding pandemic outbreaks that occur in the real world. The model takes into account that a susceptible person either gets immediately infected or weakened when getting into contact with an infectious one. As the number of weakened people increases, they eventually can become infected in a short time period and a pandemic outbreak occurs. The time required to reach such a pandemic outbreak allows for intervention and is often called golden time. Understanding the size-dependence of the golden time is useful for controlling pandemic outbreak. Using an approach based on a nonlinear mapping, here we find that there exist two types of golden times in the two-step contagion model, which scale as O(N^{1/3}) and O(N^{ζ}) with the system size N on Erdős-Rényi networks, where the measured ζ is slightly larger than 1/4. They are distinguished by the initial number of infected nodes, o(N) and O(N), respectively. While the exponent 1/3 of the N-dependence of the golden time is universal even in other models showing discontinuous transitions induced by cascading dynamics, the measured ζ exponents are all close to 1/4 but show model-dependence. It remains open whether or not ζ reduces to 1/4 in the asymptotically large-N limit. Our method can be applied to several models showing a hybrid percolation transition and gives insight into the origin of the two golden times.
Collapse
Affiliation(s)
- Wonjun Choi
- CCSS, CTP and Department of Physics and Astronomy, Seoul National University, Seoul 08826, Korea
| | - Deokjae Lee
- CCSS, CTP and Department of Physics and Astronomy, Seoul National University, Seoul 08826, Korea
| | - J Kertész
- Center for Network Science, Central European University, H-1051, Budapest, Hungary
- Department of Theoretical Physics, Budapest University of Technology and Economics, H-1111, Budapest, Hungary
| | - B Kahng
- CCSS, CTP and Department of Physics and Astronomy, Seoul National University, Seoul 08826, Korea
| |
Collapse
|
7
|
Min B, Zheng M. Correlated network of networks enhances robustness against catastrophic failures. PLoS One 2018; 13:e0195539. [PMID: 29668730 PMCID: PMC5905981 DOI: 10.1371/journal.pone.0195539] [Citation(s) in RCA: 18] [Impact Index Per Article: 3.0] [Reference Citation Analysis] [Abstract] [MESH Headings] [Grants] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 11/14/2017] [Accepted: 03/23/2018] [Indexed: 12/03/2022] Open
Abstract
Networks in nature rarely function in isolation but instead interact with one another with a form of a network of networks (NoN). A network of networks with interdependency between distinct networks contains instability of abrupt collapse related to the global rule of activation. As a remedy of the collapse instability, here we investigate a model of correlated NoN. We find that the collapse instability can be removed when hubs provide the majority of interconnections and interconnections are convergent between hubs. Thus, our study identifies a stable structure of correlated NoN against catastrophic failures. Our result further suggests a plausible way to enhance network robustness by manipulating connection patterns, along with other methods such as controlling the state of node based on a local rule.
Collapse
Affiliation(s)
- Byungjoon Min
- Department of Physics, Chungbuk National University, Cheongju, Chungbuk 28644, Korea
- Levich Institute and Physics Department, City College of New York, New York, New York 10031, United States of America
- * E-mail:
| | - Muhua Zheng
- Levich Institute and Physics Department, City College of New York, New York, New York 10031, United States of America
- Department of Physics, East China Normal University, Shanghai, 200062, China
| |
Collapse
|
8
|
Liu RR, Eisenberg DA, Seager TP, Lai YC. The "weak" interdependence of infrastructure systems produces mixed percolation transitions in multilayer networks. Sci Rep 2018; 8:2111. [PMID: 29391411 PMCID: PMC5794991 DOI: 10.1038/s41598-018-20019-7] [Citation(s) in RCA: 37] [Impact Index Per Article: 6.2] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 10/11/2017] [Accepted: 01/09/2018] [Indexed: 11/25/2022] Open
Abstract
Previous studies of multilayer network robustness model cascading failures via a node-to-node percolation process that assumes "strong" interdependence across layers-once a node in any layer fails, its neighbors in other layers fail immediately and completely with all links removed. This assumption is not true of real interdependent infrastructures that have emergency procedures to buffer against cascades. In this work, we consider a node-to-link failure propagation mechanism and establish "weak" interdependence across layers via a tolerance parameter α which quantifies the likelihood that a node survives when one of its interdependent neighbors fails. Analytical and numerical results show that weak interdependence produces a striking phenomenon: layers at different positions within the multilayer system experience distinct percolation transitions. Especially, layers with high super degree values percolate in an abrupt manner, while those with low super degree values exhibit both continuous and discontinuous transitions. This novel phenomenon we call mixed percolation transitions has significant implications for network robustness. Previous results that do not consider cascade tolerance and layer super degree may be under- or over-estimating the vulnerability of real systems. Moreover, our model reveals how nodal protection activities influence failure dynamics in interdependent, multilayer systems.
Collapse
Affiliation(s)
- Run-Ran Liu
- Alibaba Research Center for Complexity Sciences, Hangzhou Normal University, Hangzhou, Zhejiang, 311121, China.
- School of Electrical, Computer, and Energy Engineering, Arizona State University, Tempe, AZ, 85287, USA.
| | - Daniel A Eisenberg
- School of Sustainable Engineering and Built Environment, Arizona State University, Tempe, AZ, 85287, USA
| | - Thomas P Seager
- School of Sustainable Engineering and Built Environment, Arizona State University, Tempe, AZ, 85287, USA
| | - Ying-Cheng Lai
- School of Electrical, Computer, and Energy Engineering, Arizona State University, Tempe, AZ, 85287, USA
- Department of Physics, Arizona State University, Tempe, AZ, 85287, USA
| |
Collapse
|
9
|
Yubero P, Manrubia S, Aguirre J. The space of genotypes is a network of networks: implications for evolutionary and extinction dynamics. Sci Rep 2017; 7:13813. [PMID: 29062002 PMCID: PMC5653773 DOI: 10.1038/s41598-017-14048-x] [Citation(s) in RCA: 10] [Impact Index Per Article: 1.4] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 07/31/2017] [Accepted: 10/04/2017] [Indexed: 11/09/2022] Open
Abstract
The forcing that environmental variation exerts on populations causes continuous changes with only two possible evolutionary outcomes: adaptation or extinction. Here we address this topic by studying the transient dynamics of populations on complex fitness landscapes. There are three important features of realistic landscapes of relevance in the evolutionary process: fitness landscapes are rough but correlated, their fitness values depend on the current environment, and many (often most) genotypes do not yield viable phenotypes. We capture these properties by defining time-varying, holey, NK fitness landscapes. We show that the structure of the space of genotypes so generated is that of a network of networks: in a sufficiently holey landscape, populations are temporarily stuck in local networks of genotypes. Sudden jumps to neighbouring networks through narrow adaptive pathways (connector links) are possible, though strong enough local trapping may also cause decays in population growth and eventual extinction. A combination of analytical and numerical techniques to characterize complex networks and population dynamics on such networks permits to derive several quantitative relationships between the topology of the space of genotypes and the fate of evolving populations.
Collapse
Affiliation(s)
- Pablo Yubero
- Centro Nacional de Biotecnología, CSIC, c/Darwin 3, 28049, Madrid, Spain
| | - Susanna Manrubia
- Centro Nacional de Biotecnología, CSIC, c/Darwin 3, 28049, Madrid, Spain
- Grupo Interdisciplinar de Sistemas Complejos (GISC), Madrid, Spain
| | - Jacobo Aguirre
- Centro Nacional de Biotecnología, CSIC, c/Darwin 3, 28049, Madrid, Spain.
- Grupo Interdisciplinar de Sistemas Complejos (GISC), Madrid, Spain.
| |
Collapse
|
10
|
Choi K, Lee D, Cho YS, Thiele JC, Herrmann HJ, Kahng B. Critical phenomena of a hybrid phase transition in cluster merging dynamics. Phys Rev E 2017; 96:042148. [PMID: 29347575 DOI: 10.1103/physreve.96.042148] [Citation(s) in RCA: 5] [Impact Index Per Article: 0.7] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 06/19/2017] [Indexed: 11/07/2022]
Abstract
Recently, a hybrid percolation transition (HPT) that exhibits both a discontinuous transition and critical behavior at the same transition point has been observed in diverse complex systems. While the HPT induced by avalanche dynamics has been studied extensively, the HPT induced by cluster merging dynamics (HPT-CMD) has received little attention. Here, we aim to develop a theoretical framework for the HPT-CMD. We find that two correlation-length exponents are necessary for characterizing the giant cluster and finite clusters separately. The conventional formula of the fractal dimension in terms of the critical exponents is not valid. Neither the giant nor finite clusters are fractals, but they have fractal boundaries. A finite-size scaling method for the HPT-CMD is also introduced.
Collapse
Affiliation(s)
- K Choi
- CCSS, CTP, and Department of Physics and Astronomy, Seoul National University, Seoul 08826, Korea
| | - Deokjae Lee
- CCSS, CTP, and Department of Physics and Astronomy, Seoul National University, Seoul 08826, Korea
| | - Y S Cho
- Department of Physics, Chonbuk National University, Jeonju 54896, Korea
| | - J C Thiele
- Computational Physics for Engineering Materials, Institute for Building Materials, ETH Zürich, 8093 Zürich, Switzerland
| | - H J Herrmann
- Computational Physics for Engineering Materials, Institute for Building Materials, ETH Zürich, 8093 Zürich, Switzerland
| | - B Kahng
- CCSS, CTP, and Department of Physics and Astronomy, Seoul National University, Seoul 08826, Korea
| |
Collapse
|
11
|
Abstract
Hybrid percolation transitions (HPTs) induced by cascading processes have been observed in diverse complex systems such as k-core percolation, breakdown on interdependent networks and cooperative epidemic spreading models. Here we present the microscopic universal mechanism underlying those HPTs. We show that the discontinuity in the order parameter results from two steps: a durable critical branching (CB) and an explosive, supercritical (SC) process, the latter resulting from large loops inevitably present in finite size samples. In a random network of N nodes at the transition the CB process persists for O(N 1/3) time and the remaining nodes become vulnerable, which are then activated in the short SC process. This crossover mechanism and scaling behavior are universal for different HPT systems. Our result implies that the crossover time O(N 1/3) is a golden time, during which one needs to take actions to control and prevent the formation of a macroscopic cascade, e.g., a pandemic outbreak.
Collapse
|
12
|
Choi W, Lee D, Kahng B. Critical behavior of a two-step contagion model with multiple seeds. Phys Rev E 2017; 95:062115. [PMID: 28709296 PMCID: PMC7217524 DOI: 10.1103/physreve.95.062115] [Citation(s) in RCA: 10] [Impact Index Per Article: 1.4] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 03/13/2017] [Indexed: 11/07/2022]
Abstract
A two-step contagion model with a single seed serves as a cornerstone for understanding the critical behaviors and underlying mechanism of discontinuous percolation transitions induced by cascade dynamics. When the contagion spreads from a single seed, a cluster of infected and recovered nodes grows without any cluster merging process. However, when the contagion starts from multiple seeds of O(N) where N is the system size, a node weakened by a seed can be infected more easily when it is in contact with another node infected by a different pathogen seed. This contagion process can be viewed as a cluster merging process in a percolation model. Here we show analytically and numerically that when the density of infectious seeds is relatively small but O(1), the epidemic transition is hybrid, exhibiting both continuous and discontinuous behavior, whereas when it is sufficiently large and reaches a critical point, the transition becomes continuous. We determine the full set of critical exponents describing the hybrid and the continuous transitions. Their critical behaviors differ from those in the single-seed case.
Collapse
Affiliation(s)
- Wonjun Choi
- CCSS, CTP, and Department of Physics and Astronomy, Seoul National University, Seoul 08826, Republic of Korea
| | - Deokjae Lee
- CCSS, CTP, and Department of Physics and Astronomy, Seoul National University, Seoul 08826, Republic of Korea
| | - B Kahng
- CCSS, CTP, and Department of Physics and Astronomy, Seoul National University, Seoul 08826, Republic of Korea
| |
Collapse
|
13
|
Shu P, Gao L, Zhao P, Wang W, Stanley HE. Social contagions on interdependent lattice networks. Sci Rep 2017; 7:44669. [PMID: 28300198 PMCID: PMC5353708 DOI: 10.1038/srep44669] [Citation(s) in RCA: 18] [Impact Index Per Article: 2.6] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 11/09/2016] [Accepted: 02/13/2017] [Indexed: 11/15/2022] Open
Abstract
Although an increasing amount of research is being done on the dynamical processes on interdependent spatial networks, knowledge of how interdependent spatial networks influence the dynamics of social contagion in them is sparse. Here we present a novel non-Markovian social contagion model on interdependent spatial networks composed of two identical two-dimensional lattices. We compare the dynamics of social contagion on networks with different fractions of dependency links and find that the density of final recovered nodes increases as the number of dependency links is increased. We use a finite-size analysis method to identify the type of phase transition in the giant connected components (GCC) of the final adopted nodes and find that as we increase the fraction of dependency links, the phase transition switches from second-order to first-order. In strong interdependent spatial networks with abundant dependency links, increasing the fraction of initial adopted nodes can induce the switch from a first-order to second-order phase transition associated with social contagion dynamics. In networks with a small number of dependency links, the phase transition remains second-order. In addition, both the second-order and first-order phase transition points can be decreased by increasing the fraction of dependency links or the number of initially-adopted nodes.
Collapse
Affiliation(s)
- Panpan Shu
- School of Sciences, Xi’an University of Technology, Xi’an, 710054, China
| | - Lei Gao
- Web Sciences Center, University of Electronic Science and Technology of China, Chengdu, 610054, China
| | - Pengcheng Zhao
- School of Physics and Optoelectronic Engineering, Xidian University, Xi’an, 710071, China
| | - Wei Wang
- Web Sciences Center, University of Electronic Science and Technology of China, Chengdu, 610054, China
- Big data research center, University of Electronic Science and Technology of China, Chengdu 610054, China
- Center for Polymer Studies and Department of Physics, Boston University, Boston, Massachusetts, 02215, USA
| | - H. Eugene Stanley
- Center for Polymer Studies and Department of Physics, Boston University, Boston, Massachusetts, 02215, USA
| |
Collapse
|
14
|
Chen H, Zhao X, Liu F, Xu S, Lu W. Optimizing interconnections to maximize the spectral radius of interdependent networks. Phys Rev E 2017; 95:032308. [PMID: 28415238 DOI: 10.1103/physreve.95.032308] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 07/20/2016] [Indexed: 06/07/2023]
Abstract
The spectral radius (i.e., the largest eigenvalue) of the adjacency matrices of complex networks is an important quantity that governs the behavior of many dynamic processes on the networks, such as synchronization and epidemics. Studies in the literature focused on bounding this quantity. In this paper, we investigate how to maximize the spectral radius of interdependent networks by optimally linking k internetwork connections (or interconnections for short). We derive formulas for the estimation of the spectral radius of interdependent networks and employ these results to develop a suite of algorithms that are applicable to different parameter regimes. In particular, a simple algorithm is to link the k nodes with the largest k eigenvector centralities in one network to the node in the other network with a certain property related to both networks. We demonstrate the applicability of our algorithms via extensive simulations. We discuss the physical implications of the results, including how the optimal interconnections can more effectively decrease the threshold of epidemic spreading in the susceptible-infected-susceptible model and the threshold of synchronization of coupled Kuramoto oscillators.
Collapse
Affiliation(s)
- Huashan Chen
- State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China
- School of Mathematical Sciences, Fudan University, Shanghai 200433, People's Republic of China
- Department of Computer Science, University of Texas at San Antonio, San Antonio, Texas 78249, USA
| | - Xiuyan Zhao
- School of Mathematical Sciences, Fudan University, Shanghai 200433, People's Republic of China
| | - Feng Liu
- State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China
| | - Shouhuai Xu
- Department of Computer Science, University of Texas at San Antonio, San Antonio, Texas 78249, USA
| | - Wenlian Lu
- School of Mathematical Sciences, Fudan University, Shanghai 200433, People's Republic of China
- Institute of Science and Technology for Brain-Inspired Intelligence, Fudan University, Shanghai 200433, China
| |
Collapse
|
15
|
Zhuang Y, Arenas A, Yağan O. Clustering determines the dynamics of complex contagions in multiplex networks. Phys Rev E 2017; 95:012312. [PMID: 28208373 PMCID: PMC7217513 DOI: 10.1103/physreve.95.012312] [Citation(s) in RCA: 17] [Impact Index Per Article: 2.4] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 08/28/2016] [Indexed: 12/04/2022]
Abstract
We present the mathematical analysis of generalized complex contagions in a class of clustered multiplex networks. The model is intended to understand spread of influence, or any other spreading process implying a threshold dynamics, in setups of interconnected networks with significant clustering. The contagion is assumed to be general enough to account for a content-dependent linear threshold model, where each link type has a different weight (for spreading influence) that may depend on the content (e.g., product, rumor, political view) that is being spread. Using the generating functions formalism, we determine the conditions, probability, and expected size of the emergent global cascades. This analysis provides a generalization of previous approaches and is especially useful in problems related to spreading and percolation. The results present nontrivial dependencies between the clustering coefficient of the networks and its average degree. In particular, several phase transitions are shown to occur depending on these descriptors. Generally speaking, our findings reveal that increasing clustering decreases the probability of having global cascades and their size, however, this tendency changes with the average degree. There exists a certain average degree from which on clustering favors the probability and size of the contagion. By comparing the dynamics of complex contagions over multiplex networks and their monoplex projections, we demonstrate that ignoring link types and aggregating network layers may lead to inaccurate conclusions about contagion dynamics, particularly when the correlation of degrees between layers is high.
Collapse
Affiliation(s)
- Yong Zhuang
- Department of Electrical and Computer Engineering, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213, USA
| | - Alex Arenas
- Departament d'Enginyeria Informática i Matemátiques, Universitat Rovira i Virgili, 43007 Tarragona, Spain
| | - Osman Yağan
- Department of Electrical and Computer Engineering, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213, USA
| |
Collapse
|
16
|
Lowinger S, Cwilich GA, Buldyrev SV. Interdependent lattice networks in high dimensions. Phys Rev E 2016; 94:052306. [PMID: 27967181 DOI: 10.1103/physreve.94.052306] [Citation(s) in RCA: 11] [Impact Index Per Article: 1.4] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 04/17/2016] [Indexed: 11/07/2022]
Abstract
We study the mutual percolation of two interdependent lattice networks ranging from two to seven dimensions, denoted as D. We impose that the length (measured as chemical distance) of interdependency links connecting nodes in the two lattices be less than or equal to a certain value, r. For each value of D and r, we find the mutual percolation threshold, p_{c}[D,r], below which the system completely collapses through a cascade of failures following an initial destruction of a fraction (1-p) of the nodes in one of the lattices. We find that for each dimension, D<6, there is a value of r=r_{I}>1 such that for r≥r_{I} the cascading failures occur as a discontinuous first-order transition, while for r<r_{I} the system undergoes a continuous second-order transition, as in the classical percolation theory. Remarkably, for D=6, r_{I}=1, which is the same as in random regular graphs with the same degree (coordination number) of nodes. We also find that in all dimensions, the interdependent lattices reach maximal vulnerability (maximal p_{c}[D,r]) at a distance r=r_{max}>r_{I}, and for r>r_{max} the vulnerability starts to decrease as r→∞. However, the decrease becomes less significant as D increases, and p_{c}[D,r_{max}]-p_{c}[D,∞] decreases exponentially with D. We also investigate the dependence of p_{c}[D,r] on the system size as well as how the nature of the transition changes as the number of lattice sites, N→∞.
Collapse
Affiliation(s)
- Steven Lowinger
- Department of Physics, Yeshiva University, 500 West 185th Street, New York, New York 10033, USA
| | - Gabriel A Cwilich
- Department of Physics, Yeshiva University, 500 West 185th Street, New York, New York 10033, USA
| | - Sergey V Buldyrev
- Department of Physics, Yeshiva University, 500 West 185th Street, New York, New York 10033, USA
| |
Collapse
|
17
|
Bai YN, Huang N, Wang L, Wu ZX. Robustness and Vulnerability of Networks with Dynamical Dependency Groups. Sci Rep 2016; 6:37749. [PMID: 27892940 PMCID: PMC5125273 DOI: 10.1038/srep37749] [Citation(s) in RCA: 21] [Impact Index Per Article: 2.6] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 04/11/2016] [Accepted: 11/02/2016] [Indexed: 11/08/2022] Open
Abstract
The dependency property and self-recovery of failure nodes both have great effects on the robustness of networks during the cascading process. Existing investigations focused mainly on the failure mechanism of static dependency groups without considering the time-dependency of interdependent nodes and the recovery mechanism in reality. In this study, we present an evolving network model consisting of failure mechanisms and a recovery mechanism to explore network robustness, where the dependency relations among nodes vary over time. Based on generating function techniques, we provide an analytical framework for random networks with arbitrary degree distribution. In particular, we theoretically find that an abrupt percolation transition exists corresponding to the dynamical dependency groups for a wide range of topologies after initial random removal. Moreover, when the abrupt transition point is above the failure threshold of dependency groups, the evolving network with the larger dependency groups is more vulnerable; when below it, the larger dependency groups make the network more robust. Numerical simulations employing the Erdős-Rényi network and Barabási-Albert scale free network are performed to validate our theoretical results.
Collapse
Affiliation(s)
- Ya-Nan Bai
- School of Reliability and Systems Engineering, Beihang University, Beijing, 100191, P.R. China
| | - Ning Huang
- School of Reliability and Systems Engineering, Beihang University, Beijing, 100191, P.R. China
- Key Laboratory of Science & Technology on Reliability & Environmental Engineering, Beihang University, Beijing, 100191, P.R. China
| | - Lei Wang
- School of Automation Science and Electrical Engineering, Beihang University, Beijing, 100191, P.R. China
| | - Zhi-Xi Wu
- Institute of Computational Physics and Complex Systems, Lanzhou University, Lanzhou, Gansu, 730000, P.R. China
| |
Collapse
|
18
|
Liu RR, Li M, Jia CX. Cascading failures in coupled networks: The critical role of node-coupling strength across networks. Sci Rep 2016; 6:35352. [PMID: 27748446 PMCID: PMC5066212 DOI: 10.1038/srep35352] [Citation(s) in RCA: 29] [Impact Index Per Article: 3.6] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 08/04/2016] [Accepted: 09/28/2016] [Indexed: 11/18/2022] Open
Abstract
The robustness of coupled networks against node failure has been of interest in the past several years, while most of the researches have considered a very strong node-coupling method, i.e., once a node fails, its dependency partner in the other network will fail immediately. However, this scenario cannot cover all the dependency situations in real world, and in most cases, some nodes cannot go so far as to fail due to theirs self-sustaining ability in case of the failures of their dependency partners. In this paper, we use the percolation framework to study the robustness of interdependent networks with weak node-coupling strength across networks analytically and numerically, where the node-coupling strength is controlled by an introduced parameter α. If a node fails, each link of its dependency partner will be removed with a probability 1-α. By tuning the fraction of initial preserved nodes p, we find a rich phase diagram in the plane p-α, with a crossover point at which a first-order percolation transition changes to a second-order percolation transition.
Collapse
Affiliation(s)
- Run-Ran Liu
- Alibaba Research Center for Complexity Sciences, Hangzhou Normal University, Hangzhou, 311121, People’s Republic of China
| | - Ming Li
- School of Engineering Science, University of Science and Technology of China, Hefei, 230026, People’s Republic of China
| | - Chun-Xiao Jia
- Alibaba Research Center for Complexity Sciences, Hangzhou Normal University, Hangzhou, 311121, People’s Republic of China
| |
Collapse
|
19
|
Liu RR, Li M, Jia CX, Wang BH. Cascading failures in coupled networks with both inner-dependency and inter-dependency links. Sci Rep 2016; 6:25294. [PMID: 27142883 PMCID: PMC4855168 DOI: 10.1038/srep25294] [Citation(s) in RCA: 19] [Impact Index Per Article: 2.4] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 12/22/2015] [Accepted: 04/14/2016] [Indexed: 11/26/2022] Open
Abstract
We study the percolation in coupled networks with both inner-dependency and inter-dependency links, where the inner- and inter-dependency links represent the dependencies between nodes in the same or different networks, respectively. We find that when most of dependency links are inner- or inter-ones, the coupled networks system is fragile and makes a discontinuous percolation transition. However, when the numbers of two types of dependency links are close to each other, the system is robust and makes a continuous percolation transition. This indicates that the high density of dependency links could not always lead to a discontinuous percolation transition as the previous studies. More interestingly, although the robustness of the system can be optimized by adjusting the ratio of the two types of dependency links, there exists a critical average degree of the networks for coupled random networks, below which the crossover of the two types of percolation transitions disappears, and the system will always demonstrate a discontinuous percolation transition. We also develop an approach to analyze this model, which is agreement with the simulation results well.
Collapse
Affiliation(s)
- Run-Ran Liu
- Alibaba Research Center for Complexity Sciences, Hangzhou Normal University, Hangzhou, 311121, People’s Republic of China
| | - Ming Li
- Department of Modern Physics, University of Science and Technology of China, Hefei, 230026, People’s Republic of China
- Department of Applied Physics, Hong Kong Polytechnic University, Hung Hom, Hong Kong
| | - Chun-Xiao Jia
- Alibaba Research Center for Complexity Sciences, Hangzhou Normal University, Hangzhou, 311121, People’s Republic of China
| | - Bing-Hong Wang
- Department of Modern Physics, University of Science and Technology of China, Hefei, 230026, People’s Republic of China
| |
Collapse
|
20
|
Lee D, Choi S, Stippinger M, Kertész J, Kahng B. Hybrid phase transition into an absorbing state: Percolation and avalanches. Phys Rev E 2016; 93:042109. [PMID: 27176256 DOI: 10.1103/physreve.93.042109] [Citation(s) in RCA: 8] [Impact Index Per Article: 1.0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 12/22/2015] [Indexed: 06/05/2023]
Abstract
Interdependent networks are more fragile under random attacks than simplex networks, because interlayer dependencies lead to cascading failures and finally to a sudden collapse. This is a hybrid phase transition (HPT), meaning that at the transition point the order parameter has a jump but there are also critical phenomena related to it. Here we study these phenomena on the Erdős-Rényi and the two-dimensional interdependent networks and show that the hybrid percolation transition exhibits two kinds of critical behaviors: divergence of the fluctuations of the order parameter and power-law size distribution of finite avalanches at a transition point. At the transition point global or "infinite" avalanches occur, while the finite ones have a power law size distribution; thus the avalanche statistics also has the nature of a HPT. The exponent β_{m} of the order parameter is 1/2 under general conditions, while the value of the exponent γ_{m} characterizing the fluctuations of the order parameter depends on the system. The critical behavior of the finite avalanches can be described by another set of exponents, β_{a} and γ_{a}. These two critical behaviors are coupled by a scaling law: 1-β_{m}=γ_{a}.
Collapse
Affiliation(s)
- Deokjae Lee
- CCSS, CTP and Department of Physics and Astronomy, Seoul National University, Seoul 08826, Korea
| | - S Choi
- CCSS, CTP and Department of Physics and Astronomy, Seoul National University, Seoul 08826, Korea
| | - M Stippinger
- Department of Theoretical Physics, Budapest University of Technology and Economics, Budapest H-1111, Hungary
| | - J Kertész
- Department of Theoretical Physics, Budapest University of Technology and Economics, Budapest H-1111, Hungary
- Center for Network Science, Central European University, Budapest H-1051, Hungary
| | - B Kahng
- CCSS, CTP and Department of Physics and Astronomy, Seoul National University, Seoul 08826, Korea
| |
Collapse
|
21
|
Oh SM, Son SW, Kahng B. Explosive percolation transitions in growing networks. Phys Rev E 2016; 93:032316. [PMID: 27078375 DOI: 10.1103/physreve.93.032316] [Citation(s) in RCA: 2] [Impact Index Per Article: 0.3] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 10/16/2015] [Indexed: 06/05/2023]
Abstract
Recent extensive studies of the explosive percolation (EP) model revealed that the EP transition is second order with an extremely small value of the critical exponent β associated with the order parameter. This result was obtained from static networks, in which the number of nodes in the system remains constant during the evolution of the network. However, explosive percolating behavior of the order parameter can be observed in social networks, which are often growing networks, where the number of nodes in the system increases as dynamics proceeds. However, extensive studies of the EP transition in such growing networks are still missing. Here we study the nature of the EP transition in growing networks by extending an existing growing network model to a general case in which m node candidates are picked up in the Achiloptas process. When m = 2, this model reduces to the existing model, which undergoes an infinite-order transition. We show that when m ≥ 3, the transition becomes second order due to the suppression effect against the growth of large clusters. Using the rate-equation approach and performing numerical simulations, we also show that the exponent β decreases algebraically with increasing m, whereas it does exponentially in a corresponding static random network model. Finally, we find that the hyperscaling relations hold but in different forms.
Collapse
Affiliation(s)
- S M Oh
- CCSS, CTP and Department of Physics and Astronomy, Seoul National University, Seoul 08826, Korea
| | - S-W Son
- Department of Applied Physics, Hanyang University, Ansan 15588, Korea
| | - B Kahng
- CCSS, CTP and Department of Physics and Astronomy, Seoul National University, Seoul 08826, Korea
| |
Collapse
|
22
|
Galindo-Torres SA, Molebatsi T, Kong XZ, Scheuermann A, Bringemeier D, Li L. Scaling solutions for connectivity and conductivity of continuous random networks. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2015; 92:041001. [PMID: 26565157 DOI: 10.1103/physreve.92.041001] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 03/17/2015] [Indexed: 06/05/2023]
Abstract
Connectivity and conductivity of two-dimensional fracture networks (FNs), as an important type of continuous random networks, are examined systematically through Monte Carlo simulations under a variety of conditions, including different power law distributions of the fracture lengths and domain sizes. The simulation results are analyzed using analogies of the percolation theory for discrete random networks. With a characteristic length scale and conductivity scale introduced, we show that the connectivity and conductivity of FNs can be well described by universal scaling solutions. These solutions shed light on previous observations of scale-dependent FN behavior and provide a powerful method for quantifying effective bulk properties of continuous random networks.
Collapse
Affiliation(s)
- S A Galindo-Torres
- Geotechnical Engineering Centre. School of Civil Engineering, The University of Queensland, Brisbane QLD 4072, Australia
- Research Group on Complex Processes in Geo-Systems, School of Civil Engineering, The University of Queensland, Brisbane QLD 4072, Australia
| | - T Molebatsi
- Research Group on Complex Processes in Geo-Systems, School of Civil Engineering, The University of Queensland, Brisbane QLD 4072, Australia
| | - X-Z Kong
- Research Group on Complex Processes in Geo-Systems, School of Civil Engineering, The University of Queensland, Brisbane QLD 4072, Australia
- Institute fur Geophysik, ETH-Zurich, CH-8092 Zurich, Switzerland
| | - A Scheuermann
- Geotechnical Engineering Centre. School of Civil Engineering, The University of Queensland, Brisbane QLD 4072, Australia
- Research Group on Complex Processes in Geo-Systems, School of Civil Engineering, The University of Queensland, Brisbane QLD 4072, Australia
| | - D Bringemeier
- Geotechnical Engineering Centre. School of Civil Engineering, The University of Queensland, Brisbane QLD 4072, Australia
- Golder Associates, Milton, Queensland, Australia
| | - L Li
- Research Group on Complex Processes in Geo-Systems, School of Civil Engineering, The University of Queensland, Brisbane QLD 4072, Australia
| |
Collapse
|
23
|
Grassberger P. Percolation transitions in the survival of interdependent agents on multiplex networks, catastrophic cascades, and solid-on-solid surface growth. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2015; 91:062806. [PMID: 26172753 DOI: 10.1103/physreve.91.062806] [Citation(s) in RCA: 5] [Impact Index Per Article: 0.6] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 02/11/2015] [Indexed: 06/04/2023]
Abstract
We present an efficient algorithm for simulating percolation transitions of mutually supporting viable clusters on multiplex networks (also known as "catastrophic cascades on interdependent networks"). This algorithm maps the problem onto a solid-on-solid-type model. We use this algorithm to study interdependent agents on duplex Erdös-Rényi (ER) networks and on lattices with dimensions 2, 3, 4, and 5. We obtain surprising results in all these cases, and we correct statements in the literature for ER networks and for two-dimensional lattices. In particular, we find that d=4 is the upper critical dimension and that the percolation transition is continuous for d≤4 but-at least for d≠3-not in the universality class of ordinary percolation. For ER networks we verify that the cluster statistics is exactly described by mean-field theory but find evidence that the cascade process is not. For d=5 we find a first-order transition as for ER networks, but we find also that small clusters have a nontrivial mass distribution that scales at the transition point. Finally, for d=2 with intermediate-range dependency links we propose a scenario that differs from that proposed in W. Li et al. [Phys. Rev. Lett. 108, 228702 (2012)].
Collapse
Affiliation(s)
- Peter Grassberger
- JSC, FZ Jülich, D-52425 Jülich, Germany and Institute for Advanced Studies in Basic Sciences, Gava Zang, Zanjan 45137-66731, Iran
| |
Collapse
|
24
|
Wang H, Li M, Deng L, Wang BH. Percolation on networks with conditional dependence group. PLoS One 2015; 10:e0126674. [PMID: 25978634 PMCID: PMC4433190 DOI: 10.1371/journal.pone.0126674] [Citation(s) in RCA: 9] [Impact Index Per Article: 1.0] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 11/14/2014] [Accepted: 04/06/2015] [Indexed: 11/30/2022] Open
Abstract
Recently, the dependence group has been proposed to study the robustness of networks with interdependent nodes. A dependence group means that a failed node in the group can lead to the failures of the whole group. Considering the situation of real networks that one failed node may not always break the functionality of a dependence group, we study a cascading failure model that a dependence group fails only when more than a fraction β of nodes of the group fail. We find that the network becomes more robust with the increasing of the parameter β. However, the type of percolation transition is always first order unless the model reduces to the classical network percolation model, which is independent of the degree distribution of the network. Furthermore, we find that a larger dependence group size does not always make the networks more fragile. We also present exact solutions to the size of the giant component and the critical point, which are in agreement with the simulations well.
Collapse
Affiliation(s)
- Hui Wang
- School of Computer and Information/Hefei University of Technology, Hefei, Anhui Province, 230009, P.R. China
- Department of Modern Physics/University of Science and Technology of China, Hefei, Anhui Province, 230026, P.R. China
- Information Construction and Development Center/Hefei University of Technology, Hefei, Anhui Province, 230009, P.R. China
- Center of Information Support and Assurance Technology, Anhui University, Hefei, Anhui Province, 230601, P.R. China
| | - Ming Li
- Department of Modern Physics/University of Science and Technology of China, Hefei, Anhui Province, 230026, P.R. China
| | - Lin Deng
- School of Computer and Information/Hefei University of Technology, Hefei, Anhui Province, 230009, P.R. China
- Information Construction and Development Center/Hefei University of Technology, Hefei, Anhui Province, 230009, P.R. China
| | - Bing-Hong Wang
- Department of Modern Physics/University of Science and Technology of China, Hefei, Anhui Province, 230026, P.R. China
| |
Collapse
|
25
|
Hwang S, Choi S, Lee D, Kahng B. Efficient algorithm to compute mutually connected components in interdependent networks. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2015; 91:022814. [PMID: 25768559 DOI: 10.1103/physreve.91.022814] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.1] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 09/04/2014] [Indexed: 06/04/2023]
Abstract
Mutually connected components (MCCs) play an important role as a measure of resilience in the study of interdependent networks. Despite their importance, an efficient algorithm to obtain the statistics of all MCCs during the removal of links has thus far been absent. Here, using a well-known fully dynamic graph algorithm, we propose an efficient algorithm to accomplish this task. We show that the time complexity of this algorithm is approximately O(N(1.2)) for random graphs, which is more efficient than O(N(2)) of the brute-force algorithm. We confirm the correctness of our algorithm by comparing the behavior of the order parameter as links are removed with existing results for three types of double-layer multiplex networks. We anticipate that this algorithm will be used for simulations of large-size systems that have been previously inaccessible.
Collapse
Affiliation(s)
- S Hwang
- Institute for Theoretical Physics, University of Cologne, 50937 Köln, Germany
- CCSS and CTP, Department of Physics and Astronomy, Seoul National University, Seoul 151-747, Korea
| | - S Choi
- CCSS and CTP, Department of Physics and Astronomy, Seoul National University, Seoul 151-747, Korea
| | - Deokjae Lee
- CCSS and CTP, Department of Physics and Astronomy, Seoul National University, Seoul 151-747, Korea
| | - B Kahng
- CCSS and CTP, Department of Physics and Astronomy, Seoul National University, Seoul 151-747, Korea
| |
Collapse
|
26
|
Min Y, Hu J, Wang W, Ge Y, Chang J, Jin X. Diversity of multilayer networks and its impact on collaborating epidemics. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2014; 90:062803. [PMID: 25615144 DOI: 10.1103/physreve.90.062803] [Citation(s) in RCA: 3] [Impact Index Per Article: 0.3] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 12/15/2013] [Indexed: 06/04/2023]
Abstract
Interacting epidemics on diverse multilayer networks are increasingly important in modeling and analyzing the diffusion processes of real complex systems. A viral agent spreading on one layer of a multilayer network can interact with its counterparts by promoting (cooperative interaction), suppressing (competitive interaction), or inducing (collaborating interaction) its diffusion on other layers. Collaborating interaction displays different patterns: (i) random collaboration, where intralayer or interlayer induction has the same probability; (ii) concentrating collaboration, where consecutive intralayer induction is guaranteed with a probability of 1; and (iii) cascading collaboration, where consecutive intralayer induction is banned with a probability of 0. In this paper, we develop a top-bottom framework that uses only two distributions, the overlaid degree distribution and edge-type distribution, to model collaborating epidemics on multilayer networks. We then state the response of three collaborating patterns to structural diversity (evenness and difference of network layers). For viral agents with small transmissibility, we find that random collaboration is more effective in networks with higher diversity (high evenness and difference), while the concentrating pattern is more suitable in uneven networks. Interestingly, the cascading pattern requires a network with moderate difference and high evenness, and the moderately uneven coupling of multiple network layers can effectively increase robustness to resist cascading failure. With large transmissibility, however, we find that all collaborating patterns are more effective in high-diversity networks. Our work provides a systemic analysis of collaborating epidemics on multilayer networks. The results enhance our understanding of biotic and informative diffusion through multiple vectors.
Collapse
Affiliation(s)
- Yong Min
- College of Computer Science, Zhejiang University of Technology, Hangzhou 310024, China
| | - Jiaren Hu
- College of Computer Science, Zhejiang University of Technology, Hangzhou 310024, China
| | - Weihong Wang
- College of Computer Science, Zhejiang University of Technology, Hangzhou 310024, China
| | - Ying Ge
- College of Life Sciences, Zhejiang University, Hangzhou 310028, China
| | - Jie Chang
- College of Life Sciences, Zhejiang University, Hangzhou 310028, China
| | - Xiaogang Jin
- College of Computer Science, Zhejiang University, Hangzhou 310028, China
| |
Collapse
|
27
|
Boccaletti S, Bianconi G, Criado R, del Genio C, Gómez-Gardeñes J, Romance M, Sendiña-Nadal I, Wang Z, Zanin M. The structure and dynamics of multilayer networks. PHYSICS REPORTS 2014; 544:1-122. [PMID: 32834429 PMCID: PMC7332224 DOI: 10.1016/j.physrep.2014.07.001] [Citation(s) in RCA: 874] [Impact Index Per Article: 87.4] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Accepted: 07/03/2014] [Indexed: 05/05/2023]
Abstract
In the past years, network theory has successfully characterized the interaction among the constituents of a variety of complex systems, ranging from biological to technological, and social systems. However, up until recently, attention was almost exclusively given to networks in which all components were treated on equivalent footing, while neglecting all the extra information about the temporal- or context-related properties of the interactions under study. Only in the last years, taking advantage of the enhanced resolution in real data sets, network scientists have directed their interest to the multiplex character of real-world systems, and explicitly considered the time-varying and multilayer nature of networks. We offer here a comprehensive review on both structural and dynamical organization of graphs made of diverse relationships (layers) between its constituents, and cover several relevant issues, from a full redefinition of the basic structural measures, to understanding how the multilayer nature of the network affects processes and dynamics.
Collapse
Affiliation(s)
- S. Boccaletti
- CNR - Institute of Complex Systems, Via Madonna del Piano, 10, 50019 Sesto Fiorentino, Florence, Italy
- The Italian Embassy in Israel, 25 Hamered st., 68125 Tel Aviv, Israel
| | - G. Bianconi
- School of Mathematical Sciences, Queen Mary University of London, London, United Kingdom
| | - R. Criado
- Departamento de Matemática Aplicada, Universidad Rey Juan Carlos, 28933 Móstoles, Madrid, Spain
- Center for Biomedical Technology, Universidad Politécnica de Madrid, 28223 Pozuelo de Alarcón, Madrid, Spain
| | - C.I. del Genio
- Warwick Mathematics Institute, University of Warwick, Gibbet Hill Road, Coventry CV4 7AL, United Kingdom
- Centre for Complexity Science, University of Warwick, Gibbet Hill Road, Coventry CV4 7AL, United Kingdom
- Warwick Infectious Disease Epidemiology Research (WIDER) Centre, University of Warwick, Gibbet Hill Road, Coventry CV4 7AL, United Kingdom
| | - J. Gómez-Gardeñes
- Institute for Biocomputation and Physics of Complex Systems, University of Zaragoza, Zaragoza, Spain
| | - M. Romance
- Departamento de Matemática Aplicada, Universidad Rey Juan Carlos, 28933 Móstoles, Madrid, Spain
- Center for Biomedical Technology, Universidad Politécnica de Madrid, 28223 Pozuelo de Alarcón, Madrid, Spain
| | - I. Sendiña-Nadal
- Center for Biomedical Technology, Universidad Politécnica de Madrid, 28223 Pozuelo de Alarcón, Madrid, Spain
- Complex Systems Group, Universidad Rey Juan Carlos, 28933 Móstoles, Madrid, Spain
| | - Z. Wang
- Department of Physics, Hong Kong Baptist University, Kowloon Tong, Hong Kong Special Administrative Region
- Center for Nonlinear Studies, Beijing–Hong Kong–Singapore Joint Center for Nonlinear and Complex Systems (Hong Kong) and Institute of Computational and Theoretical Studies, Hong Kong Baptist University, Kowloon Tong, Hong Kong Special Administrative Region
| | - M. Zanin
- Innaxis Foundation & Research Institute, José Ortega y Gasset 20, 28006 Madrid, Spain
- Faculdade de Ciências e Tecnologia, Departamento de Engenharia Electrotécnica, Universidade Nova de Lisboa, 2829-516 Caparica, Portugal
| |
Collapse
|
28
|
Aguirre J, Sevilla-Escoboza R, Gutiérrez R, Papo D, Buldú JM. Synchronization of interconnected networks: the role of connector nodes. PHYSICAL REVIEW LETTERS 2014; 112:248701. [PMID: 24996113 DOI: 10.1103/physrevlett.112.248701] [Citation(s) in RCA: 28] [Impact Index Per Article: 2.8] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Received: 10/21/2013] [Indexed: 05/07/2023]
Abstract
In this Letter we identify the general rules that determine the synchronization properties of interconnected networks. We study analytically, numerically, and experimentally how the degree of the nodes through which two networks are connected influences the ability of the whole system to synchronize. We show that connecting the high-degree (low-degree) nodes of each network turns out to be the most (least) effective strategy to achieve synchronization. We find the functional relation between synchronizability and size for a given network of networks, and report the existence of the optimal connector link weights for the different interconnection strategies. Finally, we perform an electronic experiment with two coupled star networks and conclude that the analytical results are indeed valid in the presence of noise and parameter mismatches.
Collapse
Affiliation(s)
- J Aguirre
- Centro de Astrobiología, CSIC-INTA. Carretera de Ajalvir km 4, 28850 Torrejón de Ardoz, Madrid, Spain and Grupo Interdisciplinar de Sistemas Complejos (GISC)
| | - R Sevilla-Escoboza
- Centro Universitario de los Lagos, Universidad de Guadalajara, Enrique Díaz de Leon, Paseos de la Montaña, Lagos de Moreno, Jalisco 47460, Mexico and Laboratory of Biological Networks, Center for Biomedical Technology, UPM, Pozuelo de Alarcón, 28223 Madrid, Spain
| | - R Gutiérrez
- Department of Chemical Physics, The Weizmann Institute of Science, Rehovot 76100, Israel
| | - D Papo
- Group of Computational Systems Biology, Center for Biomedical Technology, UPM, Pozuelo de Alarcón, 28223 Madrid, Spain
| | - J M Buldú
- Laboratory of Biological Networks, Center for Biomedical Technology, UPM, Pozuelo de Alarcón, 28223 Madrid, Spain and Complex Systems Group, Universidad Rey Juan Carlos, 28933 Móstoles, Madrid, Spain
| |
Collapse
|
29
|
Baxter GJ, Dorogovtsev SN, Mendes JFF, Cellai D. Weak percolation on multiplex networks. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2014; 89:042801. [PMID: 24827287 DOI: 10.1103/physreve.89.042801] [Citation(s) in RCA: 16] [Impact Index Per Article: 1.6] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 12/17/2013] [Indexed: 06/03/2023]
Abstract
Bootstrap percolation is a simple but nontrivial model. It has applications in many areas of science and has been explored on random networks for several decades. In single-layer (simplex) networks, it has been recently observed that bootstrap percolation, which is defined as an incremental process, can be seen as the opposite of pruning percolation, where nodes are removed according to a connectivity rule. Here we propose models of both bootstrap and pruning percolation for multiplex networks. We collectively refer to these two models with the concept of "weak" percolation, to distinguish them from the somewhat classical concept of ordinary ("strong") percolation. While the two models coincide in simplex networks, we show that they decouple when considering multiplexes, giving rise to a wealth of critical phenomena. Our bootstrap model constitutes the simplest example of a contagion process on a multiplex network and has potential applications in critical infrastructure recovery and information security. Moreover, we show that our pruning percolation model may provide a way to diagnose missing layers in a multiplex network. Finally, our analytical approach allows us to calculate critical behavior and characterize critical clusters.
Collapse
Affiliation(s)
| | - Sergey N Dorogovtsev
- Department of Physics & I3N, University of Aveiro, Portugal and A. F. Ioffe Physico-Technical Institute, 194021 St. Petersburg, Russia
| | | | - Davide Cellai
- MACSI, Department of Mathematics and Statistics, University of Limerick, Ireland
| |
Collapse
|
30
|
Kornbluth Y, Lowinger S, Cwilich G, Buldyrev SV. Cascading failures in networks with proximate dependent nodes. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2014; 89:032808. [PMID: 24730900 DOI: 10.1103/physreve.89.032808] [Citation(s) in RCA: 6] [Impact Index Per Article: 0.6] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 10/22/2013] [Indexed: 06/03/2023]
Abstract
We study the mutual percolation of a system composed of two interdependent random regular networks. We introduce a notion of distance to explore the effects of the proximity of interdependent nodes on the cascade of failures after an initial attack. We find a nontrivial relation between the nature of the transition through which the networks disintegrate and the parameters of the system, which are the degree of the nodes and the maximum distance between interdependent nodes. We explain this relation by solving the problem analytically for the relevant set of cases. In the process, we solve a variant of Rényi's parking problem on treelike graphs.
Collapse
Affiliation(s)
- Yosef Kornbluth
- Department of Physics, Yeshiva University, 500 West 185th Street, New York, New York 10033, USA
| | - Steven Lowinger
- Department of Physics, Yeshiva University, 500 West 185th Street, New York, New York 10033, USA
| | - Gabriel Cwilich
- Department of Physics, Yeshiva University, 500 West 185th Street, New York, New York 10033, USA
| | - Sergey V Buldyrev
- Department of Physics, Yeshiva University, 500 West 185th Street, New York, New York 10033, USA
| |
Collapse
|
31
|
Watanabe S, Kabashima Y. Cavity-based robustness analysis of interdependent networks: influences of intranetwork and internetwork degree-degree correlations. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2014; 89:012808. [PMID: 24580282 DOI: 10.1103/physreve.89.012808] [Citation(s) in RCA: 15] [Impact Index Per Article: 1.5] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 08/06/2013] [Indexed: 06/03/2023]
Abstract
We develop a methodology for analyzing the percolation phenomena of two mutually coupled (interdependent) networks based on the cavity method of statistical mechanics. In particular, we take into account the influence of degree-degree correlations inside and between the networks on the network robustness against targeted (random degree-dependent) attacks and random failures. We show that the developed methodology is reduced to the well-known generating function formalism in the absence of degree-degree correlations. The validity of the developed methodology is confirmed by a comparison with the results of numerical experiments. Our analytical results indicate that the robustness of the interdependent networks depends on both the intranetwork and internetwork degree-degree correlations in a nontrivial way for both cases of random failures and targeted attacks.
Collapse
Affiliation(s)
- Shunsuke Watanabe
- Department of Computational Intelligence and Systems Science, Tokyo Institute of Technology, Yokohama 2268502, Japan
| | - Yoshiyuki Kabashima
- Department of Computational Intelligence and Systems Science, Tokyo Institute of Technology, Yokohama 2268502, Japan
| |
Collapse
|
32
|
Berezin Y, Bashan A, Havlin S. Comment on "Percolation transitions are not always sharpened by making networks interdependent". PHYSICAL REVIEW LETTERS 2013; 111:189601. [PMID: 24237574 DOI: 10.1103/physrevlett.111.189601] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.1] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 04/18/2013] [Revised: 07/14/2013] [Indexed: 06/02/2023]
Abstract
A Comment on the Letter by S. W. Son, P. Grassberger, and M. Paczuski, Phys. Rev. Lett. 107, 195702 (2011). The authors of the Letter offer a Reply.
Collapse
Affiliation(s)
- Y Berezin
- Department of Physics, Bar Ilan University, Ramat Gan 5290002, Israel
| | | | | |
Collapse
|
33
|
Son SW, Grassberger P, Paczuski M. Son, Grassberger, and Paczuski reply. PHYSICAL REVIEW LETTERS 2013; 111:189602. [PMID: 24237575 DOI: 10.1103/physrevlett.111.189602] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.1] [Reference Citation Analysis] [Track Full Text] [Subscribe] [Scholar Register] [Received: 09/01/2013] [Indexed: 06/02/2023]
Affiliation(s)
- Seung-Woo Son
- Department of Applied Physics, Hanyang University, Ansan, Gyunggi-do 426-791, Korea
| | | | | |
Collapse
|
34
|
Schneider CM, Araújo NAM, Herrmann HJ. Algorithm to determine the percolation largest component in interconnected networks. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2013; 87:043302. [PMID: 23679543 DOI: 10.1103/physreve.87.043302] [Citation(s) in RCA: 3] [Impact Index Per Article: 0.3] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 01/12/2013] [Indexed: 06/02/2023]
Abstract
Interconnected networks have been shown to be much more vulnerable to random and targeted failures than isolated ones, raising several interesting questions regarding the identification and mitigation of their risk. The paradigm to address these questions is the percolation model, where the resilience of the system is quantified by the dependence of the size of the largest cluster on the number of failures. Numerically, the major challenge is the identification of this cluster and the calculation of its size. Here, we propose an efficient algorithm to tackle this problem. We show that the algorithm scales as O(NlogN), where N is the number of nodes in the network, a significant improvement compared to O(N(2)) for a greedy algorithm, which permits studying much larger networks. Our new strategy can be applied to any network topology and distribution of interdependencies, as well as any sequence of failures.
Collapse
Affiliation(s)
- Christian M Schneider
- Department of Civil and Environmental Engineering, Massachusetts Institute of Technology, 77 Massachusetts Avenue, Cambridge, Massachusetts 02139, USA.
| | | | | |
Collapse
|
35
|
Lau HW, Paczuski M, Grassberger P. Agglomerative percolation on bipartite networks: nonuniversal behavior due to spontaneous symmetry breaking at the percolation threshold. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2012; 86:011118. [PMID: 23005379 DOI: 10.1103/physreve.86.011118] [Citation(s) in RCA: 2] [Impact Index Per Article: 0.2] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Received: 04/10/2012] [Indexed: 06/01/2023]
Abstract
Ordinary bond percolation (OP) can be viewed as a process where clusters grow by joining them pairwise, adding links chosen randomly one by one from a set of predefined virtual links. In contrast, in agglomerative percolation (AP) clusters grow by choosing randomly a target cluster and joining it with all its neighbors, as defined by the same set of virtual links. Previous studies showed that AP is in different universality classes from OP for several types of (virtual) networks (linear chains, trees, Erdös-Rényi networks), but most surprising were the results for two-dimensional (2D) lattices: While AP on the triangular lattice was found to be in the OP universality class, it behaved completely differently on the square lattice. In the present paper we explain this striking violation of universality by invoking bipartivity. While the square lattice is a bipartite graph, the triangular lattice is not. In conformity with this we show that AP on the honeycomb and simple cubic (3D) lattices--both of which are bipartite--are also not in the OP universality classes. More precisely, we claim that this violation of universality is basically due to a Z(2) symmetry that is spontaneously broken at the percolation threshold. We also discuss AP on bipartite random networks and suitable generalizations of AP on k-partite graphs.
Collapse
Affiliation(s)
- Hon Wai Lau
- Complexity Science Group, University of Calgary, Calgary T2N 1N4, Canada
| | | | | |
Collapse
|
36
|
Li W, Bashan A, Buldyrev SV, Stanley HE, Havlin S. Cascading failures in interdependent lattice networks: the critical role of the length of dependency links. PHYSICAL REVIEW LETTERS 2012; 108:228702. [PMID: 23003664 DOI: 10.1103/physrevlett.108.228702] [Citation(s) in RCA: 40] [Impact Index Per Article: 3.3] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 12/26/2011] [Indexed: 05/07/2023]
Abstract
We study the cascading failures in a system composed of two interdependent square lattice networks A and B placed on the same Cartesian plane, where each node in network A depends on a node in network B randomly chosen within a certain distance r from the corresponding node in network A and vice versa. Our results suggest that percolation for small r below r(max)≈8 (lattice units) is a second-order transition, and for larger r is a first-order transition. For r<r(max), the critical threshold increases linearly with r from 0.593 at r=0 and reaches a maximum, 0.738 for r=r(max), and then gradually decreases to 0.683 for r=∞. Our analytical considerations are in good agreement with simulations. Our study suggests that interdependent infrastructures embedded in Euclidean space become most vulnerable when the distance between interdependent nodes is in the intermediate range, which is much smaller than the size of the system.
Collapse
Affiliation(s)
- Wei Li
- Center for Polymer Studies and Department of Physics, Boston University, Boston, Massachusetts 02215, USA
| | | | | | | | | |
Collapse
|