Multiple percolation transitions in a configuration model of a network of networks

Cascading failures in networks of networks linked by directional and bidirectional hyperlinks

We study the cascading failures in systems of any number of networks connected to each other via groups of supply links, which we call hyperlinks. The individual supply links of a hyperlink connect individual nodes belonging to the pair of networks connected by this hyperlink. Such a system is called a network of networks (NON). NONs based on the idea of mutual percolation have been studied for the case of dependency hyperlinks. The present model generalizes the heterogeneous k-core percolation for the NON, where any number of hyperlinks can be directional and any number of them can be bidirectional. We show that, by utilizing generating function formalism, the cascading process can be modeled by a set of recursive relations that are generalizations of previously studied relations in heterogeneous k-core percolation for single or bipartite networks. We demonstrate that the order in which failures propagate throughout the system does not matter for determining the final fraction of functional nodes, which depends only on the NON topology. We show that, in the NONs, there can be more than one transition point, defined as the discontinuous jump in the fraction of functional nodes at the end of the cascade as the strength of the initial attack on one of the networks gradually changes, and more than one critical point, defined as when the behavior changes from continuous to discontinuous. We find that the number of these points is strongly related to the number of hyperlinks in the NON. We further generalize previously studied criteria for the transition points and critical points in the bipartite network to the NONs with hyperlinks, and compare the phase diagrams of NONs with multiple critical points to the phase diagrams of protein solutions.

Dynamics of cascades in spatial interdependent networks

The dynamics of cascading failures in spatial interdependent networks significantly depends on the interaction range of dependency couplings between layers. In particular, for an increasing range of dependency couplings, different types of phase transition accompanied by various cascade kinetics can be observed, including mixed-order transition characterized by critical branching phenomena, first-order transition with nucleation cascades, and continuous second-order transition with weak cascades. We also describe the dynamics of cascades at the mutual mixed-order resistive transition in interdependent superconductors and show its similarity to that of percolation of interdependent abstract networks. Finally, we lay out our perspectives for the experimental observation of these phenomena, their phase diagrams, and the underlying kinetics, in the context of physical interdependent networks. Our studies of interdependent networks shed light on the possible mechanisms of three known types of phase transitions, second order, first order, and mixed order as well as predicting a novel fourth type where a microscopic intervention will yield a macroscopic phase transition.

Aftermath epidemics: Percolation on the sites visited by generalized random walks

We study percolation on the sites of a finite lattice visited by a generalized random walk of finite length with periodic boundary conditions. More precisely, consider Levy flights and walks with finite jumps of length >1 [like Knight's move random walks (RWs) in two dimensions and generalized Knight's move RWs in 3D]. In these walks, the visited sites do not form (as in ordinary RWs) a single connected cluster, and thus percolation on them is nontrivial. The model essentially mimics the spreading of an epidemic in a population weakened by the passage of some devastating agent-like diseases in the wake of a passing army or of a hurricane. Using the density of visited sites (or the number of steps in the walk) as a control parameter, we find a true continuous percolation transition in all cases except for the 2D Knight's move RWs and Levy flights with Levy parameter σ≥2. For 3D generalized Knight's move RWs, the model is in the universality class of pacman percolation, and all critical exponents seem to be simple rationals, in particular, β=1. For 2D Levy flights with 0<σ<2, scale invariance is broken even at the critical point, which leads at least to very large corrections in finite-size scaling, and even very large simulations were unable to unambiguously determine the critical exponents.

Correlation analysis of combined layers in multiplex networks based on entropy

The interactions between layers of a multiplex network would generate new structural features, the most prominent feature being the existence of link overlaps between layers. How to capture the associations with the network behavior through the structural interaction between the combined layers of the multiplex network is a critical issue. In this paper, a new structure entropy is proposed by combining the overlapping links between the combined layers of a multiplex network. The correlation between layers is evaluated by structure entropy, and the results are consistent with the behaviors exhibited by the network. In addition, the validity and applicability of the proposed method were verified by conducting trials on four sets of real multiplex network data, which included the multiplex social network of a research department at Aarhus, tailor shop multiplex network, C. elegans multiplex network, and the network collected by Vickers from 29 seventh grade students in a school in Victoria.

The fundamental benefits of multiplexity in ecological networks

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.

Stability of synchronization in simplicial complexes with multiple interaction layers

Understanding how the interplay between higher-order and multilayer structures of interconnections influences the synchronization behaviors of dynamical systems is a feasible problem of interest, with possible application in essential topics such as neuronal dynamics. Here, we provide a comprehensive approach for analyzing the stability of the complete synchronization state in simplicial complexes with numerous interaction layers. We show that the synchronization state exists as an invariant solution and derive the necessary condition for a stable synchronization state in the presence of general coupling functions. It generalizes the well-known master stability function scheme to the higher-order structures with multiple interaction layers. We verify our theoretical results by employing them on networks of paradigmatic Rössler oscillators and Sherman neuronal models, and we demonstrate that the presence of group interactions considerably improves the synchronization phenomenon in the multilayer framework.

Targeting attack hypergraph networks

