Beyond Asymptotics: Practical Insights into Community Detection in Complex Networks

2024/12/05 by T. Tony Ke, Zhiyu Xu, Ke, Tianjun +1
Physics and Astronomy · Computer Science · #Complex Network Analysis Techniques #Opinion Dynamics and Social Influence #Network Security and Intrusion Detection

paper · pdf · doi:10.48550/arxiv.2412.03805

Abstract

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.

Related

• Improved Community Detection using Stochastic Block Models
• Minimax Rates of Community Detection in Stochastic Block Models
• Algorithm independent bounds on community detection problems and\n associated transitions in stochastic block model graphs
• Accurate Community Detection in the Stochastic Block Model via Spectral Algorithms
• Semi-Supervised Community Detection via Quasi-Stationary Distributions