  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. We prove consistency of the method for directed
and undirected graphs. The consistent block assignment makes possible
consistent parameter estimation for a stochastic blockmodel. We extend the
result in the setting where the number of blocks grows slowly with the number
of nodes. Our method is also computationally feasible even for very large
graphs. We compare our method to Laplacian spectral clustering through analysis
of simulated data and a graph derived from Wikipedia documents.
