Critical phenomena in heterogeneous k-core percolation

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.

Cascading failures in bipartite networks with directional support links

We study the cascading failures in a system of two interdependent networks whose internetwork supply links are directional. We will show that, by utilizing generating function formalism, the cascading process can be modeled by a set of recursive relations. Most importantly, the functions involved in these relations are solely dependent upon the choice of the degree distribution of ingoing links. Simulation results in the limit of very large networks based on different choices of degree distributions for outgoing links, e.g., Kronecker delta, Poisson and Pareto, are indeed identical and are in excellent agreement with the theory. However, for Pareto distribution with the shape parameter 1<α<2, the convergence is slow. In general, directional networks can be more vulnerable or less vulnerable than their bidirectional counterparts. For three special settings of interdependent networks, we analytically compare their vulnerability. For practical applications it is important to predict if a system responds to the size of the initial attack continuously or if there is catastrophic collapse of the system if the attack exceeds a specific transition size. We analytically show that systems with lower average degrees are more resilient against this abrupt transition. We also establish an equivalence of this transition with the liquid-gas transition in statistical mechanics. In the last section, we derive the set of recursive relation to describe the cascading process where the initial attack is not restricted to a single network.

Influencer identification in dynamical complex systems

The integrity and functionality of many real-world complex systems hinge on a small set of pivotal nodes, or influencers. In different contexts, these influencers are defined as either structurally important nodes that maintain the connectivity of networks, or dynamically crucial units that can disproportionately impact certain dynamical processes. In practice, identification of the optimal set of influencers in a given system has profound implications in a variety of disciplines. In this review, we survey recent advances in the study of influencer identification developed from different perspectives, and present state-of-the-art solutions designed for different objectives. In particular, we first discuss the problem of finding the minimal number of nodes whose removal would breakdown the network (i.e. the optimal percolation or network dismantle problem), and then survey methods to locate the essential nodes that are capable of shaping global dynamics with either continuous (e.g. independent cascading models) or discontinuous phase transitions (e.g. threshold models). We conclude the review with a summary and an outlook.

Fate of the Hybrid Transition of Bootstrap Percolation in Physical Dimension

Bootstrap, or k-core, percolation displays on the Bethe lattice a mixed first- and second-order phase transition with both a discontinuous order parameter and diverging critical fluctuations. I apply the recently introduced M-layer technique to study corrections to mean-field theory showing that at all orders in the loop expansion the problem is equivalent to a spinodal with quenched disorder. This implies that the mean-field hybrid transition does not survive in physical dimension. Nevertheless, its critical properties as an avoided transition make it a proxy of the avoided mode-coupling-theory critical point of supercooled liquids.

Insights into bootstrap percolation: Its equivalence with k-core percolation and the giant component

K-core and bootstrap percolation are widely studied models that have been used to represent and understand diverse deactivation and activation processes in natural and social systems. Since these models are considerably similar, it has been suggested in recent years that they could be complementary. In this manuscript we provide a rigorous analysis that shows that for any degree and threshold distributions heterogeneous bootstrap percolation can be mapped into heterogeneous k-core percolation and vice versa, if the functionality thresholds in both processes satisfy a complementary relation. Another interesting problem in bootstrap and k-core percolation is the fraction of nodes belonging to their giant connected components P_{∞b} and P_{∞c}, respectively. We solve this problem analytically for arbitrary randomly connected graphs and arbitrary threshold distributions, and we show that P_{∞b} and P_{∞c} are not complementary. Our theoretical results coincide with computer simulations in the limit of very large graphs. In bootstrap percolation, we show that when using the branching theory to compute the size of the giant component, we must consider two different types of links, which are related to distinct spanning branches of active nodes.

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.

Generalized model for k-core percolation and interdependent networks

