An Impossibility Result for Reconstruction in a Degree-Corrected Planted-Partition Model

We consider a degree-corrected planted-partition model: a random graph on $n$ nodes with two equal-sized clusters. The model parameters are two constants $a,b > 0$ and an i.i.d. sequence $(\phi_i)_{i=1}^n$, with second moment $\Phi^2$. Vertices $i$ and $j$ are joined by an edge with probability $\frac{\phi_i \phi_j}{n}a$ whenever they are in the same class and with probability $\frac{\phi_i \phi_j}{n}b$ otherwise. We prove that the underlying community structure cannot be accurately recovered from observations of the graph when $(a-b)^2 \Phi^2 \leq 2(a+b)$.

• Publication year

  2015

• Venue

  arXiv.org

• Publication date

  2015-11-02

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 1511.00546
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Non-Backtracking Spectrum of Degree-Corrected Stochastic Block Models

  2016cited by this paper
• A spectral method for community detection in moderately sparse degree-corrected stochastic block models

  2015cited by this paper
• Non-backtracking Spectrum of Random Graphs: Community Detection and Non-regular Ramanujan Graphs

  2014cited by this paper
• Community detection thresholds and the weak Ramanujan property

  2013cited by this paper
• Spectral redemption in clustering sparse networks

  2013cited by this paper
• A Proof of the Block Model Threshold Conjecture

  2013cited by this paper
• Consistency of spectral clustering in stochastic block models

  2013cited by this paper
• Reconstruction and estimation in the planted partition model

  2012influential reference
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications

  2011cited by this paper
• Stochastic blockmodels and community structure in networks

  2010cited by this paper
• Graph Partitioning via Adaptive Spectral Techniques

  2009cited by this paper
• Partitioning Random Graphs with General Degree Distributions

  2008cited by this paper
• The phase transition in inhomogeneous random graphs

  2007influential reference
• The phase transition in inhomogeneous random graphs

  2005influential reference
• DIMACS Series in Discrete Mathematics and Theoretical Computer Science Survey : Information flow on trees

  2004cited by this paper
• Spectral analysis of random graphs with skewed degree distributions

  2004cited by this paper
• The Spectra of Random Graphs with Given Expected Degrees

  2004cited by this paper
• Statistical Inference and Simulation for Spatial Point Processes

  2003cited by this paper
• A Random Graph Model for Power Law Graphs

  2001influential reference
• Spectral partitioning of random graphs

  2001cited by this paper
• Broadcasting on trees and the Ising model

  2000influential reference
• The Metropolis Algorithm for Graph Bisection

  1998cited by this paper
• Random Walks and Percolation on Trees

  1990influential reference
• The Solution of Some Random NP-Hard Problems in Polynomial Expected Time

  1989cited by this paper
• The evolution of random graphs

  1984cited by this paper
• Graph bisection algorithms with good average case behavior

  1984cited by this paper
• Stochastic blockmodels: First steps

  1983cited by this paper

• Efficient distributed representations beyond negative sampling

  2023cites this paper
• Optimized Deformed Laplacian for Spectrum-based Community Detection in Sparse Heterogeneous Graphs

  2019cites this paper
• Detecting a planted community in an inhomogeneous random graph

  2019cites this paper
• Community detection in inhomogeneous random graphs.

  2019cites this paper
• Minimax Rates in Network Analysis: Graphon Estimation, Community Detection and Hypothesis Testing

  2018cites this paper
• Sur deux problèmes d'apprentissage automatique : la détection de communautés et l'appariement adaptatif. (On two problems in machine learning : community detection and adaptive matching)

  2017cites this paper
• Testing for Global Network Structure Using Small Subgraph Statistics

  2017cites this paper
• Community detection and stochastic block models: recent developments

  2017cites this paper
• Community Detection in Degree-Corrected Block Models

  2016cites this paper
• Non-Backtracking Spectrum of Degree-Corrected Stochastic Block Models

  2016cites this paper