7.10 Stochastic Block Models

7.10.1 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{align} & \begin{bmatrix} 0.8 & 0.05 & 0.02 \\ 0.05 & 0.9 & 0.03 \\ 0.02 & 0.03 & 0.7 \end{bmatrix} && \begin{bmatrix} b_{11} & b_{12} & b_{13} \\ b_{21} & b_{22} & b_{23} \\ b_{31} & b_{32} & b_{32} \end{bmatrix} \end{align}\] $$

• \(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)'\)
• \(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 라는 것.

\(\Rightarrow\) 1. \(Y_{ij} \sim\) Bernoulli distribution with success probability \(z_i ' C z_j\) 2. independent of \(Y_{kl}\) for \((i,j) \not = (k,l)\), given \(z_i\) and \(z_j\).

7.10.1.1 Likelihood function

\[ P (Y \Big | Z, C) = \prod_{i<j} P (y_{ij} \Big | Z, C) = \prod_{i<j} \Bigg [ \Big (z_i ' Cz_j \Big )^{y_{ij}} \Big (1-z_i ' Cz_j \Big )^{1-y_{ij}} \Bigg ] \tag{1} \]

In real data, \(z\) and \(C\) are unknown. \(\Rightarrow\) we need additional assumptions. \(\underbrace{1}_{2}\) 1. \(z_i\) is independent of \(z_j\). 2. \(P(z_{i \underbrace{k}_{\text group}} =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 \Big | \theta) = \prod_{i=1}^n z_i ' \theta = \prod_{k=1}^K \theta_k^{n_k} \tag{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)\).

7.10.1.2 Inference

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

7.10.1.3 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.

7.10.1.4 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.

---

7.10.2 Mixed Membership Block Model (MMBM)

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

\[ \begin{align} z_i &= (1, 0, 0) \tag{SBM} \\ \theta_i &= (0.7, 0.2, 0.1) \tag{MMSB} \end{align} \]

이때 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 \Big | \Theta) = \prod\limits_{i \not = j} (z_{ij}'\theta_i x z_{ji}'\theta_j)\), where \(\Theta := (\theta_1 , \cdots, \theta_k)\) is \(n \times k\) Matrix of membership probability.

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

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

7.10.2.1 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} \Big | Z, C) = (Y_{ij}!)^{-1} \exp \Big \{ (-z_i ' C z_j ) (z_i ' C z_j )^{y_{ij}} \Big \} \tag{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).

• \(\phi_p\): the ratio of node \(i\)’s degree to the sum of degrees in node \(i\)’s group.

Under constraint \(\sum_{i=1}^n \phi_i \cdot I \Big ( z_{ik} = 1 \Big) =1\), then equation (3) becomes

\[ f(y_{ij} \Big | Z, C, \phi) = (y_{ij}!)^{-1} \exp \Big \{ (- \phi_i \phi_j z_i ' C z_j ) (\phi_i \phi_j z_i ' C z_j )^{y_{ij}} \Big \} \]

which is DC-SBM.

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

With DC-SBM, we can make correction better.