The phase transition in inhomogeneous random graphs

The “classical” random graph models, in particular G(n,p), are “homogeneous,” in the sense that the degrees (for example) tend to be concentrated around a typical value. Many graphs arising in the real world do not have this property, having, for example, power‐law degree distributions. Thus there has been a lot of recent interest in defining and studying “inhomogeneous” random graph models. One of the most studied properties of these new models is their “robustness”, or, equivalently, the “phase transition” as an edge density parameter is varied. For G(n,p), p = c/n, the phase transition at c = 1 has been a central topic in the study of random graphs for well over 40 years. Many of the new inhomogeneous models are rather complicated; although there are exceptions, in most cases precise questions such as determining exactly the critical point of the phase transition are approachable only when there is independence between the edges. Fortunately, some models studied have this property already, and others can be approximated by models with independence. Here we introduce a very general model of an inhomogeneous random graph with (conditional) independence between the edges, which scales so that the number of edges is linear in the number of vertices. This scaling corresponds to the p = c/n scaling for G(n,p) used to study the phase transition; also, it seems to be a property of many large real‐world graphs. Our model includes as special cases many models previously studied. We show that, under one very weak assumption (that the expected number of edges is “what it should be”), many properties of the model can be determined, in particular the critical point of the phase transition, and the size of the giant component above the transition. We do this by relating our random graphs to branching processes, which are much easier to analyze. We also consider other properties of the model, showing, for example, that when there is a giant component, it is “stable”: for a typical random graph, no matter how we add or delete o(n) edges, the size of the giant component does not change by more than o(n). © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 31, 3–122, 2007     

The phase transition in random graphs: A simple proof

The classical result of Erd?s and Rényi asserts that the random graph G(n,p) experiences sharp phase transition around \begin{align*}p=\frac{1}{n}\end{align*} – for any ε > 0 and \begin{align*}p=\frac{1-\epsilon}{n}\end{align*}, all connected components of G(n,p) are typically of size O_ε(log n), while for \begin{align*}p=\frac{1+\epsilon}{n}\end{align*}, with high probability there exists a connected component of size linear in n. We provide a very simple proof of this fundamental result; in fact, we prove that in the supercritical regime \begin{align*}p=\frac{1+\epsilon}{n}\end{align*}, the random graph G(n,p) contains typically a path of linear length. We also discuss applications of our technique to other random graph models and to positional games. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

The phase transition in the cluster‐scaled model of a random graph

For 0 < p < 1 and q > 0 let G_q(n,p) denote the random graph with vertex set [n]={1,…,n} such that, for each graph G on [n] with e(G) edges and c(G) components, the probability that G_q(n,p)=G is proportional to . The first systematic study of G_q(n,p) was undertaken by 6 , who analyzed the phase transition phenomenon corresponding to the emergence of the giant component. In this paper we describe the structure of G_q(n,p) very close the critical threshold. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

A continuous–discontinuous second‐order transition in the satisfiability of random Horn‐SAT formulas

We compute the probability of satisfiability of a class of random Horn‐SAT formulae, motivated by a connection with the nonemptiness problem of finite tree automata. In particular, when the maximum clause length is three, this model displays a curve in its parameter space, along which the probability of satisfiability is discontinuous, ending in a second‐order phase transition where it is continuous but its derivative diverges. This is the first case in which a phase transition of this type has been rigorously established for a random constraint satisfaction problem. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

Biased positional games and the phase transition

Let 𝔏(n, q) be the game in which two players, Maker and Breaker, alternately claim 1 and q edges of the complete graph K_n, respectively. Maker's goal is to maximize the number of vertices in the largest component of his graph; Breaker tries to make it as small as possible. Let L(n,q) denote the size of the largest component in Maker's graph when both players follow their optimal strategies. We study the behavior of L(n, q) for large n and q=q(n). In particular, we show that the value of L(n, q) abruptly changes for q∼n and discuss the differences between this phenomenon and a similar one, which occurs in the evolution of random graphs. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 18: 141–152, 2001     

Merging percolation on Zd and classical random graphs: Phase transition

