On the number of circuits in random graphs

Abstract

We apply in this article (non rigorous) statistical mechanics methods to the problem of counting long circuits in graphs. The outcomes of this approach have two complementary flavours. On the algorithmic side, we propose an approximate counting procedure, valid in principle for a large class of graphs. On a more theoretical side, we study the typical number of long circuits in random graph ensembles, reproducing rigorously known results and stating new conjectures.

30 pages

References in corpus (22)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• Random graphs with arbitrary degree distributions and their applications
• The Bethe lattice spin glass revisited
• k-core organization of complex networks
• Broken Replica Symmetry Bounds in the Mean Field Spin Glass Model
• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• Universality Classes for Extreme Value Statistics
• Glass models on Bethe lattices
• Instability of one-step replica-symmetry-broken phase in satisfiability problems
• Replica bounds for diluted non-Poissonian spin systems
• Loops of any size and Hamilton cycles in random scale-free networks
• Kinetic Theory of Random Graphs: from Paths to Cycles
• How to Compute Loop Corrections to Bethe Approximation
• Loops structure of the Internet at the Autonomous System Level
• Statistics of Cycles: How Loopy is your Network?
• Circuits in random graphs: from local trees to global loops
• Spin glass models with ferromagnetically biased couplings on the Bethe lattice: analytic solutions and numerical simulations
• An algorithm for counting circuits: application to real-world and random graphs
• Statistics of cycles in large networks
• The cavity method for large deviations
• Glassy phases in Random Heteropolymers with correlated sequences

Cited by in corpus (19)

• The number of matchings in random graphs
• Gibbs entropy of networks ensembles by cavity methods
• Spin glass approach to the feedback vertex set problem
• Rare events and discontinuous percolation transitions
• Constraint satisfaction problems with isolated solutions are hard
• Networking - A Statistical Physics Perspective
• Collaboration in Social Networks
• Algorithm for counting large directed loops
• Distribution of shortest cycle lengths in random networks
• Phase diagram of an Ising model with competitive interactions on a Husimi tree and its disordered counterpart
• Ranking by Loops: a new approach to categorization
• Statistical analysis of articulation points in configuration model networks
• Statistical mechanics of budget-constrained auctions
• Ising spin glass models versus Ising models: an effective mapping at high temperature II. Applications to graphs and networks
• The distribution of shortest path lengths on trees of a given size in subcritical Erdos-Renyi networks
• Code optimization, frozen glassy phase and improved decoding algorithms for low-density parity-check codes
• The planted matching problem: Sharp threshold and infinite-order phase transition
• The distribution of the number of cycles in directed and undirected random 2-regular graphs
• Strong Spatial Mixing and Approximating Partition Functions of Two-State Spin Systems without Hard Constrains