# A simpler spectral approach for clustering in directed networks

arXiv: https://arxiv.org/abs/2102.03188 · HTML: https://mlsanity.com/paper/2102.03188/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 40 references that are in the map.
- First posted on arXiv 5 Feb 2021.

## Builds on (most cited first, 12 of 12)

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Community detection thresholds and the weak Ramanujan property](https://mlsanity.com/paper/1311.3085/) (2013)
- [Clustering and Community Detection in Directed Networks: A Survey](https://mlsanity.com/paper/1308.0971/) (2013)
- [Hermitian matrices for clustering directed graphs: insights and applications](https://mlsanity.com/paper/1908.02096/) (2019)
- [Analysis of spectral clustering algorithms for community detection: the general bipartite setting](https://mlsanity.com/paper/1803.04547/) (2018)
- [Higher-Order Spectral Clustering of Directed Graphs](https://mlsanity.com/paper/2011.05080/) (2020)
- [Community detection in the sparse hypergraph stochastic block model](https://mlsanity.com/paper/1904.05981/) (2019)
- [Graph powering and spectral robustness](https://mlsanity.com/paper/1809.04818/) (2018)
- [Asymmetry Helps: Eigenvalue and Eigenvector Analyses of Asymmetrically Perturbed Low-Rank Matrices](https://mlsanity.com/paper/1811.12804/) (2018)
- [Optimal Bipartite Network Clustering](https://mlsanity.com/paper/1803.06031/) (2018)
- [Robustness of spectral methods for community detection](https://mlsanity.com/paper/1811.05808/) (2018)
- [Spectral clustering algorithms for the detection of clusters in block-cyclic and block-acyclic graphs](https://mlsanity.com/paper/1805.00862/) (2018)

## Built on by (most cited first, 2 of 2)

- [Sparse random hypergraphs: Non-backtracking spectra and community detection](https://mlsanity.com/paper/2203.07346/) (2022)
- [Generalized Dirichlet Energy and Graph Laplacians for Clustering Directed and Undirected Graphs](https://mlsanity.com/paper/2203.03221/) (2022)

## Abstract (arXiv)

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.