A large deviation principle for block models
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2020
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914039214374912 |
|---|---|
| author | Borgs, Christian Chayes, Jennifer Gaudio, Julia Petti, Samantha Sen, Subhabrata |
| author_facet | Borgs, Christian Chayes, Jennifer Gaudio, Julia Petti, Samantha Sen, Subhabrata |
| contents | We initiate a study of large deviations for block model random graphs in the dense regime. Following Chatterjee-Varadhan(2011), we establish an LDP for dense block models, viewed as random graphons. As an application of our result, we study upper tail large deviations for homomorphism densities of regular graphs. We identify the existence of a "symmetric" phase, where the graph, conditioned on the rare event, looks like a block model with the same block sizes as the generating graphon. In specific examples, we also identify the existence of a "symmetry breaking" regime, where the conditional structure is not a block model with compatible dimensions. This identifies a "reentrant phase transition" phenomenon for this problem -- analogous to one established for Erdos-Renyi random graphs (Chatterjee-Dey(2010), Chatterjee-Varadhan(2011)). Finally, extending the analysis of Lubetzky-Zhao(2015), we identify the precise boundary between the symmetry and symmetry breaking regime for homomorphism densities of regular graphs and the operator norm on Erdos-Renyi bipartite graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2007_14508 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | A large deviation principle for block models Borgs, Christian Chayes, Jennifer Gaudio, Julia Petti, Samantha Sen, Subhabrata Probability Combinatorics 60F10, 05C80, 60C05 We initiate a study of large deviations for block model random graphs in the dense regime. Following Chatterjee-Varadhan(2011), we establish an LDP for dense block models, viewed as random graphons. As an application of our result, we study upper tail large deviations for homomorphism densities of regular graphs. We identify the existence of a "symmetric" phase, where the graph, conditioned on the rare event, looks like a block model with the same block sizes as the generating graphon. In specific examples, we also identify the existence of a "symmetry breaking" regime, where the conditional structure is not a block model with compatible dimensions. This identifies a "reentrant phase transition" phenomenon for this problem -- analogous to one established for Erdos-Renyi random graphs (Chatterjee-Dey(2010), Chatterjee-Varadhan(2011)). Finally, extending the analysis of Lubetzky-Zhao(2015), we identify the precise boundary between the symmetry and symmetry breaking regime for homomorphism densities of regular graphs and the operator norm on Erdos-Renyi bipartite graphs. |
| title | A large deviation principle for block models |
| topic | Probability Combinatorics 60F10, 05C80, 60C05 |
| url | https://arxiv.org/abs/2007.14508 |