Stochastic block model

The stochastic block model takes the following parameters:

• The number ${\displaystyle n}$ of vertices;
• a partition of the vertex set ${\displaystyle \{1,\ldots ,n\}}$ into disjoint subsets ${\displaystyle C_{1},\ldots ,C_{r}}$, called communities;
• a symmetric ${\displaystyle r\times r}$ matrix ${\displaystyle P}$ of edge probabilities.

The edge set is then sampled at random as follows: any two vertices ${\displaystyle u\in C_{i}}$ and ${\displaystyle v\in C_{j}}$ are connected by an edge with probability ${\displaystyle P_{ij}}$. An example problem is: given a graph with ${\displaystyle n}$ vertices, where the edges are sampled as described, recover the groups ${\displaystyle C_{1},\ldots ,C_{r}}$.

If the probability matrix is a constant, in the sense that ${\displaystyle P_{ij}=p}$ for all ${\displaystyle i,j}$, then the result is the Erdős–Rényi model ${\displaystyle G(n,p)}$. This case is degenerate—the partition into communities becomes irrelevant—but it illustrates a close relationship to the Erdős–Rényi model.

The planted partition model is the special case that the values of the probability matrix ${\displaystyle P}$ are a constant ${\displaystyle p}$ on the diagonal and another constant ${\displaystyle q}$ off the diagonal. Thus two vertices within the same community share an edge with probability ${\displaystyle p}$, while two vertices in different communities share an edge with probability ${\displaystyle q}$. Sometimes it is this restricted model that is called the stochastic block model. The case where ${\displaystyle p>q}$ is called an assortative model, while the case ${\displaystyle p<q}$ is called disassortative.

Returning to the general stochastic block model, a model is called strongly assortative if ${\displaystyle P_{ii}>P_{jk}}$ whenever ${\displaystyle j\neq k}$: all diagonal entries dominate all off-diagonal entries. A model is called weakly assortative if ${\displaystyle P_{ii}>P_{ij}}$ whenever ${\displaystyle i\neq j}$: each diagonal entry is only required to dominate the rest of its own row and column.[1] Disassortative forms of this terminology exist, by reversing all inequalities. Algorithmic recovery is often easier against block models with assortative or disassortative conditions of this form.[1]

Much of the literature on algorithmic community detection addresses three statistical tasks: detection, partial recovery, and exact recovery.

Stochastic block models exhibit a sharp threshold effect reminiscent of percolation thresholds.[6][2][7] Suppose that we allow the size ${\displaystyle n}$ of the graph to grow, keeping the community sizes in fixed proportions. If the probability matrix remains fixed, tasks such as partial and exact recovery become feasible for all non-degenerate parameter settings. However, if we scale down the probability matrix at a suitable rate as ${\displaystyle n}$ increases, we observe a sharp phase transition: for certain settings of the parameters, it will become possible to achieve recovery with probability tending to 1, whereas on the opposite side of the parameter threshold, the probability of recovery tends to 0 no matter what algorithm is used.

For partial recovery, the appropriate scaling is to take ${\displaystyle P_{ij}={\tilde {P}}_{ij}/n}$ for fixed ${\displaystyle {\tilde {P}}}$, resulting in graphs of constant average degree. In the case of two equal-sized communities, in the assortative planted partition model with probability matrix

$${\displaystyle P=\left({\begin{array}{cc}{\tilde {p}}/n&{\tilde {q}}/n\\{\tilde {q}}/n&{\tilde {p}}/n\end{array}}\right),}$$

partial recovery is feasible[3] with probability ${\displaystyle 1-o(1)}$ whenever ${\displaystyle ({\tilde {p}}-{\tilde {q}})^{2}>2({\tilde {p}}+{\tilde {q}})}$, whereas any estimator fails[2] partial recovery with probability ${\displaystyle 1-o(1)}$ whenever ${\displaystyle ({\tilde {p}}-{\tilde {q}})^{2}<2({\tilde {p}}+{\tilde {q}})}$.

For exact recovery, the appropriate scaling is to take ${\displaystyle P_{ij}={\tilde {P}}_{ij}\log n/n}$, resulting in graphs of logarithmic average degree. Here a similar threshold exists: for the assortative planted partition model with ${\displaystyle r}$ equal-sized communities, the threshold lies at ${\displaystyle {\sqrt {\tilde {p}}}-{\sqrt {\tilde {q}}}={\sqrt {r}}}$. In fact, the exact recovery threshold is known for the fully general stochastic block model.[4]

In principle, exact recovery can be solved in its feasible range using maximum likelihood, but this amounts to solving a constrained or regularized cut problem such as minimum bisection that is typically NP-complete. Hence, no known efficient algorithms will correctly compute the maximum-likelihood estimate in the worst case.

However, a wide variety of algorithms perform well in the average case, and many high-probability performance guarantees have been proven for algorithms in both the partial and exact recovery settings. Successful algorithms include spectral clustering of the vertices,[8][3][4][9] semidefinite programming,[1][7] forms of belief propagation,[6][10] and community detection [11] among others.

Several variants of the model exist. One minor tweak allocates vertices to communities randomly, according to a categorical distribution, rather than in a fixed partition.[4] More significant variants include the geometric block model,[12] censored block model and the mixed-membership block model.[13]

Stochastic Block Model have been recognised to be a topic model on bipartite networks.[14] In a network of documents and words, Stochastic Block Model can identify topics: group of words with a similar meaning.