Network Outcome Models - Stochastic Block Models and Network Checks

Summary

Concept note (no raw source). Stochastic block models (SBMs) give each node a latent role and let tie probability depend only on the pair of roles; mixed-membership and degree-corrected variants relax hard roles and degree homogeneity. Marginalising roles avoids discrete sampling in PyMC; network posterior predictive checks (degree, transitivity, shared partners, geodesics) show what each model misses. Complements the latent-space model of Hoff 2002 - Latent Space Models Overview.

Overview

Used in PyMC example E21 (Lazega lawyers; mixed-membership SBM with marginalised roles, degree-corrected or not, co-clustering matrix, network PPCs). Example list: https://redam94.github.io/pymc-challenges/examples.html.

Main Content

Stochastic block model (Holland, Laskey & Leinhardt 1983; Nowicki & Snijders 2001)

Nodes $i=\mathrm{1..}n$ have latent classes $c_i\sim \text{Categorical}(\pi )$ over $K$ groups; for a directed binary network $y_{ij}\mid c_i,c_j\sim \text{Bernoulli}(B_{c_i{c}_j})$ independently, $B\in [0,1{]}^{K\times K}$ the block matrix.

Mixed-membership SBM (Airoldi et al. 2008)

Each node has membership vector ${\pi }_i\sim \text{Dirichlet}(\alpha )$; for each ordered pair draw sender role $s_{ij}\sim {\pi }_i$ and receiver role $r_{ij}\sim {\pi }_j$; $y_{ij}\sim \text{Bernoulli}(B_{s_{ij}{r}_{ij}})$. Marginalising roles gives $P(y_{ij}=1)={\pi }_i^{\top }B{\pi }_j$.

Degree-corrected SBM (Karrer & Newman 2011)

Poisson-edge version: $A_{ij}\sim \text{Poisson}({\theta }_i{\theta }_j{\omega }_{c_i{c}_j})$ with node propensity ${\theta }_i$, absorbing heterogeneous degrees that a plain SBM would assign to extra blocks.

Marginalising roles: for the classical SBM, $P(y_{ij}=1)$ conditioned on $c$ is block-constant; a node’s likelihood contribution is ${\sum }_k{\pi }_k{\prod }_j{B}_{k{c}_j}^{y_{ij}}(1-B_{k{c}_j}{)}^{1-y_{ij}}$ only when other labels are known, so exact marginalisation is not available; the mixed-membership form is tractable because pairs are independent given $({\pi }_i,{\pi }_j)$: ${\pi }_i^{\top }B{\pi }_j$. Identification: label switching (use ordered/identifiable constraints on $B$‘s diagonal), and the co-clustering matrix $C_{ij}={\pi }_i^{\top }{\pi }_j$ (a posterior summary invariant to relabeling).

Network posterior predictive checks: simulate $y^{\text{rep}}$ from the posterior and compare statistics: degree distribution, global transitivity, edgewise shared partners, geodesic distance distribution. A latent-space model captures transitivity; a plain SBM typically misses degree heterogeneity (a motivation for degree correction); a dyad logistic with sociality random effects $\log \text{odds}(y_{ij})=\alpha +s_i+r_j$ captures degree but not triads.

Examples

Mixed-membership tie probability, tiny check

$K=2$, $B=\left(\begin{array}{cc}0.8& 0.05\\ 0.05& 0.6\end{array}\right)$; nodes ${\pi }_1=(0.9,0.1)$, ${\pi }_2=(0.1,0.9)$ give $P(y_{12}=1)={\pi }_1^{\top }B{\pi }_2=0.9\cdot 0.1\cdot 0.8+0.9\cdot 0.9\cdot 0.05+0.1\cdot 0.1\cdot 0.05+0.1\cdot 0.9\cdot 0.6=0.072+0.0405+0.0005+0.054=0.167$.

import numpy as np
B = np.array([[.8, .05], [.05, .6]]); p1 = np.array([.9, .1]); p2 = np.array([.1, .9]); print(p1 @ B @ p2)   # 0.167

PyMC sketch (untested):

import pymc as pm
with pm.Model():
    pi = pm.Dirichlet("pi", a=np.ones(K)*0.5, shape=(n, K))
    B = pm.Beta("B", 1, 1, shape=(K, K))
    P = pm.math.dot(pi, pm.math.dot(B, pi.T))
    pm.Bernoulli("y", p=P[iu], observed=y[iu])

Connections

Social Network Models (basic network models); Hoff 2002 - Monks Florentine Families and Classroom Examples (SBM vs latent space log-likelihoods); marketing: roles = customer segments in referral graphs.

See Also

Hoff 2002 - Latent Space Approaches to Social Network Analysis