Asymptotics for cliques in scale-free random graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2020
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910687271321600 |
|---|---|
| author | Daly, Fraser Haig, Alastair Shneer, Seva |
| author_facet | Daly, Fraser Haig, Alastair Shneer, Seva |
| contents | In this paper we establish asymptotics (as the size of the graph grows to infinity) for the expected number of cliques in the Chung--Lu inhomogeneous random graph model in which vertices are assigned independent weights which have tail probabilities $h^{1-α}l(h)$, where $α>2$ and $l$ is a slowly varying function. Each pair of vertices is connected by an edge with a probability proportional to the product of the weights of those vertices. We present a complete set of asymptotics for all clique sizes and for all non-integer $α> 2$. We also explain why the case of an integer $α$ is different, and present partial results for the asymptotics in that case. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2008_11557 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | Asymptotics for cliques in scale-free random graphs Daly, Fraser Haig, Alastair Shneer, Seva Probability 05C80, 60F05 In this paper we establish asymptotics (as the size of the graph grows to infinity) for the expected number of cliques in the Chung--Lu inhomogeneous random graph model in which vertices are assigned independent weights which have tail probabilities $h^{1-α}l(h)$, where $α>2$ and $l$ is a slowly varying function. Each pair of vertices is connected by an edge with a probability proportional to the product of the weights of those vertices. We present a complete set of asymptotics for all clique sizes and for all non-integer $α> 2$. We also explain why the case of an integer $α$ is different, and present partial results for the asymptotics in that case. |
| title | Asymptotics for cliques in scale-free random graphs |
| topic | Probability 05C80, 60F05 |
| url | https://arxiv.org/abs/2008.11557 |