Community detection by spectral methods in multi-layer networks

Abstract

Community detection in multi-layer networks is a crucial problem in network analysis. In this paper, we analyze the performance of two spectral clustering algorithms for community detection within the framework of the multi-layer degree-corrected stochastic block model (MLDCSBM) framework. One algorithm is based on the sum of adjacency matrices, while the other utilizes the debiased sum of squared adjacency matrices. We also provide their accelerated versions through subsampling to handle large-scale multi-layer networks. We establish consistency results for community detection of the two proposed methods under MLDCSBM as the size of the network and/or the number of layers increases. Our theorems demonstrate the advantages of utilizing multiple layers for community detection. Our analysis also indicates that spectral clustering with the debiased sum of squared adjacency matrices is generally superior to spectral clustering with the sum of adjacency matrices. Furthermore, we provide a strategy to estimate the number of communities in multi-layer networks by maximizing the averaged modularity. Substantial numerical simulations demonstrate the superiority of our algorithm employing the debiased sum of squared adjacency matrices over existing methods for community detection in multi-layer networks, the high computational efficiency of our accelerated algorithms for large-scale multi-layer networks, and the high accuracy of our strategy in estimating the number of communities. Finally, the analysis of several real-world multi-layer networks yields meaningful insights.

References in corpus (24)

• Finding and evaluating community structure in networks
• Community detection in graphs
• Assortative mixing in networks
• Multilayer Networks
• Mixing patterns in networks
• The structure and dynamics of multilayer networks
• Comparing community structure identification
• Defining and identifying communities in networks
• Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
• Stochastic blockmodels and community structure in networks
• User-friendly tail bounds for sums of random matrices
• Layer aggregation and reducibility of multilayer interconnected networks
• The Multilayer Nature of Ecological Networks
• Emergence of network features from multiplexity
• Fuzzy communities and the concept of bridgeness in complex networks
• Consistency of spectral clustering in stochastic block models
• Fast community detection by SCORE
• Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodel
• Evaluating Local Community Methods in Networks
• Community detection in multi-relational data with restricted multi-layer stochastic blockmodel
• Spectral Algorithms for Community Detection in Directed Networks
• Community detection for weighted bipartite networks
• Spectral co-Clustering in Multi-layer Directed Networks
• Finding mixed memberships in categorical data