Optimal couplings between sparse block models

DOI10.1090/PROC/15218MaRDI QIDQ5146538zbMATH OpenOpenAlexFDO

Authors James Hirst

Publication date 26 January 2021

Published in Proceedings of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1910.05442

zbMATH Keywords

uniform random graphstochastic block model with a planted bisection

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: We study the problem of coupling a stochastic block model with a planted bisection to a uniform random graph having the same average degree. Focusing on the regime where the average degree is a constant relative to the number of vertices $n$, we show that the distance to which the models can be coupled undergoes a phase transition from $O(sqrtn)$ to $Omega(n)$ as the planted bisection in the block model varies. This settles half of a conjecture of Bollob'{a}s and Riordan and has some implications for sparse graph limit theory. In particular, for certain ranges of parameters, a block model and the corresponding uniform model produce samples which must converge to the same limit point. This implies that any notion of convergence for sequences of graphs with $Theta(n)$ edges which allows for samples from a limit object to converge back to the limit itself must identify these models.

Recommendations

• Hurdle Blockmodels for Sparse Network Modeling
• scientific article; zbMATH DE number 7626708
• Sparse estimation of huge networks with a block‐wise structure
• On model selection for dense stochastic block models
• Sparse and smooth: improved guarantees for spectral clustering in the dynamic stochastic block model
• Hypothesis testing in sparse weighted stochastic block model
• Sparse nonparametric graphical models
• Sparse Matrix Graphical Models
• Community detection in the sparse hypergraph stochastic block model
• Hybrid maximum likelihood inference for stochastic block models

Cites work

• scientific article; zbMATH DE number 3172309 (Why is no real title available?)
• A proof of the block model threshold conjecture
• An Efron-Stein inequality for nonsymmetric statistics
• An L^p theory of sparse graph convergence. I: Limits, sparse random graph models, and power law distributions
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• Extremal cuts of sparse random graphs
• Metrics for sparse graphs
• Optimal transport for applied mathematicians. Calculus of variations, PDEs, and modeling
• Optimization on sparse random hypergraphs and spin glasses
• Phase transitions in semidefinite relaxations
• Reconstruction and estimation in the planted partition model
• Semidefinite programs on sparse random graphs and their application to community detection
• Sparse graphs: metrics and random models

Cited in

(2)

• Contiguity and non-reconstruction results for planted partition models: the dense case
• Strong couplings for static locally tree-like random graphs

This page was built for publication: Optimal couplings between sparse block models

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5146538)