Spectral Clustering for Multiple Sparse Networks: I

Abstract

Although much of the focus of statistical works on networks has been on static networks, multiple networks are currently becoming more common among network data sets. Usually, a number of network data sets, which share some form of connection between each other are known as multiple or multi-layer networks. We consider the problem of identifying the common community structures for multiple networks. We consider extensions of the spectral clustering methods for the multiple sparse networks, and give theoretical guarantee that the spectral clustering methods produce consistent community detection in case of both multiple stochastic block model and multiple degree-corrected block models. The methods are shown to work under sufficiently mild conditions on the number of multiple networks to detect associative community structures, even if all the individual networks are sparse and most of the individual networks are below community detectability threshold. We reinforce the validity of the theoretical results via simulations too.

References in corpus (12)

• Emergence of scaling in random networks
• Finding and evaluating community structure in networks
• Community detection in graphs
• Stochastic blockmodels and community structure in networks
• Consistency of spectral clustering
• Matrix estimation by Universal Singular Value Thresholding
• Fast community detection by SCORE
• Dynamic stochastic blockmodels for time-evolving social networks
• Citation Networks in High Energy Physics
• 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

Cited by in corpus (8)

• Inference for multiple heterogeneous networks with a common invariant subspace
• Community detection in multiplex networks based on orthogonal nonnegative matrix tri-factorization
• Change-point detection in dynamic networks via graphon estimation
• Network Representation Using Graph Root Distributions
• Hierarchical Stochastic Block Model for Community Detection in Multiplex Networks
• Spectral clustering via adaptive layer aggregation for multi-layer networks
• Online network change point detection with missing values and temporal dependence
• Clustering multilayer graphs with missing nodes