Percolation on Infinite Graphs and Isoperimetric Inequalities

We consider the Bernoulli bond percolation process (with parameter p) on infinite graphs and we give a general criterion for bounded degree graphs to exhibit a non-trivial percolation threshold based either on a single isoperimetric inequality if the graph has a bi-infinite geodesic, or two isoperimetric inequalities if the graph has not a bi-infinite geodesic. This new criterion extends previous criteria and brings together a large class of amenable graphs (such as regular lattices) and non-amenable graphs (such trees). We also study the finite connectivity in graphs satisfying the new general criterion and show that graphs in this class with a bi-infinite geodesic always have finite connectivity functions with exponential decay when p is sufficiently close to one. On the other hand, we show that there are graphs in the same class with no bi-infinite geodesic for which the finite connectivity decays sub-exponentially (down to polynomially) in the highly supercritical phase even for p arbitrarily close to one.     

Percolation in self-similar networks

We provide a simple proof that graphs in a general class of self-similar networks have zero percolation threshold. The considered self-similar networks include random scale-free graphs with given expected node degrees and zero clustering, scale-free graphs with finite clustering and metric structure, growing scale-free networks, and many real networks. The proof and the derivation of the giant component size do not require the assumption that networks are treelike. Our results rely only on the observation that self-similar networks possess a hierarchy of nested subgraphs whose average degree grows with their depth in the hierarchy. We conjecture that this property is pivotal for percolation in networks.     

Multiplicity of Phase Transitions and Mean-Field Criticality on Highly Non-Amenable Graphs

We consider independent percolation, Ising and Potts models, and the contact process, on infinite, locally finite, connected graphs. It is shown that on graphs with edge-isoperimetric Cheeger constant sufficiently large, in terms of the degrees of the vertices of the graph, each of the models exhibits more than one critical point, separating qualitatively distinct regimes. For unimodular transitive graphs of this type, the critical behaviour in independent percolation, the Ising model and the contact process are shown to be mean-field type. For Potts models on unimodular transitive graphs, we prove the monotonicity in the temperature of the property that the free Gibbs measure is extremal in the set of automorphism invariant Gibbs measures, and show that the corresponding critical temperature is positive if and only if the threshold for uniqueness of the infinite cluster in independent bond percolation on the graph is less than 1. We establish conditions which imply the finite-island property for independent percolation at large densities, and use those to show that for a large class of graphs the q-state Potts model has a low temperature regime in which the free Gibbs measure decomposes as the uniform mixture of the q ordered phases. In the case of non-amenable transitive planar graphs with one end, we show that the q-state Potts model has a critical point separating a regime of high temperatures in which the free Gibbs measure is extremal in the set of automorphism-invariant Gibbs measures from a regime of low temperatures in which the free Gibbs measure decomposes as the uniform mixture of the q ordered phases. Received: 27 March 2000 / Accepted: 7 December 2000     

Complex networks renormalization: flows and fixed points

Recently, it has been claimed that some complex networks are self-similar under a convenient renormalization procedure. We present a general method to study renormalization flows in graphs. We find that the behavior of some variables under renormalization, such as the maximum number of connections of a node, obeys simple scaling laws, characterized by critical exponents. This is true for any class of graphs, from random to scale-free networks, from lattices to hierarchical graphs. Therefore, renormalization flows for graphs are similar as in the renormalization of spin systems. An analysis of classic renormalization for percolation and the Ising model on the lattice confirms this analogy. Critical exponents and scaling functions can be used to classify graphs in universality classes, and to uncover similarities between graphs that are inaccessible to a standard analysis.     

Some Exact Results on Bond Percolation

We present some exact results on bond percolation. We derive a relation that specifies the consequences for bond percolation quantities of replacing each bond of a lattice ?? by ? bonds connecting the same adjacent vertices, thereby yielding the lattice ?? _? . This relation is used to calculate the bond percolation threshold on ?? _? . We show that this bond inflation leaves the universality class of the percolation transition invariant on a lattice of dimensionality d??2 but changes it on a one-dimensional lattice and quasi-one-dimensional infinite-length strips. We also present analytic expressions for the average cluster number per vertex and correlation length for the bond percolation problem on the N???? limits of several families of N-vertex graphs. Finally, we explore the effect of bond vacancies on families of graphs with the property of bounded diameter as N????.     

Directed Dominating Set Problem Studied by Cavity Method: Warning Propagation and Population Dynamics