We study a random graph model which is a superposition of bond percolation on Z^d with parameter p, and a classical random graph G(n,c/n). We show that this model, being a homogeneous random graph, has a natural relation to the so‐called “rank 1 case” of inhomogeneous random graphs. This allows us to use the newly developed theory of inhomogeneous random graphs to describe the phase diagram on the set of parameters c ≥ 0 and 0 ≤ p < p_c, where p_c = p_c(d) is the critical probability for the bond percolation on Z^d. The phase transition is of second order as in the classical random graph. We find the scaled size of the largest connected component in the supercritical regime. We also provide a sharp upper bound for the largest connected component in the subcritical regime. The latter is a new result for inhomogeneous random graphs with unbounded kernels. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2010     

Phase transition of the minimum degree random multigraph process

We study the phase transition of the minimum degree multigraph process. We prove that for a constant h_g ≈︁ 0.8607, with probability tending to 1 as n → ∞, the graph consists of small components on O(log n) vertices when the number of edges of a graph generated so far is smaller than h_gn, the largest component has order roughly n^2/3 when the number of edges added is exactly h_gn, and the graph consists of one giant component on Θ(n) vertices and small components on O(log n) vertices when the number of edges added is larger than h_gn. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

THE ANALYTICAL PROPERTIES FOR HOMOGENEOUS RANDOM TRANSITION FUNCTIONS

The concepts of Markov process in random environment and homogeneous random transition functions are introduced. The necessary and sufficient conditions for homogeneous random transition function are given. The main results in this article are the analytical properties, such as continuity, differentiability, random Kolmogorov backward equation and random Kolmogorov forward equation of homogeneous random transition functions.     

Diameter, connectivity, and phase transition of the uniform random intersection graph

We study properties of the uniform random intersection graph model G(n,m,d). We find asymptotic estimates on the diameter of the largest connected component of the graph near the phase transition and connectivity thresholds. Moreover we manage to prove an asymptotically tight bound for the connectivity and phase transition thresholds for all possible ranges of d, which has not been obtained before. The main motivation of our research is the usage of the random intersection graph model in the studies of wireless sensor networks.     

Model investigation of non-thermal phase transition in high energy collisions

The non-thermal phase transition in high energy collisions is studied in detail in the framework of random cascade model. The relation between the characteristic parameter A_p, of phase transition and the rank q of moment is obtained using Monte Carlo simulation, and the existence of two phases in self-similar cascading multiparticle systems is shown. The relation between the critical point qc of phase transition on the fluctuation parameter a is obtained and compared with the experimental results from NA22. The same study is carried out also by analytical calculation under central limit approximation. The range of validity of the central limit approximation is discussed.     

Phase transition for SIR model with random transition rates on complete graphs

We are concerned with the susceptible-infective-removed (SIR) model with random transition rates on complete graphs C _n with n vertices. We assign independent and identically distributed (i.i.d.) copies of a positive random variable ξ on each vertex as the recovery rates and i.i.d. copies of a positive random variable ρ on each edge as the edge infection weights. We assume that a susceptible vertex is infected by an infective one at rate proportional to the edge weight on the edge connecting these two vertices while an infective vertex becomes removed with rate equals the recovery rate on it, then we show that the model performs the following phase transition when at t = 0 one vertex is infective and others are susceptible. There exists λ _c > 0 such that when λ < λ _c ; the proportion r∞ of vertices which have ever been infective converges to 0 weakly as n → +∞ while when λ > λ _c ; there exist c(λ) > 0 and b(λ) > 0 such that for each n ≥ 1 with probability p ≥ b(λ); the proportion r_∞ ≥ c(λ): Furthermore, we prove that λ _c is the inverse of the production of the mean of ρ and the mean of the inverse of ξ.     

The critical behavior of random digraphs

We study the critical behavior of the random digraph D(n,p) for np = 1 + ε, where ε = ε(n) = o(1). We show that if ε³n →—∞, then a.a.s. D(n,p) consists of components which are either isolated vertices or directed cycles, each of size O_p(|ε|^?1). On the other hand, if ε³n →∞, then a.a.s. the structure of D(n,p) is dominated by the unique complex component of size (4 + o(1))ε²n, whereas all other components are of size O_p(ε^?1). © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

Degenerate random environments

