Random incidence matrices: moments of the spectral density
arXiv:cond-mat/0007127 · doi:10.1023/A:1004879905284
Abstract
We study numerically and analytically the spectrum of incidence matrices of random labeled graphs on N vertices : any pair of vertices is connected by an edge with probability p. We give two algorithms to compute the moments of the eigenvalue distribution as explicit polynomials in N and p. For large N and fixed p the spectrum contains a large eigenvalue at Np and a semi-circle of "small" eigenvalues. For large N and fixed average connectivity pN (dilute or sparse random matrices limit), we show that the spectrum always contains a discrete component. An anomaly in the spectrum near eigenvalue 0 for connectivity close to e=2.72... is observed. We develop recursion relations to compute the moments as explicit polynomials in pN. Their growth is slow enough so that they determine the spectrum. The extension of our methods to the Laplacian matrix is given in Appendix. Keywords: random graphs, random matrices, sparse matrices, incidence matrices spectrum, moments
arXiv comment39 pages, 9 figures, Latex2e, [v2: ref. added, Sect. 4 modified]
References in corpus (3)
Cited by in corpus (52)
- Spectra of "Real-World" Graphs: Beyond the Semi-Circle Law
- Sparse random matrices: the eigenvalue spectrum revisited
- Cavity Approach to the Spectral Density of Sparse Symmetric Random Matrices
- Network Transitivity and Matrix Models
- Random matrix analysis of complex networks
- Spectral distributions of adjacency and Laplacian matrices of random graphs
- On the localization transition in symmetric random matrices
- Networks in life: Scaling properties and eigenvalue spectra
- The Canopy Graph and Level Statistics for Random Operators on Trees
- Spectral Theory of Sparse Non-Hermitian Random Matrices
- Sparse regular random graphs: Spectral density and eigenvectors
- Cavity and replica methods for the spectral density of sparse symmetric random matrices
- Localization of eigenvectors in random graphs
- Lifshitz tails for spectra of Erdős--Rényi random graphs
- Spectral Analysis of Protein-Protein Interactions in Drosophila melanogaster
- Spectral density of random graphs with topological constraints
- Perturbing General Uncorrelated Networks
- Localization and universality of eigenvectors in directed random graphs
- Dynamics of dilute disordered models: a solvable case
- Dynamical systems on large networks with predator-prey interactions are stable and exhibit oscillations
- A unifying model for random matrix theory in arbitrary space dimensions
- Equivalence of replica and cavity methods for computing spectra of sparse random matrices
- Exponential growth of random determinants beyond invariance
- The spectral density of dense random networks and the breakdown of the Wigner semicircle law
- Lifshitz tails on the Bethe lattice: a combinatorial approach
- Large deviation theory for diluted Wishart random matrices
- Multifractal phase in the weighted adjacency matrices of random Erdös-Rényi graphs
- Central limit theorem for fluctuations of linear eigenvalue statistics of large random graphs. Diluted regime
- Central limit theorem for fluctuations of linear eigenvalue statistics of large random graphs
- Native ultrametricity of sparse random ensembles
- Index statistical properties of sparse random graphs
- Disentangling Giant Component and Finite Cluster Contributions in Sparse Matrix Spectra
- Localization in random bipartite graphs: numerical and empirical study
- On the correlation functions of the characteristic polynomials of the sparse hermitian random matrices
- The integrated density of states of the random graph Laplacian
- A dynamical characterization of the small world phase
- On Connected Diagrams and Cumulants of Erdos-Renyi Matrix Models
- Null-eigenvalue localization of quantum walks on real-world complex networks
- Proof of a conjecture on the infinite dimension limit of a unifying model for random matrix theory
- Hammerstein equations for sparse random matrices
- Typical Performance of Approximation Algorithms for NP-hard Problems
- Sparse Random Block Matrices
- Real symmetric random matrices and paths counting
- Phase transitions in atypical systems induced by a condensation transition on graphs
- Real symmetric random matrices and replicas
- Random Antagonistic Matrices
- Spectral properties of unimodular lattice triangulations
- Resistance distance distribution in large sparse random graphs
- Unsupervised Techniques to Detect Quantum Chaos
- Properties of dense partially random graphs
- Localization properties of the sparse Barrat-Mézard trap model
- Spectral densities of scale-free networks