Spectral clustering via adaptive layer aggregation for multi-layer networks
arXiv:2012.04646
Abstract
One of the fundamental problems in network analysis is detecting community structure in multi-layer networks, of which each layer represents one type of edge information among the nodes. We propose integrative spectral clustering approaches based on effective convex layer aggregations. Our aggregation methods are strongly motivated by a delicate asymptotic analysis of the spectral embedding of weighted adjacency matrices and the downstream -means clustering, in a challenging regime where community detection consistency is impossible. In fact, the methods are shown to estimate the optimal convex aggregation, which minimizes the mis-clustering error under some specialized multi-layer network models. Our analysis further suggests that clustering using Gaussian mixture models is generally superior to the commonly used -means in spectral clustering. Extensive numerical studies demonstrate that our adaptive aggregation techniques, together with Gaussian mixture model clustering, make the new spectral clustering remarkably competitive compared to several popularly used methods.
arXiv comment74 pages
References in corpus (25)
- Community structure in social and biological networks
- Finding and evaluating community structure in networks
- Modularity and community structure in networks
- Community detection in graphs
- Maps of random walks on complex networks reveal community structure
- Stochastic blockmodels and community structure in networks
- Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
- Spectral redemption: clustering sparse networks
- Fast community detection by SCORE
- Distance, dissimilarity index, and network community structure
- Stochastic blockmodels with growing number of classes
- Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels
- Modeling homophily and stochastic equivalence in symmetric relational data
- Community detection, link prediction, and layer interdependence in multilayer networks
- Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodel
- Sharp nonasymptotic bounds on the norm of random matrices with independent entries
- Clustering with Multi-Layer Graphs: A Spectral Perspective
- Consistent estimation of dynamic and multi-layer block models
- A Survey on Theoretical Advances of Community Detection in Networks
- Estimating the number of communities in networks by spectral methods
- Mixed Membership Estimation for Social Networks
- Bayesian Poisson Tucker Decomposition for Learning the Structure of International Relations
- Contextual Stochastic Block Models
- Spectral Clustering for Multiple Sparse Networks: I
- Asymptotic Theory of Eigenvectors for Random Matrices with Diverging Spikes