Scholarlink

<p>Large-scale multi-layer networks with large numbers of nodes, edges, and layers arise across various domains, which poses a great computational challenge for downstream analysis. In this paper, we develop an efficient randomized spectral clustering algorithm for community detection in multi-layer networks. We first utilize the random sampling strategy to sparsify the adjacency matrix of each layer. Then we use the random projection strategy to accelerate the eigen-decomposition of the sum of squared sparsified adjacency matrices of all layers. The communities are finally obtained via the <i>k</i>-means of the eigenvectors. The algorithm not only has low time complexity but also saves storage space. Theoretically, we study the misclassification error rate of the proposed algorithm under the multi-layer stochastic block model, which shows that the randomization does not deteriorate the error bound under certain conditions. Numerical studies on multi-layer networks with millions of nodes show the superior efficiency of the proposed algorithm, which achieves clustering results rapidly. We develop a new R package, <Emphasis FontCategory="NonProportional">MLRclust</Emphasis>, which makes the proposed methods available for both simulated and real multi-layer networks.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Randomized Spectral Clustering for Large-Scale Multi-Layer Networks

  • 期刊论文

  • 发表日期：

    2025年9月16日

查看全文
  • Wenqing Su,
  • Xiao Guo,
  • Xiangyu Chang,
  • Ying Yang

摘要

Large-scale multi-layer networks with large numbers of nodes, edges, and layers arise across various domains, which poses a great computational challenge for downstream analysis. In this paper, we develop an efficient randomized spectral clustering algorithm for community detection in multi-layer networks. We first utilize the random sampling strategy to sparsify the adjacency matrix of each layer. Then we use the random projection strategy to accelerate the eigen-decomposition of the sum of squared sparsified adjacency matrices of all layers. The communities are finally obtained via the k-means of the eigenvectors. The algorithm not only has low time complexity but also saves storage space. Theoretically, we study the misclassification error rate of the proposed algorithm under the multi-layer stochastic block model, which shows that the randomization does not deteriorate the error bound under certain conditions. Numerical studies on multi-layer networks with millions of nodes show the superior efficiency of the proposed algorithm, which achieves clustering results rapidly. We develop a new R package, MLRclust, which makes the proposed methods available for both simulated and real multi-layer networks.