Fragility of spectral clustering for networks with an overlapping structure

Abstract

Communities commonly overlap in real-world networks. This is a motivation to develop overlapping community detection methods, because methods for non-overlapping communities may not perform well. However, deterioration mechanism of the detection methods used for non-overlapping communities have rarely been investigated theoretically. Here, we analyze an accuracy of spectral clustering, which does not consider overlapping structures, by using the replica method from statistical physics. Our analysis on an overlapping stochastic block model reveals how the structural information is lost from the leading eigenvector because of the overlapping structure.

arXiv comment23 pages, 16 figures

References in corpus (14)

• Modularity and community structure in networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Link communities reveal multiscale complexity in networks
• Higher-order organization of complex networks
• Spectral redemption: clustering sparse networks
• Memory in network flows and its effects on spreading dynamics and community detection
• Graph spectra and the detectability of community structure in networks
• Nonparametric Bayesian inference of the microcanonical stochastic block model
• Model selection and hypothesis testing for large-scale network models with overlapping groups
• A single defect approximation for localized states on random lattices
• Limitations in the spectral method for graph partitioning: detectability threshold and localization of eigenvectors
• First eigenvalue/eigenvector in sparse random symmetric matrices: influences of degree fluctuation
• Detectability of the spectral method for sparse graph partitioning
• Graph powering and spectral robustness