Phase Transitions in Dynamical Random Graphs

We study a large-time limit of a Markov process whose states are finite graphs. The number of the vertices is described by a supercritical branching process, and the dynamics of edges is determined by the rates of appending and deleting. We find a phase transition in our model similar to the one in the random graph model G _n,p . We derive a formula for the line of critical parameters which separates two different phases: one is where the size of the largest component is proportional to the size of the entire graph, and another one, where the size of the largest component is at most logarithmic with respect to the size of the entire graph. In the supercritical phase we find the asymptotics for the size of the largest component.     

Causal Set Dynamics and Elementary Particles

A causal set is considered a finite, acyclic oriented graph with special restrictions: each vertex has two incident edges directed to this vertex and two incident edges directed from this vertex. This graph is called a causal graph. The vertex with incident edges is called an X-structure. Quantum measurements are discussed. A dynamics of the causal graph is a random sequence of elementary interactions of edges that is described by complex amplitudes. These amplitudes correspond to each pair of interacting edges. The edges are elementary particles. The mass of a particle is a probability of the interaction. An equation of particles is proposed. In a simple case this equation for X-structure is the Dirac's equation. The edges are fermions with the spin 1/2.     

Core percolation in random graphs: a critical phenomena analysis

We study both numerically and analytically what happens to a random graph of average connectivity α when its leaves and their neighbors are removed iteratively up to the point when no leaf remains. The remnant is made of isolated vertices plus an induced subgraph we call the core. In the thermodynamic limit of an infinite random graph, we compute analytically the dynamics of leaf removal, the number of isolated vertices and the number of vertices and edges in the core. We show that a second order phase transition occurs at α = e = 2.718 ... : below the transition, the core is small but above the transition, it occupies a finite fraction of the initial graph. The finite size scaling properties are then studied numerically in detail in the critical region, and we propose a consistent set of critical exponents, which does not coincide with the set of standard percolation exponents for this model. We clarify several aspects in combinatorial optimization and spectral properties of the adjacency matrix of random graphs. Received 31 January 2001 and Received in final form 26 June 2001     

Polynomial growth in branching processes with diverging reproductive number

We study the spreading dynamics on graphs with a power law degree distribution pk approximately k-gamma, with 2相似文献   

Network Models in Class C on Arbitrary Graphs

We consider network models of quantum localisation in which a particle with a two-component wave function propagates through the nodes and along the edges of an arbitrary directed graph, subject to a random SU(2) rotation on each edge it traverses. The propagation through each node is specified by an arbitrary but fixed S-matrix. Such networks model localisation problems in class C of the classification of Altland and Zirnbauer [1], and, on suitable graphs, they model the spin quantum Hall transition. We extend the analyses of Gruzberg, Ludwig and Read [5] and of Beamond, Cardy and Chalker [2] to show that, on an arbitrary graph, the mean density of states and the mean conductance may be calculated in terms of observables of a classical history-dependent random walk on the same graph. The transition weights for this process are explicitly related to the elements of the S-matrices. They are correctly normalised but, on graphs with nodes of degree greater than 4, not necessarily non-negative (and therefore interpretable as probabilities) unless a sufficient number of them happen to vanish. Our methods use a supersymmetric path integral formulation of the problem which is completely finite and rigorous.     

Local Statistics of Realizable Vertex Models

We study planar “vertex” models, which are probability measures on edge subsets of a planar graph, satisfying certain constraints at each vertex, examples including the dimer model, and 1-2 model, which we will define. We express the local statistics of a large class of vertex models on a finite hexagonal lattice as a linear combination of the local statistics of dimers on the corresponding Fisher graph, with the help of a generalized holographic algorithm. Using an n × n torus to approximate the periodic infinite graph, we give an explicit integral formula for the free energy and local statistics for configurations of the vertex model on an infinite bi-periodic graph. As an example, we simulate the 1-2 model by the technique of Glauber dynamics.     

Infinite Systems of Interacting Chains with Memory of Variable Length—A Stochastic Model for Biological Neural Nets

We consider a new class of non Markovian processes with a countable number of interacting components. At each time unit, each component can take two values, indicating if it has a spike or not at this precise moment. The system evolves as follows. For each component, the probability of having a spike at the next time unit depends on the entire time evolution of the system after the last spike time of the component. This class of systems extends in a non trivial way both the interacting particle systems, which are Markovian (Spitzer in Adv. Math. 5:246–290, 1970) and the stochastic chains with memory of variable length which have finite state space (Rissanen in IEEE Trans. Inf. Theory 29(5):656–664, 1983). These features make it suitable to describe the time evolution of biological neural systems. We construct a stationary version of the process by using a probabilistic tool which is a Kalikow-type decomposition either in random environment or in space-time. This construction implies uniqueness of the stationary process. Finally we consider the case where the interactions between components are given by a critical directed Erdös-Rényi-type random graph with a large but finite number of components. In this framework we obtain an explicit upper-bound for the correlation between successive inter-spike intervals which is compatible with previous empirical findings.     

Inhomogeneous Ballistic Aggregation

