120. Stochastic Block Models

Stochastic Block Model

• Latent Class Model
• for each actor (node), we assign group memberships

two components in the block model,

1. the vector of grop membership : $z$
2. conditional on the group membership, the block matrix represents the edge probability of two nodes

$$\begin{array}{rlrl}& \left[\begin{array}{ccc}0.8& 0.05& 0.02\\ 0.05& 0.9& 0.03\\ 0.02& 0.03& 0.7\end{array}\right]& & \left[\begin{array}{ccc}{b}_{11}& b_{12}& b_{13}\\ b_{21}& b_{22}& b_{23}\\ b_{31}& b_{32}& b_{32}\end{array}\right]\end{array}$$

• $b_{11}$ 에 부여된 확률 0.8: the connection prob within group 1
• $b_{22}$ 에 부여된 확률 0.9: the connection prob within group 1
• $b_{11}$ 에 부여된 확률 0.05: the connection prob b/w group 1 and group 2

※ notations:

• $Y$: adjacency Matrix
• $K$: the total membership groups ($<n$)
• $Z_i$: $k$-vector. node $i$ 가 속하게 될 group 에만 $1$ 부여하고 이외에는 모두 $0$.
• $Z:=(z_1,\cdots ,z_n{)}^{\prime }$
• $C$: $k\times k$ block matrix

  • entry $C_{ij}\in [0,1]$: prob of occurence of a edge from a node in $g$

block Matrix $C$ 라는 발상은, block membership 이 given 일 때, edge 들이 conditionally independent 라는 것.

⇒ 따라서

1. $Y_{ij}\sim$ Bernoulli distribution with success probability $z_i^{\prime }C{z}_j$
2. independent of $Y_{kl}$ for $(i,j)\ne (k,l)$, given $z_i$ and $z_j$.

Likelihood function

$$P(Y|Z,C)=\prod _{i<j}P(y_{ij}|Z,C)=\prod _{i<j}\left[\right(z_i^{\prime }C{z}_j{)}^{y_{ij}}(1-z_i^{\prime }C{z}_j{)}^{1-y_{ij}}]\text{\hspace{1em}(1)}$$

In real data, $z$ and $C$ are unknown. $\Rightarrow$ we need additional assumptions. $\underset{2}{\underbrace{1}}$

1. $z_i$ is independent of $z_j$.
2. $P(z_{i\underset{\text{g}roup}{\underbrace{k}}}=1)={\theta }_k$, ${\sum }_{j=1}^k{\theta }_k=1$ $\Rightarrow$ the latent group $z_p$ follows multinomial distribution with $\theta$, i.e.,

$$\pi (z|\theta )=\prod _{i=1}^n{z}_i^{\prime }\theta =\prod _{k=1}^K{\theta }_k^{n_k}\text{\hspace{1em}(2)}$$

, where $n_k$ is the total number of nodes that belongs to group $K$.

In a Bayesian inference, we can assign $Dirichlet$ prior $\alpha ,\cdots ,\alpha$ $\pi (\alpha )\sim Gamma(a,b)$.

Inference

By combining equation (1) and (2), we can make an inference by the frequentist way using EM algorithm.

Bayesian

we need to assign prior for $C\sim BETA$, $C_{ij}\sim BETA(A_{ij},B_{ij})$, where $A,B$ are $k\times k$ Matrix.

Posterior Distribution

