Localized geometry detection in scale-free random graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866917199983149056 |
|---|---|
| author | Bet, Gianmarco Michielan, Riccardo Stegehuis, Clara |
| author_facet | Bet, Gianmarco Michielan, Riccardo Stegehuis, Clara |
| contents | We consider the problem of detecting whether a power-law inhomogeneous random graph contains a geometric community, and we frame this as an hypothesis testing problem. More precisely, we assume that we are given a sample from an unknown distribution on the space of graphs on n vertices. Under the null hypothesis, the sample originates from the inhomogeneous random graph with a heavy-tailed degree sequence. Under the alternative hypothesis, $k = o(n)$ vertices are given spatial locations and connect between each other following the geometric inhomogeneous random graph connection rule. The remaining $n-k$ vertices follow the inhomogeneous random graph connection rule. We propose a simple and efficient test, which is based on counting normalized triangles, to differentiate between the two hypotheses. We prove that our test correctly detects the presence of the community with high probability as $n \to \infty$, and identifies large-degree vertices of the community with high probability. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2303_02965 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Localized geometry detection in scale-free random graphs Bet, Gianmarco Michielan, Riccardo Stegehuis, Clara Statistics Theory Probability We consider the problem of detecting whether a power-law inhomogeneous random graph contains a geometric community, and we frame this as an hypothesis testing problem. More precisely, we assume that we are given a sample from an unknown distribution on the space of graphs on n vertices. Under the null hypothesis, the sample originates from the inhomogeneous random graph with a heavy-tailed degree sequence. Under the alternative hypothesis, $k = o(n)$ vertices are given spatial locations and connect between each other following the geometric inhomogeneous random graph connection rule. The remaining $n-k$ vertices follow the inhomogeneous random graph connection rule. We propose a simple and efficient test, which is based on counting normalized triangles, to differentiate between the two hypotheses. We prove that our test correctly detects the presence of the community with high probability as $n \to \infty$, and identifies large-degree vertices of the community with high probability. |
| title | Localized geometry detection in scale-free random graphs |
| topic | Statistics Theory Probability |
| url | https://arxiv.org/abs/2303.02965 |