Counting cliques and cycles in scale-free inhomogeneous random graphs

A.J.E.M. Janssen, Johan S.H. van Leeuwaarden (Corresponding author), Seva Shneer

    Research output: Contribution to journalArticleAcademicpeer-review

    39 Downloads (Pure)

    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.

    Original languageEnglish
    Pages (from-to)161-184
    Number of pages24
    JournalJournal of Statistical Physics
    Volume175
    Issue number1
    Early online date18 Jan 2019
    DOIs
    Publication statusPublished - 15 Apr 2019

    Keywords

    • Cliques
    • Power-law distributions
    • Random graphs
    • Scale-free networks
    • Subgraphs

    Fingerprint Dive into the research topics of 'Counting cliques and cycles in scale-free inhomogeneous random graphs'. Together they form a unique fingerprint.

    Cite this