Spectral redemption: clustering sparse networks
Spectral algorithms are classic approaches to clustering and community detection in networks. However, for sparse networks the standard versions of these algorithms are suboptimal, in some cases completely failing to detect communities even when other algorithms such as belief propagation can do so. Here we introduce a new class of spectral algorithms based on a non-backtracking walk on the directed edges of the graph. The spectrum of this operator is much better-behaved than that of the adjacency matrix or other commonly used matrices, maintaining a strong separation between the bulk eigenvalues and the eigenvalues relevant to community structure even in the sparse case. We show that our algorithm is optimal for graphs generated by the stochastic block model, detecting communities all the way down to the theoretical limit. We also show the spectrum of the non-backtracking operator for some real-world networks, illustrating its advantages over traditional spectral clustering.
Code (0)
등록된 구현이 없습니다.
Tasks
ClusteringCommunity DetectionStochastic Block ModelSimilar Papers 제목 키워드 기반
Convex Sparse Spectral Clustering: Single-view to Multi-view
Spectral Clustering (SC) is one of the most widely used methods for data clustering. It first finds a low-dimensonal embedding $U$ of data by computing the eigenvectors of the normalized Laplacian matrix, and then perfor…
ClusteringSparse Subspace Clustering with Entropy-Norm
Sparse subspace clustering (SSC) and spectral clustering (SC) are both state-of-the-art methods to identify complex clusters in high-dimensional input space. However, there are few researches to discuss the relation betw…
ClusteringSpatial Sparse subspace clustering for Compressive Spectral imaging
This paper aims at developing a clustering approach with spectral images directly from CASSI compressive measurements. The proposed clustering method first assumes that compressed measurements lie in the union of multipl…
ClusteringImage ClusteringUnderstanding Regularized Spectral Clustering via Graph Conductance
This paper uses the relationship between graph conductance and spectral clustering to study (i) the failures of spectral clustering and (ii) the benefits of regularization. The explanation is simple. Sparse and stochasti…
ClusteringSpectral Sparse Representation for Clustering: Evolved from PCA, K-means, Laplacian Eigenmap, and Ratio Cut
Dimensionality reduction, cluster analysis, and sparse representation are basic components in machine learning. However, their relationships have not yet been fully investigated. In this paper, we find that the spectral …
ClusteringDimensionality Reduction