Limit theorems for eigenvectors of the normalized Laplacian for random graphs

DOI10.1214/17-AOS1623zbMath1408.62120arXiv1607.08601WikidataQ129368867 ScholiaQ129368867MaRDI QIDQ1800805

Minh Tang, Carey E. Priebe

Publication date: 24 October 2018

Published in: The Annals of Statistics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1607.08601

zbMATH Keywords

spectral clusteringrandom dot product graphstochastic blockmodelsconvergence of eigenvectorsChernoff information

Mathematics Subject Classification ID

Multivariate analysis (62H99) Classification and discrimination; cluster analysis (statistical aspects) (62H30) Random graphs (graph-theoretic aspects) (05C80) Inference from stochastic processes and spectral analysis (62M15)

Related Items (19)

Asymptotic Theory of Eigenvectors for Random Matrices With Diverging Spikes ⋮ Maximum A Posteriori Inference of Random Dot Product Graphs via Conic Programming ⋮ Sparse and smooth: improved guarantees for spectral clustering in the dynamic stochastic block model ⋮ Asymptotically efficient estimators for stochastic blockmodels: the naive MLE, the rank-constrained MLE, and the spectral estimator ⋮ Simultaneous Dimensionality and Complexity Model Selection for Spectral Graph Clustering ⋮ Spectral graph clustering via the expectation-solution algorithm ⋮ The expected values for the Schultz index, Gutman index, multiplicative degree-Kirchhoff index and additive degree-Kirchhoff index of a random polyphenylene chain ⋮ Robust Recommendation via Social Network Enhanced Matrix Completion ⋮ Efficient Estimation for Random Dot Product Graphs via a One-Step Procedure ⋮ Euclidean Representation of Low-Rank Matrices and Its Geometric Properties ⋮ Entrywise limit theorems for eigenvectors of signal-plus-noise matrix models with weak signals ⋮ Spectral Clustering via Adaptive Layer Aggregation for Multi-Layer Networks ⋮ Spectral Estimation of Large Stochastic Blockmodels with Discrete Nodal Covariates ⋮ Bayesian estimation of the latent dimension and communities in stochastic blockmodels ⋮ Normal approximation and confidence region of singular subspaces ⋮ Unnamed Item ⋮ Statistical inference on random dot product graphs: a survey ⋮ The two-to-infinity norm and singular subspace geometry with applications to high-dimensional statistics ⋮ Detecting Overlapping Communities in Networks Using Spectral Methods

Uses Software

• mclust

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Pseudo-likelihood methods for community detection in large sparse networks
• A nonparametric two-sample hypothesis testing problem for random graphs
• A limit theorem for scaled eigenvectors of random dot product graphs
• Impact of regularization on spectral clustering
• Spectra of edge-independent random graphs
• Perfect clustering for stochastic blockmodel graphs via adjacency spectral embedding
• Reconstruction and estimation in the planted partition model
• Spectral clustering and the high-dimensional stochastic blockmodel
• Laplacian matrices of graphs: A survey
• Estimation and prediction for stochastic blockmodels for graphs with latent block structure
• Concentration inequalities using the entropy method
• MCLUST: Software for model-based cluster analysis
• Consistency of spectral clustering in stochastic block models
• Role of normalization in spectral clustering for stochastic blockmodels
• Consistency of spectral clustering
• Diffusion maps
• Stochastic blockmodels with a growing number of classes
• A nonparametric view of network models and Newman–Girvan and other modularities
• Large-Sample Theory: Parametric Case
• On Divergences and Informations in Statistics and Information Theory
• Graph limits and exchangeable random graphs
• On the asymptotics of M-hypothesis Bayesian detection
• Latent Space Approaches to Social Network Analysis
• A Consistent Adjacency Spectral Embedding for Stochastic Blockmodel Graphs
• Laplacian Eigenmaps for Dimensionality Reduction and Data Representation
• The phase transition in inhomogeneous random graphs
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations

This page was built for publication: Limit theorems for eigenvectors of the normalized Laplacian for random graphs