Europhys. Lett.
Volume 73, Number 1, January 2006
Page(s) 8 - 14
Section General
Published online 23 November 2005
Europhys. Lett., 73 (1), pp. 8-14 (2006)
DOI: 10.1209/epl/i2005-10355-0

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

E. 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