Counting cliques and cycles in scale-free inhomogeneous random graphs

Abstract

Scale-free networks contain many small cliques and cycles. We model such networks as inhomogeneous random graphs with regularly varying infinite-variance weights. For these models, the number of cliques and cycles have exact integral expressions amenable to asymptotic analysis. We obtain various asymptotic descriptions for how the average number of cliques and cycles, of any size, grow with the network size. For the cycle asymptotics we invoke the theory of circulant matrices.

References in corpus (11)

• The statistical mechanics of networks
• The phase transition in inhomogeneous random graphs
• Class of correlated random networks with hidden variables
• Generating simple random graphs with prescribed degree distribution
• Scale-free Networks Well Done
• Emergence of large cliques in random scale-free network
• Loops of any size and Hamilton cycles in random scale-free networks
• Local clustering in scale-free networks with hidden variables
• Clustering Spectrum of scale-free networks
• Triadic closure in configuration models with unbounded degree fluctuations
• Degree correlations in scale-free null models

Cited by in corpus (8)

• Cliques in geometric inhomogeneous random graph
• Quantum Motif Clustering
• Sharpest possible clustering bounds using robust random graph analysis
• Asymptotics for cliques in scale-free random graphs
• On the distances within cliques in a soft random geometric graph
• Phase transition in a power-law uniform hypergraph
• Robust subgraph counting with distribution-free random graph analysis
• Poisson approximation for cycles in the generalised random graph