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. In the localized state, when the largest eigenvalue of the subgraph is the highest of the two, we derive explicit expressions for the NBCs of nodes in the subgraph and other nodes in the network. In this state, nonbacktracking centrality is concentrated on the subgraph and its immediate neighborhood in the enclosing network. We obtain simple, exact formulas in the case where the enclosing network is uncorrelated. We find that the mean NBC decays exponentially around the finite subgraph, at a rate which is independent of the structure of the enclosing network, contrary to what was found for the localization of the principal eigenvector of the adjacency matrix. Numerical simulations confirm that our results provide good approximations even in moderately sized, loopy, real-world networks.

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]. Above a critical value of a control parameter, the removal of a tiny fraction [Formula: see text] of nodes or edges triggers a failure cascade which ends either with the total collapse of the network, or a return to stability with the system essentially intact. The discontinuity is not accompanied by any singularity of the giant component, in contrast to the discontinuous hybrid transition which usually appears in such problems. The control parameter is the fraction of nodes in each layer with a single connection, [Formula: see text]. We obtain asymptotic expressions for the collapse time and relaxation time, above and below the critical point [Formula: see text], respectively. In the limit [Formula: see text] the total collapse for [Formula: see text] takes a time [Formula: see text], while there is an exponential relaxation below [Formula: see text] with a relaxation time [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. Our findings suggest that in most networks, degree-degree correlations beyond nearest neighbor are actually not strong, and our first-order description already results in accurate estimates, particularly when message-passing itself is a good approximation to the original model in question, that is, when the number of short cycles in the network is sufficiently low. We show that localization of the nonbacktracking centrality is also captured well by our scheme, particularly in large networks. Our method provides an alternative to working with the full nonbacktracking matrix in very large networks where this may not be possible due to memory limitations.

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. In this problem, multiple inputs map to the same output, and the statistics of filtering is represented by the distribution of this degeneracy. For a few simple filter patterns on a ring, we obtained an exact solution of the problem and numerically described more difficult filter setups. For each of the filter patterns and networks, we found three key numbers that essentially describe the statistics of filtering and compared them for different networks. Our results for networks with diverse architectures are essentially determined by two factors: whether the graphs structure is deterministic or random and the vertex degree. We find that filtering in random graphs produces much richer statistics than in deterministic graphs, reflecting the greater complexity of such graphs. Increasing the graph's degree reduces this statistical richness, while being at its maximum at the smallest degree not equal to two. A filter pattern with a strong dependence on the neighbourhood of a node is much more sensitive to these effects.

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. We show that our linear-time algorithm produces the exact stepwise most probable history in a broad class of tree growth models. Our formulation is able to treat very large trees and therefore allows us to make reliable numerical observations regarding the possibility of root inference and history reconstruction in growing trees. We obtain the general formula 〈lnN〉≅NlnN-cN for the size dependence of the mean logarithmic number of possible histories of a given tree, a quantity that largely determines the reconstructability of tree histories. We also reveal an uncertainty principle: a relationship between the inferability of the root and that of the complete history, indicating that there is a tradeoff between the two tasks; the root and the complete history cannot both be inferred with high accuracy at the same time.

Exotic critical behavior of weak multiplex percolation.

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

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). Performing this pruning for the sequence of natural numbers k, we decompose the network into a hierarchy of progressively nested Gk-cores. We present an analytical framework for description of Gk-core percolation for undirected uncorrelated networks with arbitrary degree distributions (configuration model). To confirm our results, we also derive rate equations for the k-leaf removal algorithm which enable us to obtain the structural characteristics of the Gk-cores in another way. Also we apply our algorithm to a number of real-world networks and perform the Gk-core decomposition for them.

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.e., vertices that have only two of its faces cut away from each other in the net. Previous methods for finding such nets are based on random search, and thus, they do not guarantee the optimal solution. Here, we propose a deterministic procedure. We map the connectivity of the shell into a shell graph, where the nodes and links of the graph represent the vertices and edges of the shell, respectively. Identifying the nets that maximize the number of vertex connections corresponds to finding the set of maximum leaf spanning trees of the shell graph. This method allows us not only to design the self-assembly of much larger shell structures but also to apply additional design criteria, as a complete catalog of the maximum leaf spanning trees is obtained.

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.

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. With increasing damage, the giant components decrease in size while the number and size of tendril layers increase, enhancing the susceptibility of the networks to damage.

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^{-γ}. Such degree distributions can be identified in empirical data only if the mean degree of a network is sufficiently high. Our models exploit a rewiring mechanism. They are local in the sense that no knowledge of the network structure, apart from the immediate neighborhood of the vertices, is required. These models generate uncorrelated networks in the infinite size limit, where they are solved explicitly. We investigate finite size effects by the use of simulations. We find that both models exhibit disassortative degree-degree correlations for finite network sizes. In addition, we observe a markedly degree-dependent clustering in the finite networks. We indicate a real-world network with a similar degree distribution.

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. Analyzing these long-lasting local outbreaks for a random regular graph with a hub, we show how this localization can be detected from the shape of the distribution of the number of infective nodes.

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. We develop a theory of this kind of percolation based on the Smoluchowsky equation, find the percolation threshold, and describe the scaling properties of this continuous transition, namely, the critical exponents and amplitudes, and scaling functions. We show that, qualitatively, this transition is similar to the ordinary percolation one, though occurring in less connected systems.

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. In this article we analyze the evolution starting from clusters of nodes whose sizes are distributed according to a power law. We show that these initial distributions change dramatically the position and order of the phase transitions in these problems. We find a particular initial power-law distribution producing a peculiar effect on explosive percolation, namely, before the emergence of the percolation cluster, the system is in a "critical phase" with an infinite generalized susceptibility. This critical phase is absent in ordinary percolation models with any power-law initial conditions. The transition from the critical phase is an infinite-order phase transition, which resembles the scenario of the Berezinskii-Kosterlitz-Thouless phase transition. We obtain the critical singularity of susceptibility at this peculiar infinite-order transition in explosive percolation. It turns out that susceptibility in this situation does not obey the Curie-Weiss law.

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. If, in particular, m=2, we define a strongly viable component as a set of vertices in which for each type of edges each two vertices are interconnected by at least two directed paths in both directions, running through the edges of only this type. We show that in this case, a directed multiplex network contains in total nine different giant components including the strongly viable component. In general, the total number of giant components is 3^{m}. For uncorrelated directed multiplex networks, we obtain exactly the size and the emergence point of the strongly viable component and estimate the sizes of other giant components.

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),...,k(M)). Multiplex networks can be defined as networks with vertices of one kind but M different types of edges, representing different types of interactions. For such networks, the k-core is defined as the largest subgraph in which each vertex has at least k(i) edges of each type, i=1,2,...,M. We derive self-consistency equations to obtain the birth points of the k-cores and their relative sizes for uncorrelated multiplex networks with an arbitrary degree distribution. To clarify our general results, we consider in detail multiplex networks with edges of two types and solve the equations in the particular case of Erdos-Rényi and scale-free multiplex networks. We find hybrid phase transitions at the emergence points of k-cores except the (1,1)-core for which the transition is continuous. We apply the k-core decomposition algorithm to air-transportation multiplex networks, composed of two layers, and obtain the size of (k(1),k(2))-cores.

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. For a wide class of representative models, we develop a strict scaling theory of this exotic transition which provides the full set of scaling functions and critical exponents. This theory indicates the relevant order parameter and susceptibility for the problem and explains the continuous nature of this transition and its unusual properties.

