Recovery and rigidity in a regular stochastic block model

DOI10.1137/1.9781611974331.CH108MaRDI QIDQ4575692zbMATH OpenOpenAlexFDO

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)

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

Mathematics Subject Classification ID

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

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.

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

Cited in

(21)

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

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)