In modern systems, from brain neural networks to social group networks, pairwise interactions are not sufficient to express higher-order relationships. The smallest unit of their internal function is not composed of a single functional node but results from multiple functional nodes acting together. Therefore, researchers adopt the hypergraph to describe complex systems. The targeted attack on random hypergraph networks is still a problem worthy of study. This work puts forward a theoretical framework to analyze the robustness of random hypergraph networks under the background of a targeted attack on nodes with high or low hyperdegrees. We discovered the process of cascading failures and the giant connected cluster (GCC) of the hypergraph network under targeted attack by associating the simple mapping of the factor graph with the hypergraph and using percolation theory and generating function. On random hypergraph networks, we do Monte-Carlo simulations and find that the theoretical findings match the simulation results. Similarly, targeted attacks are more effective than random failures in disintegrating random hypergraph networks. The threshold of the hypergraph network grows as the probability of high hyperdegree nodes being deleted increases, indicating that the network's resilience becomes more fragile. When considering real-world scenarios, our conclusions are validated by real-world hypergraph networks. These findings will help us understand the impact of the hypergraph's underlying structure on network resilience.

Pattern Discovery in Multilayer Networks

MOTIVATION

In bioinformatics, complex cellular modeling and behavior simulation to identify significant molecular interactions is considered a relevant problem. Traditional methods model such complex systems using single and binary network. However, this model is inadequate to represent biological networks as different sets of interactions can simultaneously take place for different interaction constraints (such as transcription regulation and protein interaction). Furthermore, biological systems may exhibit varying interaction topologies even for the same interaction type under different developmental stages or stress conditions. Therefore, models which consider biological systems as solitary interactions are inaccurate as they fail to capture the complex behavior of cellular interactions within organisms. Identification and counting of recurrent motifs within a network is one of the fundamental problems in biological network analysis. Existing methods for motif counting on single network topologies are inadequate to capture patterns of molecular interactions that have significant changes in biological expression when identified across different organisms that are similar, or even time-varying networks within the same organism. That is, they fail to identify recurrent interactions as they consider a single snapshot of a network among a set of multiple networks. Therefore, we need methods geared towards studying multiple network topologies and the pattern conservation among them. Contributions: In this paper, we consider the problem of counting the number of instances of a user supplied motif topology in a given multilayer network. We model interactions among a set of entities (e.g., genes)describing various conditions or temporal variation as multilayer networks. Thus a separate network as each layer shows the connectivity of the nodes under a unique network state. Existing motif counting and identification methods are limited to single network topologies, and thus cannot be directly applied on multilayer networks. We apply our model and algorithm to study frequent patterns in cellular networks that are common in varying cellular states under different stress conditions, where the cellular network topology under each stress condition describes a unique network layer.

RESULTS

We develop a methodology and corresponding algorithm based on the proposed model for motif counting in multilayer networks. We performed experiments on both real and synthetic datasets. We modeled the synthetic datasets under a wide spectrum of parameters, such as network size, density, motif frequency. Results on synthetic datasets demonstrate that our algorithm finds motif embeddings with very high accuracy compared to existing state-of-the-art methods such as G-tries, ESU (FANMODE)and mfinder. Furthermore, we observe that our method runs from several times to several orders of magnitude faster than existing methods. For experiments on real dataset, we consider Escherichia coli (E. coli)transcription regulatory network under different experimental conditions. We observe that the genes selected by our method conserves functional characteristics under various stress conditions with very low false discovery rates. Moreover, the method is scalable to real networks in terms of both network size and number of layers.

Higher-order percolation processes on multiplex hypergraphs

Higher-order interactions are increasingly recognized as a fundamental aspect of complex systems ranging from the brain to social contact networks. Hypergraphs as well as simplicial complexes capture the higher-order interactions of complex systems and allow us to investigate the relation between their higher-order structure and their function. Here we establish a general framework for assessing hypergraph robustness and we characterize the critical properties of simple and higher-order percolation processes. This general framework builds on the formulation of the random multiplex hypergraph ensemble where each layer is characterized by hyperedges of given cardinality. We observe that in presence of the structural cutoff the ensemble of multiplex hypergraphs can be mapped to an ensemble of multiplex bipartite networks. We reveal the relation between higher-order percolation processes in random multiplex hypergraphs, interdependent percolation of multiplex networks, and K-core percolation. The structural correlations of the random multiplex hypergraphs are shown to have a significant effect on their percolation properties. The wide range of critical behaviors observed for higher-order percolation processes on multiplex hypergraphs elucidates the mechanisms responsible for the emergence of discontinuous transition and uncovers interesting critical properties which can be applied to the study of epidemic spreading and contagion processes on higher-order networks.

Antiphase synchronization in multiplex networks with attractive and repulsive interactions

