A simpler spectral approach for clustering in directed networks
arXiv:2102.03188
Abstract
We study the task of clustering in directed networks. We show that using the eigenvalue/eigenvector decomposition of the adjacency matrix is simpler than all common methods which are based on a combination of data regularization and SVD truncation, and works well down to the very sparse regime where the edge density has constant order. Our analysis is based on a Master Theorem describing sharp asymptotics for isolated eigenvalues/eigenvectors of sparse, non-symmetric matrices with independent entries. We also describe the limiting distribution of the entries of these eigenvectors; in the task of digraph clustering with spectral embeddings, we provide numerical evidence for the superiority of Gaussian Mixture clustering over the widely used k-means algorithm.
arXiv comment42 pages
References in corpus (6)
- Scikit-learn: Machine Learning in Python
- Community structure in directed networks
- Uncovering latent structure in valued graphs: A variational approach
- Asymmetry Helps: Eigenvalue and Eigenvector Analyses of Asymmetrically Perturbed Low-Rank Matrices
- Optimal Bipartite Network Clustering
- Spectral clustering algorithms for the detection of clusters in block-cyclic and block-acyclic graphs