Perfect Spectral Clustering with Discrete Covariates
From MaRDI portal
Publication:6399321
arXiv2205.08047MaRDI QIDQ6399321FDOQ6399321
Jonathan Hehir, Xiaoyue Niu, Aleksandra Slavkovic
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)