A series of recent publications, within the framework of network science, have focused on the coexistence of mixed attractive and repulsive (excitatory and inhibitory) interactions among the units within the same system, motivated by the analogies with spin glasses as well as to neural networks, or ecological systems. However, most of these investigations have been restricted to single layer networks, requiring further analysis of the complex dynamics and particular equilibrium states that emerge in multilayer configurations. This article investigates the synchronization properties of dynamical systems connected through multiplex architectures in the presence of attractive intralayer and repulsive interlayer connections. This setting enables the emergence of antisynchronization, i.e., intralayer synchronization coexisting with antiphase dynamics between coupled systems of different layers. We demonstrate the existence of a transition from interlayer antisynchronization to antiphase synchrony in any connected bipartite multiplex architecture when the repulsive coupling is introduced through any spanning tree of a single layer. We identify, analytically, the required graph topologies for interlayer antisynchronization and its interplay with intralayer and antiphase synchronization. Next, we analytically derive the invariance of intralayer synchronization manifold and calculate the attractor size of each oscillator exhibiting interlayer antisynchronization together with intralayer synchronization. The necessary conditions for the existence of interlayer antisynchronization along with intralayer synchronization are given and numerically validated by considering Stuart-Landau oscillators. Finally, we also analytically derive the local stability condition of the interlayer antisynchronization state using the master stability function approach.

Dependency-based targeted attacks in interdependent networks

Modern large engineered network systems normally work in cooperation and incorporate dependencies between their components for purposes of efficiency and regulation. Such dependencies may become a major risk since they can cause small-scale failures to propagate throughout the system. Thus, the dependent nodes could be a natural target for malicious attacks that aim to exploit these vulnerabilities. Here we consider a type of targeted attack that is based on the dependencies between the networks. We study strategies of attacks that range from dependency-first to dependency-last, where a fraction 1-p of the nodes with dependency links, or nodes without dependency links, respectively, are initially attacked. We systematically analyze, both analytically and numerically, the percolation transition of partially interdependent networks, where a fraction q of the nodes in each network are dependent on nodes in the other network. We find that for a broad range of dependency strength q, the "dependency-first" attack strategy is actually less effective, in terms of lower critical percolation threshold p_{c}, compared with random attacks of the same size. In contrast, the "dependency-last" attack strategy is more effective, i.e., higher p_{c}, compared with a random attack. This effect is explained by exploring the dynamics of the cascading failures initiated by dependency-based attacks. We show that while "dependency-first" strategy increases the short-term impact of the initial attack, in the long term the cascade slows down compared with the case of random attacks and vice versa for "dependency-last." Our results demonstrate that the effectiveness of attack strategies over a system of interdependent networks should be evaluated not only by the immediate impact but mainly by the accumulated damage during the process of cascading failures. This highlights the importance of understanding the dynamics of avalanches that may occur due to different scenarios of failures in order to design resilient critical infrastructures.

Invariance and stability conditions of interlayer synchronization manifold

We investigate interlayer synchronization in a stochastic multiplex hypernetwork which is defined by the two types of connections, one is the intralayer connection in each layer with hypernetwork structure and the other is the interlayer connection between the layers. Here all types of interactions within and between the layers are allowed to vary with a certain rewiring probability. We address the question about the invariance and stability of the interlayer synchronization state in this stochastic multiplex hypernetwork. For the invariance of interlayer synchronization manifold, the adjacency matrices corresponding to each tier in each layer should be equal and the interlayer connection should be either bidirectional or the interlayer coupling function should vanish after achieving the interlayer synchronization state. We analytically derive a necessary-sufficient condition for local stability of the interlayer synchronization state using master stability function approach and a sufficient condition for global stability by constructing a suitable Lyapunov function. Moreover, we analytically derive that intralayer synchronization is unattainable for this network architecture due to stochastic interlayer connections. Remarkably, our derived invariance and stability conditions (both local and global) are valid for any rewiring probabilities, whereas most of the previous stability conditions are only based on a fast switching approximation.

Percolation on branching simplicial and cell complexes and its relation to interdependent percolation

Network geometry has strong effects on network dynamics. In particular, the underlying hyperbolic geometry of discrete manifolds has recently been shown to affect their critical percolation properties. Here we investigate the properties of link percolation in nonamenable two-dimensional branching simplicial and cell complexes, i.e., simplicial and cell complexes in which the boundary scales like the volume. We establish the relation between the equations determining the percolation probability in random branching cell complexes and the equation for interdependent percolation in multiplex networks with interlayer degree correlation equal to one. By using this relation we show that branching cell complexes can display more than two percolation phase transitions: the upper percolation transition, the lower percolation transition, and one or more intermediate phase transitions. At these additional transitions the percolation probability and the fractal exponent both feature a discontinuity. Furthermore, by using the renormalization group theory we show that the upper percolation transition can belong to various universality classes including the Berezinskii-Kosterlitz-Thouless (BKT) transition, the discontinuous percolation transition, and continuous transitions with anomalous singular behavior that generalize the BKT transition.

Enhancing the robustness of a multiplex network leads to multiple discontinuous percolation transitions

Determining design principles that boost the robustness of interdependent networks is a fundamental question of engineering, economics, and biology. It is known that maximizing the degree correlation between replicas of the same node leads to optimal robustness. Here we show that increased robustness might also come at the expense of introducing multiple phase transitions. These results reveal yet another possible source of fragility of multiplex networks that has to be taken into the account during network optimization and design.

Local floods induce large-scale abrupt failures of road networks

