Comparative Study for Inference of Hidden Classes in Stochastic Block Models

Abstract

Inference of hidden classes in stochastic block model is a classical problem with important applications. Most commonly used methods for this problem involve na\"ıve mean field approaches or heuristic spectral methods. Recently, belief propagation was proposed for this problem. In this contribution we perform a comparative study between the three methods on synthetically created networks. We show that belief propagation shows much better performance when compared to na\"ıve mean field and spectral approaches. This applies to accuracy, computational efficiency and the tendency to overfit the data.

8 pages, 5 figures AIGM12

References in corpus (10)

• Finding and evaluating community structure in networks
• Finding community structure in networks using the eigenvectors of matrices
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Phase transition in the detection of modules in sparse networks
• Graph spectra and the detectability of community structure in networks
• A Bayesian Approach to Network Modularity
• Community Detection as an Inference Problem
• (Un)detectable cluster structure in sparse networks
• Protein-Interaction-Networks: More than mere modules
• The interplay of microscopic and mesoscopic structure in complex networks

Cited by in corpus (15)

• Spectral redemption: clustering sparse networks
• Statistical physics of inference: Thresholds and algorithms
• Parsimonious module inference in large networks
• Learning Latent Block Structure in Weighted Networks
• Evaluating Overfit and Underfit in Models of Network Community Structure
• Detectability thresholds and optimal algorithms for community structure in dynamic networks
• Phase transitions in semisupervised clustering of sparse networks
• Community Detection with Side Information: Exact Recovery under the Stochastic Block Model
• Limitations in the spectral method for graph partitioning: detectability threshold and localization of eigenvectors
• Hierarchical community structure in networks
• Finding communities in sparse networks
• Universal Phase Transition in Community Detectability under a Stochastic Block Model
• Fast Maximum Likelihood estimation via Equilibrium Expectation for Large Network Data
• Multilayer Modularity Belief Propagation To Assess Detectability Of Community Structure
• Soft happy colourings and community structure of networks