# Randomized spectral co-clustering for large-scale directed networks

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Apr 2020.

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

- [An Introduction to Johnson-Lindenstrauss Transforms](https://mlsanity.com/paper/2103.00564/) (2021)
- [Community detection for weighted bipartite networks](https://mlsanity.com/paper/2109.10319/) (2021)
- [FedPower: Privacy-Preserving Distributed Eigenspace Estimation](https://mlsanity.com/paper/2103.00704/) (2021)
- [Directed mixed membership stochastic blockmodel](https://mlsanity.com/paper/2101.02307/) (2021)
- [Privacy-Preserving Community Detection for Locally Distributed Multiple Networks](https://mlsanity.com/paper/2306.15709/) (2023)
- [How many asymmetric communities are there in multi-layer directed networks?](https://mlsanity.com/paper/2602.21569/) (2026)
- [Randomized SVD Approximations for Spectral Co-Clustering of Word-Document Matrices](https://mlsanity.com/paper/2609.19243/) (2026)

## Abstract (arXiv)

Directed networks are broadly used to represent asymmetric relationships among units. Co-clustering aims to cluster the senders and receivers of directed networks simultaneously. In particular, the well-known spectral clustering algorithm could be modified as the spectral co-clustering to co-cluster directed networks. However, large-scale networks pose great computational challenges to it. In this paper, we leverage sketching techniques and derive two randomized spectral co-clustering algorithms, one random-projection-based and the other random-sampling-based, to accelerate the co-clustering of large-scale directed networks. We theoretically analyze the resulting algorithms under two generative models -- the stochastic co-block model and the degree-corrected stochastic co-block model, and establish their approximation error rates and misclustering error rates, indicating better bounds than the state-of-the-art results of co-clustering literature. Numerically, we design and conduct simulations to support our theoretical results and test the efficiency of the algorithms on real networks with up to millions of nodes. A publicly available R package textsfRandClust is developed for better usability and reproducibility of the proposed methods.