SASH: Decoding Community Structure in Graphs
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_ | 1866915404809502720 |
|---|---|
| author | Beemer, Allison Bolkema, Jessalyn |
| author_facet | Beemer, Allison Bolkema, Jessalyn |
| contents | Detection of communities in a graph entails identifying clusters of densely connected vertices; the area has a variety of important applications and a rich literature. The problem has previously been situated in the realm of error correcting codes by viewing a graph as a noisy version of the assumed underlying communities. In this paper, we introduce an encoding of community structure along with the resulting code's parameters. We then present a novel algorithm, SASH, to decode to estimated communities given an observed dataset. We demonstrate the performance of SASH via simulations on an assortative planted partition model and on the Zachary's Karate Club dataset. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_16583 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | SASH: Decoding Community Structure in Graphs Beemer, Allison Bolkema, Jessalyn Social and Information Networks Information Theory Combinatorics Detection of communities in a graph entails identifying clusters of densely connected vertices; the area has a variety of important applications and a rich literature. The problem has previously been situated in the realm of error correcting codes by viewing a graph as a noisy version of the assumed underlying communities. In this paper, we introduce an encoding of community structure along with the resulting code's parameters. We then present a novel algorithm, SASH, to decode to estimated communities given an observed dataset. We demonstrate the performance of SASH via simulations on an assortative planted partition model and on the Zachary's Karate Club dataset. |
| title | SASH: Decoding Community Structure in Graphs |
| topic | Social and Information Networks Information Theory Combinatorics |
| url | https://arxiv.org/abs/2507.16583 |