It may be helpful to work on this problem in conjunction with the relevant lab. The stochastic block model (SBM) defines the random graph G(n,p,q) consisting of two communities of size n2 each, such that the probability an edge exists between two nodes of the same community is p, and the probability an edge exists between two nodes in different communities is q < p. The goal of the problem is to exactly determine the two communities, given only the graph. Show that the MAP estimate of the two communities is equivalent to finding the min-bisection or balanced min-cut of the graph, the split of G into two groups of size n2 that has the minimum edge weight across the partition. Assume that any assignment of the communities is a priori equally likely