Exactly solvable models of adaptive networks

A satisfiability-unsatisfiability (SAT-UNSAT) transition takes place for many optimization problems when the number of constraints, graphically represented by links between variables nodes, is brought above some threshold. If the network of constraints is allowed to adapt by redistributing its links, the SAT-UNSAT transition may be delayed and preceded by an intermediate phase where the structure self-organizes to satisfy the constraints. We present an analytic approach, based on the recently introduced cavity method for large deviations, which exactly describes the two phase transitions delimiting this adaptive intermediate phase. We give explicit results for random bond models subject to the connectivity or rigidity percolation transitions, and compare them with numerical simulations.     

Freezing and microphase separation in random copolymers

Summary A two-letter random copolymer with attraction between similar monomers and repulsion between different ones is investigated using the replica method. This type of interactions favors microphase separation (MPS) in a compact state of a polymer or in a melt. Frustrations between interactions and polymeric bonds may lead to freezing transition in a phase where only a few conformations dominate and replica symmetry is broken. Our analysis reveals that stiff polymers have a frozen phase and do not undergo transition to a phase with microdomain structure. In flexible polymers the microphase transition may occur before freezing. A complete phase diagram showing the interplay between the two phase transitions is constructed for the two-letter random copolymer. Paper presented at the I International Conference on Scaling Concepts and Complex Fluids, Copanello, Italy, July 4–8, 1994.     

On the Freezing of Variables in Random Constraint Satisfaction Problems

The set of solutions of random constraint satisfaction problems (zero energy groundstates of mean-field diluted spin glasses) undergoes several structural phase transitions as the amount of constraints is increased. This set first breaks down into a large number of well separated clusters. At the freezing transition, which is in general distinct from the clustering one, some variables (spins) take the same value in all solutions of a given cluster. In this paper we introduce and study a message passing procedure that allows to compute, for generic constraint satisfaction problems, the sizes of the rearrangements induced in response to the modification of a variable. These sizes diverge at the freezing transition, with a critical behavior which is also investigated in details. We apply the generic formalism in particular to the random satisfiability of boolean formulas and to the coloring of random graphs. The computation is first performed in random tree ensembles, for which we underline a connection with percolation models and with the reconstruction problem of information theory. The validity of these results for the original random ensembles is then discussed in the framework of the cavity method.     

Erdös Rényi随机网络上爆炸渗流模型相变性质的数值模拟研究

基于改进的Newman和Ziff算法以及有限尺寸标度理论, 通过对表征渗流相变特征物理量的序参量、平均集团尺寸、二阶矩、标准偏差及尺寸不均匀性的数值模拟, 分析研究了Erdös Rényi随机网络上Achlioptas爆炸渗流模型的相变性质.研究表明: 尽管序参量表现出了不连续相变的特征, 但序参量以及其他特征物理量仍具有连续相变的幂律标度行为.因此严格地说, Erdös Rényi随机网络中的爆炸渗流相变是一种奇异相变, 它既不是标准的不连续相变, 又与常规随机渗流表现出的连续相变处于不同的普适类. 关键词： Erdös Rényi随机网络 爆炸渗流模型 相变 幂律标度行为     

Hiding solutions in random satisfiability problems: a statistical mechanics approach

A major problem in evaluating stochastic local search algorithms for NP-complete problems is the need for a systematic generation of hard test instances having previously known properties of the optimal solutions. On the basis of statistical mechanics results, we propose random generators of hard and satisfiable instances for the 3-satisfiability problem. The design of the hardest problem instances is based on the existence of a first order ferromagnetic phase transition and the glassy nature of excited states. The analytical predictions are corroborated by numerical results obtained from complete as well as stochastic local algorithms.     

Risk minimization through portfolio replication

We use a replica approach to deal with portfolio optimization problems. A given risk measure is minimized using empirical estimates of asset values correlations. We study the phase transition which happens when the time series is too short with respect to the size of the portfolio. We also study the noise sensitivity of portfolio allocation when this transition is approached. We consider explicitely the cases where the absolute deviation and the conditional value-at-risk are chosen as a risk measure. We show how the replica method can study a wide range of risk measures, and deal with various types of time series correlations, including realistic ones with volatility clustering.     

随机化的Eigen模型研究

为了使Eigen模型能够更真实地描述物种的演化过程,将确定性Eigen模型改造成随机模型.以Eigen模型为理论框架,把基因序列中每一个位点的突变率看作一个高斯随机变量,从而导出随机性Eigen模型.对于此随机性Eigen模型,当突变率的涨落强度较小时,准物种的误差阈位置几乎没有改变,仍是个相变点;而当突变率的涨落强度变大时,误差阈由一个相变点变为一个转变区域.在真实的物种演化过程中,误差阈应是一个转变区域,而且在解决实际问题时应考虑该转变区域的上限.     

Partially Observed Markov Random Fields Are Variable Neighborhood Random Fields

