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 language | English |
|---|---|
| Pages (from-to) | 161-184 |
| Number of pages | 24 |
| Journal | Journal of Statistical Physics |
| Volume | 175 |
| Issue number | 1 |
| Early online date | 18 Jan 2019 |
| DOIs | |
| Publication status | Published - 15 Apr 2019 |
Fingerprint
Keywords
- Cliques
- Power-law distributions
- Random graphs
- Scale-free networks
- Subgraphs
Cite this
}
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 journal › Article › Academic › peer-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 -