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

18 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

Fingerprint

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

Keywords

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

Cite this

@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",
day = "15",
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, No. 1, 15.04.2019, p. 161-184.

Research output: Contribution to journalArticleAcademicpeer-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/15

Y1 - 2019/4/15

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

AN - SCOPUS:85061721289

VL - 175

SP - 161

EP - 184

JO - Journal of Statistical Physics

JF - Journal of Statistical Physics

SN - 0022-4715

IS - 1

ER -