The present paper has two goals. First to present a natural example of a new class of random fields which are the variable neighborhood random fields. The example we consider is a partially observed nearest neighbor binary Markov random field. The second goal is to establish sufficient conditions ensuring that the variable neighborhoods are almost surely finite. We discuss the relationship between the almost sure finiteness of the interaction neighborhoods and the presence/absence of phase transition of the underlying Markov random field. In the case where the underlying random field has no phase transition we show that the finiteness of neighborhoods depends on a specific relation between the noise level and the minimum values of the one-point specification of the Markov random field. The case in which there is phase transition is addressed in the frame of the ferromagnetic Ising model. We prove that the existence of infinite interaction neighborhoods depends on the phase.     

Phase Transition and Critical Behavior for XY Model on 2-Dimensional Random Triangle Lattice

The Monte Carlo renormalization group method is applied to discussing the nature of phase transition of XY model on 2-dimensional random triangle lattices. A line of fixed point and un-universal phase transition are found. The results are in agreement with Kosterlitz-Thouless theory. The susceptibility ehows a clear size-dependent behaviorin low temperature region. This means that it should be divergent in this region.     

Isotropic phase of nematics in porous media

We study the effect of random porous matrices on the isotropic-nematic phase transition. Sufficiently close to the cleaning temperature, both random field and thermal fluctuations are important as disordering agents. A novel random field fixed point of the renormalization group equation was found that controls the transition from isotropic to the replica symmetric phase. Explicit evaluation of the exponents in d = 6 ? ε dimensions yields to a dimensional reduction and three-exponent scaling.     

Phase Transitions in Self-Driven Many-Particle Systems and Related Non-Equilibrium Models: A Network Approach

We investigate the conditions that produce a phase transition from an ordered to a disordered state in a family of models of two-dimensional elements with a ferromagnetic-like interaction. This family is defined to contain under the same framework, among others, the XY-model and the Self-Driven Particles Model introduced by Vicsek et al. Each model is distinguished only by the rules that determine the set of elements with which each element interacts. We propose a new member of the family: the vectorial network model, in which a given fraction of the elements interact through direct random connections. This model is analogous to an XY-system on a network, and as such can be of interest for a wide range of problems. It captures the main aspects of the interaction dynamics that produce the phase transition in other models of the family. The network approach allows us to show analytically the existence of a phase transition in this vectorial network model, and to compute its relevant parameters for the case in which all elements are randomly connected. Finally we study numerically the conditions required for a phase transition to exist for different members of the family. Our results show that a qualitatively equivalent phase transition appears whenever even a small amount of long-range interactions are present (or built over time), regardless of other equilibrium or non-equilibrium properties of the system.     

Comparative study of liquid-crystalline ordering in a monomer,linear polymer,and graft copolymer by the photon transmission technique

The photon transmission technique was used to study the phase transitions of a liquid crystalline acrylate monomer, 6-(4-cyanobiphenyl-4′oxy)hexyl acrylate (LC6), its homopolymer (PLC6) and its graft copolymer (GLC6) with polytetrahydrofuran grafts. The phase transitions were also confirmed by DSC and polarizing microscopy. We observed the phase transition sequence isotropic–nematic–smectic A–smectic C in the LC6 monomer. In PLC6 and GLC6 polymers, the nematic and smectic A phases appear dominant. The apparent nematic–smectic A transition is of first order in PLC6 and of second order in GLC6, with the transition temperature remaining the same. The effects of quenched random constraints introduced in GLC6 are consistent with the theory of quenched random interactions. The critical exponents were also evaluated.     

Locally ordered regions in the phase transition in the systems with a finite-range correlated quenched disorder

The locally ordered regions (LOR) in the phase transition in disordered systems are studied. There are two parts in this paper. One part is to report our numerical results on the one-dimensional saddle point equation of the Ginzburg-Landau Hamiltonian with random temperature in the presence of an ordering field. The disordered system is modelled as a lattice, on which each cell has a local reduced temperature. The random part of the local reduced temperature is distributed in the Gaussian form. The one-dimensional saddle point equation is solved numerically. The average, the fluctuation and the correlation length of the solution are calculated. The scaling relations for these quantities with the temperature, the ordering field and the disorder strength are derived. The numerical data are fitted with the scaling relations well. Another part is to discuss qualitatively the phase diagram of the finite-range correlated disordered systems. There are two proposed classes for the phase transition in connection with the LOR. One class is described by the percolative scenario, in which the phase transition is inhomogeneous. In the percolative scenario the percolation of the LOR dominates the phase transition. In another class, the phase transition is homogeneous, and can be described by the renormalization group (RG) with replica symmetry breaking (RSB). In the RG with RSB, there is nothing to do with the percolation of LOR. We shall show that these two theories, which seem contradictory, may describe two parts of the whole phase diagram. Whether the phase transition is homogeneous or inhomogeneous depends on the interaction between the LOR. If the interaction between the LOR is strong enough, the phase transition is percolative and inhomogeneous. If the interaction between the LOR is weak, the phase transition is homogeneous. The interaction between the LOR is discussed with the numerical solution on the saddle point equation.     

From Continuous to First Order Phase Transition in a Generalized XY Model

