Stochastic Block Models regimes and topology

69 Views Asked by At

Hi I'm trying to understand how regimes and thresholds of Erdős–Rényi model are valid in symmetric stochastic block model. In Erdős–Rényi model $G(n,p)$ each edge is drawn independently with probability $p$ and in symmetric stochastic block model SSBM$(n,k,q_{in}, q_{out})$ we have $k$ clusters, the probability that there is an edge intra-cluster is $q_{in}$, between clusters is $q_{out}$, always independently. For $G(n,p)$ we know that $G(n,c \log(n)/n)$ is connected with high probability if and only if $c > 1$, $G(n, c/n)$ has a giant component (i.e., a component of size linear in n) if and only if $c > 1$.

In section $2.4$ http://www.princeton.edu/~eabbe/publications/abbe_FNT_final4_plain.pdf I've found:

For SSBM($n,k,q_{in}, q_{out}$), these results hold by essentially replacing c with the average degree, for example

For $a, b > 0$, SSBM($n, k, a \log n/n, b \log n/n$) is connected with high probability if and only if $\frac{a+(k−1)b}{k}$ > 1 (if a or b is equal to 0, the graph is of course not connected).

SSBM($n, k, a/n, b/n$) has a giant component (i.e., a component of size linear in n) if and only if d :=$\frac{a+(k−1)b}{k}$ > 1.

I think that considering the average degree in SSBM makes the graph more homogeneous, then similar to $G(n,p)$, so it works. Could you help me to make/find a more specific proof?