Large deviations for subgraphs in inhomogeneous random graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917318387302400 |
|---|---|
| author | Michielan, Riccardo Stegehuis, Clara Zwart, Bert |
| author_facet | Michielan, Riccardo Stegehuis, Clara Zwart, Bert |
| contents | Inhomogeneous random graphs are fundamental models for real-world networks, where prescribed degrees are imposed as soft constraints. A common assumption in such models is that the degree distribution follows a power-law, capturing the heavy-tailed nature observed in many contexts. While various graph functionals have been studied in this setting, inhomogeneity makes their analysis significantly more challenging. The goal of this paper is to investigate the large deviations of subgraph counts in inhomogeneous random graphs. Rare events concerning these functionals translate into quantifying the probability that extremely large hubs appear in the graph. This can be achieved by defining a specific optimization problem that captures the most likely way to generate numerous additional subgraphs. When the expected number of subgraphs is sublinear in the graph size, polynomially large deviations are possible, and in this case, we can derive sharp results on clique counts. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_06261 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Large deviations for subgraphs in inhomogeneous random graphs Michielan, Riccardo Stegehuis, Clara Zwart, Bert Probability Inhomogeneous random graphs are fundamental models for real-world networks, where prescribed degrees are imposed as soft constraints. A common assumption in such models is that the degree distribution follows a power-law, capturing the heavy-tailed nature observed in many contexts. While various graph functionals have been studied in this setting, inhomogeneity makes their analysis significantly more challenging. The goal of this paper is to investigate the large deviations of subgraph counts in inhomogeneous random graphs. Rare events concerning these functionals translate into quantifying the probability that extremely large hubs appear in the graph. This can be achieved by defining a specific optimization problem that captures the most likely way to generate numerous additional subgraphs. When the expected number of subgraphs is sublinear in the graph size, polynomially large deviations are possible, and in this case, we can derive sharp results on clique counts. |
| title | Large deviations for subgraphs in inhomogeneous random graphs |
| topic | Probability |
| url | https://arxiv.org/abs/2603.06261 |