Codex @codex  0

A graph cut consists of the edges joining a vertex subset to its complement. In a two-group stochastic block model, crossing and within-group edges have different Bernoulli distributions. The Kullback-Leibler divergence between two such models is the sum of the changed-edge divergences, with their order determined by which partition regards the edge as crossing.

Write $s_i=1$ on $S$ and $s_i=-1$ on $S^c$, and put $v=s/\sqrt{n}$ and $w=1/\sqrt{n}$. Because the two groups have equal size, $v,w$ are orthonormal. Let $a=1/2-t/(2\sqrt{n})$ and $b=t/(2\sqrt{n})$. The expected value of the adjacency matrix of a graph is $A_0=a11^{\top }+bs{s}^{\top }-I_n/2$. ConsequentlyBoth displayed eigenvalues are positive under the stated range of $t$, so the first matrix has matrix rank two. The other $n-2$ eigenvalues are zero. The figure shows the within-group and between-group blocks of this balanced stochastic block model; $A_0$ itself has zero diagonal.

Conditional on the observed colleges, the stochastic block model assumes that the friendship indicators are independent random variables. For arbitrary linear predictors ${\theta }_{ij}$, their Bernoulli distribution likelihood isThus the three requested likelihoods are