| Register
\(\newcommand{\Cat}{{\rm Cat}} \) \(\newcommand{\A}{\mathcal A} \) \(\newcommand{\freestar}{ \framebox[7pt]{$\star$} }\)

Connecting communities via the block model

Edited by org.aimpl.user:awein@mit.edu

The stochastic block model is a generative model for random graphs with community structure. A simple variant is the following. Let each of the $n$ vertices have a community assignment chosen independently and uniformly from $[k]$. For each pair of nodes: if they are in the same community, add an edge between them with probability $p$; otherwise add an edge between them with probability $q$. We now consider the inference problem in which we are given this graph and want to identify the communities (either exactly or approximately).

    Sections

    1. 1. New models and algorithms
    2. 2. ML vs. Bayes
    3. 3. Hardness at the KS threshold
    4. 4. Provable algorithms at the KS threshold
    5. 5. Random matrix theory
    1. Bibliography

      Cite this as: AimPL: Connecting communities via the block model, available at http://aimpl.org/blockmodel.