Recovery and rigidity in a regular stochastic block model

DOI10.1137/1.9781611974331.CH108zbMATH Open1410.68283arXiv1507.00930OpenAlexW1427638023MaRDI QIDQ4575692FDOQ4575692

Authors: Gerandy Brito, Ioana Dumitriu, Shirshendu Ganguly, Christopher Hoffman, Linh Viet Tran 

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Abstract: The stochastic block model is a natural model for studying community detection in random networks. Its clustering properties have been extensively studied in the statistics, physics and computer science literature. Recently this area has experienced major mathematical breakthroughs, particularly for the binary (two-community) version, see Mossel, Neeman, Sly (2012, 2013) and Massoulie (2013). In this paper, we introduce a variant of the binary model which we call the regular stochastic block model (RSBM). We prove rigidity by showing that with high probability an exact recovery of the community structure is possible. Spectral methods exhibit a regime where this can be done efficiently. Moreover we also prove that, in this setting, any suitably good partial recovery can be bootstrapped to obtain a full recovery of the communities.

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

Recommendations

• Community detection and stochastic block models: recent developments
• Community detection and stochastic block models
• Non-convex exact community recovery in stochastic block model
• A spectral method for community detection in moderately sparse degree-corrected stochastic block models
• Consistency of spectral clustering in stochastic block models

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Social networks; opinion dynamics (91D30)

Cited In (20)

• Community detection in the sparse hypergraph stochastic block model
• Exact recovery in the Ising blockmodel
• Average whenever you meet: opportunistic protocols for community detection
• The Lovász theta function for random regular graphs and community detection in the hard regime
• An impossibility result for reconstruction in the degree-corrected stochastic block model
• Exact Recovery and Sharp Thresholds of Stochastic Ising Block Model
• Spectral gap in random bipartite biregular graphs and applications
• Non-convex exact community recovery in stochastic block model
• Empirical spectral measures of quantum graphs in the Benjamini-Schramm limit
• Nonreconstruction of high-dimensional stochastic block model with bounded degree
• The Lovász theta function for random regular graphs and community detection in the hard regime
• Community detection and stochastic block models
• Quantum ergodicity for expanding quantum graphs in the regime of spectral delocalization
• Spectra of random regular hypergraphs
• Stochastic block model in a new critical regime and the interacting multiplicative coalescent
• Recent results of quantum ergodicity on graphs and further investigation
• Find Your Place: Simple Distributed Algorithms for Community Detection
• Spectral density of equitable core-periphery graphs
• Sparse general Wigner-type matrices: local law and eigenvector delocalization
• \(L^p\) norms and support of eigenfunctions on graphs

This page was built for publication: Recovery and rigidity in a regular stochastic block model

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