How Local Separators Shape Community Structure in Large Networks
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916698862387200 |
|---|---|
| author | Frenkel, Sarah Carmesin, Johannes |
| author_facet | Frenkel, Sarah Carmesin, Johannes |
| contents | Community detection is a key tool for analyzing the structure of large networks. Standard methods, such as modularity optimization, focus on identifying densely connected groups but often overlook natural local separations in the graph. In this paper, we investigate local separator methods, which decompose networks based on structural bottlenecks rather than global connectivity. We systematically compare them with well-established community detection algorithms on large real-world networks. Our results show that local 1-separators consistently identify the densest communities, outperforming modularity-based methods in this regard, while local 2-separators reveal hierarchical structures but may over-fragment small clusters. These findings are particularly strong for road networks, suggesting practical applications in transportation and infrastructure analysis. Our study highlights local separators as a scalable and interpretable alternative for network decomposition. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_14501 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | How Local Separators Shape Community Structure in Large Networks Frenkel, Sarah Carmesin, Johannes Social and Information Networks Discrete Mathematics 68R10 (Primary) 05C40, 05C85, 05C90 (Secondary) G.2.2; G.2.1; F.2.2 Community detection is a key tool for analyzing the structure of large networks. Standard methods, such as modularity optimization, focus on identifying densely connected groups but often overlook natural local separations in the graph. In this paper, we investigate local separator methods, which decompose networks based on structural bottlenecks rather than global connectivity. We systematically compare them with well-established community detection algorithms on large real-world networks. Our results show that local 1-separators consistently identify the densest communities, outperforming modularity-based methods in this regard, while local 2-separators reveal hierarchical structures but may over-fragment small clusters. These findings are particularly strong for road networks, suggesting practical applications in transportation and infrastructure analysis. Our study highlights local separators as a scalable and interpretable alternative for network decomposition. |
| title | How Local Separators Shape Community Structure in Large Networks |
| topic | Social and Information Networks Discrete Mathematics 68R10 (Primary) 05C40, 05C85, 05C90 (Secondary) G.2.2; G.2.1; F.2.2 |
| url | https://arxiv.org/abs/2504.14501 |