Spectral Detection in the Censored Block Model
We consider the problem of partially recovering hidden binary variables from the observation of (few) censored edge weights, a problem with applications in community detection, correlation clustering and synchronization. We describe two spectral algorithms for this task based on the non-backtracking and the Bethe Hessian operators. These algorithms are shown to be asymptotically optimal for the partial recovery problem, in that they detect the hidden assignment as soon as it is information theoretically possible to do so.
Code (0)
등록된 구현이 없습니다.
Tasks
ClusteringCommunity DetectionmodelSimilar Papers 제목 키워드 기반
Spectral Algorithms Optimally Recover Planted Sub-structures
Spectral algorithms are an important building block in machine learning and graph algorithms. We are interested in studying when such algorithms can be applied directly to provide optimal solutions to inference tasks. Pr…
Community DetectionStochastic Block ModelCommunity detection in censored hypergraph
Community detection refers to the problem of clustering the nodes of a network (either graph or hypergrah) into groups. Various algorithms are available for community detection and all these methods apply to uncensored n…
Community DetectionMissing ValuesSpectral Clustering of Signed Graphs via Matrix Power Means
Signed graphs encode positive (attractive) and negative (repulsive) relations between nodes. We extend spectral clustering to signed graphs via the one-parameter family of Signed Power Mean Laplacians, defined as the mat…
ClusteringStochastic Block ModelAn improved spectral clustering method for community detection under the degree-corrected stochastic blockmodel
For community detection problem, spectral clustering is a widely used method for detecting clusters in networks. In this paper, we propose an improved spectral clustering (ISC) approach under the degree corrected stochas…
ClusteringCommunity DetectionStochastic Block ModelHyperspectral Image Classification Based on Sparse Modeling of Spectral Blocks
Hyperspectral images provide abundant spatial and spectral information that is very valuable for material detection in diverse areas of practical science. The high-dimensions of data lead to many processing challenges th…
ClassificationGeneral ClassificationHyperspectral Image Classificationimage-classification+1