Stochastic block model: Difference between revisions

Revision as of 15:10, 20 February 2021

Revision as of 15:45, 14 March 2021

Line 14:

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

Returning to the general stochastic block model, a model is called ''strongly assortative'' if <math>P_{ii} > P_{jk}</math> whenever <math>j \neq k</math>: all diagonal entries dominate all off-diagonal entries. A model is called ''weakly assortative'' if <math>P_{ii} > P_{ij}</math> and <math>P_{ii} > P_{ji}</math> whenever <math>i \neq j</math>: each diagonal entry is only required to dominate the rest of its own row and column.<ref name="al14" /> ''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.<ref name="al14" />

== Typical statistical tasks ==