The adverse effect of climate change continues to expand, and the risks of flooding are increasing. Despite advances in network science and risk analysis, we lack a systematic mathematical framework for road network percolation under the disturbance of flooding. The difficulty is rooted in the unique three-dimensional nature of a flood, where altitude plays a critical role as the third dimension, and the current network-based framework is unsuitable for it. Here we develop a failure model to study the effect of floods on road networks; the result covers 90.6% of road closures and 94.1% of flooded streets resulting from Hurricane Harvey. We study the effects of floods on road networks in China and the United States, showing a discontinuous phase transition, indicating that a small local disturbance may lead to a large-scale systematic malfunction of the entire road network at a critical point. Our integrated approach opens avenues for understanding the resilience of critical infrastructure networks against floods.

Multiple phase transitions in networks of directed networks

The robustness in real-world complex systems with dependency connectivities differs from that in isolated networks. Although most complex network research has focused on interdependent undirected systems, many real-world networks-such as gene regulatory networks and traffic networks-are directed. We thus develop an analytical framework for examining the robustness of networks made up of directed networks of differing topologies. We use it to predict the phase transitions that occur during node failures and to generate the phase diagrams of a number of different systems, including treelike and random regular (RR) networks of directed Erdős-Rényi (ER) networks and scale-free networks. We find that the the phase transition and phase diagram of networks of directed networks differ from those of networks of undirected networks. For example, the RR networks of directed ER networks show a hybrid phase transition that does not occur in networks of undirected ER networks. In addition, system robustness is affected by network topology in networks of directed networks. As coupling strength q increases, treelike networks of directed ER networks change from a second-order phase transition to a first-order phase transition, and RR networks of directed ER networks change from a second-order phase transition to a hybrid phase transition, then to a first-order phase transition, and finally to a region of collapse. We also find that heterogenous network systems are more robust than homogeneous network systems. We note that there are multiple phase transitions and triple points in the phase diagram of RR networks of directed networks and this helps us understand how to increase network robustness when designing interdependent infrastructure systems.

Bond percolation in coloured and multiplex networks

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.

Multiple structural transitions in interacting networks

Many real-world systems can be modeled as interconnected multilayer networks, namely, a set of networks interacting with each other. Here, we present a perturbative approach to study the properties of a general class of interconnected networks as internetwork interactions are established. We reveal multiple structural transitions for the algebraic connectivity of such systems, between regimes in which each network layer keeps its independent identity or drives diffusive processes over the whole system, thus generalizing previous results reporting a single transition point. Furthermore, we show that, at first order in perturbation theory, the growth of the algebraic connectivity of each layer depends only on the degree configuration of the interaction network (projected on the respective Fiedler vector), and not on the actual interaction topology. Our findings can have important implications in the design of robust interconnected networked systems, particularly in the presence of network layers whose integrity is more crucial for the functioning of the entire system. We finally show results of perturbation theory applied to the adjacency matrix of the interconnected network, which can be useful to characterize percolation processes on such systems.

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.

Group percolation in interdependent networks

In many real network systems, nodes usually cooperate with each other and form groups to enhance their robustness to risks. This motivates us to study an alternative type of percolation, group percolation, in interdependent networks under attack. In this model, nodes belonging to the same group survive or fail together. We develop a theoretical framework for this group percolation and find that the formation of groups can improve the resilience of interdependent networks significantly. However, the percolation transition is always of first order, regardless of the distribution of group sizes. As an application, we map the interdependent networks with intersimilarity structures, which have attracted much attention recently, onto the group percolation and confirm the nonexistence of continuous phase transitions.

Cascading failures in interdependent systems under a flow redistribution model

Robustness and cascading failures in interdependent systems has been an active research field in the past decade. However, most existing works use percolation-based models where only the largest component of each network remains functional throughout the cascade. Although suitable for communication networks, this assumption fails to capture the dependencies in systems carrying a flow (e.g., power systems, road transportation networks), where cascading failures are often triggered by redistribution of flows leading to overloading of lines. Here, we consider a model consisting of systems A and B with initial line loads and capacities given by {L_{A,i},C_{A,i}}_{i=1}^{n} and {L_{B,i},C_{B,i}}_{i=1}^{n}, respectively. When a line fails in system A, a fraction of its load is redistributed to alive lines in B, while remaining (1-a) fraction is redistributed equally among all functional lines in A; a line failure in B is treated similarly with b giving the fraction to be redistributed to A. We give a thorough analysis of cascading failures of this model initiated by a random attack targeting p_{1} fraction of lines in A and p_{2} fraction in B. We show that (i) the model captures the real-world phenomenon of unexpected large scale cascades and exhibits interesting transition behavior: the final collapse is always first order, but it can be preceded by a sequence of first- and second-order transitions; (ii) network robustness tightly depends on the coupling coefficients a and b, and robustness is maximized at non-trivial a,b values in general; (iii) unlike most existing models, interdependence has a multifaceted impact on system robustness in that interdependency can lead to an improved robustness for each individual network.

The "weak" interdependence of infrastructure systems produces mixed percolation transitions in multilayer networks

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.

Time-varying multiplex network: Intralayer and interlayer synchronization

