Percolation on correlated random networks

Percolation may explain efficiency, robustness, and economy of the brain

The brain consists of billions of neurons connected by ultra-dense synapses, showing remarkable efficiency, robust flexibility, and economy in information processing. It is generally believed that these advantageous properties are rooted in brain connectivity; however, direct evidence remains absent owing to technical limitations or theoretical vacancy. This research explores the origins of these properties in the largest yet brain connectome of the fruit fly. We reveal that functional connectivity formation in the brain can be explained by a percolation process controlled by synaptic excitation-inhibition (E/I) balance. By increasing the E/I balance gradually, we discover the emergence of these properties as byproducts of percolation transition when the E/I balance arrives at 3:7. As the E/I balance keeps increase, an optimal E/I balance 1:1 is unveiled to ensure these three properties simultaneously, consistent with previous in vitro experimental predictions. Once the E/I balance reaches over 3:2, an intrinsic limitation of these properties determined by static (anatomical) brain connectivity can be observed. Our work demonstrates that percolation, a universal characterization of critical phenomena and phase transitions, may serve as a window toward understanding the emergence of various brain properties.

A comparative analysis of link removal strategies in real complex weighted networks

In this report we offer the widest comparison of links removal (attack) strategies efficacy in impairing the robustness of six real-world complex weighted networks. We test eleven different link removal strategies by computing their impact on network robustness by means of using three different measures, i.e. the largest connected cluster (LCC), the efficiency (Eff) and the total flow (TF). We find that, in most of cases, the removal strategy based on the binary betweenness centrality of the links is the most efficient to disrupt the LCC. The link removal strategies based on binary-topological network features are less efficient in decreasing the weighted measures of the network robustness (e.g. Eff and TF). Removing highest weight links first is the best strategy to decrease the efficiency (Eff) in most of the networks. Last, we found that the removal of a very small fraction of links connecting higher strength nodes or of highest weight does not affect the LCC but it determines a rapid collapse of the network efficiency Eff and the total flow TF. This last outcome raises the importance of both to adopt weighted measures of network robustness and to focus the analyses on network response to few link removals.

Topological properties of hierarchical networks

Hierarchical networks are attracting a renewal interest for modeling the organization of a number of biological systems and for tackling the complexity of statistical mechanical models beyond mean-field limitations. Here we consider the Dyson hierarchical construction for ferromagnets, neural networks, and spin glasses, recently analyzed from a statistical-mechanics perspective, and we focus on the topological properties of the underlying structures. In particular, we find that such structures are weighted graphs that exhibit a high degree of clustering and of modularity, with a small spectral gap; the robustness of such features with respect to the presence of thermal noise is also studied. These outcomes are then discussed and related to the statistical-mechanics scenario in full consistency. Last, we look at these weighted graphs as Markov chains and we show that in the limit of infinite size, the emergence of ergodicity breakdown for the stochastic process mirrors the emergence of metastabilities in the corresponding statistical mechanical analysis.

Cavity-based robustness analysis of interdependent networks: influences of intranetwork and internetwork degree-degree correlations

We develop a methodology for analyzing the percolation phenomena of two mutually coupled (interdependent) networks based on the cavity method of statistical mechanics. In particular, we take into account the influence of degree-degree correlations inside and between the networks on the network robustness against targeted (random degree-dependent) attacks and random failures. We show that the developed methodology is reduced to the well-known generating function formalism in the absence of degree-degree correlations. The validity of the developed methodology is confirmed by a comparison with the results of numerical experiments. Our analytical results indicate that the robustness of the interdependent networks depends on both the intranetwork and internetwork degree-degree correlations in a nontrivial way for both cases of random failures and targeted attacks.

Percolation of spatially constrained Erdős-Rényi networks with degree correlations

Motivated by experiments on activity in neuronal cultures [ J. Soriano, M. Rodríguez Martínez, T. Tlusty and E. Moses Proc. Natl. Acad. Sci. 105 13758 (2008)], we investigate the percolation transition and critical exponents of spatially embedded Erdős-Rényi networks with degree correlations. In our model networks, nodes are randomly distributed in a two-dimensional spatial domain, and the connection probability depends on Euclidian link length by a power law as well as on the degrees of linked nodes. Generally, spatial constraints lead to higher percolation thresholds in the sense that more links are needed to achieve global connectivity. However, degree correlations favor or do not favor percolation depending on the connectivity rules. We employ two construction methods to introduce degree correlations. In the first one, nodes stay homogeneously distributed and are connected via a distance- and degree-dependent probability. We observe that assortativity in the resulting network leads to a decrease of the percolation threshold. In the second construction methods, nodes are first spatially segregated depending on their degree and afterwards connected with a distance-dependent probability. In this segregated model, we find a threshold increase that accompanies the rising assortativity. Additionally, when the network is constructed in a disassortative way, we observe that this property has little effect on the percolation transition.

Parallel processing in immune networks

In this work, we adopt a statistical-mechanics approach to investigate basic, systemic features exhibited by adaptive immune systems. The lymphocyte network made by B cells and T cells is modeled by a bipartite spin glass, where, following biological prescriptions, links connecting B cells and T cells are sparse. Interestingly, the dilution performed on links is shown to make the system able to orchestrate parallel strategies to fight several pathogens at the same time; this multitasking capability constitutes a remarkable, key property of immune systems as multiple antigens are always present within the host. We also define the stochastic process ruling the temporal evolution of lymphocyte activity and show its relaxation toward an equilibrium measure allowing statistical-mechanics investigations. Analytical results are compared with Monte Carlo simulations and signal-to-noise outcomes showing overall excellent agreement. Finally, within our model, a rationale for the experimentally well-evidenced correlation between lymphocytosis and autoimmunity is achieved; this sheds further light on the systemic features exhibited by immune networks.

Percolation transitions with nonlocal constraint

We investigate percolation transitions in a nonlocal network model numerically. In this model, each node has an exclusive partner and a link is forbidden between two nodes whose r-neighbors share any exclusive pair. The r-neighbor of a node x is defined as a set of at most N(r) neighbors of x, where N is the total number of nodes. The parameter r controls the strength of a nonlocal effect. The system is found to undergo a percolation transition belonging to the mean-field universality class for r<1/2. On the other hand, for r>1/2, the system undergoes a peculiar phase transition from a nonpercolating phase to a quasicritical phase where the largest cluster size G scales as G~N(α) with α=0.74(1). In the marginal case with r=1/2, the model displays a percolation transition that does not belong to the mean-field universality class.

Organization and evolution of synthetic idiotypic networks

We introduce a class of weighted graphs whose properties are meant to mimic the topological features of idiotypic networks, namely, the interaction networks involving the B core of the immune system. Each node is endowed with a bit string representing the idiotypic specificity of the corresponding B cell, and the proper distance between any couple of bit strings provides the coupling strength between the two nodes. We show that a biased distribution of the entries in bit strings can yield fringes in the (weighted) degree distribution, small-world features, and scaling laws, in agreement with experimental findings. We also investigate the role of aging, thought of as a progressive increase in the degree of bias in bit strings, and we show that it can possibly induce mild percolation phenomena, which are investigated too.

Alternative criterion for two-dimensional wrapping percolation

Based on the difference between a spanning cluster and a wrapping cluster, an alternative criterion for testing wrapping percolation is provided for two-dimensional lattices. By following the Newman-Ziff method, the finite size scalings of estimates for percolation thresholds are given. The results are consistent with those from Machta's method.