The one-dimensional ballistic aggregation process is considered when the initial mass density or the initial particle velocities vanish outside of a finite or semi-infinite interval. In all cases, we compute the mass distributions in closed analytical form and study their long time asymptotics. The relevant length scales are found different (of the order t, t ^2/3, t ^1/2) if, at the initial time, particles occupy a finite (or semi-infinite) interval and if a finite (or infinite) number of them are set into motion.     

Families of Line-Graphs and Their Quantization

Any directed graph G with N vertices and J edges has an associated line-graph L(G) where the J edges form the vertices of L(G). We show that the non-zero eigenvalues of the adjacency matrices are the same for all graphs of such a family L ⁿ (G). We give necessary and sufficient conditions for a line-graph to be quantisable and demonstrate that the spectra of associated quantum propagators follow the predictions of random matrices under very general conditions. Line-graphs may therefore serve as models to study the semiclassical limit (of large matrix size) of a quantum dynamics on graphs with fixed classical behaviour.     

Relative Equilibria in Continuous Stellar Dynamics

We study a three dimensional continuous model of gravitating matter rotating at constant angular velocity. In the rotating reference frame, by a finite dimensional reduction, we prove the existence of non-radial stationary solutions whose supports are made of an arbitrarily large number of disjoint compact sets, in the low angular velocity and large scale limit. At first order, the solutions behave like point particles, thus making the link with the relative equilibria in N-body dynamics.     

Activity Phase Transition for Constrained Dynamics

We consider two cases of kinetically constrained models, namely East and FA-1f models. The object of interest of our work is the activity A(t){\mathcal {A}(t)} defined as the total number of configuration changes in the interval [0, t] for the dynamics on a finite domain. It has been shown in Garrahan et al. (J Phys A 42:075007, 2009; Phys Rev Lett 98:195702, 2007) that the large deviations of the activity exhibit a non-equilibrium phase transition in the thermodynamic limit and that reducing the activity is more likely than increasing it due to a blocking mechanism induced by the constraints. In this paper, we study the finite size effects around this first order phase transition and analyze the phase coexistence between the active and inactive dynamical phases in dimension 1. In higher dimensions, we show that the finite size effects are determined by the dimension and the choice of the boundary conditions.     

Solving the undirected feedback vertex set problem by local search

An undirected graph consists of a set of vertices and a set of undirected edges between vertices. Such a graph may contain an abundant number of cycles, in which case a feedback vertex set (FVS) is a set of vertices intersecting with each of these cycles. Constructing a FVS of cardinality approaching the global minimum value is an optimization problem in the nondeterministic polynomial-complete complexity class, and therefore it might be extremely difficult for some large graph instances. In this paper we develop a simulated annealing local search algorithm for the undirected FVS problem by adapting the heuristic procedure of Galinier et al. [P. Galinier, E. Lemamou, M.W. Bouzidi, J. Heuristics 19, 797 (2013)], which worked for the directed FVS problem. By defining an order for the vertices outside the FVS, we replace the global cycle constraints by a set of local vertex constraints on this order. Under these local constraints the cardinality of the focal FVS is then gradually reduced by the simulated annealing dynamical process. We test this heuristic algorithm on large instances of Erdös-Rényi random graph and regular random graph, and find that this algorithm is comparable in performance to the belief propagation-guided decimation algorithm.     

Infinite-range mean-field percolation: Transfer matrix study of longitudinal correlation length

Two infinite-range directed percolation models, equivalent also to epidemic models, are considered for a finite population (finite number of sites)N at each time (directed axis) step. The general features of the transfer matrix spectrum (evolution operator spectrum for the epidemic) are studied numerically, and compared with analytical predictions in the limitN = . One of the models is devised to allow numerical results to be obtained forN as high as nearly 800 for the largest longitudinal percolation correlation length (relaxation time for epidemic). The finite-N behavior of this correlation length is studied in detail, including scaling near the percolation transition, exponential divergence (withN) above the percolation transition, as well as other noncritical and critical-point properties.     

A model for anomalous directed percolation

We introduce a model for the spreading of epidemics by long-range infections and investigate the critical behaviour at the spreading transition. The model generalizes directed bond percolation and is characterized by a probability distribution for long-range infections which decays in d spatial dimensions as . Extensive numerical simulations are performed in order to determine the density exponent and the correlation length exponents and for various values of . We observe that these exponents vary continuously with , in agreement with recent field-theoretic predictions. We also study a model for pairwise annihilation of particles with algebraically distributed long-range interactions. Received: 4 September 1998 / Accepted: 22 September 1998     

Phase Transitions for the Growth Rate of Linear Stochastic Evolutions

We consider a discrete-time stochastic growth model on d-dimensional lattice. The growth model describes various interesting examples such as oriented site/bond percolation, directed polymers in random environment, time discretizations of binary contact path process and the voter model. We study the phase transition for the growth rate of the “total number of particles” in this framework. The main results are roughly as follows: If d≥3 and the system is “not too random”, then, with positive probability, the growth rate of the total number of particles is of the same order as its expectation. If on the other hand, d=1,2, or the system is “random enough”, then the growth rate is slower than its expectation. We also discuss the above phase transition for the dual processes and its connection to the structure of invariant measures for the model with proper normalization. Supported in part by JSPS Grant-in-Aid for Scientific Research, Kiban (C) 17540112.     

