  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.
