Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models

Abstract

We present an efficient algorithm for the inference of stochastic block models in large networks. The algorithm can be used as an optimized Markov chain Monte Carlo (MCMC) method, with a fast mixing time and a much reduced susceptibility to getting trapped in metastable states, or as a greedy agglomerative heuristic, with an almost linear $O(N{\ln }^{2}N)$ complexity, where $N$ is the number of nodes in the network, independent on the number of blocks being inferred. We show that the heuristic is capable of delivering results which are indistinguishable from the more exact and numerically expensive MCMC method in many artificial and empirical networks, despite being much faster. The method is entirely unbiased towards any specific mixing pattern, and in particular it does not favor assortative community structures.

9 pages, 9 figures

References in corpus (18)

• Fast unfolding of communities in large networks
• Finding community structure in networks using the eigenvectors of matrices
• Resolution limit in community detection
• Stochastic blockmodels and community structure in networks
• An information-theoretic framework for resolving community structure in complex networks
• Missing and spurious interactions and the reconstruction of complex networks
• Mixture models and exploratory analysis in networks
• Phase transition in the detection of modules in sparse networks
• A Bayesian Approach to Network Modularity
• The entropy of network ensembles
• Parsimonious module inference in large networks
• Uncovering latent structure in valued graphs: A variational approach
• Community Detection as an Inference Problem
• Maximum likelihood: extracting unbiased information from complex networks
• Efficient modularity optimization by multistep greedy algorithm and vertex mover refinement
• Role models for complex networks
• (Un)detectable cluster structure in sparse networks
• Multistep greedy algorithm identifies community structure in real-world and computer-generated networks

Cited by in corpus (67)

• Social physics
• The ground truth about metadata and community detection in networks
• Community detection in networks: Modularity optimization and maximum likelihood are equivalent
• Hierarchical Block Structures and High-resolution Model Selection in Large Networks
• A Review of Stochastic Block Models and Extensions for Graph Clustering
• Nonparametric Bayesian inference of the microcanonical stochastic block model
• On community structure in complex networks: challenges and opportunities
• Inferring the mesoscale structure of layered, edge-valued and time-varying networks
• Network reconstruction and community detection from dynamics
• Modeling sequences and temporal networks with dynamic community structures
• EdMot: An Edge Enhancement Approach for Motif-aware Community Detection
• Bayesian stochastic blockmodeling
• Nonparametric weighted stochastic block models
• Model selection and hypothesis testing for large-scale network models with overlapping groups
• Multilayer stochastic block models reveal the multilayer structure of complex networks
• A Clarified Typology of Core-Periphery Structure in Networks
• Reconstructing networks with unknown and heterogeneous errors
• Automatic Detection of Influential Actors in Disinformation Networks
• Streaming Graph Challenge: Stochastic Block Partition
• Descriptive vs. inferential community detection in networks: pitfalls, myths, and half-truths
• Disentangling bipartite and core-periphery structure in financial networks
• Collective dynamics of stock market efficiency
• Exploring the solution landscape enables more reliable network community detection
• Graph Clustering with Graph Neural Networks
• Merge-split Markov chain Monte Carlo for community detection
• Link prediction with hyperbolic geometry
• Community Detection in Bipartite Networks with Stochastic Blockmodels
• Network structure, metadata and the prediction of missing nodes and annotations
• Core-Periphery Structure in Directed Networks
• Incremental Lossless Graph Summarization
• Revealing consensus and dissensus between network partitions
• Universality of the stochastic block model
• Synwalk -- Community Detection via Random Walk Modelling
• Mean-field theory of graph neural networks in graph partitioning
• The organization of the interbank network and how ECB unconventional measures affected the e-MID overnight market
• Meta-validation of bipartite network projections
• From Relational Data to Graphs: Inferring Significant Links using Generalized Hypergeometric Ensembles
• Multilayer Networks for Text Analysis with Multiple Data Types
• The Infinite Degree Corrected Stochastic Block Model
• Algorithmic detectability threshold of the stochastic block model
• Discovering the hidden community structure of public transportation networks
• Percolation and the effective structure of complex networks
• Micro, Meso, Macro: the effect of triangles on communities in networks
• Comparative analysis on the selection of number of clusters in community detection
• Heuristic Modularity Maximization Algorithms for Community Detection Rarely Return an Optimal Partition or Anything Similar
• Ordered community detection in directed networks
• Regularized Stochastic Block Model for robust community detection in complex networks
• Weighted Community Detection and Data Clustering Using Message Passing
• Bayan Algorithm: Detecting Communities in Networks Through Exact and Approximate Optimization of Modularity
• Computational limits to the legibility of the imaged human brain
• Detectability thresholds of general modular graphs
• Probabilistic community detection with unknown number of communities
• CACTUS: a Comprehensive Abstraction and Classification Tool for Uncovering Structures
• Inference of hidden structures in complex physical systems by multi-scale clustering
• Social Discrete Choice Models
• The Atlas for the Aspiring Network Scientist
• Large deviations of connected components in the stochastic block model
• Detect opinion-based groups and reveal polarisation in survey data
• On role extraction for digraphs via neighbourhood pattern similarity
• Quantifying metadata relevance to network block structure using description length
• Finding community structure using the ordered random graph model
• The Feature-First Block Model
• Systematic assessment of the quality of fit of the stochastic block model for empirical networks
• Loan maturity aggregation in interbank lending networks obscures mesoscale structure and economic functions
• A Formal Critique of the Value of the Colombian Páramo
• Probabilistic Multilayer Networks
• Mapping Inter-City Trade Networks to Maximum Entropy Models using Electronic Invoice Data