General Community Detection with Optimal Recovery Conditions for Multi-relational Sparse Networks with Dependent Layers
arXiv:2004.03480
Abstract
Multilayer and multiplex networks are becoming common network data sets in recent times. We consider the problem of identifying the common community structure for a special type of multilayer networks called multi-relational networks. We consider extensions of the spectral clustering methods for multi-relational networks and give theoretical guarantees that the spectral clustering methods recover community structure consistently for multi-relational networks generated from multilayer versions of both stochastic and degree-corrected block models even with dependence between network layers. The methods are shown to work under optimal conditions on the degree parameter of the networks to detect both assortative and disassortative community structures with vanishing error proportions even if individual layers of the multi-relational network has the network structures below community detectability threshold. We reinforce the validity of the theoretical results via simulations too.
7 figures
References in corpus (16)
- Finding and evaluating community structure in networks
- Community detection in graphs
- Mixing patterns in networks
- Stochastic blockmodels and community structure in networks
- Consistency of spectral clustering
- Matrix estimation by Universal Singular Value Thresholding
- Fast community detection by SCORE
- Citation Networks in High Energy Physics
- Clustering with Multi-Layer Graphs: A Spectral Perspective
- Random graph models for dynamic networks
- Detectability thresholds and optimal algorithms for community structure in dynamic networks
- Nonparametric Bayes dynamic modeling of relational data
- Consistent estimation of dynamic and multi-layer block models
- Enhanced detectability of community structure in multilayer networks through layer aggregation
- Estimating the number of communities in networks by spectral methods
- Exact ICL maximization in a non-stationary temporal extension of the stochastic block model for dynamic networks