Randomized spectral co-clustering for large-scale directed networks

Abstract

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 \emph{random-projection-based} and the other \emph{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 \textsf{RandClust} is developed for better usability and reproducibility of the proposed methods.

References in corpus (11)

• Community detection in graphs
• Stochastic blockmodels and community structure in networks
• Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodel
• Randomized algorithms for matrices and data
• Coauthorship and Citation Networks for Statisticians
• Randomized Matrix Decompositions using R
• Efficient and fast estimation of the geometric median in Hilbert spaces with an averaged stochastic gradient algorithm
• Sketched Ridge Regression: Optimization Perspective, Statistical Perspective, and Model Averaging
• Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squares
• Co-clustering for directed graphs: the Stochastic co-Blockmodel and spectral algorithm Di-Sim
• Error Bounds for Random Matrix Approximation Schemes

Cited by in corpus (4)

• Community detection for weighted bipartite networks
• Spectral co-Clustering in Multi-layer Directed Networks
• Finding mixed memberships in categorical data
• FedPower: Privacy-Preserving Distributed Eigenspace Estimation