Degree-Corrected Stochastic Blockmodel and Edge-Stub Kullback-Leibler Divergence Profile Log-Likelihood

Degree-Corrected Stochastic Blockmodel and Edge-Stub Kullback-Leibler Divergence Profile Log-Likelihood is a generative random multigraph model and maximum-likelihood community-inference formulation introduced by Karrer and Newman (2011, Physical Review E 83(1):016107, DOI:10.1103/PhysRevE.83.016107, arXiv:1008.3926v1) that augments the $K$-block Poisson stochastic blockmodel with within-group-normalized vertex degree propensity parameters $\theta_i$ ($\sum_i \theta_i \delta_{g_i, r} = 1$ for each group $r \in \{1, \dots, K\}$, Eq. 15) so that off-diagonal edge counts satisfy $A_{ij} \sim \operatorname{Poisson}(\theta_i \theta_j \omega_{g_i g_j})$ and self-edge counts satisfy $A_{ii}/2 \sim \operatorname{Poisson}(\frac{1}{2}\theta_i^2 \omega_{g_i g_i})$ (Eqs. 14, 16). Maximizing the log-likelihood $\log P(G \mid \theta, \omega, g) = 2\sum_i k_i \log \theta_i + \sum_{rs}(m_{rs}\log \omega_{rs} - \omega_{rs})$ (Eq. 17) over $(\theta, \omega)$ in closed form yields $\hat{\theta}_i = k_i / \kappa_{g_i}$ and $\hat{\omega}_{rs} = m_{rs}$ (Eq. 18)—where $k_i = \sum_j A_{ij}$ is vertex degree, $m_{rs} = \sum_{ij} A_{ij}\delta_{g_i, r}\delta_{g_j, s}$ is the inter-group edge count, and $\kappa_r = \sum_s m_{rs} = \sum_i k_i \delta_{g_i, r}$ is the total number of edge stubs in group $r$—which exactly preserves both expected block edge counts $m_{rs}$ and every vertex's expected degree $\langle k_i \rangle = k_i$ (Eqs. 19-20) and reduces to the unnormalized profile log-likelihood $\mathcal{L}_{\text{DC}}(G \mid g) = \sum_{r,s=1}^K m_{rs} \log \frac{m_{rs}}{\kappa_r \kappa_s} \propto D_{\text{KL}}(p_K \parallel p_{\text{degree}})$ (Eqs. 23-24), measuring the Kullback-Leibler divergence between empirical block edge fractions $p_K(r,s) = m_{rs}/(2m)$ and the degree-preserving configuration-model null $p_{\text{degree}}(r,s) = (\kappa_r/2m)(\kappa_s/2m)$.