Universality for the Distance in Finite Variance Random Graphs

We generalize the asymptotic behavior of the graph distance between two uniformly chosen nodes in the configuration model to a wide class of random graphs. Among others, this class contains the Poissonian random graph, the expected degree random graph and the generalized random graph (including the classical Erdős-Rényi graph). In the paper we assign to each node a deterministic capacity and the probability that there exists an edge between a pair of nodes is equal to a function of the product of the capacities of the pair divided by the total capacity of all the nodes. We consider capacities which are such that the degrees of a node have uniformly bounded moments of order strictly larger than two, so that, in particular, the degrees have finite variance. We prove that the graph distance grows like log  _ν N, where the ν depends on the capacities and N denotes the size of the graph. In addition, the random fluctuations around this asymptotic mean log  _ν N are shown to be tight. We also consider the case where the capacities are independent copies of a positive random Λ with , for some constant c and τ>3, again resulting in graphs where the degrees have finite variance. The method of proof of these results is to couple each member of the class to the Poissonian random graph, for which we then give the complete proof by adapting the arguments of van der Hofstad et al. (Random Struct. Algorithms 27(2):76–123, 2005).     

A New Class of Cellular Automata with a Discontinuous Glass Transition

We introduce a new class of two-dimensional cellular automata with a bootstrap percolation-like dynamics. Each site can be either empty or occupied by a single particle and the dynamics follows a deterministic updating rule at discrete times which allows only emptying sites. We prove that the threshold density ρ _c for convergence to a completely empty configuration is non trivial, 0<ρ _c <1, contrary to standard bootstrap percolation. Furthermore we prove that in the subcritical regime, ρ<ρ _c , emptying always occurs exponentially fast and that ρ _c coincides with the critical density for two-dimensional oriented site percolation on ℤ². This is known to occur also for some cellular automata with oriented rules for which the transition is continuous in the value of the asymptotic density and the crossover length determining finite size effects diverges as a power law when the critical density is approached from below. Instead for our model we prove that the transition is discontinuous and at the same time the crossover length diverges faster than any power law. The proofs of the discontinuity and the lower bound on the crossover length use a conjecture on the critical behaviour for oriented percolation. The latter is supported by several numerical simulations and by analytical (though non rigorous) works through renormalization techniques. Finally, we will discuss why, due to the peculiar mixed critical/first order character of this transition, the model is particularly relevant to study glassy and jamming transitions. Indeed, we will show that it leads to a dynamical glass transition for a Kinetically Constrained Spin Model. Most of the results that we present are the rigorous proofs of physical arguments developed in a joint work with D.S. Fisher.     

Escape of a Uniform Random Walk from an Interval

We study the first-passage properties of a random walk in the unit interval in which the length of a single step is uniformly distributed over the finite range [−a,a]. For a of the order of one, the exit probabilities to each edge of the interval and the exit time from the interval exhibit anomalous properties stemming from the change in the minimum number of steps to escape the interval as a function of the starting point. As a decreases, first-passage properties approach those of continuum diffusion, but non-diffusive effects remain because of residual discreteness effects. PACS: 02.50.C2, 05.40.Fb     

Asymptotic dynamics,non-critical and critical fluctuations for a geometric long-range interacting model

We study the dynamics of geometric spin system on the torus with long-range interaction. As the number of particles goes to infinity, the process converges to a deterministic, dynamical magnetization field that satisfies an Euler equation (law of large numbers). Its stable steady states are related to the limits of the equilibrium measures (Gibbs states) of the finite particle system. A related equation holds for the magnetization densities, for which the property of propagation of chaos also is established. We prove a dynamical central limit theorem with an infinite-dimensional Ornstein-Uhlenbeck process as a limiting fluctuation process. At the critical temperature of a ferromagnetic phase transition, both a tighter quantity scaling and a time scaling is required to obtain convergence to a one-dimensional critical fluctuation process with constant magnetization fields, which has a non-Gaussian invariant distribution. Similarly, at the phase transition to an antiferromagnetic state with frequencyp ₀, the fluctuation process with critical scaling converges to a two-dimensional critical fluctuation process, which consists of fields with frequencyp ₀ and has a non-Gaussian invariant distribution on these fields. Finally, we compute the critical fluctuation process in the infinite particle limit at a triple point, where a ferromagnetic and an antiferromagnetic phase transition coincide.Work supported by Deutsche Forschungsgemeinschaft     

Lyapunov Bounds for Lattice Gauge Dynamics

We study the classical Hamiltonian dynamics of the Kogut–Susskind model for lattice gauge theories on a finite box in a d-dimensional integer lattice. The coupling constant for the plaquette interaction is denoted λ². When the gauge group is a real or a complex subgroup of a unitary matrix group U(N), N≥ 1, we show that the maximal Lyapunov exponent is bounded by , uniformly in the size of the lattice, the energy of the system as well as the order, N, of the gauge group. Received: 20 December 1997 / Accepted: 21 July 1998