Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userResistance distance distribution in large sparse random graphs
170
0
0.0
(
0
)
Added by
Pawat Akarapipattana
Publication date
2021
fields
Physics
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We consider an Erdos-Renyi random graph consisting of N vertices connected by randomly and independently drawing an edge between every pair of them with probability c/N so that at N->infinity one obtains a graph of finite mean degree c. In this regime, we study the distribution of resistance distances between the vertices of this graph and develop an auxiliary field representation for this quantity in the spirit of statistical field theory. Using this representation, a saddle point evaluation of the resistance distance distribution is possible at N->infinity in terms of an 1/c expansion. The leading order of this expansion captures the results of numerical simulations very well down to rather small values of c; for example, it recovers the empirical distribution at c=4 or 6 with an overlap of around 90%. At large values of c, the distribution tends to a Gaussian of mean 2/c and standard deviation sqrt{2/c^3}. At small values of c, the distribution is skewed toward larger values, as captured by our saddle point analysis, and many fine features appear in addition to the main peak, including subleading peaks that can be traced back to resistance distances between vertices of specific low degrees and the rest of the graph. We develop a more refined saddle point scheme that extracts the corresponding degree-differentiated resistance distance distributions. We then use this approach to recover analytically the most apparent of the subleading peaks that originates from vertices of degree 1. Rather intuitively, this subleading peak turns out to be a copy of the main peak, shifted by one unit of resistance distance and scaled down by the probability for a vertex to have degree 1. We comment on a possible lack of smoothness in the true N->infinity distribution suggested by the numerics.
rate research
Read More
We present a general method for obtaining the spectra of large graphs with short cycles using ideas from statistical mechanics of disordered systems. This approach leads to an algorithm that determines the spectra of graphs up to a high accuracy. In particular, for (un)directed regular graphs with cycles of arbitrary length we derive exact and simple equations for the resolvent of the associated adjacency matrix. Solving these equations we obtain analytical formulas for the spectra and the boundaries of their support.
We solve the q-state Potts model with anti-ferromagnetic interactions on large random lattices of finite coordination. Due to the frustration induced by the large loops and to the local tree-like structure of the lattice this model behaves as a mean field spin glass. We use the cavity method to compute the temperature-coordination phase diagram and to determine the location of the dynamic and static glass transitions, and of the Gardner instability. We show that for q>=4 the model possesses a phenomenology similar to the one observed in structural glasses. We also illustrate the links between the positive and the zero-temperature cavity approaches, and discuss the consequences for the coloring of random graphs. In particular we argue that in the colorable region the one-step replica symmetry breaking solution is stable towards more steps of replica symmetry breaking.
We present a full description of the nonergodic properties of wavefunctions on random graphs without boundary in the localized and critical regimes of the Anderson transition. We find that they are characterized by two critical localization lengths: the largest one describes localization along rare branches and diverges with a critical exponent $ u_parallel=1$ at the transition. The second length, which describes localization along typical branches, reaches at the transition a finite universal value (which depends only on the connectivity of the graph), with a singularity controlled by a new critical exponent $ u_perp=1/2$. We show numerically that these two localization lengths control the finite-size scaling properties of key observables: wavefunction moments, correlation functions and spectral statistics. Our results are identical to the theoretical predictions for the typical localization length in the many-body localization transition, with the same critical exponent. This strongly suggests that the two transitions are in the same universality class and that our techniques could be directly applied in this context.
We consider the problem of coloring the vertices of a large sparse random graph with a given number of colors so that no adjacent vertices have the same color. Using the cavity method, we present a detailed and systematic analytical study of the space of proper colorings (solutions). We show that for a fixed number of colors and as the average vertex degree (number of constraints) increases, the set of solutions undergoes several phase transitions similar to those observed in the mean field theory of glasses. First, at the clustering transition, the entropically dominant part of the phase space decomposes into an exponential number of pure states so that beyond this transition a uniform sampling of solutions becomes hard. Afterward, the space of solutions condenses over a finite number of the largest states and consequently the total entropy of solutions becomes smaller than the annealed one. Another transition takes place when in all the entropically dominant states a finite fraction of nodes freezes so that each of these nodes is allowed a single color in all the solutions inside the state. Eventually, above the coloring threshold, no more solutions are available. We compute all the critical connectivities for Erdos-Renyi and regular random graphs and determine their asymptotic values for large number of colors. Finally, we discuss the algorithmic consequences of our findings. We argue that the onset of computational hardness is not associated with the clustering transition and we suggest instead that the freezing transition might be the relevant phenomenon. We also discuss the performance of a simple local Walk-COL algorithm and of the belief propagation algorithm in the light of our results.
The fidelity susceptibility measures sensitivity of eigenstates to a change of an external parameter. It has been fruitfully used to pin down quantum phase transitions when applied to ground states (with extensions to thermal states). Here we propose to use the fidelity susceptibility as a useful dimensionless measure for complex quantum systems. We find analytically the fidelity susceptibility distributions for Gaussian orthogonal and unitary universality classes for arbitrary system size. The results are verified by a comparison with numerical data.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