A large class of engineered and natural systems, ranging from transportation networks to neuronal networks, are best represented by multiplex network architectures, namely a network composed of two or more different layers where the mutual interaction in each layer may differ from other layers. Here we consider a multiplex network where the intralayer coupling interactions are switched stochastically with a characteristic frequency. We explore the intralayer and interlayer synchronization of such a time-varying multiplex network. We find that the analytically derived necessary condition for intralayer and interlayer synchronization, obtained by the master stability function approach, is in excellent agreement with our numerical results. Interestingly, we clearly find that the higher frequency of switching links in the layers enhances both intralayer and interlayer synchrony, yielding larger windows of synchronization. Further, we quantify the resilience of synchronous states against random perturbations, using a global stability measure based on the concept of basin stability, and this reveals that intralayer coupling strength is most crucial for determining both intralayer and interlayer synchrony. Lastly, we investigate the robustness of interlayer synchronization against a progressive demultiplexing of the multiplex structure, and we find that for rapid switching of intralayer links, the interlayer synchronization persists even when a large number of interlayer nodes are disconnected.

Optimal percolation on multiplex networks

Optimal percolation is the problem of finding the minimal set of nodes whose removal from a network fragments the system into non-extensive disconnected clusters. The solution to this problem is important for strategies of immunization in disease spreading, and influence maximization in opinion dynamics. Optimal percolation has received considerable attention in the context of isolated networks. However, its generalization to multiplex networks has not yet been considered. Here we show that approximating the solution of the optimal percolation problem on a multiplex network with solutions valid for single-layer networks extracted from the multiplex may have serious consequences in the characterization of the true robustness of the system. We reach this conclusion by extending many of the methods for finding approximate solutions of the optimal percolation problem from single-layer to multiplex networks, and performing a systematic analysis on synthetic and real-world multiplex networks.

Cascading Failures in Interdependent Networks with Multiple Supply-Demand Links and Functionality Thresholds

Various social, financial, biological and technological systems can be modeled by interdependent networks. It has been assumed that in order to remain functional, nodes in one network must receive the support from nodes belonging to different networks. So far these models have been limited to the case in which the failure propagates across networks only if the nodes lose all their supply nodes. In this paper we develop a more realistic model for two interdependent networks in which each node has its own supply threshold, i.e., they need the support of a minimum number of supply nodes to remain functional. In addition, we analyze different conditions of internal node failure due to disconnection from nodes within its own network. We show that several local internal failure conditions lead to similar nontrivial results. When there are no internal failures the model is equivalent to a bipartite system, which can be useful to model a financial market. We explore the rich behaviors of these models that include discontinuous and continuous phase transitions. Using the generating functions formalism, we analytically solve all the models in the limit of infinitely large networks and find an excellent agreement with the stochastic simulations.

Diffusion dynamics and synchronizability of hierarchical products of networks

The hierarchical product of networks represents a natural tool for building large networks out of two smaller subnetworks: a primary subnetwork and a secondary subnetwork. Here we study the dynamics of diffusion and synchronization processes on hierarchical products. We apply techniques previously used for approximating the eigenvalues of the adjacency matrix to the Laplacian matrix, allowing us to quantify the effects that the primary and secondary subnetworks have on diffusion and synchronization in terms of a coupling parameter that weighs the secondary subnetwork relative to the primary subnetwork. Diffusion processes are separated into two regimes: for small coupling the diffusion rate is determined by the structure of the secondary network, scaling with the coupling parameter, while for large coupling it is determined by the primary network and saturates. Synchronization, on the other hand, is separated into three regimes, for both small and large coupling hierarchical products have poor synchronization properties, but is optimized at an intermediate value. Moreover, the critical coupling value that optimizes synchronization is shaped by the relative connectivities of the primary and secondary subnetworks, compensating for significant differences between the two subnetworks.

The interdependent network of gene regulation and metabolism is robust where it needs to be

Despite being highly interdependent, the major biochemical networks of the living cell-the networks of interacting genes and of metabolic reactions, respectively-have been approached mostly as separate systems so far. Recently, a framework for interdependent networks has emerged in the context of statistical physics. In a first quantitative application of this framework to systems biology, here we study the interdependent network of gene regulation and metabolism for the model organism Escherichia coli in terms of a biologically motivated percolation model. Particularly, we approach the system's conflicting tasks of reacting rapidly to (internal and external) perturbations, while being robust to minor environmental fluctuations. Considering its response to perturbations that are localized with respect to functional criteria, we find the interdependent system to be sensitive to gene regulatory and protein-level perturbations, yet robust against metabolic changes. We expect this approach to be applicable to a range of other interdependent networks.Although networks of interacting genes and metabolic reactions are interdependent, they have largely been treated as separate systems. Here the authors apply a statistical framework for interdependent networks to E. coli, and show that it is sensitive to gene and protein perturbations but robust against metabolic changes.

Fluctuations in percolation of sparse complex networks

We study the role of fluctuations in percolation of sparse complex networks. To this end we consider two random correlated realizations of the initial damage of the nodes and we evaluate the fraction of nodes that are expected to remain in the giant component of the network in both cases or just in one case. Our framework includes a message-passing algorithm able to predict the fluctuations in a single network, and an analytic prediction of the expected fluctuations in ensembles of sparse networks. This approach is applied to real ecological and infrastructure networks and it is shown to characterize the expected fluctuations in their response to external damage.