Cascading failures in complex systems have been studied extensively using two different models: k-core percolation and interdependent networks. We combine the two models into a general model, solve it analytically, and validate our theoretical results through extensive simulations. We also study the complete phase diagram of the percolation transition as we tune the average local k-core threshold and the coupling between networks. We find that the phase diagram of the combined processes is very rich and includes novel features that do not appear in the models studying each of the processes separately. For example, the phase diagram consists of first- and second-order transition regions separated by two tricritical lines that merge and enclose a two-stage transition region. In the two-stage transition, the size of the giant component undergoes a first-order jump at a certain occupation probability followed by a continuous second-order transition at a lower occupation probability. Furthermore, at certain fixed interdependencies, the percolation transition changes from first-order → second-order → two-stage → first-order as the k-core threshold is increased. The analytic equations describing the phase boundaries of the two-stage transition region are set up, and the critical exponents for each type of transition are derived analytically.

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.

Improving the accuracy of the k-shell method by removing redundant links: From a perspective of spreading dynamics

Recent study shows that the accuracy of the k-shell method in determining node coreness in a spreading process is largely impacted due to the existence of core-like group, which has a large k-shell index but a low spreading efficiency. Based on the analysis of the structure of core-like groups in real-world networks, we discover that nodes in the core-like group are mutually densely connected with very few out-leaving links from the group. By defining a measure of diffusion importance for each edge based on the number of out-leaving links of its both ends, we are able to identify redundant links in the spreading process, which have a relatively low diffusion importance but lead to form the locally densely connected core-like group. After filtering out the redundant links and applying the k-shell method to the residual network, we obtain a renewed coreness k_s for each node which is a more accurate index to indicate its location importance and spreading influence in the original network. Moreover, we find that the performance of the ranking algorithms based on the renewed coreness are also greatly enhanced. Our findings help to more accurately decompose the network core structure and identify influential nodes in spreading processes.

Analytical approach to the dynamics of facilitated spin models on random networks

Facilitated spin models were introduced some decades ago to mimic systems characterized by a glass transition. Recent developments have shown that a class of facilitated spin models is also able to reproduce characteristic signatures of the structural relaxation properties of glass-forming liquids. While the equilibrium phase diagram of these models can be calculated analytically, the dynamics are usually investigated numerically. Here we propose a network-based approach, called approximate master equation (AME), to the dynamics of the Fredrickson-Andersen model. The approach correctly predicts the critical temperature at which the glass transition occurs. We also find excellent agreement between the theory and the numerical simulations for the transient regime, except in close proximity of the liquid-glass transition. Finally, we analytically characterize the critical clusters of the model and show that the departures between our AME approach and the Monte Carlo can be related to the large interface between blocked and unblocked spins at temperatures close to the glass transition.

Complete set of types of phase transition in generalized heterogeneous k-core percolation

We study heterogeneous k-core (HKC) percolation with a general mixture of the threshold k, with k(min) = 2 on random networks. Based on the local tree approximation, the scaling behaviors of the percolation order parameter P(∞)(p) are analytically obtained for general distributions of the threshold k. The analytic calculations predict that the generalized HKC percolation is completely described by the series of continuous transitions with order parameter exponents β(n) = 2/n, discontinuous hybrid transitions with β(H) = 1/2 or β(A)(4)) = 1/4, and three kinds of multiple transitions. Simulations of the generalized HKC percolations are carried out to confirm analytically predicted transition natures. Specifically, the exponents of the series of continuous transitions are shown to satisfy the hyperscaling relation 2β(n) + γ(n) = ν(n).

Weak percolation on multiplex networks

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.

Percolation in multiplex networks with overlap

From transportation networks to complex infrastructures, and to social and communication networks, a large variety of systems can be described in terms of multiplexes formed by a set of nodes interacting through different networks (layers). Multiplexes may display an increased fragility with respect to the single layers that constitute them. However, so far the overlap of the links in different layers has been mostly neglected, despite the fact that it is an ubiquitous phenomenon in most multiplexes. Here, we show that the overlap among layers can improve the robustness of interdependent multiplex systems and change the critical behavior of the percolation phase transition in a complex way.