Randomized spectral co-clustering for large-scale directed networks
Randomized spectral co-clustering for large-scale directed networks
复制标题
DOI：
--
复制
发表时间：
2020-04
期刊：
影响因子：
--
通讯作者：
Xiao Guo;Yixuan Qiu;Hai Zhang;Xiangyu Chang
中科院分区：
文献类型：
--
作者：
Xiao Guo;Yixuan Qiu;Hai Zhang;Xiangyu Chang
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 of proposed two randomized spectral co-clustering algorithms 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.