A generalized XY model with interaction V(θ) = 2 J{1 - [cos² (θ/2)]^p2} is studied by Monte Carlo renormalization group method on two-dimensional random triangle lattice. For p = √2, a line of fixed points has been found. It characterizes that there is a Kosterlitz-Thouless phase transition. For p = 2, a first order phase transition has been found. Both of them show the relationship between the nature of phase transition and the class of interactions.     

Dynamical simulations on the two-dimensional XY model with random-phase shift

Using resistively-shunted-junction dynamics, we numerically investigate the two-dimensional XY model with random phase shift. The critical temperatures and critical exponents are determined by dynamic scaling analysis. For weak disorder strengths, the system undergoes a Kosterlitz-Thouless (KT). A non-KT type phase transition is also observed for strong disorders. A genuine continuous depinning transition at zero temperature and creep motion at low temperature are also studied for various disorder strengths. The relevant critical currents and critical exponents are evaluated, and a non-Arrhenius creep motion is observed in the low temperature phases.     

On the bethe approximation for the random bond Ising model

A random bond Ising model is considered in terms of the pair approximation, which is equivalent to the Bethe approximation, of the cluster variation method. On taking the configurational average over the random distribution of bonds ±J, we take into account the nearest neighbor correlations between effective fields and bonds. We investigate their effects to the phase transition temperature from the paramagnetic phase to the ferro- (or antiferro-) magnetic phase and to the spin glass phase for the Ising model on the square lattice. It turns out that the correlation effects act favorably to the spin glass phase and bend upward the line of transition temperature from the paramagnetic phase to the spin glass phase as the concentration being apart from 0.5. In the appendix, we derive the expression of free energy in the weak interaction limit.     

Large deviations for multiplicative chaos

The local singularities for a class of random measures, obtained by random iterated multiplications, are investigated using the thermodynamic formalism. This analysis can be interpreted as a rigorous study of the phase transition of a system with random interactions.Partially supported by SCIENCE grant CT000307UPR A014 du CNRS     

Driven spin wave modes in XY ferromagnet: non-equilibrium phase transition

The dynamical responses of XY ferromagnet driven by linearly polarised propagating and standing magnetic field wave have been studied by Monte Carlo simulation in three dimensions. In the case of propagating magnetic field wave (with specified amplitude, frequency and the wavelength), the low temperature dynamical mode is a propagating spin wave and the system becomes structureless (or random) in the high temperature. A dynamical symmetry breaking phase transition is observed at a finite (non-zero) temperature. This symmetry breaking is confirmed by studying the statistical distribution of the angle of the spin vector. The dynamic non-equilibrium transition temperature was found to decrease as the amplitude of the propagating magnetic field wave increased. A comprehensive phase boundary is drawn in the plane formed by temperature and amplitude of propagating field wave. The phase boundary was observed to shrink (in the low temperature side) for longer wavelength of the propagating magnetic wave. In the case of standing magnetic field wave, the low temperature excitation is a standing spin wave which becomes structureless (or random) in the high temperature. Here also, like the case of propagating magnetic wave, a dynamical symmetry breaking non-equilibrium phase transition was observed. A comprehensive phase boundary was drawn. Unlike the case of propagating magnetic wave, the phase boundary does not show any systematic variation with the wavelength of the standing magnetic field wave. In the limit of vanishingly small amplitude of the field, the phase boundaries approach the recent Monte Carlo estimate of equilibrium transition temperature.     

The crumpling transition of crystalline random surfaces

We investigate the crumpling transition in two different models of crystalline random surfaces with extrinsic curvature which have recently caused some confusion and find that many of the results previously obtained are erroneous. Using the Fourier acceleration technique to ameliorate critical slowing down problems we have made numerical simulations of surfaces of up to 128² points embedded in three dimensions. The first model, which has a non-compact lattice version of the extrinsic curvature, suffers from a sickness in the non-crumpled phase which is a lattice artefact; it is smooth in one intrinsic direction and folded up on the scale of the lattice spacing in the other, so we call this phase corrugated. The crumpling transition is continuous, having a diverging persistence length with critical exponent v = 1.15 ± 0.15 and a cusp in the specific heat indicating that 0. The second model, in which the extrinsic curvature depends upon the cosine of the angle between normals of adjacent triangles, also has a continuous transition with v = 0.94 ± 0.20 and = 0.53 ± 0.15. Just beyond the crumpling transition, the smooth phase is found to have Hausdorff dimension d_H < 2.14 at two standard deviations and so we conclude that d_H = 2 throughout this phase. A study of the correlation functions shows that, in the crumpled phase, the system is apparently described by a very simple gaussian action. If true, this result could have important implications which we discuss briefly.     

Critical Phenomena in Exponential Random Graphs

The exponential family of random graphs is one of the most promising class of network models. Dependence between the random edges is defined through certain finite subgraphs, analogous to the use of potential energy to provide dependence between particle states in a grand canonical ensemble of statistical physics. By adjusting the specific values of these subgraph densities, one can analyze the influence of various local features on the global structure of the network. Loosely put, a phase transition occurs when a singularity arises in the limiting free energy density, as it is the generating function for the limiting expectations of all thermodynamic observables. We derive the full phase diagram for a large family of 3-parameter exponential random graph models with attraction and show that they all consist of a first order surface phase transition bordered by a second order critical curve.