Stochastic Block Model

• Motivation: Stochastic block models (SBMs) generalize ER models to accommodate community structure, also known as homophily or assortative mixing

  • Homophily

    tendency of individuals to associate disproportionately with others who are similar (e.g. ethnicity, age, profession, religion, etc) to themselves.

    • Lazarsfeld, P.F. “Friendship as a social process: A substantive and methodological analysis.” Freedom and Control in Modern Society (1954)

    Link to original

• Model: Fixed $n$, undirected, a partition of nodes into disjoint $r$ communities $(N_s{)}_{s=1}^r$, $1\{(i,j)\in E\}\sim \mathrm{Bernoulli}(p_{s_i{s}_j})$ with $i\in N_{s_i}$ and $j\in N_{s_j}$
  • We write $n_s$ and $c_s=n_s/n$ for the absolute and relative size of community $s$, respectively
  • We write $P=(p_{sl}{)}_{sl}\in {\mathbb{R}}^{r\times r}$ for edge probabilities between communities
• Basic properties
  • Expected degree: $\mathbb{E}{D}_i\approx {\sum }_{s=1}^r{c}_s\left({\sum }_{l=1}^r{c}_l{p}_{sl}\right)={\sum }_{s,l}{c}_s{c}_l{p}_{sl}$
• Remarks:
  • Reduces to ER model when there is only one community
  • Thus also known as multi-type ER model

Multi-Type Branching

Analyzing SBM requires generalizing the Local Branching to multi-type.

Transclude of 6-7260-hw2#problem-2

Testing

Consider a two-community SBM with $n_1=n_2=n/2$ and $p_1=a_1\frac{\ln n}{n},p_2=a_2\frac{\ln n}{n}$ for some constants $a_1,a_2$. We can recover the community structure with high probability if and only if $(\sqrt{a}-\sqrt{b}{)}^2>2$.

Degree Correlated SBM

Within each community, standard SBM recovers ER model. We can also equip Chung–Lu Model with community structure to allow for degree heterogeneity within communities. This is known as degree-correlated SBM. Specifically, for an expected degree sequence $(d_i)$ and community weight $(w_{sl})\in {\mathbb{R}}^{r\times r}$, we have $1\{(i,j)\in E\}\sim \mathrm{Bernoulli}\left(\frac{d_i{d}_j}{{\sum }_k{d}_k}{w}_{s_i{s}_j}\right)$. To ensure node $i$ has the expect degree of $d_i$, we have $r$ linear constraints for $(w_{sl})$:

$$\sum _i{w}_{l{s}_i}{c}_i=2\sum _k{d}_k,l=1,\dots ,r.$$