Semi-supervised Community Detection using Glauber Dynamics for an Ising Model
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913889137983488 |
|---|---|
| author | Avrachenkov, Konstantin Goldsztajn, Diego |
| author_facet | Avrachenkov, Konstantin Goldsztajn, Diego |
| contents | We consider graphs with two communities and analyze an algorithm for learning the community labels when the edges of the graph and only a small fraction of the labels are known in advance. The algorithm is based on the Glauber dynamics for an Ising model where the energy function includes a quadratic penalty on the magnetization. The analysis focuses on graphs sampled from a Stochastic Block Model (SBM) with slowly growing mean degree. We derive a mean-field limit for the magnetization of each community, which can be used to choose the run-time of the algorithm to obtain a target accuracy level. We further prove that almost exact recovery is achieved in a number of iterations that is quasi-linear in the number of nodes. As a special case, our results provide the first rigorous analysis of the label propagation algorithm in the SBM with slowly diverging mean degree. We complement our theoretical results with several numerical experiments. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_09223 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Semi-supervised Community Detection using Glauber Dynamics for an Ising Model Avrachenkov, Konstantin Goldsztajn, Diego Statistics Theory 62H30 (Primary) 05C80, 60F17, 60J28 (Secondary) We consider graphs with two communities and analyze an algorithm for learning the community labels when the edges of the graph and only a small fraction of the labels are known in advance. The algorithm is based on the Glauber dynamics for an Ising model where the energy function includes a quadratic penalty on the magnetization. The analysis focuses on graphs sampled from a Stochastic Block Model (SBM) with slowly growing mean degree. We derive a mean-field limit for the magnetization of each community, which can be used to choose the run-time of the algorithm to obtain a target accuracy level. We further prove that almost exact recovery is achieved in a number of iterations that is quasi-linear in the number of nodes. As a special case, our results provide the first rigorous analysis of the label propagation algorithm in the SBM with slowly diverging mean degree. We complement our theoretical results with several numerical experiments. |
| title | Semi-supervised Community Detection using Glauber Dynamics for an Ising Model |
| topic | Statistics Theory 62H30 (Primary) 05C80, 60F17, 60J28 (Secondary) |
| url | https://arxiv.org/abs/2506.09223 |