Clique and cycle frequencies in a sparse random graph model with overlapping communities
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2019
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912160390578176 |
|---|---|
| author | Gröhn, Tommi Karjalainen, Joona Leskelä, Lasse |
| author_facet | Gröhn, Tommi Karjalainen, Joona Leskelä, Lasse |
| contents | A statistical network model with overlapping communities can be generated as a superposition of mutually independent random graphs of varying size. The model is parameterized by the number of nodes, the number of communities, and the joint distribution of the community size and the edge probability. This model admits sparse parameter regimes with power-law limiting degree distributions and non-vanishing clustering coefficients. This article presents large-scale approximations of clique and cycle frequencies for graph samples generated by the model, which are valid for regimes with unbounded numbers of overlapping communities. Our results reveal the growth rates of these subgraph frequencies and show that their theoretical densities can be reliably estimated from data. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1911_12827 |
| institution | arXiv |
| publishDate | 2019 |
| record_format | arxiv |
| spellingShingle | Clique and cycle frequencies in a sparse random graph model with overlapping communities Gröhn, Tommi Karjalainen, Joona Leskelä, Lasse Probability Social and Information Networks Statistics Theory 62F10, 05C80, 60C05 A statistical network model with overlapping communities can be generated as a superposition of mutually independent random graphs of varying size. The model is parameterized by the number of nodes, the number of communities, and the joint distribution of the community size and the edge probability. This model admits sparse parameter regimes with power-law limiting degree distributions and non-vanishing clustering coefficients. This article presents large-scale approximations of clique and cycle frequencies for graph samples generated by the model, which are valid for regimes with unbounded numbers of overlapping communities. Our results reveal the growth rates of these subgraph frequencies and show that their theoretical densities can be reliably estimated from data. |
| title | Clique and cycle frequencies in a sparse random graph model with overlapping communities |
| topic | Probability Social and Information Networks Statistics Theory 62F10, 05C80, 60C05 |
| url | https://arxiv.org/abs/1911.12827 |