Multiple resource demands and viability in multiplex networks

No-exclaves percolation

Network robustness has been a pivotal issue in the study of system failure in network science since its inception. To shed light on this subject, we introduce and study a new percolation process based on a new cluster called an 'exclave' cluster. The entities comprising exclave clusters in a network are the sets of connected unfailed nodes that are completely surrounded by the failed (i.e., nonfunctional) nodes. The exclave clusters are thus detached from other unfailed parts of the network, thereby becoming effectively nonfunctional. This process defines a new class of clusters of nonfunctional nodes. We call it the no-exclave percolation cluster (NExP cluster), formed by the connected union of failed clusters and the exclave clusters they enclose. Here we showcase the effect of NExP cluster, suggesting a wide and disruptive collapse in two empirical infrastructure networks. We also study on two-dimensional Euclidean lattice to analyze the phase transition behavior using finite-size scaling. The NExP model considering the collective failure clusters uncovers new aspects of network collapse as a percolation process, such as quantitative change of transition point and qualitative change of transition type. Our study discloses hidden indirect damage added to the damage directly from attacks, and thus suggests a new useful way for finding nonfunctioning areas in complex systems under external perturbations as well as internal partial closures.

Hidden transition in multiplex networks

Weak multiplex percolation generalizes percolation to multi-layer networks, represented as networks with a common set of nodes linked by multiple types (colors) of edges. We report a novel discontinuous phase transition in this problem. This anomalous transition occurs in networks of three or more layers without unconnected nodes, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$P(0)\,=\,0$$\end{document}P(0)=0. Above a critical value of a control parameter, the removal of a tiny fraction \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Delta$$\end{document}Δ of nodes or edges triggers a failure cascade which ends either with the total collapse of the network, or a return to stability with the system essentially intact. The discontinuity is not accompanied by any singularity of the giant component, in contrast to the discontinuous hybrid transition which usually appears in such problems. The control parameter is the fraction of nodes in each layer with a single connection, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Pi \,=\,P(1)$$\end{document}Π=P(1). We obtain asymptotic expressions for the collapse time and relaxation time, above and below the critical point \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Pi _c$$\end{document}Πc, respectively. In the limit \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Delta \rightarrow 0$$\end{document}Δ→0 the total collapse for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Pi \,>\,\Pi _\text {c}$$\end{document}Π>Πc takes a time \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$T \propto 1/(\Pi -\Pi _\text {c})$$\end{document}T∝1/(Π-Πc), while there is an exponential relaxation below \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Pi _\text {c}$$\end{document}Πc with a relaxation time \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\tau \propto 1/[\Pi _\text {c}-\Pi ]$$\end{document}τ∝1/[Πc-Π].

Double transitions and hysteresis in heterogeneous contagion processes

In many real-world contagion phenomena, the number of contacts to spreading entities for adoption varies for different individuals. Therefore, we study a model of contagion dynamics with heterogeneous adoption thresholds. We derive mean-field equations for the fraction of adopted nodes and obtain phase diagrams in terms of the transmission probability and fraction of nodes requiring multiple contacts for adoption. We find a double phase transition exhibiting a continuous transition and a subsequent discontinuous jump in the fraction of adopted nodes because of the heterogeneity in adoption thresholds. Additionally, we observe hysteresis curves in the fraction of adopted nodes owing to adopted nodes in the densely connected core in a network.

Exotic critical behavior of weak multiplex percolation

We describe the critical behavior of weak multiplex percolation, a generalization of percolation to multiplex or interdependent networks. A node can determine its active or inactive status simply by referencing neighboring nodes. This is not the case for the more commonly studied generalization of percolation to multiplex networks, the mutually connected clusters, which requires an interconnecting path within each layer between any two vertices in the giant mutually connected component. We study the emergence of a giant connected component of active nodes under the weak percolation rule, finding several nontypical phenomena. In two layers, the giant component emerges with a continuous phase transition, but with quadratic growth above the critical threshold. In three or more layers, a discontinuous hybrid transition occurs, similar to that found in the giant mutually connected component. In networks with asymptotically powerlaw degree distributions, defined by the decay exponent γ, the discontinuity vanishes but at γ=1.5 in three layers, more generally at γ=1+1/(M-1) in M layers.

