almost exact recovery is impossible when the signal to noise ratio is less than the threshold

Suppose we have a stochastic block model problem where the adjacency matrix $A\sim P,P=YB{Y}^T$, and $B=\{\begin{array}{l}p\text{ if }{c}_1=c_2\\ q\text{ otherwise}\end{array}$.

If the signal to noise ratio $SNR\frac{<1}{n}$, then almost exact recovery is impossible.

Even with infinite time and resources, there is no algorithm that can recover the true communities with just the probabilities of adjacency. This gives us the information theoretic threshold

$p=\frac{a}{n},q=\frac{b}{n}$ and $\frac{|E|}{n^2}\to 0$ as $n\to \mathrm{\infty }$ (the average degree vanishes).
Then $$SNR = \frac{\left( \frac{a}{n} - \frac{b}{n} \right)^2}{2\frac{(a+b)}{n}} = \frac{1}{2n} \frac{(a-b)^2}{(a+b)}$$
ie, in sparse graphs, it is not difficult to identify the information theoretic threshhold (we can easily calculate the signal to noise ratio)