Counting cliques and cycles in scale-free inhomogeneous random graphs

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

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

Uittreksel

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.

TaalEngels
Pagina's161-184
Aantal pagina's24
TijdschriftJournal of Statistical Physics
Volume175
Nummer van het tijdschrift1
Vroegere onlinedatum18 jan 2019
DOI's
StatusGepubliceerd - apr 2019

Vingerafdruk

Clique
Random Graphs
Counting
counting
Cycle
cycles
Infinite Variance
Circulant Matrix
Scale-free Networks
Asymptotic Analysis
matrices
Model

Trefwoorden

    Citeer dit

    @article{9c303af7546049489d163828837ea99e,
    title = "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.",
    keywords = "Cliques, Power-law distributions, Random graphs, Scale-free networks, Subgraphs",
    author = "A.J.E.M. Janssen and {van Leeuwaarden}, {Johan S.H.} and Seva Shneer",
    year = "2019",
    month = "4",
    doi = "10.1007/s10955-019-02248-w",
    language = "English",
    volume = "175",
    pages = "161--184",
    journal = "Journal of Statistical Physics",
    issn = "0022-4715",
    publisher = "Springer",
    number = "1",

    }

    Counting cliques and cycles in scale-free inhomogeneous random graphs. / Janssen, A.J.E.M.; van Leeuwaarden, Johan S.H. (Corresponding author); Shneer, Seva.

    In: Journal of Statistical Physics, Vol. 175, Nr. 1, 04.2019, blz. 161-184.

    Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

    TY - JOUR

    T1 - Counting cliques and cycles in scale-free inhomogeneous random graphs

    AU - Janssen,A.J.E.M.

    AU - van Leeuwaarden,Johan S.H.

    AU - Shneer,Seva

    PY - 2019/4

    Y1 - 2019/4

    N2 - 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.

    AB - 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.

    KW - Cliques

    KW - Power-law distributions

    KW - Random graphs

    KW - Scale-free networks

    KW - Subgraphs

    UR - http://www.scopus.com/inward/record.url?scp=85061721289&partnerID=8YFLogxK

    U2 - 10.1007/s10955-019-02248-w

    DO - 10.1007/s10955-019-02248-w

    M3 - Article

    VL - 175

    SP - 161

    EP - 184

    JO - Journal of Statistical Physics

    T2 - Journal of Statistical Physics

    JF - Journal of Statistical Physics

    SN - 0022-4715

    IS - 1

    ER -