We consider connectivity properties of certain i.i.d. random environments on , where at each location some steps may not be available. Site percolation and oriented percolation are examples of such environments. In these models, one of the quantities most often studied is the (random) set of vertices that can be reached from the origin by following a connected path. More generally, for the models we consider, multiple different types of connectivity are of interest, including: the set of vertices that can be reached from the origin; the set of vertices from which the origin can be reached; the intersection of the two. As with percolation models, many of the models we consider admit, or are expected to admit phase transitions. Among the main results of the paper is a proof of the existence of phase transitions for some two‐dimensional models that are non‐monotone in their underlying parameter, and an improved bound on the critical value for oriented site percolation on the triangular lattice. The connectivity of the random directed graphs provides a foundation for understanding the asymptotic properties of random walks in these random environments, which we study in a second paper. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 45, 111–137, 2014     

A phase transition in the random transposition random walk

Our work is motivated by Bourque and Pevzner's (2002) simulation study of the effectiveness of the parsimony method in studying genome rearrangement, and leads to a surprising result about the random transposition walk on the group of permutations on n elements. Consider this walk in continuous time starting at the identity and let D _t be the minimum number of transpositions needed to go back to the identity from the location at time t. D _t undergoes a phase transition: the distance D _{cn /2}∼u(c)n, where u is an explicit function satisfying u(c)=c/2 for c≤1 and u(c)<c/2 for c>1. In addition, we describe the fluctuations of D _{cn /2} about its mean in each of the three regimes (subcritical, critical and supercritical). The techniques used involve viewing the cycles in the random permutation as a coagulation-fragmentation process and relating the behavior to the Erdős-Renyi random graph model.     

Sparse random graphs with clustering

In 2007, we introduced a general model of sparse random graphs with (conditional) independence between the edges. The aim of this article is to present an extension of this model in which the edges are far from independent, and to prove several results about this extension. The basic idea is to construct the random graph by adding not only edges but also other small graphs. In other words, we first construct an inhomogeneous random hypergraph with (conditionally) independent hyperedges, and then replace each hyperedge by a (perhaps complete) graph. Although flexible enough to produce graphs with significant dependence between edges, this model is nonetheless mathematically tractable. Indeed, we find the critical point where a giant component emerges in full generality, in terms of the norm of a certain integral operator, and relate the size of the giant component to the survival probability of a certain (non‐Poisson) multi‐type branching process. While our main focus is the phase transition, we also study the degree distribution and the numbers of small subgraphs. We illustrate the model with a simple special case that produces graphs with power‐law degree sequences with a wide range of degree exponents and clustering coefficients. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 38, 269–323, 2011     

Layer dynamics and phase transition for non-linear thermoviscoelasticity

In this article, we study the dynamics of transition layers for a system of 1D non-linear thermoviscoelasticity with non-monotone stress–strain relation.     

Numerical study of phase transition in thermoviscoelasticity

We study the spatially periodic problem of thermoviscoelasticity with non-monotone structure relations. By pseudo-spectral method, we demonstrate numerically phase transitions for certain symmetric initial data. Without symmetry, the simulations show that a translation occurs for the phase boundary.     

A random walk with a branching system in random environments

We consider a branching random walk in random environments, where the particles are reproduced as a branching process with a random environment (in time), and move independently as a random walk on Z with a random environment (in locations). We obtain the asymptotic properties on the position of the rightmost particle at time n, revealing a phase transition phenomenon of the system.     

Large deviations and phase transition for random walks in random nonnegative potentials

We establish large deviation principles and phase transition results for both quenched and annealed settings of nearest-neighbor random walks with constant drift in random nonnegative potentials on Z^d${\mathbb{Z}}^d$. We complement the analysis of M.P.W. Zerner [Directional decay of the Green’s function for a random nonnegative potential on Z^d${\mathbb{Z}}^d$, Ann. Appl. Probab. 8 (1996) 246–280], where a shape theorem on the Lyapunov functions and a large deviation principle in absence of the drift are achieved for the quenched setting.     

The phase transition and classification of critical points in the multistability chemical reactions

IntroductionThe multistability in chemical reaction has been paid much attention to at all timesll--3].As chemical multistability acts at the non-linear area, and its critical phenomenon is part ofnon-equilibrium statistical mechanics of non-linearity, we usually take the critical phenomenaand phase transition in the equilibrium thermodynamic for -reference when we discuss the critical phenomena and phase transition in non-linear systemsl'--6]. As we all know, Ehrenfest (see,for example, [7]) …