Limit theorems for eigenvectors of the normalized Laplacian for random graphs (Q1800805)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Limit theorems for eigenvectors of the normalized Laplacian for random graphs
scientific article

    Statements

    Limit theorems for eigenvectors of the normalized Laplacian for random graphs (English)
    0 references
    0 references
    0 references
    0 references
    24 October 2018
    0 references
    Distributional limit results are established for the eigenvectors corresponding to the largest eigenvalues of the adjacency or Laplacian matrix. It is shown that the Chernoff information between the multivariate normals approximation of the embedding characterizes the minimum error rate achievable by any clustering procedure that operates only on the spectral embedding. The contribution reinforces results concerning the prediction accuracy's improvements using the normalization from [\textit{P. Sarkar} and \textit{P. J. Bickel}, Ann. Stat. 43, No. 3, 962--990 (2015; Zbl 1320.62150)], ref. also [\textit{U. von Luxburg}, ``A tutorial on spectral clustering'', Stat. Comput. 17, No. 4, 395--416 (2007; \url{doi:10.1007/s11222-007-9033-z})].
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    spectral clustering
    0 references
    random dot product graph
    0 references
    stochastic blockmodels
    0 references
    convergence of eigenvectors
    0 references
    Chernoff information
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references