Nonbacktracking expansion of finite graphs

Message passing equations yield a sharp percolation transition in finite graphs, as an artifact of the locally treelike approximation. For an arbitrary finite, connected, undirected graph we construct an infinite tree having the same local structural properties as this finite graph, when observed by a nonbacktracking walker. Formally excluding the boundary, this infinite tree is a generalization of the Bethe lattice. We indicate an infinite, locally treelike, random network whose local structure is exactly given by this infinite tree. Message passing equations for various cooperative models on this construction are the same as for the original finite graph, but here they provide the exact solutions of the corresponding cooperative problems. These solutions are good approximations to observables for the models on the original graph when it is sufficiently large and not strongly correlated. We show how to express these solutions in the critical region in terms of the principal eigenvector components of the nonbacktracking matrix. As representative examples we formulate the problems of the random and optimal destruction of a connected graph in terms of our construction, the nonbacktracking expansion. We analyze the limitations and the accuracy of the message passing algorithms for different classes of networks and compare the complexity of the message passing calculations to that of direct numerical simulations. Notably, in a range of important cases, simulations turn out to be more efficient computationally than the message passing.

Multilayer modeling and analysis of human brain networks

Understanding how the human brain is structured, and how its architecture is related to function, is of paramount importance for a variety of applications, including but not limited to new ways to prevent, deal with, and cure brain diseases, such as Alzheimer's or Parkinson's, and psychiatric disorders, such as schizophrenia. The recent advances in structural and functional neuroimaging, together with the increasing attitude toward interdisciplinary approaches involving computer science, mathematics, and physics, are fostering interesting results from computational neuroscience that are quite often based on the analysis of complex network representation of the human brain. In recent years, this representation experienced a theoretical and computational revolution that is breaching neuroscience, allowing us to cope with the increasing complexity of the human brain across multiple scales and in multiple dimensions and to model structural and functional connectivity from new perspectives, often combined with each other. In this work, we will review the main achievements obtained from interdisciplinary research based on magnetic resonance imaging and establish de facto, the birth of multilayer network analysis and modeling of the human brain.

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.

Clustering determines the dynamics of complex contagions in multiplex networks

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.

Percolation in real multiplex networks

We present an exact mathematical framework able to describe site-percolation transitions in real multiplex networks. Specifically, we consider the average percolation diagram valid over an infinite number of random configurations where nodes are present in the system with given probability. The approach relies on the locally treelike ansatz, so that it is expected to accurately reproduce the true percolation diagram of sparse multiplex networks with negligible number of short loops. The performance of our theory is tested in social, biological, and transportation multiplex graphs. When compared against previously introduced methods, we observe improvements in the prediction of the percolation diagrams in all networks analyzed. Results from our method confirm previous claims about the robustness of real multiplex networks, in the sense that the average connectedness of the system does not exhibit any significant abrupt change as its individual components are randomly destroyed.

Synchronization in networks with multiple interaction layers

The structure of many real-world systems is best captured by networks consisting of several interaction layers. Understanding how a multilayered structure of connections affects the synchronization properties of dynamical systems evolving on top of it is a highly relevant endeavor in mathematics and physics and has potential applications in several socially relevant topics, such as power grid engineering and neural dynamics. We propose a general framework to assess the stability of the synchronized state in networks with multiple interaction layers, deriving a necessary condition that generalizes the master stability function approach. We validate our method by applying it to a network of Rössler oscillators with a double layer of interactions and show that highly rich phenomenology emerges from this. This includes cases where the stability of synchronization can be induced even if both layers would have individually induced unstable synchrony, an effect genuinely arising from the true multilayer structure of the interactions among the units in the network.

Collective Influence of Multiple Spreaders Evaluated by Tracing Real Information Flow in Large-Scale Social Networks

Identifying the most influential spreaders that maximize information flow is a central question in network theory. Recently, a scalable method called "Collective Influence (CI)" has been put forward through collective influence maximization. In contrast to heuristic methods evaluating nodes' significance separately, CI method inspects the collective influence of multiple spreaders. Despite that CI applies to the influence maximization problem in percolation model, it is still important to examine its efficacy in realistic information spreading. Here, we examine real-world information flow in various social and scientific platforms including American Physical Society, Facebook, Twitter and LiveJournal. Since empirical data cannot be directly mapped to ideal multi-source spreading, we leverage the behavioral patterns of users extracted from data to construct "virtual" information spreading processes. Our results demonstrate that the set of spreaders selected by CI can induce larger scale of information propagation. Moreover, local measures as the number of connections or citations are not necessarily the deterministic factors of nodes' importance in realistic information spreading. This result has significance for rankings scientists in scientific networks like the APS, where the commonly used number of citations can be a poor indicator of the collective influence of authors in the community.

Cascading failures in coupled networks: The critical role of node-coupling strength across networks

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.

Cascading failures in interdependent networks with finite functional components

