Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userIndex statistical properties of sparse random graphs
73
0
0.0
(
0
)
Added by
Fernando Lucas Metz
Publication date
2015
fields
Physics
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Using the replica method, we develop an analytical approach to compute the characteristic function for the probability $mathcal{P}_N(K,lambda)$ that a large $N times N$ adjacency matrix of sparse random graphs has $K$ eigenvalues below a threshold $lambda$. The method allows to determine, in principle, all moments of $mathcal{P}_N(K,lambda)$, from which the typical sample to sample fluctuations can be fully characterized. For random graph models with localized eigenvectors, we show that the index variance scales linearly with $N gg 1$ for $|lambda| > 0$, with a model-dependent prefactor that can be exactly calculated. Explicit results are discussed for Erdos-Renyi and regular random graphs, both exhibiting a prefactor with a non-monotonic behavior as a function of $lambda$. These results contrast with rotationally invariant random matrices, where the index variance scales only as $ln N$, with an universal prefactor that is independent of $lambda$. Numerical diagonalization results confirm the exactness of our approach and, in addition, strongly support the Gaussian nature of the index fluctuations.
rate research
Read More
We propose a method for solving statistical mechanics problems defined on sparse graphs. It extracts a small Feedback Vertex Set (FVS) from the sparse graph, converting the sparse system to a much smaller system with many-body and dense interactions with an effective energy on every configuration of the FVS, then learns a variational distribution parameterized using neural networks to approximate the original Boltzmann distribution. The method is able to estimate free energy, compute observables, and generate unbiased samples via direct sampling without auto-correlation. Extensive experiments show that our approach is more accurate than existing approaches for sparse spin glasses. On random graphs and real-world networks, our approach significantly outperforms the standard methods for sparse systems such as the belief-propagation algorithm; on structured sparse systems such as two-dimensional lattices our approach is significantly faster and more accurate than recently proposed variational autoregressive networks using convolution neural networks.
This review is devoted to the detailed consideration of the universal statistical properties of one-dimensional directed polymers in a random potential. In terms of the replica Bethe ansatz technique we derive several exact results for different types of the free energy probability distribution functions. In the second part of the review we discuss the problems which are still waiting for their solutions. Several mathematical appendices in the ending part of the review contain various technical details of the performed calculations.
We derive exact equations that determine the spectra of undirected and directed sparsely connected regular graphs containing loops of arbitrary length. The implications of our results to the structural and dynamical properties of networks are discussed by showing how loops influence the size of the spectral gap and the propensity for synchronization. Analytical formulas for the spectrum are obtained for specific length of the loops.
The Erdos-Renyi classical random graph is characterized by a fixed linking probability for all pairs of vertices. Here, this concept is generalized by drawing the linking probability from a certain distribution. Such a procedure is found to lead to a static complex network with an arbitrary connectivity distribution. In particular, a scale-free network with the hierarchical organization is constructed without assuming any knowledge about the global linking structure, in contrast to the preferential attachment rule for a growing network. The hierarchical and mixing properties of the static scale-free network thus constructed are studied. The present approach establishes a bridge between a scalar characterization of individual vertices and topology of an emerging complex network. The result may offer a clue for understanding the origin of a few abundance of connectivity distributions in a wide variety of static real-world networks.
This paper develops results for the next nearest neighbour Ising model on random graphs. Besides being an essential ingredient in classic models for frustrated systems, second neighbour interactions interactions arise naturally in several applications such as the colour diversity problem and graphical games. We demonstrate ensembles of random graphs, including regular connectivity graphs, that have a periodic variation of free energy, with either the ratio of nearest to next nearest couplings, or the mean number of nearest neighbours. When the coupling ratio is integer paramagnetic phases can be found at zero temperature. This is shown to be related to the locked or unlocked nature of the interactions. For anti-ferromagnetic couplings, spin glass phases are demonstrated at low temperature. The interaction structure is formulated as a factor graph, the solution on a tree is developed. The replica symmetric and energetic one-step replica symmetry breaking solution is developed using the cavity method. We calculate within these frameworks the phase diagram and demonstrate the existence of dynamical transitions at zero temperature for cases of anti-ferromagnetic coupling on regular and inhomogeneous random graphs.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
