## Optimal couplings between sparse block models

HTML articles powered by AMS MathViewer

- by James Hirst PDF
- Proc. Amer. Math. Soc.
**149**(2021), 97-105 Request permission

## 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(\sqrt {n})$ to $\Omega (n)$ as the planted bisection in the block model varies. This settles half of a conjecture of Bollobá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.## References

- Béla Bollobás and Oliver Riordan,
*Metrics for sparse graphs*, Surveys in combinatorics 2009, London Math. Soc. Lecture Note Ser., vol. 365, Cambridge Univ. Press, Cambridge, 2009, pp. 211–287. MR**2588543** - Béla Bollobás and Oliver Riordan,
*Sparse graphs: metrics and random models*, Random Structures Algorithms**39**(2011), no. 1, 1–38. MR**2839983**, DOI 10.1002/rsa.20334 - Christian Borgs, Jennifer T. Chayes, Henry Cohn, and Yufei Zhao,
*An $L^p$ theory of sparse graph convergence I: Limits, sparse random graph models, and power law distributions*, Trans. Amer. Math. Soc.**372**(2019), no. 5, 3019–3062. MR**3988601**, DOI 10.1090/tran/7543 - C. Borgs, J. T. Chayes, L. Lovász, V. T. Sós, and K. Vesztergombi,
*Convergent sequences of dense graphs. I. Subgraph frequencies, metric properties and testing*, Adv. Math.**219**(2008), no. 6, 1801–1851. MR**2455626**, DOI 10.1016/j.aim.2008.07.008 - Aurelien Decelle, Florent Krzakala, Cristopher Moore, and Lenka Zdeborová,
*Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications*, Phys. Rev. E**84**(2011), 066106. - Amir Dembo, Andrea Montanari, and Subhabrata Sen,
*Extremal cuts of sparse random graphs*, Ann. Probab.**45**(2017), no. 2, 1190–1217. MR**3630296**, DOI 10.1214/15-AOP1084 - Adel Javanmard, Andrea Montanari, and Federico Ricci-Tersenghi,
*Phase transitions in semidefinite relaxations*, Proc. Natl. Acad. Sci. USA**113**(2016), no. 16, E2218–E2223. MR**3494080**, DOI 10.1073/pnas.1523097113 - Oystein Ore,
*Theory of graphs*, American Mathematical Society Colloquium Publications, Vol. XXXVIII, American Mathematical Society, Providence, R.I., 1962. MR**0150753** - Andrea Montanari and Subhabrata Sen,
*Semidefinite programs on sparse random graphs and their application to community detection*, STOC’16—Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, ACM, New York, 2016, pp. 814–827. MR**3536616**, DOI 10.1145/2897518.2897548 - Elchanan Mossel, Joe Neeman, and Allan Sly,
*Reconstruction and estimation in the planted partition model*, Probab. Theory Related Fields**162**(2015), no. 3-4, 431–461. MR**3383334**, DOI 10.1007/s00440-014-0576-6 - Elchanan Mossel, Joe Neeman, and Allan Sly,
*A proof of the block model threshold conjecture*, Combinatorica**38**(2018), no. 3, 665–708. MR**3876880**, DOI 10.1007/s00493-016-3238-8 - Filippo Santambrogio,
*Optimal transport for applied mathematicians*, Progress in Nonlinear Differential Equations and their Applications, vol. 87, Birkhäuser/Springer, Cham, 2015. Calculus of variations, PDEs, and modeling. MR**3409718**, DOI 10.1007/978-3-319-20828-2 - Subhabrata Sen,
*Optimization on sparse random hypergraphs and spin glasses*, Random Structures Algorithms**53**(2018), no. 3, 504–536. MR**3854043**, DOI 10.1002/rsa.20774 - J. Michael Steele,
*An Efron-Stein inequality for nonsymmetric statistics*, Ann. Statist.**14**(1986), no. 2, 753–758. MR**840528**, DOI 10.1214/aos/1176349952

## Additional Information

**James Hirst**- Affiliation: Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
- MR Author ID: 1048445
- Email: jhirst137@gmail.com
- Received by editor(s): October 14, 2019
- Received by editor(s) in revised form: June 1, 2020
- Published electronically: October 9, 2020
- Communicated by: Patricia L. Hersh
- © Copyright 2020 American Mathematical Society
- Journal: Proc. Amer. Math. Soc.
**149**(2021), 97-105 - MSC (2010): Primary 05C80
- DOI: https://doi.org/10.1090/proc/15218
- MathSciNet review: 4172589