Circuits in random graphs: from local trees to global loops
arXiv:cond-mat/0407253 · doi:10.1088/1742-5468/2004/09/P09004
Abstract
We compute the number of circuits and of loops with multiple crossings in random regular graphs. We discuss the importance of this issue for the validity of the cavity approach. On the one side we obtain analytic results for the infinite volume limit in agreement with existing exact results. On the other side we implement a counting algorithm, enumerate circuits at finite N and draw some general conclusions about the finite N behavior of the circuits.
submitted to JSTAT
References in corpus (1)
Cited by in corpus (24)
- Dynamical Organization of Cooperation in Complex Topologies
- Identifying optimal targets of network attack by belief propagation
- Emergence of large cliques in random scale-free network
- Loops of any size and Hamilton cycles in random scale-free networks
- Anderson transition on the Bethe lattice: an approach with real energies
- Number of cliques in random scale-free network ensembles
- Networking - A Statistical Physics Perspective
- On the number of circuits in random graphs
- An algorithm for counting circuits: application to real-world and random graphs
- Distribution of shortest cycle lengths in random networks
- Self-Sustaining Oscillations in Complex Networks of Excitable Elements
- Statistical analysis of articulation points in configuration model networks
- Cluster approximations for infection dynamics on random networks
- Multifractal phase in the weighted adjacency matrices of random Erdös-Rényi graphs
- Percolation and Loop Statistics in Complex Networks
- Sudden emergence of q-regular subgraphs in random graphs
- Exact spin-spin correlation function for the zero-temperature random-field Ising model
- Density matrix renormalization on random graphs and the quantum spin-glass transition
- Spin-glass model for the C-dismantling problem
- The distribution of shortest path lengths on trees of a given size in subcritical Erdos-Renyi networks
- Simple evolving random graphs
- Solvable Metric Growing Networks
- The distribution of the number of cycles in directed and undirected random 2-regular graphs
- Effect of disorder on condensation in the lattice gas model on a random graph