Optimal couplings between sparse block models
Author:
James Hirst
Journal:
Proc. Amer. Math. Soc. 149 (2021), 97-105
MSC (2010):
Primary 05C80
DOI:
https://doi.org/10.1090/proc/15218
Published electronically:
October 9, 2020
Full-text PDF
Abstract | References | Similar Articles | Additional Information
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 , we show that the distance to which the models can be coupled undergoes a phase transition from
to
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
edges which allows for samples from a limit object to converge back to the limit itself must identify these models.
- [1] 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
- [2] Béla Bollobás and Oliver Riordan, Sparse graphs: metrics and random models, Random Structures Algorithms 39 (2011), no. 1, 1–38. MR 2839983, https://doi.org/10.1002/rsa.20334
- [3] Christian Borgs, Jennifer T. Chayes, Henry Cohn, and Yufei Zhao, An 𝐿^{𝑝} 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, https://doi.org/10.1090/tran/7543
- [4] 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, https://doi.org/10.1016/j.aim.2008.07.008
- [5]
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. - [6] Amir Dembo, Andrea Montanari, and Subhabrata Sen, Extremal cuts of sparse random graphs, Ann. Probab. 45 (2017), no. 2, 1190–1217. MR 3630296, https://doi.org/10.1214/15-AOP1084
- [7] 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, https://doi.org/10.1073/pnas.1523097113
- [8] Oystein Ore, Theory of graphs, American Mathematical Society Colloquium Publications, Vol. XXXVIII, American Mathematical Society, Providence, R.I., 1962. MR 0150753
- [9] 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, https://doi.org/10.1145/2897518.2897548
- [10] 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, https://doi.org/10.1007/s00440-014-0576-6
- [11] Elchanan Mossel, Joe Neeman, and Allan Sly, A proof of the block model threshold conjecture, Combinatorica 38 (2018), no. 3, 665–708. MR 3876880, https://doi.org/10.1007/s00493-016-3238-8
- [12] 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
- [13] Subhabrata Sen, Optimization on sparse random hypergraphs and spin glasses, Random Structures Algorithms 53 (2018), no. 3, 504–536. MR 3854043, https://doi.org/10.1002/rsa.20774
- [14] J. Michael Steele, An Efron-Stein inequality for nonsymmetric statistics, Ann. Statist. 14 (1986), no. 2, 753–758. MR 840528, https://doi.org/10.1214/aos/1176349952
Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 05C80
Retrieve articles in all journals with MSC (2010): 05C80
Additional Information
James Hirst
Affiliation:
Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Email:
jhirst137@gmail.com
DOI:
https://doi.org/10.1090/proc/15218
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
Article copyright:
© Copyright 2020
American Mathematical Society