Understand
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.
Built on
Uniform convergence of martingales in the branching random walk
J. D. Biggins · 1992
Earlier work this paper cites.
Random walk in a random environment and first-passage percolation on trees
Russell Lyons and Robin Pemantle · 1992
Earlier work this paper cites.
Broadcasting on trees and the Ising model
William Evans, Claire Kenyon, Yuval Peres, and Leonard J. Schulman · 2000
Earlier work this paper cites.
Spectral partitioning of ranodm graphs
F. McSherry · 2001
Earlier work this paper cites.
Similar
Robust reconstruction on trees is determined by the second eigenvalue
S. Janson and E. Mossel · 2004
Cited alongside, same era.
Survey: information flow on trees
Elchanan Mossel · 2004
Cited alongside, same era.
Reconstruction for models on random graphs
A. Gerschenfeld and A. Monatanari · 2007
Cited alongside, same era.
Graph partitioning via adaptive specral techniques
A. Coja-Oghlan · 2010
Cited alongside, same era.
Probability on Trees and Networks
Russel Lyons and Yuval Peres
Cited in the paper.
Then
Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
Aurelien Decelle, Florent Krzakala, Cristopher Moore, and Lenka Zdeborová · 2011
Later among the works it cites.
Spectral Clustering and the High-Dimensional Stochastic Blockmodel
Karl Rohe, Sourav Chatterjee, and Bin Yu · 2011
Later among the works it cites.
Stochastic Block Models and Reconstruction, February 2012, arXiv:1202.1499
Elchanan Mossel, Joe Neeman, and Allan Sly · 2012
Closest in time.
Beyond the bibliography
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…