Limit theorems for eigenvectors of the normalized Laplacian for random graphs

By Minh Tang, Carey E. Priebe. Annals of Statistics, 2016

109 citations recorded by the source corpus.

We prove a central limit theorem for the components of the eigenvectors corresponding to the $d$ largest eigenvalues of the normalized Laplacian matrix of a finite dimensional random dot product graph. As a corollary, we show that for stochastic blockmodel graphs, the rows of the spectral embedding of the normalized Laplacian converge to multivariate normals and furthermore the mean and the covariance matrix of each row are functions of the associated vertex's block membership. Together with prior results for the eigenvectors of the adjacency matrix, we then compare, via the Chernoff information between multivariate normal distributions, how the choice of embedding method impacts subsequent inference. We demonstrate that neither embedding method dominates with respect to the inference task of recovering the latent block assignments.

Subfields: Geometry and Topology, Statistical and Nonlinear Physics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/35c7b37a82f828f8292b9e37fba4b718307edb0b

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Geometry and Topology

In Statistical and Nonlinear Physics

In Statistics and Probability

Citations in the corpus

Statistical Inference on Random Dot Product Graphs: a Survey (2017, methodology): “For a given embedding method, the metric used in [98] is based on the notion of statistical information between the limiting distributions of the blocks.”