mlsanityData to 7 Oct 2026

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

arXiv 1310.4378 ↗First posted 16 Oct 2013physics.data-an cond-mat.stat-mech cs.SIcited by 29

Not on the map. Why?

Abstract (arXiv)

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(Nln2N) 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.

Key facts. Cited by 29 papers in the map (data through 7 Oct 2026). First posted on arXiv 16 Oct 2013.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 5; 2022: 4; 2023: 7; 2024: 3; 2025: 7; 2026: 3.

29 papers.

Sort:

  1. 2023DGCLUSTER: A Neural Framework for Attributed Graph Clustering via Modularity Maximizationcited by 21
  2. 2024Node Identifiers: Compact, Discrete Representations for Efficient Graph Learningcited by 10
  3. 2022Bayan Algorithm: Detecting Communities in Networks Through Exact and Approximate Optimization of Modularitycited by 5
  4. 2023Analyzing Modularity Maximization in Approximation, Heuristic, and Graph Neural Network Algorithms for Community Detectioncited by 4
  5. 2021Multilayer Networks for Text Analysis with Multiple Data Typescited by 3
  6. 2021Descriptive vs. inferential community detection in networks: pitfalls, myths, and half-truthscited by 3
  7. 2023CACTUS: a Comprehensive Abstraction and Classification Tool for Uncovering Structurescited by 3
  8. 2025Generating Directed Graphs with Dual Attention and Asymmetric Encodingcited by 3
  9. 2022Tackling Provably Hard Representative Selection via Graph Neural Networkscited by 2
  10. 2023Heuristic Modularity Maximization Algorithms for Community Detection Rarely Return an Optimal Partition or Anything Similarcited by 2
  11. 2023The Map Equation Goes Neural: Mapping Network Flows with Graph Neural Networkscited by 2
  12. 2024Towards Faster Graph Partitioning via Pre-training and Inductive Inferencecited by 2
17 more
  1. 2022Systematic assessment of the quality of fit of the stochastic block model for empirical networkscited by 1
  2. 2023Computational limits to the legibility of the imaged human braincited by 1
  3. 2025InfraredGP: Efficient Graph Partitioning via Spectral Graph Neural Networks with Negative Correctionscited by 1
  4. 2026Matrix Factorization Framework for Community Detection under the Degree-Corrected Block Modelcited by 1
  5. 2026Cluster Attention for Graph Machine Learningcited by 1
  6. 2021Synwalk -- Community Detection via Random Walk Modellingcited by 0
  7. 2021The Feature-First Block Modelcited by 0
  8. 2021SamBaS: Sampling-Based Stochastic Block Partitioningcited by 0
  9. 2022Trading off Quality for Efficiency of Community Detection: An Inductive Method across Graphscited by 0
  10. 2023Balancing Summarization and Change Detection in Graph Streamscited by 0
  11. 2024PASCO (PArallel Structured COarsening): an overlay to speed up graph clustering algorithmscited by 0
  12. 2025Robust Markov stability for community detection at a scale learned based on the structurecited by 0
  13. 2025Building Models of Neurological Languagecited by 0
  14. 2025How do Probabilistic Graphical Models and Graph Neural Networks Look at Network Data?cited by 0
  15. 2025Urban delineation through the lens of commute networks: Leveraging graph embeddings to distinguish socioeconomic groups in citiescited by 0
  16. 2025Model-free algorithms for fast node clustering in SBM type graphs and application to social role inference in animalscited by 0
  17. 2026Instance Discrimination for Link Predictioncited by 0