2022/05/17 by Jonathan Hehir, Hehir, Jonathan, Xiaoyue Niu +3
Computer Science · Mathematics · #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Social and Information Networks (cs.SI) #Statistics Theory (math.ST) #cs.LG #cs.SI #math.ST #stat.ML #stat.TH
paper · pdf · doi:10.48550/arxiv.2205.08047
23 pages, 1 figure
arxiv created 2022/05/17 · arxiv updated 2022/05/18
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.