Perfect Spectral Clustering with Discrete Covariates

Author name not available (Why is that?)

Publication date: 16 May 2022

Abstract: Among community detection methods, spectral clustering enjoys two desirable properties: computational efficiency and theoretical guarantees of consistency. Most studies of spectral clustering consider only the edges of a network as input to the algorithm. Here we consider the problem of performing community detection in the presence of discrete node covariates, where network structure is determined by a combination of a latent block model structure and homophily on the observed covariates. We propose a spectral algorithm that we prove achieves perfect clustering with high probability on a class of large, sparse networks with discrete covariates, effectively separating latent network structure from homophily on observed covariates. To our knowledge, our method is the first to offer a guarantee of consistent latent structure recovery using spectral clustering in the setting where edge formation is dependent on both latent and observed factors.

Has companion code repository: https://github.com/jonhehir/acsbm

This page was built for publication: Perfect Spectral Clustering with Discrete Covariates

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6399321)