Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSpectra of sparse regular graphs with loops
156
0
0.0
(
0
)
Added by
Fernando Lucas Metz
Publication date
2011
fields
Physics
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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.
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.
Belief propagation is a widely used message passing method for the solution of probabilistic models on networks such as epidemic models, spin models, and Bayesian graphical models, but it suffers from the serious shortcoming that it works poorly in the common case of networks that contain short loops. Here we provide a solution to this long-standing problem, deriving a belief propagation method that allows for fast calculation of probability distributions in systems with short loops, potentially with high density, as well as giving expressions for the entropy and partition function, which are notoriously difficult quantities to compute. Using the Ising model as an example, we show that our approach gives excellent results on both real and synthetic networks, improving significantly on standard message passing methods. We also discuss potential applications of our method to a variety of other problems.
We develop a novel method based in the sparse random graph to account the interplay between geometric frustration and disorder in cluster magnetism. Our theory allows to introduce the cluster network connectivity as a controllable parameter. Two types of inner cluster geometry are considered: triangular and tetrahedral. The theory was developed for a general, non-uniform intra-cluster interactions, but in the present paper the results presented correspond to uniform, anti-ferromagnetic (AF) intra-clusters interactions $J_{0}/J$. The clusters are represented by nodes on a finite connectivity random graph, and the inter-cluster interactions are random Gaussian distributed. The graph realizations are treated in replica theory using the formalism of order parameter functions, which allows to calculate the distribution of local fields and, as a consequence, the relevant observable. In the case of triangular cluster geometry, there is the onset of a classical Spin Liquid state at a temperature $T^{*}/J$ and then, a Cluster Spin Glass (CSG) phase at a temperature $T_{f}/J$. The CSG ground state is robust even for very weak disorder or large negative $J_{0}/J$. These results does not depend on the network connectivity. Nevertheless, variations in the connectivity strongly affect the level of frustration $f_{p}=-Theta_{CW}/T_{f}$ for large $J_{0}/J$. In contrast, for the non-frustrated tetrahedral cluster geometry, the CSG ground state is suppressed for weak disorder or large negative $J_{0}/J$. The CSG boundary phase presents a re-entrance which is dependent on the network connectivity.
Simple models of irreversible dynamical processes such as Bootstrap Percolation have been successfully applied to describe cascade processes in a large variety of different contexts. However, the problem of analyzing non-typical trajectories, which can be crucial for the understanding of the out-of-equilibrium phenomena, is still considered to be intractable in most cases. Here we introduce an efficient method to find and analyze optimized trajectories of cascade processes. We show that for a wide class of irreversible dynamical rules, this problem can be solved efficiently on large-scale systems.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
