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

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)

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

(20)

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