Counting cliques and cycles in scale-free inhomogeneous random graphs

DOI10.1007/S10955-019-02248-WMaRDI QIDQ1999415zbMATH OpenOpenAlexWikidataFDO

Authors A. J. E. M. Janssen, Johan S. H. van Leeuwaarden, V. Shneer

Publication date 26 June 2019

Published in Journal of Statistical Physics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1812.04384

zbMATH Keywords

cliquespower-law distributionsrandom graphsscale-free networkssubgraphs

Mathematics Subject Classification ID

Paths and cycles (05C38) Random graphs (graph-theoretic aspects) (05C80) Small world graphs, complex networks (graph-theoretic aspects) (05C82)

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.

Recommendations

• Asymptotics for cliques in scale-free random graphs
• Number of cliques in random scale-free network ensembles
• Analyzing the cliques in scale-free random graphs
• Cliques in rank-1 random graphs: the role of inhomogeneity
• Statistics of cycles: how loopy is your network?

Cites work

• Degree correlations in scale-free random graph models
• Generating simple random graphs with prescribed degree distribution
• scientific article; zbMATH DE number 43570 (Why is no real title available?)
• Loops of any size and Hamilton cycles in random scale-free networks
• Number of cliques in random scale-free network ensembles
• On a conditionally Poissonian graph process
• Optimal subgraph structures in scale-free configuration models
• The average distances in random graphs with given expected degrees
• The phase transition in inhomogeneous random graphs

Cited in

(9)

• Cliques in rank-1 random graphs: the role of inhomogeneity
• Asymptotics for cliques in scale-free random graphs
• Analyzing the cliques in scale-free random graphs
• Loops of any size and Hamilton cycles in random scale-free networks
• Phase transitions in a power-law uniform hypergraph
• On the distances within cliques in a soft random geometric graph
• On the Rényi index of random graphs
• Robustness of clustering coefficients
• Number of cliques in random scale-free network ensembles

This page was built for publication: Counting cliques and cycles in scale-free inhomogeneous random graphs

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