An impossibility result for reconstruction in the degree-corrected stochastic block model

DOI10.1214/18-AAP1381zbMATH Open1417.91409MaRDI QIDQ1617152FDOQ1617152

Authors: Lennart Gulikers, Marc Lelarge, Laurent Massoulié 

Publication date: 7 November 2018

Published in: The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL: https://projecteuclid.org/euclid.aoap/1535443240

Recommendations

• Nonreconstruction of high-dimensional stochastic block model with bounded degree
• Exact Recovery in the Stochastic Block Model
• Proof of the achievability conjectures for the general stochastic block model
• Non-backtracking spectrum of degree-corrected stochastic block models
• Degree-corrected stochastic block models and reliability in networks
• Exact recovery in the hypergraph stochastic block model: a spectral algorithm
• Recovery and rigidity in a regular stochastic block model
• Non-convex exact community recovery in stochastic block model
• Testing degree corrections in stochastic block models
• Convexified modularity maximization for degree-corrected stochastic block models

zbMATH Keywords

machine learningdegree-corrected stochastic block modelrandom graphsspectral algorithmsocial and information networks

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Randomized algorithms (68W20) Clustering in the social and behavioral sciences (91C20) Social networks; opinion dynamics (91D30)

Cites Work

• Consistency of spectral clustering in stochastic block models
• Spectral redemption in clustering sparse networks
• Reconstruction and estimation in the planted partition model
• Community detection thresholds and the weak Ramanujan property
• The phase transition in inhomogeneous random graphs
• The Spectra of Random Graphs with Given Expected Degrees
• Broadcasting on trees and the Ising model.
• Information flow on trees
• A Random Graph Model for Power Law Graphs
• Random walks and percolation on trees
• Title not available (Why is that?)
• Finding Planted Partitions in Random Graphs with General Degree Distributions
• A spectral method for community detection in moderately sparse degree-corrected stochastic block models

Cited In (13)

• A proof of the block model threshold conjecture
• Exact Recovery and Sharp Thresholds of Stochastic Ising Block Model
• Optimal adaptivity of signed-polygon statistics for network testing
• Non-backtracking spectrum of degree-corrected stochastic block models
• Learning sparse graphons and the generalized Kesten-Stigum threshold
• Nonreconstruction of high-dimensional stochastic block model with bounded degree
• Minimax rates in network analysis: graphon estimation, community detection and hypothesis testing
• PageRank Nibble on the sparse directed stochastic block model
• Detecting a planted community in an inhomogeneous random graph
• Clustering heterogeneous financial networks
• Broadcasting‐induced colorings of preferential attachment trees
• Title not available (Why is that?)
• Sparse random hypergraphs: non-backtracking spectra and community detection

This page was built for publication: An impossibility result for reconstruction in the degree-corrected stochastic block model

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