An algorithm for counting circuits: Application to real-world and random graphsE. Marinari1, R. Monasson2 and G. Semerjian3
1 Dipartimento di Fisica and INFN, Università di Roma La Sapienza P. A. Moro 2, 00185 Roma, Italy
2 CNRS-Laboratoire de Physique Théorique de l'ENS - 24 rue Lhomond 75005 Paris, France
3 Dipartimento di Fisica and SMC-INFM, Università di Roma La Sapienza P. A. Moro 2, 00185 Roma, Italy
received 9 September 2005; accepted 26 October 2005
published online 23 November 2005
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.
05.20.-y - Classical statistical mechanics.
02.10.Ox - Combinatorics; graph theory.
89.75.Hc - Networks and genealogical trees.
© EDP Sciences 2005