Large deviations for triangles in scale-free random graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913277163864064 |
|---|---|
| author | Stegehuis, Clara Zwart, Bert |
| author_facet | Stegehuis, Clara Zwart, Bert |
| contents | We provide large deviations estimates for the upper tail of the number of triangles in scale-free inhomogeneous random graphs where the degrees have power law tails with index $-α, α\in (1,2)$. We show that upper tail probabilities for triangles undergo a phase transition. For $α<4/3$, the upper tail is caused by many vertices of degree of order $n$, and this probability is semi-exponential. In this regime, additional triangles consist of two hubs. For $α>4/3$ on the other hand, the upper tail is caused by one hub of a specific degree, and this probability decays polynomially in $n$, leading to additional triangles with one hub. In the intermediate case $α=4/3$, we show polynomial decay of the tail probability caused by multiple but finitely many hubs. In this case, the additional triangles contain either a single hub or two hubs. Our proofs are partly based on various concentration inequalities. In particular, we tailor concentration bounds for empirical processes to make them well-suited for analyzing heavy-tailed phenomena in nonlinear settings. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2303_09198 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Large deviations for triangles in scale-free random graphs Stegehuis, Clara Zwart, Bert Probability We provide large deviations estimates for the upper tail of the number of triangles in scale-free inhomogeneous random graphs where the degrees have power law tails with index $-α, α\in (1,2)$. We show that upper tail probabilities for triangles undergo a phase transition. For $α<4/3$, the upper tail is caused by many vertices of degree of order $n$, and this probability is semi-exponential. In this regime, additional triangles consist of two hubs. For $α>4/3$ on the other hand, the upper tail is caused by one hub of a specific degree, and this probability decays polynomially in $n$, leading to additional triangles with one hub. In the intermediate case $α=4/3$, we show polynomial decay of the tail probability caused by multiple but finitely many hubs. In this case, the additional triangles contain either a single hub or two hubs. Our proofs are partly based on various concentration inequalities. In particular, we tailor concentration bounds for empirical processes to make them well-suited for analyzing heavy-tailed phenomena in nonlinear settings. |
| title | Large deviations for triangles in scale-free random graphs |
| topic | Probability |
| url | https://arxiv.org/abs/2303.09198 |