On model selection for dense stochastic block models

DOI10.1017/apr.2021.29zbMath1483.62096OpenAlexW4205554023MaRDI QIDQ5066878

Ilkka Norros, Hannu Reittu, Fülöp Bazsó

Publication date: 31 March 2022

Published in: Advances in Applied Probability (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1017/apr.2021.29

zbMATH Keywords

random graphSzemerédi's regularity lemmaminimum description length principleregular decomposition

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Random matrices (probabilistic aspects) (60B20) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Statistical aspects of information-theoretic topics (62B10) Probabilistic graphical models (62H22)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Likelihood-based model selection for stochastic block models
• Relating multiway discrepancy and singular values of nonnegative rectangular matrices
• A universal prior for integers and estimation by minimum description length
• Estimating parameters of a probabilistic heterogeneous block model via the EM algorithm
• A combinatorial characterization of the testable graph properties
• Community detection thresholds and the weak Ramanujan property
• Achieving Optimal Misclassification Proportion in Stochastic Block Model