Community Detection on Block Models with Geometric Kernels
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908884698923008 |
|---|---|
| author | Avrachenkov, Konstantin Kumar, B. R. Vinay Leskelä, Lasse |
| author_facet | Avrachenkov, Konstantin Kumar, B. R. Vinay Leskelä, Lasse |
| contents | We consider the community recovery problem on a one-dimensional random geometric graph where every node has two independent labels: an observed location label and a hidden community label. A geometric kernel maps the locations of pairs of nodes to probabilities. Edges are drawn between pairs of nodes based on their communities and the value of the kernel corresponding to the respective node locations. Given the graph so generated along with the location labels, the latent communities of the nodes are to be inferred. In this work, we will look into the fundamental statistical limits for recovering the communities in such models. Additionally, we propose a linear-time algorithm (in the number of edges) and show that it recovers the communities of nodes exactly up to the information theoretic threshold. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_02802 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Community Detection on Block Models with Geometric Kernels Avrachenkov, Konstantin Kumar, B. R. Vinay Leskelä, Lasse Probability 60D05, 62F30 We consider the community recovery problem on a one-dimensional random geometric graph where every node has two independent labels: an observed location label and a hidden community label. A geometric kernel maps the locations of pairs of nodes to probabilities. Edges are drawn between pairs of nodes based on their communities and the value of the kernel corresponding to the respective node locations. Given the graph so generated along with the location labels, the latent communities of the nodes are to be inferred. In this work, we will look into the fundamental statistical limits for recovering the communities in such models. Additionally, we propose a linear-time algorithm (in the number of edges) and show that it recovers the communities of nodes exactly up to the information theoretic threshold. |
| title | Community Detection on Block Models with Geometric Kernels |
| topic | Probability 60D05, 62F30 |
| url | https://arxiv.org/abs/2403.02802 |