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