The minimal dominating set for a digraph (directed graph) is a prototypical hard combinatorial optimization problem. In a previous paper, we studied this problem using the cavity method. Although we found a solution for a given graph that gives very good estimate of the minimal dominating size, we further developed the one step replica symmetry breaking theory to determine the ground state energy of the undirected minimal dominating set problem. The solution space for the undirected minimal dominating set problem exhibits both condensation transition and cluster transition on regular random graphs. We also developed the zero temperature survey propagation algorithm on undirected Erdös-Rényi graphs to find the ground state energy. In this paper we continue to develope the one step replica symmetry breaking theory to find the ground state energy for the directed minimal dominating set problem. We find the following. (i) The warning propagation equation can not converge when the connectivity is greater than the core percolation threshold value of 3.704. Positive edges have two types warning, but the negative edges have one. (ii) We determine the ground state energy and the transition point of the Erdös-Rényi random graph. (iii) The survey propagation decimation algorithm has good results comparable with the belief propagation decimation algorithm.     

Network robustness and fragility: percolation on random graphs

Recent work on the Internet, social networks, and the power grid has addressed the resilience of these networks to either random or targeted deletion of network nodes or links. Such deletions include, for example, the failure of Internet routers or power transmission lines. Percolation models on random graphs provide a simple representation of this process but have typically been limited to graphs with Poisson degree distribution at their vertices. Such graphs are quite unlike real-world networks, which often possess power-law or other highly skewed degree distributions. In this paper we study percolation on graphs with completely general degree distribution, giving exact solutions for a variety of cases, including site percolation, bond percolation, and models in which occupation probabilities depend on vertex degree. We discuss the application of our theory to the understanding of network resilience.     

Sharpness of the Phase Transition and Exponential Decay of the Subcritical Cluster Size for Percolation on Quasi-Transitive Graphs

We study homogeneous, independent percolation on general quasi-transitive graphs. We prove that in the disorder regime where all clusters are finite almost surely, in fact the expectation of the cluster size is finite. This extends a well-known theorem by Menshikov and Aizenman & Barsky to all quasi-transitive graphs. Moreover we deduce that in this disorder regime the cluster size distribution decays exponentially, extending a result of Aizenman & Newman. Our results apply to both edge and site percolation, as well as long range (edge) percolation. The proof is based on a modification of the Aizenman & Barsky method.     

Percolation threshold on planar Euclidean Gabriel graphs

In the present article, numerical simulations have been performed to find the bond andsite percolation thresholds on two-dimensional Gabriel graphs (GG) for Poisson pointprocesses. GGs belong to the family of “proximity graphs” and are discussed, e.g., incontext of the construction of backbones for wireless ad-hoc networks. Finite-size scalinganalyses have been performed to find the critical points and critical exponentsν,β andγ. Thecritical exponents obtained this way verify that the associated universality class is thatof standard 2Dpercolation.     

Uniform Existence of the Integrated Density of States for Randomly Weighted Hamiltonians on Long-Range Percolation Graphs

We consider random Hamiltonians defined on long-range percolation graphs over $\mathbb {Z}^{d}$ . The Hamiltonian consists of a randomly weighted Laplacian plus a random potential. We prove uniform existence of the integrated density of states and express the IDS using a Pastur-Shubin trace formula.     

Percolation of entropy functionals on cayley tree graphs as a method of order-disorder character diagnostics of complex structures

The problem of long-range action identification of classical quartet, honeycomb, and simplex lattices and bihexagonal Duneau-Katz lattice has been solved. The percolation problem is considered in terms of entropy functional on Cayley tree graphs. Long-range order is described not only by hyperbolic percolation entropy dependence with γ ≤ 1 and zero-order asymptotic entropy; the residual entropy of system ordering can also be observed in some cases.     

Busemann Functions and Infinite Geodesics in Two-Dimensional First-Passage Percolation

We study first-passage percolation on ${\mathbb{Z}^2}$ , where the edge weights are given by a translation-ergodic distribution, addressing questions related to existence and coalescence of infinite geodesics. Some of these were studied in the late 1990s by C. Newman and collaborators under strong assumptions on the limiting shape and weight distribution. In this paper we develop a framework for working with distributional limits of Busemann functions and use it to prove forms of Newman’s results under minimal assumptions. For instance, we show a form of coalescence of long finite geodesics in any deterministic direction. We also introduce a purely directional condition which replaces Newman’s global curvature condition and whose assumption we show implies the existence of directional geodesics. Without this condition, we prove existence of infinite geodesics which are directed in sectors. Last, we analyze distributional limits of geodesic graphs, proving almost-sure coalescence and nonexistence of infinite backward paths. This result relates to the conjecture of nonexistence of “bigeodesics.”     

