Nature of hypergraph k-core percolation problems.

Hypergraphs are higher-order networks that capture the interactions between two or more nodes. Hypergraphs can always be represented by factor graphs, i.e., bipartite networks between nodes and factor nodes (representing groups of nodes). Despite this universal representation, here we reveal that k-core percolation on hypergraphs can be significantly distinct from k-core percolation on factor graphs. We formulate the theory of hypergraph k-core percolation based on the assumption that a hyperedge can be intact only if all its nodes are intact. This scenario applies, for instance, to supply chains where the production of a product requires all raw materials and all processing steps; in biology it applies to protein-interaction networks where protein complexes can function only if all the proteins are present; and it applies as well to chemical reaction networks where a chemical reaction can take place only when all the reactants are present. Formulating a message-passing theory for hypergraph k-core percolation, and combining it with the theory of critical phenomena on networks, we demonstrate sharp differences with previously studied factor graph k-core percolation processes where it is allowed for hyperedges to have one or more damaged nodes and still be intact. To solve the dichotomy between k-core percolation on hypegraphs and on factor graphs, we define a set of pruning processes that act either exclusively on nodes or exclusively on hyperedges and depend on their second-neighborhood connectivity. We show that the resulting second-neighbor k-core percolation problems are significantly distinct from each other. Moreover we reveal that although these processes remain distinct from factor graphs k-core processes, when the pruning process acts exclusively on hyperedges the phase diagram is reduced to the one of factor graph k-cores.

Theory of percolation on hypergraphs.

Hypergraphs capture the higher-order interactions in complex systems and always admit a factor graph representation, consisting of a bipartite network of nodes and hyperedges. As hypegraphs are ubiquitous, investigating hypergraph robustness is a problem of major research interest. In the literature the robustness of hypergraphs so far only has been treated adopting factor-graph percolation, which describes well higher-order interactions which remain functional even after the removal of one of more of their nodes. This approach, however, fall short to describe situations in which higher-order interactions fail when any one of their nodes is removed, this latter scenario applying, for instance, to supply chains, catalytic networks, protein-interaction networks, networks of chemical reactions, etc. Here we show that in these cases the correct process to investigate is hypergraph percolation, with is distinct from factor graph percolation. We build a message-passing theory of hypergraph percolation, and we investigate its critical behavior using generating function formalism supported by Monte Carlo simulations on random graph and real data. Notably, we show that the node percolation threshold on hypergraphs exceeds node percolation threshold on factor graphs. Furthermore we show that differently from what happens in ordinary graphs, on hypergraphs the node percolation threshold and hyperedge percolation threshold do not coincide, with the node percolation threshold exceeding the hyperedge percolation threshold. These results demonstrate that any fat-tailed cardinality distribution of hyperedges cannot lead to the hyper-resilience phenomenon in hypergraphs in contrast to their factor graphs, where the divergent second moment of a cardinality distribution guarantees zero percolation threshold.

Complex network view of evolving manifolds.

We study complex networks formed by triangulations and higher-dimensional simplicial complexes representing closed evolving manifolds. In particular, for triangulations, the set of possible transformations of these networks is restricted by the condition that at each step, all the faces must be triangles. Stochastic application of these operations leads to random networks with different architectures. We perform extensive numerical simulations and explore the geometries of growing and equilibrium complex networks generated by these transformations and their local structural properties. This characterization includes the Hausdorff and spectral dimensions of the resulting networks, their degree distributions, and various structural correlations. Our results reveal a rich zoo of architectures and geometries of these networks, some of which appear to be small worlds while others are finite dimensional with Hausdorff dimension equal or higher than the original dimensionality of their simplices. The range of spectral dimensions of the evolving triangulations turns out to be from about 1.4 to infinity. Our models include simplicial complexes representing manifolds with evolving topologies, for example, an h-holed torus with a progressively growing number of holes. This evolving graph demonstrates features of a small-world network and has a particularly heavy-tailed degree distribution.

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.

Cycles and clustering in multiplex networks.

In multiplex networks, cycles cannot be characterized only by their length, as edges may occur in different layers in different combinations. We define a classification of cycles by the number of edges in each layer and the number of switches between layers. We calculate the expected number of cycles of each type in the configuration model of a large sparse multiplex network. Our method accounts for the full degree distribution including correlations between degrees in different layers. In particular, we obtain the numbers of cycles of length 3 of all possible types. Using these, we give a complete set of clustering coefficients and their expected values. We show that correlations between the degrees of a vertex in different layers strongly affect the number of cycles of a given type, and the number of switches between layers. Both increase with assortative correlations and are strongly decreased by disassortative correlations. The effect of correlations on clustering coefficients is equally pronounced.

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.

Mutually connected component of networks of networks with replica nodes.

We describe the emergence of the giant mutually connected component in networks of networks in which each node has a single replica node in any layer and can be interdependent only on its replica nodes in the interdependent layers. We prove that if, in these networks, all the nodes of one network (layer) are interdependent on the nodes of the same other interconnected layer, then, remarkably, the mutually connected component does not depend on the topology of the network of networks. This component coincides with the mutual component of the fully connected network of networks constructed from the same set of layers, i.e., a multiplex network.

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

Recently much attention has been paid to the study of the robustness of interdependent and multiplex networks and, in particular, the networks of networks. The robustness of interdependent networks can be evaluated by the size of a mutually connected component when a fraction of nodes have been removed from these networks. Here we characterize the emergence of the mutually connected component in a network of networks in which every node of a network (layer) α is connected with q_{α} its randomly chosen replicas in some other networks and is interdependent of these nodes with probability r. We find that when the superdegrees q_{α} of different layers in a network of networks are distributed heterogeneously, multiple percolation phase transition can occur. We show that, depending on the value of r, these transition are continuous or discontinuous.

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.