Reversible bootstrap percolation: Fake news and fact checking

Bootstrap percolation has been used to describe opinion formation in society and other social and natural phenomena. The formal equation of the bootstrap percolation may have more than one solution, corresponding to several stable fixed points of the corresponding iteration process. We construct a reversible bootstrap percolation process, which converges to these extra solutions displaying a hysteresis typical of discontinuous phase transitions. This process provides a reasonable model for fake news spreading and the effectiveness of fact checking. We show that sometimes it is not sufficient to discard all the sources of fake news in order to reverse the belief of a population that formed under the influence of these sources.

Competition and dual users in complex contagion processes

We study the competition of two spreading entities, for example innovations, in complex contagion processes in complex networks. We develop an analytical framework and examine the role of dual users, i.e. agents using both technologies. Searching for the spreading transition of the new innovation and the extinction transition of a preexisting one, we identify different phases depending on network mean degree, prevalence of preexisting technology, and thresholds of the contagion process. Competition with the preexisting technology effectively suppresses the spread of the new innovation, but it also allows for phases of coexistence. The existence of dual users largely modifies the transient dynamics creating new phases that promote the spread of a new innovation and extinction of a preexisting one. It enables the global spread of the new innovation even if the old one has the first-mover advantage.

Competing contagion processes: Complex contagion triggered by simple contagion

Empirical evidence reveals that contagion processes often occur with competition of simple and complex contagion, meaning that while some agents follow simple contagion, others follow complex contagion. Simple contagion refers to spreading processes induced by a single exposure to a contagious entity while complex contagion demands multiple exposures for transmission. Inspired by this observation, we propose a model of contagion dynamics with a transmission probability that initiates a process of complex contagion. With this probability nodes subject to simple contagion get adopted and trigger a process of complex contagion. We obtain a phase diagram in the parameter space of the transmission probability and the fraction of nodes subject to complex contagion. Our contagion model exhibits a rich variety of phase transitions such as continuous, discontinuous, and hybrid phase transitions, criticality, tricriticality, and double transitions. In particular, we find a double phase transition showing a continuous transition and a following discontinuous transition in the density of adopted nodes with respect to the transmission probability. We show that the double transition occurs with an intermediate phase in which nodes following simple contagion become adopted but nodes with complex contagion remain susceptible.

Correlated network of networks enhances robustness against catastrophic failures

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.

Interplay of delay and multiplexing: Impact on cluster synchronization

Communication delays and multiplexing are ubiquitous features of real-world network systems. We here introduce a simple model where these two features are simultaneously present and report the rich phenomenology which is actually due to their interplay on cluster synchronization. A delay in one layer has non trivial impacts on the collective dynamics of the other layers, enhancing or suppressing synchronization. At the same time, multiplexing may also enhance cluster synchronization of delayed layers. We elucidate several nontrivial (and anti-intuitive) scenarios, which are of interest and potential application in various real-world systems, where the introduction of a delay may render synchronization of a layer robust against changes in the properties of the other layers.

Eradicating catastrophic collapse in interdependent networks via reinforced nodes

In interdependent networks, it is usually assumed, based on percolation theory, that nodes become nonfunctional if they lose connection to the network giant component. However, in reality, some nodes, equipped with alternative resources, together with their connected neighbors can still be functioning after disconnected from the giant component. Here, we propose and study a generalized percolation model that introduces a fraction of reinforced nodes in the interdependent networks that can function and support their neighborhood. We analyze, both analytically and via simulations, the order parameter-the functioning component-comprising both the giant component and smaller components that include at least one reinforced node. Remarkably, it is found that, for interdependent networks, we need to reinforce only a small fraction of nodes to prevent abrupt catastrophic collapses. Moreover, we find that the universal upper bound of this fraction is 0.1756 for two interdependent Erdős-Rényi (ER) networks: regular random (RR) networks and scale-free (SF) networks with large average degrees. We also generalize our theory to interdependent networks of networks (NONs). These findings might yield insight for designing resilient interdependent infrastructure networks.

