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

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.

arXiv comment14 pages, 4 figures, minor changes

References in corpus (14)

• Statistical mechanics of complex networks
• Epidemic spreading in scale-free networks
• Absence of epidemic threshold in scale-free networks with connectivity correlations
• Class of correlated random networks with hidden variables
• The topological relationship between the large-scale attributes and local interaction patterns of complex networks
• Cut-offs and finite size effects in scale-free networks
• Ferromagnetic ordering in graphs with arbitrary degree distribution
• Subgraphs in random networks
• Potts model on complex networks
• Clustering of correlated networks
• Number of loops of size h in growing scale-free networks
• Uncorrelated Random Networks
• Circuits in random graphs: from local trees to global loops
• Potts Model On Random Trees

Cited by in corpus (42)

• Critical phenomena in complex networks
• Analyzing and Modeling Real-World Phenomena with Complex Networks: A Survey of Applications
• Dynamical Organization of Cooperation in Complex Topologies
• Controlling edge dynamics in complex networks
• Identifying optimal targets of network attack by belief propagation
• Local structure of directed networks
• Emergence of large cliques in random scale-free network
• Spin glass approach to the feedback vertex set problem
• Enumeration of spanning trees in a pseudofractal scale-free web
• Belief-propagation algorithm and the Ising model on networks with arbitrary distributions of motifs
• Number of cliques in random scale-free network ensembles
• Biased Percolation on Scale-free Networks
• Counting cliques and cycles in scale-free inhomogeneous random graphs
• On the number of circuits in random graphs
• Algorithm for counting large directed loops
• An algorithm for counting circuits: application to real-world and random graphs
• Linear stability analysis for large dynamical systems on directed random graphs
• Distribution of shortest cycle lengths in random networks
• Phase diagram of an Ising model with competitive interactions on a Husimi tree and its disordered counterpart
• Self-Sustaining Oscillations in Complex Networks of Excitable Elements
• Dynamical systems on large networks with predator-prey interactions are stable and exhibit oscillations
• Ranking by Loops: a new approach to categorization
• Percolation on bipartite scale-free networks
• Percolation and Loop Statistics in Complex Networks
• Stochastic and mixed flower graphs
• Critical behavior and correlations on scale-free small-world networks. Application to network design
• Heterogeneous message passing for heterogeneous networks
• Ising spin glass models versus Ising models: an effective mapping at high temperature I. General result
• Cycles and Clustering in Multiplex Networks
• Ising spin glass models versus Ising models: an effective mapping at high temperature II. Applications to graphs and networks
• Clustering coefficients for networks with higher order interactions
• Role of hubs in the synergistic spread of behavior
• Spin-glass model for the C-dismantling problem
• Strongly clustered random graphs via triadic closure: An exactly solvable model
• Fluctuations of motifs and non self-averaging in complex networks. A self- vs non-self-averaging phase transition scenario
• Local sign stability and its implications for spectra of sparse random graphs and stability of ecosystems
• Simple evolving random graphs
• The distribution of the number of cycles in directed and undirected random 2-regular graphs
• Network structure and dynamics of effective models of non-equilibrium quantum transport
• Sharpest possible clustering bounds using robust random graph analysis
• Robust subgraph counting with distribution-free random graph analysis
• Poisson approximation for cycles in the generalised random graph