Beyond Asymptotics: Practical Insights into Community Detection in Complex Networks
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912145012162560 |
|---|---|
| author | Ke, Tianjun Xu, Zhiyu |
| author_facet | Ke, Tianjun Xu, Zhiyu |
| contents | The stochastic block model (SBM) is a fundamental tool for community detection in networks, yet the finite-sample performance of inference methods remains underexplored. We evaluate key algorithms-spectral methods, variational inference, and Gibbs sampling-under varying conditions, including signal-to-noise ratios, heterogeneous community sizes, and multimodality. Our results highlight significant performance variations: spectral methods, especially SCORE, excel in computational efficiency and scalability, while Gibbs sampling dominates in small, well-separated networks. Variational Expectation-Maximization strikes a balance between accuracy and cost in larger networks but struggles with optimization in highly imbalanced settings. These findings underscore the practical trade-offs among methods and provide actionable guidance for algorithm selection in real-world applications. Our results also call for further theoretical investigation in SBMs with complex structures. The code can be found at https://github.com/Toby-X/SBM_computation. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_03805 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Beyond Asymptotics: Practical Insights into Community Detection in Complex Networks Ke, Tianjun Xu, Zhiyu Social and Information Networks Applications The stochastic block model (SBM) is a fundamental tool for community detection in networks, yet the finite-sample performance of inference methods remains underexplored. We evaluate key algorithms-spectral methods, variational inference, and Gibbs sampling-under varying conditions, including signal-to-noise ratios, heterogeneous community sizes, and multimodality. Our results highlight significant performance variations: spectral methods, especially SCORE, excel in computational efficiency and scalability, while Gibbs sampling dominates in small, well-separated networks. Variational Expectation-Maximization strikes a balance between accuracy and cost in larger networks but struggles with optimization in highly imbalanced settings. These findings underscore the practical trade-offs among methods and provide actionable guidance for algorithm selection in real-world applications. Our results also call for further theoretical investigation in SBMs with complex structures. The code can be found at https://github.com/Toby-X/SBM_computation. |
| title | Beyond Asymptotics: Practical Insights into Community Detection in Complex Networks |
| topic | Social and Information Networks Applications |
| url | https://arxiv.org/abs/2412.03805 |