A simpler spectral approach for clustering in directed networks
This work offers a simpler and effective method for clustering in directed networks, which is beneficial for researchers and practitioners working with sparse graph data.
This paper tackles the problem of clustering in directed networks, demonstrating that a simpler spectral approach using the eigenvalue/eigenvector decomposition of the adjacency matrix performs effectively even in very sparse regimes. The authors also provide numerical evidence that Gaussian Mixture clustering is superior to k-means for digraph clustering with spectral embeddings.
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.