A consistent adjacency spectral embedding for stochastic blockmodel graphs

Understand

We present a method to estimate block membership of nodes in a random graph generated by a stochastic blockmodel.

• We use an embedding procedure motivated by the random dot product graph model, a particular example of the latent position model.
• The embedding associates each node with a vector; these vectors are clustered via minimization of a square error criterion.
• We prove that this method is consistent for assigning nodes to blocks, as only a negligible number of nodes will be mis-assigned.