Role of normalization in spectral clustering for stochastic blockmodels

DOI10.1214/14-AOS1285zbMath1320.62150arXiv1310.1495MaRDI QIDQ2352733

Purnamrita Sarkar, Peter J. Bickel

Publication date: 6 July 2015

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

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

zbMATH Keywords

networksasymptotic analysisnormalizationspectral clusteringstochastic blockmodel

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Random matrices (probabilistic aspects) (60B20)

Related Items

A likelihood-ratio type test for stochastic block models with bounded degrees, Smoothing graphons for modelling exchangeable relational data, A limit theorem for scaled eigenvectors of random dot product graphs, Bayesian community detection, 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, Randomized Spectral Clustering in Large-Scale Stochastic Block Models, Unnamed Item, Using Maximum Entry-Wise Deviation to Test the Goodness of Fit for Stochastic Block Models, A distributed community detection algorithm for large scale networks under stochastic block models, Efficient Estimation for Random Dot Product Graphs via a One-Step Procedure, Unnamed Item, Robust Inference of Manifold Density and Geometry by Doubly Stochastic Scaling, Entrywise limit theorems for eigenvectors of signal-plus-noise matrix models with weak signals, Spectral Clustering via Adaptive Layer Aggregation for Multi-Layer Networks, Consistent Estimation of the Number of Communities via Regularized Network Embedding, Spectral clustering in the dynamic stochastic block model, Detecting groups in large vector autoregressions, Statistical inference on random dot product graphs: a survey, Optimization via low-rank approximation for community detection in networks, Minimax rates in network analysis: graphon estimation, community detection and hypothesis testing, Limit theorems for eigenvectors of the normalized Laplacian for random graphs, Optimality of spectral clustering in the Gaussian mixture model, Extended stochastic block models with application to criminal networks, The two-to-infinity norm and singular subspace geometry with applications to high-dimensional statistics, Doubly Stochastic Normalization of the Gaussian Kernel Is Robust to Heteroskedastic Noise, Consistency of spectral clustering in stochastic block models, Role of normalization in spectral clustering for stochastic blockmodels, Robust and computationally feasible community detection in the presence of arbitrary outlier nodes, Detecting Overlapping Communities in Networks Using Spectral Methods

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Pseudo-likelihood methods for community detection in large sparse networks
• Impact of regularization on spectral clustering
• On the spectra of general random graphs
• Spectral clustering and the high-dimensional stochastic blockmodel
• The eigenvalues of random symmetric matrices
• Role of normalization in spectral clustering for stochastic blockmodels
• Consistency of spectral clustering
• A new status index derived from sociometric analysis
• A nonparametric view of network models and Newman–Girvan and other modularities
• Partitioning Sparse Matrices with Eigenvectors of Graphs
• A Consistent Adjacency Spectral Embedding for Stochastic Blockmodel Graphs
• An Improved Spectral Graph Partitioning Algorithm for Mapping Parallel Computations
• Spectral techniques applied to sparse random graphs
• Lower Bounds for the Partitioning of Graphs