Pith. sign in

REVIEW 4 cited by

Community Detection in the Labelled Stochastic Block Model

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 1209.2910 v1 pith:VDAALROZ submitted 2012-09-13 cs.SI cs.LGmath.PRphysics.soc-ph

Simon Heimlicher , Marc Lelarge , Laurent Massoulié This is my paper · ORCID
classification cs.SIcs.LGmath.PRphysics.soc-ph
keywords communityconjecturedetectionproblemthresholdbeliefblockfurther
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
read the original abstract

We consider the problem of community detection from observed interactions between individuals, in the context where multiple types of interaction are possible. We use labelled stochastic block models to represent the observed data, where labels correspond to interaction types. Focusing on a two-community scenario, we conjecture a threshold for the problem of reconstructing the hidden communities in a way that is correlated with the true partition. To substantiate the conjecture, we prove that the given threshold correctly identifies a transition on the behaviour of belief propagation from insensitive to sensitive. We further prove that the same threshold corresponds to the transition in a related inference problem on a tree model from infeasible to feasible. Finally, numerical results using belief propagation for community detection give further support to the conjecture.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 4 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. High-Dimensional Procrustes Matching via Tree Counts

    stat.ML 2026-07 accept novelty 7.0 of 10

    Exact Procrustes matching of n Gaussian vectors in d≥polylog(n) dimensions is achievable in polynomial time whenever the correlation satisfies ρ²>√α≈0.58, via counting wide trees.

  2. Low coordinate degree algorithms II: Categorical signals and generalized stochastic block models

    math.ST 2024-12 conditional novelty 7.0 of 10

    A unified tensor-based lower bound shows low-coordinate-degree tests fail for generalized stochastic block models at the generalized Kesten-Stigum threshold.

  3. Community Detection for Contextual-LSBM: Theoretical Limitations of Misclassification Rate and Efficient Algorithms

    stat.ML 2025-01 conditional novelty 6.0 of 10

    For the contextual labeled stochastic block model, any community detection algorithm must misclassify at least about n exp(-nD) nodes in expectation, where D combines network and attribute divergences, and the propose...

  4. Detecting weighted hidden cliques

    math.ST 2025-06 conditional novelty 5.0 of 10

    A weighted generalization of the planted clique problem is introduced, with detection thresholds governed by divergence measures between the two edge-weight distributions.

Pith tools