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

DOI10.1214/18-AAP1381zbMath1417.91409MaRDI QIDQ1617152

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

random graphsmachine learningspectral algorithmdegree-corrected stochastic block modelsocial and information networks

Mathematics Subject Classification ID

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

Related Items

PageRank Nibble on the sparse directed stochastic block model ⋮ Broadcasting‐induced colorings of preferential attachment trees ⋮ Learning sparse graphons and the generalized Kesten-Stigum threshold ⋮ Clustering heterogeneous financial networks ⋮ Unnamed Item ⋮ Minimax rates in network analysis: graphon estimation, community detection and hypothesis testing ⋮ Nonreconstruction of high-dimensional stochastic block model with bounded degree ⋮ Detecting a planted community in an inhomogeneous random graph ⋮ Optimal adaptivity of signed-polygon statistics for network testing ⋮ Non-Backtracking Spectrum of Degree-Corrected Stochastic Block Models

Cites Work

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

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