An algorithm for counting circuits: application to real-world and random graphs

Abstract

We introduce an algorithm which estimates the number of circuits in a graph as a function of their length. This approach provides analytical results for the typical entropy of circuits in sparse random graphs. When applied to real-world networks, it allows to estimate exponentially large numbers of circuits in polynomial time. We illustrate the method by studying a graph of the Internet structure.

7 pages, 3 figures, minor corrections, accepted version

References in corpus (8)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• Dynamical and correlation properties of the Internet
• The Bethe lattice spin glass revisited
• Loops of any size and Hamilton cycles in random scale-free networks
• Statistics of Cycles: How Loopy is your Network?
• Circuits in random graphs: from local trees to global loops
• Glassy phases in Random Heteropolymers with correlated sequences

Cited by in corpus (16)

• Identifying optimal targets of network attack by belief propagation
• The number of matchings in random graphs
• Local structure of directed networks
• Gibbs entropy of networks ensembles by cavity methods
• Spin glass approach to the feedback vertex set problem
• Message passing for vertex covers
• On the number of circuits in random graphs
• Algorithm for counting large directed loops
• Effect of degree correlations on the loop structure of scale-free networks
• Distribution of shortest cycle lengths in random networks
• Self-Sustaining Oscillations in Complex Networks of Excitable Elements
• Finding long cycles in graphs
• Statistical analysis of articulation points in configuration model networks
• Sudden emergence of q-regular subgraphs in random graphs
• Unevenness of Loop Location in Complex Networks
• Spin-glass model for the C-dismantling problem