\begin{alignat}{2} \pi(Z , \theta, C , \alpha \Big | Y) & \propto f(Y \Big | Z , \theta, C , \alpha) && \cdot \pi(Z , \theta, C , \alpha) \\ & = f(Y \Big | Z , \theta, C , \alpha) && \cdot \pi(Z \Big | \theta, C , \alpha) && \cdot \pi(\theta \Big | C , \alpha) && \cdot \pi(C, \alpha) \\ & = f(Y \Big | Z , C) && \cdot \pi(Z \Big | \theta) && \cdot \pi(\theta \Big | \alpha) && \cdot \pi(C) \cdot \pi(\alpha) \\ & \propto \prod_{i<j} \Big[ (z_i' C z_j)^{y_{ij}}(1- z_i' C z_j)^{1-y_{ij}} \Big] && \cdot \prod_{k=1}^K \theta_k^{n_k} \Bigg[\Gamma(k \alpha) \Big \{ \sum^k_{i=} \theta_k = 1 \prod_{i=1}^k \frac{\theta_z^{\alpha-1}}{\Gamma(\alpha)}\Big \} \Bigg] && \cdot\prod^k_{i<j} \Big[ C_{ij}^{A_{ij}-1} (1-C_{ij})^{B_{ij}-1} \Big] && \cdot \alpha^{a-1} e^{-b \alpha} \end{alignat}

$\Rightarrow$ Computation is veery straightforward via MCMC.

---

Mixed Membership Block Model (MMBM)

상기의 SBM 에서, 각 actor 는 오직 1개의 membership 을 가짐. 이러한 SBM 의 제약을 완화 (alleviate) 하기 위해 MMBM 이 제언되었다. 해당 모델에서는 특정 membership 에 1을 부여하는 것이 아니라, 각 membership 발생 여부에 prob 을 할당하여 다중 membership 을 각 ndoe 에 할당한다.

$$\begin{array}{rl}{z}_i& =(1,0,0)\\ {\theta }_i& =(0.7,0.2,0.1)\end{array}\text{\hspace{1em}(SBM)(MMSB)}$$

이때 MMSB 의 vector 의 각 항은 각각 group 1, group 2, group 3 일 prob.

• ${\theta }_i$: weights or probabilities in the groups that have to be non-negative and sum to 1.

For each dyad $y_{ij}$, a latent membership $z_{ij}$ is drawn from the multinomial distribution with ${\theta }_p$.

$\pi (z|\Theta )=\prod _{i\ne j}(z_{ij}^{\prime }{\theta }_{i}x{z}_{ji}^{\prime }{\theta }_j)$, where $\Theta :=({\theta }_1,\cdots ,{\theta }_k)$ is $n\times k$ Matrix of membership probability.

The likeliood is $f(Y|Z,C)=\prod _{i<j}[(z_{ij}^{\prime }C{z}_{ji}{)}^{y_{ij}}(1-z_{ij}^{\prime }C{z}_{ji}{)}^{1-y_{ij}}]$.

The goal of inference estimating not $z$ but the mixed memberships $\Theta$.

Degree-corrected SBM

use Poisson Model.

• $y_{ij}$: the number of edges from dyad (i,j) following a Poisson dist
• $C_{ij}$: the expected number of edges from a node in group $i$ to a node in group $j$

The likelihood is

$$\pi (Y_{ij}|Z,C)=(Y_{ij}!{)}^{-1}\exp \{(-z_i^{\prime }C{z}_j)(z_i^{\prime }C{z}_j{)}^{y_{ij}}\}\text{\hspace{1em}(3)}$$

In a large sparse graph, where the edge probability equals the expected number of edges, DC-SBM is asymptotically equivalient to the Bernoulli counterpart in equation (3).

• ${\varphi }_p$: the ratio of node $i$‘s degree to the sum of degrees in node $i$‘s group.

Under constraint ${\sum }_{i=1}^n{\varphi }_i\cdot I(z_{ik}=1)=1$, then equation (3) becomes

$$f(y_{ij}|Z,C,\varphi )=(y_{ij}!{)}^{-1}\exp \{(-{\varphi }_i{\varphi }_j{z}_i^{\prime }C{z}_j)({\varphi }_i{\varphi }_j{z}_i^{\prime }C{z}_j{)}^{y_{ij}}\}$$

which is DC-SBM.

$\Rightarrow$ SBM ignores the variation of node degrees in a real network.

With DC-SBM, we can make correction better.