Strength of weak layers in cascading failures on multiplex networks: case of the international trade network

Many real-world complex systems across natural, social, and economical domains consist of manifold layers to form multiplex networks. The multiple network layers give rise to nonlinear effect for the emergent dynamics of systems. Especially, weak layers that can potentially play significant role in amplifying the vulnerability of multiplex networks might be shadowed in the aggregated single-layer network framework which indiscriminately accumulates all layers. Here we present a simple model of cascading failure on multiplex networks of weight-heterogeneous layers. By simulating the model on the multiplex network of international trades, we found that the multiplex model produces more catastrophic cascading failures which are the result of emergent collective effect of coupling layers, rather than the simple sum thereof. Therefore risks can be systematically underestimated in single-layer network analyses because the impact of weak layers can be overlooked. We anticipate that our simple theoretical study can contribute to further investigation and design of optimal risk-averse real-world complex systems.

Cooperative epidemics on multiplex networks

The spread of one disease, in some cases, can stimulate the spreading of another infectious disease. Here, we treat analytically a symmetric coinfection model for spreading of two diseases on a two-layer multiplex network. We allow layer overlapping, but we assume that each layer is random and locally loopless. Infection with one of the diseases increases the probability of getting infected with the other. Using the generating function method, we calculate exactly the fraction of individuals infected with both diseases (so-called coinfected clusters) in the stationary state, as well as the epidemic spreading thresholds and the phase diagram of the model. With increasing cooperation, we observe a tricritical point and the type of transition changes from continuous to hybrid. Finally, we compare the coinfected clusters in the case of cooperating diseases with the so-called "viable" clusters in networks with dependencies.

Layer-switching cost and optimality in information spreading on multiplex networks

We study a model of information spreading on multiplex networks, in which agents interact through multiple interaction channels (layers), say online vs. offline communication layers, subject to layer-switching cost for transmissions across different interaction layers. The model is characterized by the layer-wise path-dependent transmissibility over a contact, that is dynamically determined dependently on both incoming and outgoing transmission layers. We formulate an analytical framework to deal with such path-dependent transmissibility and demonstrate the nontrivial interplay between the multiplexity and spreading dynamics, including optimality. It is shown that the epidemic threshold and prevalence respond to the layer-switching cost non-monotonically and that the optimal conditions can change in abrupt non-analytic ways, depending also on the densities of network layers and the type of seed infections. Our results elucidate the essential role of multiplexity that its explicit consideration should be crucial for realistic modeling and prediction of spreading phenomena on multiplex social networks in an era of ever-diversifying social interaction layers.

Percolation transitions in the survival of interdependent agents on multiplex networks, catastrophic cascades, and solid-on-solid surface growth

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)].

Threshold cascades with response heterogeneity in multiplex networks

Threshold cascade models have been used to describe the spread of behavior in social networks and cascades of default in financial networks. In some cases, these networks may have multiple kinds of interactions, such as distinct types of social ties or distinct types of financial liabilities; furthermore, nodes may respond in different ways to influence from their neighbors of multiple types. To start to capture such settings in a stylized way, we generalize a threshold cascade model to a multiplex network in which nodes follow one of two response rules: some nodes activate when, in at least one layer, a large enough fraction of neighbors is active, while the other nodes activate when, in all layers, a large enough fraction of neighbors is active. Varying the fractions of nodes following either rule facilitates or inhibits cascades. Near the inhibition regime, global cascades appear discontinuously as the network density increases; however, the cascade grows more slowly over time. This behavior suggests a way in which various collective phenomena in the real world could appear abruptly yet slowly.

The structure and dynamics of multilayer networks

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.