We present a cascading failure model of two interdependent networks in which functional nodes belong to components of size greater than or equal to s. We find theoretically and via simulation that in complex networks with random dependency links the transition is first order for s≥3 and continuous for s=2. We also study interdependent lattices with a distance constraint r in the dependency links and find that increasing r moves the system from a regime without a phase transition to one with a second-order transition. As r continues to increase, the system collapses in a first-order transition. Each regime is associated with a different structure of domain formation of functional nodes.

Message passing theory for percolation models on multiplex networks with link overlap

Multiplex networks describe a large variety of complex systems, including infrastructures, transportation networks, and biological systems. Most of these networks feature a significant link overlap. It is therefore of particular importance to characterize the mutually connected giant component in these networks. Here we provide a message passing theory for characterizing the percolation transition in multiplex networks with link overlap and an arbitrary number of layers M. Specifically we propose and compare two message passing algorithms that generalize the algorithm widely used to study the percolation transition in multiplex networks without link overlap. The first algorithm describes a directed percolation transition and admits an epidemic spreading interpretation. The second algorithm describes the emergence of the mutually connected giant component, that is the percolation transition, but does not preserve the epidemic spreading interpretation. We obtain the phase diagrams for the percolation and directed percolation transition in simple representative cases. We demonstrate that for the same multiplex network structure, in which the directed percolation transition has nontrivial tricritical points, the percolation transition has a discontinuous phase transition, with the exception of the trivial case in which all the layers completely overlap.

Correlated edge overlaps in multiplex networks

We develop the theory of sparse multiplex networks with partially overlapping links based on their local treelikeness. This theory enables us to find the giant mutually connected component in a two-layer multiplex network with arbitrary correlations between connections of different types. We find that correlations between the overlapping and nonoverlapping links markedly change the phase diagram of the system, leading to multiple hybrid phase transitions. For assortative correlations we observe recurrent hybrid phase transitions.

Extracting information from multiplex networks

Multiplex networks are generalized network structures that are able to describe networks in which the same set of nodes are connected by links that have different connotations. Multiplex networks are ubiquitous since they describe social, financial, engineering, and biological networks as well. Extending our ability to analyze complex networks to multiplex network structures increases greatly the level of information that is possible to extract from big data. For these reasons, characterizing the centrality of nodes in multiplex networks and finding new ways to solve challenging inference problems defined on multiplex networks are fundamental questions of network science. In this paper, we discuss the relevance of the Multiplex PageRank algorithm for measuring the centrality of nodes in multilayer networks and we characterize the utility of the recently introduced indicator function Θ̃(S) for describing their mesoscale organization and community structure. As working examples for studying these measures, we consider three multiplex network datasets coming for social science.

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.

Percolation of networks with directed dependency links

The self-consistent probabilistic approach has proven itself powerful in studying the percolation behavior of interdependent or multiplex networks without tracking the percolation process through each cascading step. In order to understand how directed dependency links impact criticality, we employ this approach to study the percolation properties of networks with both undirected connectivity links and directed dependency links. We find that when a random network with a given degree distribution undergoes a second-order phase transition, the critical point and the unstable regime surrounding the second-order phase transition regime are determined by the proportion of nodes that do not depend on any other nodes. Moreover, we also find that the triple point and the boundary between first- and second-order transitions are determined by the proportion of nodes that depend on no more than one node. This implies that it is maybe general for multiplex network systems, some important properties of phase transitions can be determined only by a few parameters. We illustrate our findings using Erdős-Rényi networks.

Cascading failures in coupled networks with both inner-dependency and inter-dependency links

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.

Systems medicine of inflammaging

Systems Medicine (SM) can be defined as an extension of Systems Biology (SB) to Clinical-Epidemiological disciplines through a shifting paradigm, starting from a cellular, toward a patient centered framework. According to this vision, the three pillars of SM are Biomedical hypotheses, experimental data, mainly achieved by Omics technologies and tailored computational, statistical and modeling tools. The three SM pillars are highly interconnected, and their balancing is crucial. Despite the great technological progresses producing huge amount of data (Big Data) and impressive computational facilities, the Bio-Medical hypotheses are still of primary importance. A paradigmatic example of unifying Bio-Medical theory is the concept of Inflammaging. This complex phenotype is involved in a large number of pathologies and patho-physiological processes such as aging, age-related diseases and cancer, all sharing a common inflammatory pathogenesis. This Biomedical hypothesis can be mapped into an ecological perspective capable to describe by quantitative and predictive models some experimentally observed features, such as microenvironment, niche partitioning and phenotype propagation. In this article we show how this idea can be supported by computational methods useful to successfully integrate, analyze and model large data sets, combining cross-sectional and longitudinal information on clinical, environmental and omics data of healthy subjects and patients to provide new multidimensional biomarkers capable of distinguishing between different pathological conditions, e.g. healthy versus unhealthy state, physiological versus pathological aging.

Competition between global and local online social networks

