Stochastic block model: Difference between revisions

Revision as of 09:19, 15 January 2021

Revision as of 21:30, 30 January 2021

Line 29:

== Statistical lower bounds and threshold behavior ==

Stochastic block models exhibit a sharp [[threshold effect (disambiguation)|threshold effect]] reminiscent of [[percolation threshold]]s.<ref name="decelle11"/><ref name="mns12" /><ref name="abh14" /> Suppose that we allow the size <math>n</math> 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 <math>n</math> 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 <math>P_{ij} = \tilde P_{ij} / n</math> for fixed <math>\tilde P</math>, resulting in graphs of constant average degree. In the case of two equal-sized communities, in the assortative planted partition model with probability matrix