Critical exponents of the explosive percolation transition.

In a new type of percolation phase transition, which was observed in a set of nonequilibrium models, each new connection between vertices is chosen from a number of possibilities by an Achlioptas-like algorithm. This causes preferential merging of small components and delays the emergence of the percolation cluster. First simulations led to a conclusion that a percolation cluster in this irreversible process is born discontinuously, by a discontinuous phase transition, which results in the term "explosive percolation transition." We have shown that this transition is actually continuous (second order) though with an anomalously small critical exponent of the percolation cluster. Here we propose an efficient numerical method enabling us to find the critical exponents and other characteristics of this second-order transition for a representative set of explosive percolation models with different number of choices. The method is based on gluing together the numerical solutions of evolution equations for the cluster size distribution and power-law asymptotics. For each of the models, with high precision, we obtain critical exponents and the critical point.

Biased imitation in coupled evolutionary games in interdependent networks.

We explore the evolutionary dynamics of two games-the Prisoner's Dilemma and the Snowdrift Game-played within distinct networks (layers) of interdependent networks. In these networks imitation and interaction between individuals of opposite layers is established through interlinks. We explore an update rule in which revision of strategies is a biased imitation process: individuals imitate neighbors from the same layer with probability p, and neighbors from the second layer with complementary probability 1 - p. We demonstrate that a small decrease of p from p = 1 (which corresponds to forbidding strategy transfer between layers) is sufficient to promote cooperation in the Prisoner's Dilemma subpopulation. This, on the other hand, is detrimental for cooperation in the Snowdrift Game subpopulation. We provide results of extensive computer simulations for the case in which layers are modelled as regular random networks, and support this study with analytical results for coupled well-mixed populations.

Localization and spreading of diseases in complex networks.

Using the susceptible-infected-susceptible model on unweighted and weighted networks, we consider the disease localization phenomenon. In contrast to the well-recognized point of view that diseases infect a finite fraction of vertices right above the epidemic threshold, we show that diseases can be localized on a finite number of vertices, where hubs and edges with large weights are centers of localization. Our results follow from the analysis of standard models of networks and empirical data for real-world networks.