The overwhelming success of online social networks, the key actors in the Web 2.0 cosmos, has reshaped human interactions globally. To help understand the fundamental mechanisms which determine the fate of online social networks at the system level, we describe the digital world as a complex ecosystem of interacting networks. In this paper, we study the impact of heterogeneity in network fitnesses on the competition between an international network, such as Facebook, and local services. The higher fitness of international networks is induced by their ability to attract users from all over the world, which can then establish social interactions without the limitations of local networks. In other words, inter-country social ties lead to increased fitness of the international network. To study the competition between an international network and local ones, we construct a 1:1000 scale model of the digital world, consisting of the 80 countries with the most Internet users. Under certain conditions, this leads to the extinction of local networks; whereas under different conditions, local networks can persist and even dominate completely. In particular, our model suggests that, with the parameters that best reproduce the empirical overtake of Facebook, this overtake could have not taken place with a significant probability.

Multiplex networks with heterogeneous activities of the nodes

In multiplex networks with a large number of layers, the nodes can have different activities, indicating the total number of layers in which the nodes are present. Here we model multiplex networks with heterogeneous activity of the nodes and we study their robustness properties. We introduce a percolation model where nodes need to belong to the giant component only on the layers where they are active (i.e., their degree on that layer is larger than zero). We show that when there are enough nodes active only in one layer, the multiplex becomes more resilient and the transition becomes continuous. We find that multiplex networks with a power-law distribution of node activities are more fragile if the distribution of activity is broader. We also show that while positive correlations between node activity and degree can enhance the robustness of the system, the phase transition may become discontinuous, making the system highly unpredictable.

Exploring percolative landscapes: Infinite cascades of geometric phase transitions

The evolution of many kinetic processes in 1+1 (space-time) dimensions results in 2D directed percolative landscapes. The active phases of these models possess numerous hidden geometric orders characterized by various types of large-scale and/or coarse-grained percolative backbones that we define. For the patterns originated in the classical directed percolation (DP) and contact process we show from the Monte Carlo simulation data that these percolative backbones emerge at specific critical points as a result of continuous phase transitions. These geometric transitions belong to the DP universality class and their nonlocal order parameters are the capacities of corresponding backbones. The multitude of conceivable percolative backbones implies the existence of infinite cascades of such geometric transitions in the kinetic processes considered. We present simple arguments to support the conjecture that such cascades of transitions are a generic feature of percolation as well as of many other transitions with nonlocal order parameters.

Control of Multilayer Networks

The controllability of a network is a theoretical problem of relevance in a variety of contexts ranging from financial markets to the brain. Until now, network controllability has been characterized only on isolated networks, while the vast majority of complex systems are formed by multilayer networks. Here we build a theoretical framework for the linear controllability of multilayer networks by mapping the problem into a combinatorial matching problem. We found that correlating the external signals in the different layers can significantly reduce the multiplex network robustness to node removal, as it can be seen in conjunction with a hybrid phase transition occurring in interacting Poisson networks. Moreover we observe that multilayer networks can stabilize the fully controllable multiplex network configuration that can be stable also when the full controllability of the single network is not stable.

Breakdown of interdependent directed networks

Increasing evidence shows that real-world systems interact with one another via dependency connectivities. Failing connectivities are the mechanism behind the breakdown of interacting complex systems, e.g., blackouts caused by the interdependence of power grids and communication networks. Previous research analyzing the robustness of interdependent networks has been limited to undirected networks. However, most real-world networks are directed, their in-degrees and out-degrees may be correlated, and they are often coupled to one another as interdependent directed networks. To understand the breakdown and robustness of interdependent directed networks, we develop a theoretical framework based on generating functions and percolation theory. We find that for interdependent Erdős-Rényi networks the directionality within each network increases their vulnerability and exhibits hybrid phase transitions. We also find that the percolation behavior of interdependent directed scale-free networks with and without degree correlations is so complex that two criteria are needed to quantify and compare their robustness: the percolation threshold and the integrated size of the giant component during an entire attack process. Interestingly, we find that the in-degree and out-degree correlations in each network layer increase the robustness of interdependent degree heterogeneous networks that most real networks are, but decrease the robustness of interdependent networks with homogeneous degree distribution and with strong coupling strengths. Moreover, by applying our theoretical analysis to real interdependent international trade networks, we find that the robustness of these real-world systems increases with the in-degree and out-degree correlations, confirming our theoretical analysis.

Collective Motion in a Network of Self-Propelled Agent Systems

Collective motions of animals that move towards the same direction is a conspicuous feature in nature. Such groups of animals are called a self-propelled agent (SPA) systems. Many studies have been focused on the synchronization of isolated SPA systems. In real scenarios, different SPA systems are coupled with each other forming a network of SPA systems. For example, a flock of birds and a school of fish show predator-prey relationships and different groups of birds may compete for food. In this work, we propose a general framework to study the collective motion of coupled self-propelled agent systems. Especially, we study how three different connections between SPA systems: symbiosis, predator-prey, and competition influence the synchronization of the network of SPA systems. We find that a network of SPA systems coupled with symbiosis relationship arrive at a complete synchronization as all its subsystems showing a complete synchronization; a network of SPA systems coupled by predator-prey relationship can not reach a complete synchronization and its subsystems converges to different synchronized directions; and the competitive relationship between SPA systems could increase the synchronization of each SPA systems, while the network of SPA systems coupled by competitive relationships shows an optimal synchronization for small coupling strength, indicating that small competition promotes the synchronization of the entire system.