Uniform Approximation of the Integrated Density of States for Long-Range Percolation Hamiltonians

In this paper we study the spectrum of long-range percolation graphs. The underlying geometry is given in terms of a finitely generated amenable group. We prove that the integrated density of states (IDS) or spectral distribution function can be approximated uniformly in the energy variable. This result is already new for percolation on ℤ ^d . Using this, we are able to characterize the set of discontinuities of the IDS.     

The Ising model and percolation on trees and tree-like graphs

We calculate the exact temperature of phase transition for the Ising model on an arbitrary infinite tree with arbitrary interaction strengths and no external field. In the same setting, we calculate the critical temperature for spin percolation. The same problems are solved for the diluted models and for more general random interaction strengths. In the case of no interaction, we generalize to percolation on certain tree-like graphs. This last calculation supports a general conjecture on the coincidence of two critical probabilities in percolation theory.Research partially supported by an NSF Mathematical Sciences Postdoctoral Research Fellowship     

Boolean Percolation on Doubling Graphs

Journal of Statistical Physics - We consider the discrete Boolean model of percolation on weighted graphs satisfying a doubling metric condition. We study sufficient conditions on the distribution...     

Exakte Lösungen von Low-Gleichungen

The general solution of the Low equation for a family of two-dimensional crossingmatrices is constructed. It depends on 2 arbitrary functions and its Riemann surface has an infinity of distinct sheets. Furthermore a subclass of solutions of the 3dimensional and 4dimensional pseudoscalar symmetricπ-N scattering theory is constructed, the former depending on 2 arbitrary functions, the latter on 3. The criterion of minimal zeros in the scattering functions on the physical sheet is applied, to restrict this manyfold. In the threedimensional case the restricted solution depends on 2 parameters which may be interpreted as “coupling constant” and “cut off”. In the 4dimensional case the criterion of minimal zeros in the scattering functions gives a solution which depends on 5 parameters and thus is not uniquely determined by a “coupling constant” and a “cut off”.     

Large-deviation properties of largest component for random graphs

Distributions of the size of the largest component, in particular the large-deviationtail, are studied numerically for two graph ensembles, for Erdös-Rényi random graphs withfinite connectivity and for two-dimensional bond percolation. Probabilities as small as10^-180 are accessed using an artificial finite-temperature (Boltzmann)ensemble. The distributions for the Erdös-Rényi ensemble agree well with previouslyobtained analytical results. The results for the percolation problem, where no analyticalresults are available, are qualitatively similar, but the shapes of the distributions aresomehow different and the finite-size corrections are sometimes much larger. Furthermore,for both problems, a first-order phase transition at low temperatures Twithin the artificial ensemble is found in the percolating regime, respectively.     

Clique percolation in random networks

The notion of k-clique percolation in random graphs is introduced, where k is the size of the complete subgraphs whose large scale organizations are analytically and numerically investigated. For the Erdos-Rényi graph of N vertices we obtain that the percolation transition of k-cliques takes place when the probability of two vertices being connected by an edge reaches the threshold p(c) (k) = [(k - 1)N](-1/(k - 1)). At the transition point the scaling of the giant component with N is highly nontrivial and depends on k. We discuss why clique percolation is a novel and efficient approach to the identification of overlapping communities in large real networks.     

The High Temperature Ising Model on the Triangular Lattice is a Critical Bernoulli Percolation Model

We define a new percolation model by generalising the FK representation of the Ising model, and show that on the triangular lattice and at high temperatures, the critical point in the new model corresponds to the Ising model. Since the new model can be viewed as Bernoulli percolation on a random graph, our result makes an explicit connection between Ising percolation and critical Bernoulli percolation, and gives a new justification of the conjecture that the high temperature Ising model on the triangular lattice is in the same universality class as Bernoulli percolation.     

Penrose tiling fractality in coordination Cayley’s tree graphs representation

We offer the mathematical apparatus for mapping lattice and cellular systems into the generalized coordination Cayley’s tree graphs. These Cayley’s trees have a random branchiness property and an intralayer interbush local intersection. Classical Bethe-Cayley tree graphs don’t have these properties. Bush type simplicial decomposition on Cayley’s tree graphs is introduced, on which the enumerating polynomials or enumerating distributions are built. Within the entropy methodology three types of fractal characteristics are introduced, which characterize quasi-crystalline pentagonal Penrose tiling. The quantitative estimate for the frontal-radial fractal percolation on a Cayley’s tree graph of a Penrose tiling leading to the overdimensioned effect is calculated.