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

DOI10.1214/18-AAP1381MaRDI QIDQ1617152zbMATH OpenFDO

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

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)

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

Cites work

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

Cited in

(13)

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

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)