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.

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.

Localization of nonbacktracking centrality on dense subgraphs of sparse networks.

The nonbacktracking matrix and the related nonbacktracking centrality (NBC) play a crucial role in models of percolation-type processes on networks, such as nonrecurrent epidemics. Here we study the localization of NBC in infinite sparse networks that contain an arbitrary finite subgraph. Assuming the local tree likeness of the enclosing network, and that branches emanating from the finite subgraph do not intersect at finite distances, we show that the largest eigenvalue of the nonbacktracking matrix of the composite network is equal to the highest of the two largest eigenvalues: that of the finite subgraph and of the enclosing network.

Hidden transition in multiplex networks.

Weak multiplex percolation generalizes percolation to multi-layer networks, represented as networks with a common set of nodes linked by multiple types (colors) of edges. We report a novel discontinuous phase transition in this problem. This anomalous transition occurs in networks of three or more layers without unconnected nodes, [Formula: see text].

Approximating nonbacktracking centrality and localization phenomena in large networks.

Message-passing theories have proved to be invaluable tools in studying percolation, nonrecurrent epidemics, and similar dynamical processes on real-world networks. At the heart of the message-passing method is the nonbacktracking matrix, whose largest eigenvalue, the corresponding eigenvector, and the closely related nonbacktracking centrality play a central role in determining how the given dynamical model behaves. Here we propose a degree-class-based method to approximate these quantities using a smaller matrix related to the joint degree-degree distribution of neighboring nodes.

Filtering Statistics on Networks.

Compression, filtering, and cryptography, as well as the sampling of complex systems, can be seen as processing information. A large initial configuration or input space is nontrivially mapped to a smaller set of output or final states. We explored the statistics of filtering of simple patterns on a number of deterministic and random graphs as a tractable example of such information processing in complex systems.

Exotic critical behavior of weak multiplex percolation.

We describe the critical behavior of weak multiplex percolation, a generalization of percolation to multiplex or interdependent networks. A node can determine its active or inactive status simply by referencing neighboring nodes. This is not the case for the more commonly studied generalization of percolation to multiplex networks, the mutually connected clusters, which requires an interconnecting path within each layer between any two vertices in the giant mutually connected component.

Choosing among alternative histories of a tree.

The structure of an evolving network contains information about its past. Extracting this information efficiently, however, is, in general, a difficult challenge. We formulate a fast and efficient method to estimate the most likely history of growing trees, based on exact results on root finding.

Generalization of core percolation on complex networks.

We introduce a k-leaf removal algorithm as a generalization of the so-called leaf removal algorithm. In this pruning algorithm, vertices of degree smaller than k, together with their first nearest neighbors and all incident edges, are progressively removed from a random network. As the result of this pruning the network is reduced to a subgraph which we call the Generalized k-core (Gk-core).

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.

Finding the Optimal Nets for Self-Folding Kirigami.

Three-dimensional shells can be synthesized from the spontaneous self-folding of two-dimensional templates of interconnected panels, called nets. However, some nets are more likely to self-fold into the desired shell under random movements. The optimal nets are the ones that maximize the number of vertex connections, i.

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.

Mapping the Structure of Directed Networks: Beyond the Bow-Tie Diagram.

We reveal a hierarchical, multilayer organization of finite components-i.e., tendrils and tubes-around the giant connected components in directed networks and propose efficient algorithms allowing one to uncover the entire organization of key real-world directed networks, such as the World Wide Web, the neural network of Caenorhabditis elegans, and others.

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.

Metastable localization of diseases in complex networks.

We describe the phenomenon of localization in the epidemic susceptible-infective-susceptible model on highly heterogeneous networks in which strongly connected nodes (hubs) play the role of centers of localization. We find that in this model the localized states below the epidemic threshold are metastable. The longevity and scale of the metastable outbreaks do not show a sharp localization transition; instead there is a smooth crossover from localized to delocalized states as we approach the epidemic threshold from below.

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.

Scale-free networks with exponent one.

A majority of studied models for scale-free networks have degree distributions with exponents greater than two. Real networks, however, can demonstrate essentially more heavy-tailed degree distributions. We explore two models of scale-free equilibrium networks that have the degree distribution exponent γ=1, P(q)∼q^{-γ}.

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.

Inverting the Achlioptas rule for explosive percolation.

In the usual Achlioptas processes the smallest clusters of a few randomly chosen ones are selected to merge together at each step. The resulting aggregation process leads to the delayed birth of a giant cluster and the so-called explosive percolation transition showing a set of anomalous features. We explore a process with the opposite selection rule, in which the biggest clusters of the randomly chosen ones merge together.

Solution of the explosive percolation quest. II. Infinite-order transition produced by the initial distributions of clusters.

We describe the effect of power-law initial distributions of clusters on ordinary percolation and its generalizations, specifically, models of explosive percolation processes based on local optimization. These aggregation processes were shown to exhibit continuous phase transitions if the evolution starts from a set of disconnected nodes. Since the critical exponents of the order parameter in explosive percolation transitions turned out to be very small, these transitions were first believed to be discontinuous.

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.

Giant components in directed multiplex networks.

We describe the complex global structure of giant components in directed multiplex networks that generalizes the well-known bow-tie structure, generic for ordinary directed networks. By definition, a directed multiplex network contains vertices of one type and directed edges of m different types. In directed multiplex networks, we distinguish a set of different giant components based on the existence of directed paths of different types between their vertices such that for each type of edges, the paths run entirely through only edges of that type.

k-core percolation on multiplex networks.

We generalize the theory of k-core percolation on complex networks to k-core percolation on multiplex networks, where k≡(k(1),k(2),...

Solution of the explosive percolation quest: scaling functions and critical exponents.

Percolation refers to the emergence of a giant connected cluster in a disordered system when the number of connections between nodes exceeds a critical value. The percolation phase transitions were believed to be continuous until recently when, in a new so-called "explosive percolation" problem for a competition-driven process, a discontinuous phase transition was reported. The analysis of evolution equations for this process showed, however, that this transition is actually continuous, though with surprisingly tiny critical exponents.

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.