Loops of any size and Hamilton cycles in random scale-free networks

DOI10.1088/1742-5468/2005/06/P06005MaRDI QIDQ4968858zbMATH OpenOpenAlexWikidataFDO

Authors Ginestra Bianconi, Matteo Marsili

Publication date 9 July 2019

Published in Journal of Statistical Mechanics: Theory and Experiment (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cond-mat/0502552

zbMATH Keywords

networksrandom graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Random walks, random surfaces, lattice animals, etc. in equilibrium statistical mechanics (82B41)

Abstract: Loops are subgraphs responsible for the multiplicity of paths going from one to another generic node in a given network. In this paper we present an analytic approach for the evaluation of the average number of loops in random scale-free networks valid at fixed number of nodes N and for any length L of the loops. We bring evidence that the most frequent loop size in a scale-free network of N nodes is of the order of N like in random regular graphs while small loops are more frequent when the second moment of the degree distribution diverges. In particular, we find that finite loops of sizes larger than a critical one almost surely pass from any node, thus casting some doubts on the validity of the random tree approximation for the solution of lattice models on these graphs. Moreover we show that Hamiltonian cycles are rare in random scale-free networks and may fail to appear if the power-law exponent of the degree distribution is close to 2 even for minimal connectivity grater than 3.

Recommendations

• Statistics of cycles: how loopy is your network?
• Loop statistics in complex networks
• Counting cliques and cycles in scale-free inhomogeneous random graphs
• Number of cliques in random scale-free network ensembles
• Circuits in random graphs: from local trees to global loops

Cites work

• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 1866312 (Why is no real title available?)
• A critical point for random graphs with a given degree sequence
• Circuits in random graphs: from local trees to global loops
• Finding All the Elementary Circuits of a Directed Graph
• Potts model on random trees
• Statistical field theory. With a foreword by David Pines
• Statistical mechanics of complex networks
• Statistics of cycles: how loopy is your network?

Cited in

(15)

• Clustering coefficients for networks with higher order interactions
• Ising spin glass models versus Ising models: an effective mapping at high temperature. II: Applications to graphs and networks
• Loop statistics in complex networks
• On the number of circuits in random graphs
• Ising spin glass models versus Ising models: an effective mapping at high temperature. I: General result
• scientific article; zbMATH DE number 6783443 (Why is no real title available?)
• The characteristics of cycle-nodes-ratio and its application to network classification
• Relationships between Perron-Frobenius eigenvalue and measurements of loops in networks
• Counting cliques and cycles in scale-free inhomogeneous random graphs
• Spin Glass approach to the feedback vertex set problem
• The Min Mean-Weight Cycle in a Random Network
• Random graph ensembles with many short loops
• Number of cliques in random scale-free network ensembles
• Circuits in random graphs: from local trees to global loops
• Statistics of cycles: how loopy is your network?

This page was built for publication: Loops of any size and Hamilton cycles in random scale-free networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4968858)