Universality of the stochastic block model

Abstract

Mesoscopic pattern extraction (MPE) is the problem of finding a partition of the nodes of a complex network that maximizes some objective function. Many well-known network inference problems fall in this category, including, for instance, community detection, core-periphery identification, and imperfect graph coloring. In this paper, we show that the most popular algorithms designed to solve MPE problems can in fact be understood as special cases of the maximum likelihood formulation of the stochastic block model (SBM), or one of its direct generalizations. These equivalence relations show that the SBM is nearly universal with respect to MPE problems.

arXiv comment13 pages, 4 figures

References in corpus (46)

• Fast unfolding of communities in large networks
• Finding and evaluating community structure in networks
• Modularity and community structure in networks
• Community detection in graphs
• Near linear time algorithm to detect community structures in large-scale networks
• Hierarchical structure and the prediction of missing links in networks
• Statistical Mechanics of Community Detection
• Stochastic blockmodels and community structure in networks
• Community detection in networks: A user guide
• Random walks and diffusion on networks
• The ground truth about metadata and community detection in networks
• Spectral methods for network community detection and graph partitioning
• Phase transition in the detection of modules in sparse networks
• Structure and inference in annotated networks
• An efficient and principled method for detecting communities in networks
• Narrow scope for resolution-limit-free community detection
• Community detection in networks: Modularity optimization and maximum likelihood are equivalent
• Detecting network communities by propagating labels under constraints
• Uncovering space-independent communities in spatial networks
• Size reduction of complex networks preserving modularity
• Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models
• Local resolution-limit-free Potts model for community detection
• Scalable detection of statistically significant communities and hierarchies, using message-passing for modularity
• Efficiently inferring community structure in bipartite networks
• Evaluating Overfit and Underfit in Models of Network Community Structure
• The many facets of community detection in complex networks
• Hiding Quiet Solutions in Random Constraint Satisfaction Problems
• Network histograms and universality of blockmodel approximation
• Community detection and graph partitioning
• Finding multiple core-periphery pairs in networks
• (Un)detectable cluster structure in sparse networks
• Unifying Sparsest Cut, Cluster Deletion, and Modularity Clustering Objectives with Correlation Clustering
• Note on the equivalence of the label propagation method of community detection and a Potts model approach
• The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness
• Network structure, metadata and the prediction of missing nodes and annotations
• Belief propagation for graph partitioning
• Algorithmic detectability threshold of the stochastic block model
• Phase Transitions in Community Detection: A Solvable Toy Model
• Comparative analysis on the selection of number of clusters in community detection
• Detectability of the spectral method for sparse graph partitioning
• Finite size analysis of the detectability limit of the stochastic block model
• Detectability thresholds of general modular graphs
• Algorithmic infeasibility of community detection in higher-order networks
• Case studies in network community detection
• On approximate equivalence of modularity, D and non-negative matrix factorization
• Relating modularity maximization and stochastic block models in multilayer networks

Cited by in corpus (15)

• Networks beyond pairwise interactions: structure and dynamics
• A Clarified Typology of Core-Periphery Structure in Networks
• Descriptive vs. inferential community detection in networks: pitfalls, myths, and half-truths
• Community Detection in Bipartite Networks with Stochastic Blockmodels
• Interplay between $k$-core and community structure in complex networks
• Exact Clustering in Tensor Block Model: Statistical Optimality and Computational Limit
• Implicit models, latent compression, intrinsic biases, and cheap lunches in community detection
• Inference of Edge Correlations in Multilayer Networks
• Exact and rapid linear clustering of networks with dynamic programming
• Metrics matter in community detection
• Detectability of Macroscopic Structures in Directed Asymmetric Stochastic Block Model
• Discovering Block Structure in Networks
• From Leiden to Pleasure Island: The Constant Potts Model for Community Detection as a Hedonic Game
• Loan maturity aggregation in interbank lending networks obscures mesoscale structure and economic functions
• Quantifying metadata relevance to network block structure using description length