X_j$. Hence, recovering the partition in this case amounts to having a connected graph $G$, and the recovery is obtained by picking a vertex label and recovering the other vertices along any spanning tree. Note that we can only hope to recover the partition and not the exact colors, as a global flipping of all the colors gives the same observations. In the more interesting setting, the observations are assumed to be noisy, i.e., with probability ${\varepsilon}$ an error is made on the parity of the two colors: $Y_{ij}=X_i \oplus X_j \oplus Z_{ij}$, where the $Z_{ij}$’s are i.i.d. Bernoulli$({\varepsilon})$. In this case, the connectivity of $G$ is a necessary condition, but it is in general not sufficient to cope with the noise. This paper investigates how to strengthen the connectivity assumption, in terms of the edge probability for random graphs or in terms of the spectral gap for deterministic graphs, in order to recover the partition despite the noise.

There are various interpretations and models that connect to this problem.

-   [**Community detection:**]{} It is worth connecting the above model to other existing models for community networks. The model in can be seen as a general probabilistic model of networks, 