Circuits in random graphs: From local trees to global loops

Enzo Marinari; Rémi Monasson

doi:10.1088/1742-5468/2004/09/P09004

Circuits in random graphs: From local trees to global loops

Enzo Marinari
, Rémi Monasson

Research output: Contribution to journal › Article › peer-review

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 hand we obtain analytical results for the infinite volume limit in agreement with existing exact results. On the other hand we implement a counting algorithm, enumerate circuits at finite N, and draw some general conclusions about the finite-N behaviour of the number of circuits.

Original language	English
Article number	P09004
Journal	Journal of Statistical Mechanics: Theory and Experiment
Issue number	9
DOIs	https://doi.org/10.1088/1742-5468/2004/09/P09004
Publication status	Published - 1 Jan 2004
Externally published	Yes

Keywords

networks
random graphs
spin glasses (theory)

Access to Document

10.1088/1742-5468/2004/09/P09004

Cite this

@article{d7bfed46292f4d72b0762dbe0382de84,

title = "Circuits in random graphs: From local trees to global loops",

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 hand we obtain analytical results for the infinite volume limit in agreement with existing exact results. On the other hand we implement a counting algorithm, enumerate circuits at finite N, and draw some general conclusions about the finite-N behaviour of the number of circuits.",

keywords = "networks, random graphs, spin glasses (theory)",

author = "Enzo Marinari and R{\'e}mi Monasson",

year = "2004",

month = jan,

day = "1",

doi = "10.1088/1742-5468/2004/09/P09004",

language = "English",

journal = "Journal of Statistical Mechanics: Theory and Experiment",

issn = "1742-5468",

number = "9",

}

TY - JOUR

T1 - Circuits in random graphs

T2 - From local trees to global loops

AU - Marinari, Enzo

AU - Monasson, Rémi

PY - 2004/1/1

Y1 - 2004/1/1

N2 - 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 hand we obtain analytical results for the infinite volume limit in agreement with existing exact results. On the other hand we implement a counting algorithm, enumerate circuits at finite N, and draw some general conclusions about the finite-N behaviour of the number of circuits.

AB - 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 hand we obtain analytical results for the infinite volume limit in agreement with existing exact results. On the other hand we implement a counting algorithm, enumerate circuits at finite N, and draw some general conclusions about the finite-N behaviour of the number of circuits.

KW - networks

KW - random graphs

KW - spin glasses (theory)

UR - https://www.scopus.com/pages/publications/84901036507

U2 - 10.1088/1742-5468/2004/09/P09004

DO - 10.1088/1742-5468/2004/09/P09004

M3 - Article

AN - SCOPUS:84901036507

SN - 1742-5468

JO - Journal of Statistical Mechanics: Theory and Experiment

JF - Journal of Statistical Mechanics: Theory and Experiment

IS - 9

M1 - P09004

ER -

Circuits in random graphs: From local trees to global loops

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this