ABSTRACT
Using the replica method, we develop an analytical approach to compute the characteristic function for the probability P(N)(K,λ) that a large N×N adjacency matrix of sparse random graphs has K eigenvalues below a threshold λ. The method allows to determine, in principle, all moments of P(N)(K,λ), 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â«1 for |λ|>0, with a model-dependent prefactor that can be exactly calculated. Explicit results are discussed for Erdös-Rényi and regular random graphs, both exhibiting a prefactor with a nonmonotonic behavior as a function of λ. These results contrast with rotationally invariant random matrices, where the index variance scales only as lnN, with an universal prefactor that is independent of λ. Numerical diagonalization results confirm the exactness of our approach and, in addition, strongly support the Gaussian nature of the index fluctuations.
ABSTRACT
We develop a thorough analytical study of the O(1/N) correction to the spectrum of regular random graphs with Nâ∞ nodes. The finite-size fluctuations of the resolvent are given in terms of a weighted series over the contributions coming from loops of all possible lengths, from which we obtain the isolated eigenvalue as well as an analytical expression for the O(1/N) correction to the continuous part of the spectrum. The comparison between this analytical formula and direct diagonalization results exhibits an excellent agreement, confirming the correctness of our expression.
ABSTRACT
We present the exact analytical expression for the spectrum of a sparse non-hermitian random matrix ensemble, generalizing two standard results in random-matrix theory: this analytical expression constitutes a non-hermitian version of the Kesten-McKay measure as well as a sparse realization of Girko's elliptic law. Our exact result opens new perspectives in the study of several physical problems modelled on sparse random graphs, which are locally treelike. In this context, we show analytically that the convergence rate of a transport process on a very sparse graph depends in a nonmonotonic way upon the degree of symmetry of the graph edges.
ABSTRACT
We derive exact equations that determine the spectra of undirected and directed sparsely connected regular graphs containing loops of arbitrary lengths. The implications of our results for the structural and dynamical properties of network models 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 lengths of the loops.
Subject(s)
Biophysics/methods , Algorithms , Computer Communication Networks , Models, Statistical , Physics/methods , Reproducibility of Results , Signal Processing, Computer-Assisted , Systems TheoryABSTRACT
We study the behavior of the inverse participation ratio and the localization transition in infinitely large random matrices through the cavity method. Results are shown for two ensembles of random matrices: Laplacian matrices on sparse random graphs and fully connected Lévy matrices. We derive a critical line separating localized from extended states in the case of Lévy matrices. Comparison between theoretical results and diagonalization of finite random matrices is shown.
ABSTRACT
The effects of dominant sequential interactions are investigated in an exactly solvable feedforward layered neural network model of binary units and patterns near saturation in which the interaction consists of a Hebbian part and a symmetric sequential term. Phase diagrams of stationary states are obtained and a phase of cyclic correlated states of period two is found for a weak Hebbian term, independently of the number of condensed patterns c.
Subject(s)
Biophysics/methods , Nerve Net/physiology , Neural Networks, Computer , Algorithms , Animals , Computer Simulation , Humans , Models, Biological , Models, Chemical , Models, Neurological , Models, Statistical , Pattern Recognition, Automated , Stochastic ProcessesABSTRACT
The dynamics and the stationary states for the competition between pattern reconstruction and asymmetric sequence processing are studied here in an exactly solvable feed-forward layered neural network model of binary units and patterns near saturation. Earlier work by Coolen and Sherrington on a parallel dynamics far from saturation is extended here to account for finite stochastic noise due to a Hebbian and a sequential learning rule. Phase diagrams are obtained with stationary states and quasiperiodic nonstationary solutions. The relevant dependence of these diagrams and of the quasiperiodic solutions on the stochastic noise and on initial inputs for the overlaps is explicitly discussed.