Replica methods for loopy sparse random graphs
arXiv:1601.08124 · doi:10.1088/1742-6596/699/1/012022
Abstract
I report on the development of a novel statistical mechanical formalism for the analysis of random graphs with many short loops, and processes on such graphs. The graphs are defined via maximum entropy ensembles, in which both the degrees (via hard constraints) and the adjacency matrix spectrum (via a soft constraint) are prescribed. The sum over graphs can be done analytically, using a replica formalism with complex replica dimensions. All known results for tree-like graphs are recovered in a suitable limit. For loopy graphs, the emerging theory has an appealing and intuitive structure, suggests how message passing algorithms should be adapted, and what is the structure of theories describing spin systems on loopy architectures. However, the formalism is still largely untested, and may require further adjustment and refinement.
arXiv comment11 pages, no figures. To be published in Proceedings of The International Meeting on High-Dimensional Data-Driven Science (HD3-2015), Kyoto, Japan, on 14-17 December, 2015
References in corpus (18)
- The Bethe lattice spin glass revisited
- Spectra of complex networks
- Spectra of Sparse Random Matrices
- Network Transitivity and Matrix Models
- Loop Calculus in Statistical Physics and Information Science
- How to Compute Loop Corrections to Bethe Approximation
- Constrained Markovian dynamics of random graphs
- Immune networks: multi-tasking capabilities near saturation
- Tailored graph ensembles as proxies or null models for real networks I: tools for quantifying structure
- Finitely connected vector spin systems with random matrix interactions
- Spectra of sparse regular graphs with loops
- Perturbing General Uncorrelated Networks
- Exact Analytic Continuation with Respect to the Replica Number in the Discrete Random Energy Model of Finite System Size
- Cluster derivation of Parisi's RSB solution for disordered systems
- A solvable model of the genesis of amino-acid sequences via coupled dynamics of folding and slow genetic variation
- Complex Replica Zeros of Ising Spin Glass at Zero Temperature
- Hierarchical Self-Programming in Recurrent Neural Networks
- Zero-Temperature Complex Replica Zeros of the Ising Spin Glass on Mean-Field Systems and Beyond
Cited by in corpus (10)
- Spectral Theory of Sparse Non-Hermitian Random Matrices
- Distribution of shortest cycle lengths in random networks
- Eigenvalue Repulsion and Eigenfunction Localization in Sparse Non-Hermitian Random Matrices
- Large deviation theory for diluted Wishart random matrices
- Imaginary replica analysis of loopy regular random graphs
- Exactly Solvable Random Graph Ensemble with Extensively Many Short Cycles
- Analytic solution of the two-star model with correlated degrees
- Belief propagation on networks with cliques and chordless cycles
- Theory for the conditioned spectral density of non-invariant random matrices
- Uncovering the non-equilibrium stationary properties in sparse Boolean networks