Directed networks are generally 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 computational challenge to it. In this paper, we leverage randomized sketching techniques to accelerate the spectral co-clustering algorithms in order to co-cluster large-scale directed networks more efficiently. Specifically, we derive two series of randomized spectral co-clustering algorithms, one is random-projection-based and the other is random-sampling-based. Theoretically, we analyze the resulting algorithms under two generative models\textendash the \emph{stochastic co-block model} and the \emph{degree corrected stochastic co-block model}. The approximation error rates and misclustering error rates are established, which indicate better bounds than the state-of-the-art results of co-clustering literature. Numerically, we conduct simulations to support our theoretical results and test the efficiency of the algorithms on real networks with up to tens of millions of nodes.

本研究提出了两种基于随机投影和随机采样的随机谱共聚类算法，以加速大规模定向网络的共聚类，并在两种生成模型下理论分析其近似误差率和误叛集错误率。我们的数值实验表明了算法的效率，并发布了一个 R 包以便更好的可用性和可复现性。

大规模有向网络的随机谱共聚类